Source-linked AI summary
Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
Vicky Choi
TL;DR
The paper addresses the problem of designing quantum hardware that satisfies physical constraints while supporting efficient minor-embedding. It develops and analyzes TRIAD, a hardware graph optimized for embedding complete graphs. The paper also identifies sparse-graph minor-universal design and the effect of embedding on adiabatic runtime as unresolved issues.
Problem
Designing a hardware graph that satisfies physical constraints and efficiently embeds a target family of sparse graphs remains an open problem.
Method
The paper formulates the intertwined architecture-design problem and constructs a triangular-layout hardware graph, TRIAD, for complete-graph minors.
Results
TRIAD satisfies the known physical constraints and admits a simple, efficient embedding of K_n, thereby allowing efficient embedding of any graph on n vertices.
Takeaways & Limitations
Complete-graph-minor hardware can be designed optimally under the stated constraints, but sparse-graph-minor hardware remains a research target.
Takeaways & Limitations
The effect of minor-embedding and its induced initial Hamiltonian on adiabatic-algorithm complexity remains to be investigated.
Abstract
from arXiv · showhide
In [Choi08], we introduced the notion of minor-embedding in adiabatic quantum optimization. A minor-embedding of a graph G in a quantum hardware graph U is a subgraph of U such that G can be obtained from it by contracting edges. In this paper, we describe the intertwined adiabatic quantum architecture design problem, which is to construct a hardware graph U that satisfies all known physical constraints and, at the same time, permits an efficient minor-embedding algorithm. We illustrate an optimal complete-graph-minor hardware graph. Given a family F of graphs, a (host) graph U is called F-minor-universal if for each graph G in F, U contains a minor-embedding of G. The problem for designing a F-minor-universal hardware graph U_{sparse} in which F consists of a family of sparse graphs (e.g., bounded degree graphs) is open.
1 Introduction
The paper frames adiabatic quantum architecture design as jointly satisfying hardware constraints and efficient minor-embedding, building on prior minor-embedding results. It presents TRIAD and identifies sparse-graph-minor hardware design as an open problem.
- The architecture design problem is to construct a hardware graph satisfying physical constraints while permitting efficient minor-embedding.
- The paper illustrates an optimal hardware graph for complete-graph minors.
- Designing a minor-universal hardware graph for sparse graph families remains open.
2 Adiabatic Quantum Optimization and Adiabatic Quantum Hardware Graph
The section introduces AQC for Ising optimization and models superconducting hardware as a constrained weighted graph. The adiabatic evolution connects an initial Hamiltonian to a problem-encoding final Hamiltonian, with runtime governed by the minimum spectral gap.
- 2 Adiabatic Quantum Optimization and Adiabatic Quantum Hardware Graph: The Ising Hamiltonian defines a graph-structured optimization problem through qubit biases, coupler strengths, and spin variables.The smallest eigenvalue corresponds to the minimum energy, whose minimizing assignment is the Ising problem’s ground state.
- 2.1 Adiabatic Quantum Algorithm: The adiabatic runtime must be large enough for slow evolution, as determined by the minimum spectral gap of the system Hamiltonian.
- 2.2 Superconducting Architecture for AQC: A superconducting hardware architecture uses flux qubits connected by tunable coupling devices to implement the transverse-field Ising model.
- 2.2 Superconducting Architecture for AQC: The hardware graph is an undirected weighted graph whose vertices are qubits and edges are couplers, with time-varying bias, tunneling, and coupling weights.
- 2.3 Physical Constraints: The architecture has bounded degree, bounded edge length, and permits crossings, making it a bounded-degree geometric graph.
3 Minor-Embedding in AQC
Minor-embedding extends AQC beyond graphs that directly fit the hardware by representing logical qubits as connected physical-qubit subtrees. Contracting those subtrees recovers the input graph, enabling the embedded Ising problem to encode the original one.
- 3 Minor-Embedding in AQC: A graph G can be solved on hardware U through minor-embedding when G is represented by a suitable subgraph of U.This extends direct subgraph embedding to cases where the input graph is not itself a hardware subgraph.
- 3 Minor-Embedding in AQC: A minor-embedding replaces each vertex of G with a connected subtree of U, with hardware connections representing edges of G.
- 3 Minor-Embedding in AQC: Contracting the replacement subtrees’ edges transforms the embedded subgraph back into G, making G a graph minor of U.
- 3 Minor-Embedding in AQC: Subgraph-embedding uses one physical vertex per logical vertex, whereas topological-minor-embedding restricts each subtree to a path.
- 3 Minor-Embedding in AQC: The embedding reduction maps the original Ising Hamiltonian on G to an embedded Hamiltonian whose solution yields the solution to the original problem.
4 TRIAD: Optimal Hardware Graph for Embedding Complete Graph Kn
TRIAD is a triangular hardware layout that embeds complete-graph minors by mapping each K_n vertex to a chain of n−1 virtual vertices. Chains are incrementally constructed and chopped into physical qubits, yielding an efficient, physically constrained host graph.
- Construction of TRIAD: TRIAD maps each vertex of K_n to a chain of n−1 virtual vertices in a triangular layout.The construction is inductive, extending the layout from K_n−1.
- Construction of TRIAD: K3→K4→K5 is constructed by extending existing chains northeast and placing a new chain to provide the required adjacency.The K3 basis uses chains of two virtual vertices, equal to the degree.
- Decomposition of TRIAD: ⌈(n−3)/(d−2)⌉ physical qubits are required per logical qubit when each physical qubit has available degree d.Non-terminal physical qubits need at least two couplers, while terminal qubits need one.
- Decomposition of TRIAD: For n=8 and d=6, each seven-vertex chain is chopped into two physical qubits containing three and four virtual vertices.The decomposition can be viewed using complete and complete bipartite subgraphs, with K_c a minor of K_c,c.
- Decomposition of TRIAD: Ω(n^2/d) physical qubits are therefore required by the hardware graph.This follows from the per-logical-qubit chain decomposition for complete-graph embedding.
- Result: TRIAD satisfies known physical constraints and efficiently embeds K_n, thereby allowing efficient embedding of any graph on n vertices.The paper contrasts this complete-graph solution with the open problem of designing sparse-graph-minor hardware.
5 Adiabatic Quantum Architecture Usparse Design Problem
The paper frames sparse-graph minor-universal hardware design as an open architecture problem combining physical constraints with efficient embedding. It also identifies limitations from existing embedding methods, hardware-compatible expanders, and the need for large treewidth, while leaving embedding effects on adiabatic complexity unresolved.
- A F-minor-universal host graph contains a minor-embedding of every graph in the family F.
- The open design problem is to construct a small U_sparse for sparse graph families that satisfies physical constraints and supports efficient minor-embedding computation.The design objective concerns both the number of qubits and couplers.
- Known explicitly constructable expanders are topological rather than geometric, requiring long edge lengths that conflict with the desired hardware setting.
- Existing minor-embedding algorithms are polynomial in host size for fixed G but exponential in the size of G, so they do not directly solve the variable-input problem with fixed U.A randomized polynomial algorithm exists for degree-bounded expanders, but known expanders do not satisfy the required physical constraints.
- The architecture requires load exactly 1 and dilation exactly 1, unlike existing parallel-processor embedding work, where at least one condition is violated.Load is the maximum number of logical qubits mapped to one physical qubit; dilation is the maximum number of stretched edges.
- U_sparse must have treewidth ω(log n); otherwise dynamic programming over its tree decomposition could solve the problem in O(exp(tw(U_sparse))) time once an embedding is given.
- The effect of minor-embedding and its induced initial Hamiltonian on adiabatic algorithm complexity remains unresolved because complexity depends on the minimum spectral gap and initial Hamiltonian.