Source-linked AI summary
Quantum Algorithms for Fixed Qubit Architectures
E. Farhi, J. Goldstone, S. Gutmann, H. Neven
TL;DR
Fixed hardware connectivity can differ from the arbitrary qubit couplings assumed by quantum algorithms, making compilation deeper and potentially problematic under limited coherence times. The approach uses parameterized unitaries native to the hardware layout and a classical optimization loop that updates parameters from measured objective values or Hamiltonian energies. 0.6924 is the guaranteed approximation ratio for lowest-depth QAOA on all instances of 3-regular MaxCut, versus 0.5 for random guessing.
Problem
Fixed hardware connectivity can differ from the arbitrary qubit couplings assumed by quantum algorithms, making compilation deeper and potentially problematic under limited coherence times.
Source: §1 · p. 1Method
The approach uses parameterized unitaries native to the hardware layout and a classical optimization loop that updates parameters from measured objective values or Hamiltonian energies.
Source: §1 · p. 2, §4 · p. 13Results
0.6924 is the guaranteed approximation ratio for lowest-depth QAOA on all instances of 3-regular MaxCut, versus 0.5 for random guessing.
Source: §2 · p. 6Takeaways & Limitations
The framework offers a way to explore computational tasks on fixed-architecture quantum processors using native gates and the same number of logical and physical qubits.
Source: §4 · p. 13The paper offers no evidence that the proposed approach finds solutions more efficiently than the best classical algorithms.
Source: §3.3 · p. 12
Abstract
from arXiv · showhide
Gate model quantum computers with too many qubits to be simulated by available classical computers are about to arrive. We present a strategy for programming these devices without error correction or compilation. This means that the number of logical qubits is the same as the number of qubits on the device. The hardware determines which pairs of qubits can be addressed by unitary operators. The goal is to build quantum states that solve computational problems such as maximizing a combinatorial objective function or minimizing a Hamiltonian. These problems may not fit naturally on the physical layout of the qubits. Our algorithms use a sequence of parameterized unitaries that sit on the qubit layout to produce quantum states depending on those parameters. Measurements of the objective function (or Hamiltonian) guide the choice of new parameters with the goal of moving the objective function up (or lowering the energy). As an example we consider finding approximate solutions to MaxCut on 3-regular graphs whereas the hardware is physical qubits laid out on a rectangular grid. We prove that the lowest depth version of the Quantum Approximate Optimization Algorithm will achieve an approximation ratio of at least 0.5293 on all large enough instances which beats random guessing (0.5). We open up the algorithm to have different parameters for each single qubit $X$ rotation and for each $ZZ$ interaction associated with the nearest neighbor interactions on the grid. Small numerical experiments indicate that an enveloping classical algorithm can be used to find the parameters which sit on the grid to optimize an objective function with a different connectivity. We discuss strategies for finding good parameters but offer no evidence yet that the proposed approach can beat the best classical algorithms. Ultimately the strength of this approach will be determined by running on actual hardware.
1 Introduction
Fixed-connectivity quantum hardware motivates algorithms that use native gates and classical parameter optimization rather than compilation to arbitrary qubit couplings. The paper frames this approach for combinatorial optimization and quantum simulation while decoupling objective-function connectivity from hardware connectivity.
1 Introduction
- Compiling interactions between physically separated qubits can greatly increase circuit depth, which is problematic under limited coherence times.Source: §1 · pp. 1–2
- For combinatorial optimization, the circuit aims to produce computational-basis states with high objective values; for quantum simulation, it aims to approach a Hamiltonian ground-state energy.Source: §1 · p. 2
- The proposed framework prepares parameter-dependent states with hardware-native unitaries, then adjusts parameters using measured objective values or Hamiltonian energies.The parameterized state is built from an initial state and a sequence of unitaries, while a classical optimizer proposes updated parameters.Source: §1 · pp. 2–3
- Objective functions traditionally help define the evolution operators, whereas this paper explores decoupling objective-function connectivity from the unitaries used to prepare the state.The approach targets pairwise objective terms whose connectivity may differ from the hardware graph.Source: §1 · p. 2
- The hardware architecture fixes which qubit pairs can interact, but qubit labels can be assigned to objective-function bits to make a judicious mapping.Source: §1 · p. 3
- Parameterized quantum circuits resemble quantum neural networks because both use classical optimization to train parameters on a fixed connectivity graph, with more parameters potentially increasing optimization effort.The paper notes that entangling gates may help prepare desirable states with shallower circuits or less training effort, but this is presented as a hope for optimization problems.Source: §1 · pp. 4–5
2 QAOA on a Native Hardware Graph
The paper applies QAOA using unitaries defined by a square-grid hardware graph while optimizing MaxCut on a potentially different 3-regular graph. At lowest depth, a greedy vertex assignment yields a worst-case approximation guarantee above random guessing.
2 QAOA on a Native Hardware Graph
- The hardware is modeled as a square grid, with each non-boundary qubit coupled to four neighbors, while the MaxCut objective is defined on a separate 3-regular graph.The analysis neglects the grid boundary for sufficiently large n.Source: §2 · pp. 5–6
- 0.5293 approximation ratio is achieved for all sufficiently large 3-regular MaxCut instances at the lowest algorithm depth, exceeding random guessing.The construction uses grid-based unitaries without directly incorporating the objective graph.Source: §2 · p. 6
- At lowest depth, objective-graph edges contribute according to four grid separations: beyond two edges, one edge, one diagonal step, or two collinear edges.Edges beyond two grid edges have expected contribution zero, corresponding to clause value 0.5.Source: §2 · p. 7, Figure 2.0 · p. 7, Figure 2.2 · p. 7
- Optimizing two parameters γ and β combines the separation-dependent contributions m1F1 + m2F2 + m3F3 into the expected MaxCut objective.The resulting lower bound is expressed using the number of graph edges, m = 3n/2.Source: §2 · pp. 7–8
- A greedy pairing procedure identifies at least n/2 graph edges that can be embedded as short grid segments, ensuring m1 is at least n/2 = m/3.The paired subgraph consists of segments of two, three, or four vertices that can be placed on the grid.Source: §2 · pp. 8–9, Figure 3 · p. 9
- For a 20-bit example, grid-based QAOA reached approximation ratio 0.6424 versus 0.7519 for original QAOA, illustrating the performance cost of mismatched connectivity.The original and grid-based procedures both optimized two angles at p = 1.Source: §2 · p. 9
- At greater depth, qubits separated by more than two grid edges can become entangled, so the preprocessing alignment may become unnecessary as depth approaches √n.The shallow-depth construction therefore motivates, but does not settle, the role of preprocessing at larger depths.Source: §2 · pp. 9–10
3 Introducing Extra Parameters
The paper expands grid-native variational circuits with independent parameters to optimize objectives whose connectivity differs from the hardware. It shows that these circuits can construct entangled computational-basis cat states and reports numerical evidence from standard and warm-started MaxCut experiments.
3 Introducing Extra Parameters
- With independent parameters for every grid qubit rotation and connected-pair interaction, the circuit can optimize an objective function whose connectivity is unrelated to the hardware graph.The approach uses separate β_j parameters for single-qubit rotations and γ_jk parameters for grid edges across each circuit level.Source: §3 · p. 10
3.1 Making Computational Basis Cat States
- At depth p = √n, the grid circuit can produce any computational-basis cat state, but its X-parity symmetry restricts outputs to entangled pairs of bit-flipped states.The construction grows entanglement outward from the grid center until it reaches the corners.Source: §3.1 · pp. 10–11
3.2 Numerical Example
- For a 16-qubit random 3-regular MaxCut instance, grid-native parameters achieved approximation ratio 0.9399, versus 0.9534 for graph-native parameters.Both searches used 160 parameters; the reported degradation from moving to the grid was small in this example.Source: §3.2 · pp. 11–12
- The 16-qubit simulation found global-optimum strings with probability above 1/100 before the expected objective reached its stopping criterion.Whether this yields asymptotic computational value depends on how the objective's standard deviation scales when p grows as √n.Source: §3.2 · p. 12
3.3 Warm Starts
- The authors report no evidence that this hardware-native approach is more efficient than the best classical algorithms, while suggesting warm starts from strong classical solutions as a strategy.They note that meaningful improvement over a classical approximation ratio must scale with n.Source: §3.3 · pp. 12–13
- A warm start from a 17-edge MaxCut solution led the optimizer to an objective value near 20, approximately the instance optimum and better than typical random initializations.The optimization moved beyond the warm-start value without getting stuck in a local minimum.Source: §3.3 · pp. 12–13
4 Discussion and Outlook
The discussion frames fixed-architecture quantum computation as a parameterized, measurement-driven approach spanning combinatorial optimization and Hamiltonian ground-state estimation. It also emphasizes open practical limits: parameter-search difficulty, error, classical cost, and the need for hardware validation.
4 Discussion and Outlook
- Fixed-architecture quantum computers use native gates, measured objective values or energies, and outer-loop parameter optimization without error correction or compilation.The framework is intended to encompass quantum algorithms executable within hardware connectivity and experimental depth limits.Source: §4 · p. 13
4.1 More or Fewer Parameters
- Opening the parameter space from shared angles to independent local gates may access better computational pathways, but can make useful parameters harder to discover.The paper considers independent grid-edge and single-qubit parameters, and even arbitrary connected one- and two-qubit unitaries.Source: §4.1 · p. 14
4.2 Ground State Energy
- Variational ground-state estimation constructs experimentally available states, measures Pauli-product terms of the Hamiltonian, and combines repeated measurements to estimate energy.Unlike combinatorial objectives, Hamiltonian terms may be non-commuting and non-diagonal in the computational basis, and the measurement cost scales with the decomposition size.Source: §4.2 · pp. 14–15
4.3 Error
- Systematic control errors may be absorbed by optimization, whereas shot-to-shot control variation and decoherence can degrade fidelity and complicate performance guarantees.The measured objective can remain reliable even at low fidelity, and the optimizer may avoid degraded computational pathways.Source: §4.3 · p. 15
4.4 Numerics
- Numerics at 16 qubits on a 4 by 4 grid used p = 4 and 160 parameters, but only demonstrated that the strategy works, not that it beats classical methods.The simulations required thousands of classical optimization calls, while brute-force search over 2^16 inputs is nearly instantaneous.Source: §4.4 · p. 15
4.5 Future Strategies
- The framework may apply broadly to optimization, with future strategies including warm starts, coarse-to-fine searches, restricted quantum subroutines, and reinforcement-learning optimizers.The paper identifies the outer-loop optimizer as central and ultimately seeks strategies that guarantee performance before hardware execution.Source: §4.5 · pp. 15–16
Appendix
The appendix evaluates the MaxCut expectation by conjugating ZiZj through single-qubit and grid ZZ operations. Surviving terms depend on local graph configurations, including shared neighbors and whether the target edge appears in the grid interaction structure.
Appendix
- Single-qubit conjugation transforms Zi into Zi cos 2β + Yi sin 2β before the grid-dependent ZZ conjugation is applied.The calculation then inserts the cost-unitary conjugation and evaluates the resulting Pauli terms in |s⟩.Source: Appendix · p. 16
- The appendix reduces the expectation calculation to terms that survive in the |s⟩ state, where only products of Xℓ operators without unpaired Yℓ or Zℓ contribute.This follows because |s⟩ has Xℓ eigenvalue 1 while single-qubit Yℓ and Zℓ expectations vanish.Source: Appendix · pp. 16–17
- For case 0, the relevant grid terms commute and the resulting expectation is zero.The local configuration has no surviving contribution after evaluating the transformed operators in |s⟩.Source: Appendix · p. 17
- For case 1, applying the conjugation to the three other neighbors of i and then to j yields the corresponding transformed expressions used in the expectation calculation.The derivation exploits that the three additional neighbors have zero Zℓ expectation in |s⟩.Source: Appendix · p. 17
- Cases 2 and 3 obtain nonzero contributions by pairing Zk factors associated with common neighbors, producing the stated expressions for those configurations.Case 2 has two common neighbors and case 3 has one.Source: Appendix · p. 17