PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor

Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Daniel Eppens, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Alan Ho, Sabrina Hong, Trent Huang, L. B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V. Klimov, Alexander N. Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Martin Leib, Orion Martin, John M. Martinis, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Charles Neill, Florian Neukart, Murphy Yuezhen Niu, Thomas E. O'Brien, Bryan O'Gorman, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Andrea Skolik, Vadim Smelyanskiy, Doug Strain, Michael Streif, Marco Szalay, Amit Vainsencher, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Leo Zhou, Hartmut Neven, Dave Bacon, Erik Lucero, Edward Farhi, Ryan Babbush

arXiv:2004.04197v3quant-ph

TL;DR

Near-term quantum optimization must move beyond hardware-native, low-depth problems because real-world graph instances often require costly compilation. This paper applies QAOA on Google’s Sycamore processor to hardware-native and compiled graph problems, finding depth-dependent gains for native graphs but size-dependent degradation for compiled problems, despite performance above random guessing in challenging cases.

  • Problem

    Real-world combinatorial optimization instances often cannot map to hardware-native topologies without significant resources, while evidence has focused primarily on hardware-tailored problems at minimal depth.

  • Method

    The study experimentally applies QAOA on Google’s Sycamore processor to hardware-grid problems and compiled Sherrington–Kirkpatrick and MaxCut instances, varying depth and problem size.

  • Results

    Performance is robust and problem-size independent on hardware-grid problems, increases with depth, and exceeds random guessing for compiled problems up to 17 bits even at p = 3.

  • Takeaways & Limitations

    QAOA performance differs qualitatively between hardware-native and compiled graphs, underscoring the challenge of applying quantum optimization beyond hardware interaction graphs.

  • Takeaways & Limitations

    For fully connected Sherrington–Kirkpatrick instances requiring compilation, performance degrades with problem size despite non-negligible results at n = 17 and p = 3.

Abstract

from arXiv · show

We demonstrate the application of the Google Sycamore superconducting qubit quantum processor to combinatorial optimization problems with the quantum approximate optimization algorithm (QAOA). Like past QAOA experiments, we study performance for problems defined on the (planar) connectivity graph of our hardware; however, we also apply the QAOA to the Sherrington-Kirkpatrick model and MaxCut, both high dimensional graph problems for which the QAOA requires significant compilation. Experimental scans of the QAOA energy landscape show good agreement with theory across even the largest instances studied (23 qubits) and we are able to perform variational optimization successfully. For problems defined on our hardware graph we obtain an approximation ratio that is independent of problem size and observe, for the first time, that performance increases with circuit depth. For problems requiring compilation, performance decreases with problem size but still provides an advantage over random guessing for circuits involving several thousand gates. This behavior highlights the challenge of using near-term quantum computers to optimize problems on graphs differing from hardware connectivity. As these graphs are more representative of real world instances, our results advocate for more emphasis on such problems in the developing tradition of using the QAOA as a holistic, device-level benchmark of quantum processors.

I. INTRODUCTION

The paper examines whether near-term superconducting processors can apply QAOA to practical optimization problems whose graphs may not match planar hardware connectivity. It introduces QAOA as a variational method and studies hardware-native and non-native problem graphs, emphasizing compilation overhead and circuit-depth effects.

  • Motivation: Non-planar optimization graphs often require ancilla or compilation to fit planar hardware, increasing circuit complexity for QAOA.Most industrially relevant problem graphs are non-planar, whereas many quantum hardware platforms have quasi-planar connectivity.
  • Motivation: QAOA is a near-term gate-model optimization approach that is also used as a system-level benchmark of quantum hardware.Its simple structure supports analytical study and implementation on current processors.
  • Experimental scope: The study uses 23 physical qubits in a two-dimensional Sycamore array to evaluate three families of optimization problem graphs.The processor contains a larger 54-qubit array, but this experiment is restricted to 23 qubits.
  • QAOA framework: QAOA alternates problem and driver unitaries, repeating the pair p times with 2p parameters.Higher depth uses different parameters for each repeated application.
  • QAOA framework: The problem unitary applies phases according to pairwise terms in the cost function, while the driver unitary induces transitions between computational-basis bitstrings.The operators are implemented by sequentially evolving under cost-function terms and the driver terms.

II. COMPILATION AND PROBLEM FAMILIES

The experiment compares hardware-native grid problems with compiled 3-regular MaxCut and fully connected SK problems. Compilation uses routing and gate synthesis to realize interactions unavailable directly in the planar Sycamore connectivity graph.

  • Compilation: Compilation proceeds through routing followed by gate synthesis, converting non-native interactions into physical gates supported by the processor.Routing permutes qubits so every problem edge becomes physically adjacent at least once; synthesis decomposes one- and two-qubit interactions.
  • Problem families: The largest depicted instances contain 23 Hardware Grid qubits, 22 MaxCut qubits, and 17 SK qubits.Figure 1 contrasts hardware-matched, random 3-regular, and fully connected problem families.
  • Hardware Grid Problems: Hardware Grid instances match the Sycamore connectivity, so their two-qubit interactions require no swap-network routing.Random edge weights are sampled as ±1 on the device topology, and interactions are scheduled in four rounds.
  • Sherrington-Kirkpatrick Model: The SK model uses a fully connected graph with random ±1 weights and requires a linear swap network for implementation.The routing uses n layers of composite phasing-and-swap interactions, each synthesized from hardware-native gates.
  • MaxCut on 3-Regular Graphs: Random 3-regular MaxCut graphs use unit edge weights and require routing because their connectivity generally differs from the hardware graph.Heuristic compilation inserts swaps to move logical qubits adjacent for interaction.

III. ENERGY LANDSCAPES AND OPTIMIZATION

The experiments compare simulated and measured QAOA energy landscapes and test classical variational optimization using quantum objective estimates. The landscapes retain recognizable theoretical features, while compiled problems degrade with increasing size.

  • Energy landscapes: Simulated and experimental p = 1 landscapes show clear correspondence across Hardware Grid, 3-regular MaxCut, and SK instances.The plotted instances contain 23, 14, and 11 qubits, respectively.
  • Variational optimization: QAOA parameters are optimized classically while expectation values are estimated by repeatedly sampling bitstrings on the quantum processor.The Sycamore platform can sample roughly five thousand bitstrings per second.
  • Evaluation: The reported objective is normalized by the negative true minimum, so maximizing ⟨C⟩/Cmin corresponds to minimizing the cost expectation.This normalization enables comparison among problem instances.
  • Energy landscapes: The p = 1 diagnostic landscape visualizes the cost expectation as a function of γ and β, allowing comparison between ideal and experimental behavior.Noise can appear as damping or warping and may overwhelm the signal needed for classical optimization.
  • Variational optimization: A classical optimizer reached the vicinity of the optimum in 10 iterations or fewer from an intentionally poor initialization.The experiment used Model Gradient Descent with a quadratic surrogate model of the objective.

IV. HARDWARE PERFORMANCE OF QAOA

QAOA performance depends on both problem size and circuit depth: hardware-native problems maintain size-independent normalized performance, while compiled problems degrade toward random guessing as size grows. Increasing depth improves ideal and some experimental performance, but eventually noise overwhelms the theoretical benefit.

  • Performance metric: The normalized observed cost ⟨C⟩/Cmin equals 1 for perfect performance and 0 for random guessing.Results use theoretically optimal (β, γ) values to separate noise effects from robustness of classical outer-loop optimization.
  • Depth dependence: Ideal simulations improve with increasing depth p, whereas experimental Hardware Grid performance improves for p > 1 before larger-depth errors dominate.The depth dependence is evaluated using both mean performance and per-instance maximizing-depth statistics.
  • Problem-size scaling: Hardware Grid performance saturates at a value independent of problem size n despite decreasing circuit fidelity.For fixed depth, each objective term remains locally affected, so total error and Cmin both scale linearly with n.
  • Problem-size scaling: Compiled SK and 3-regular MaxCut circuits become deeper with qubit count, causing errors to propagate across qubits and degrading solution quality.Performance still exceeds random guessing through n = 17 for p = 3.
  • Depth dependence: Across 130 instances with n > 10, the experimental mean performance peaks at p = 3, although instance-to-instance variation is comparable to the depth dependence.The relatively flat depth dependence indicates that noise nearly balances the theoretical performance increase for this problem family.

V. CONCLUSION

The study benchmarks QAOA on hardware-native and compiled optimization problems to assess performance beyond contrived low-depth instances. It finds robust size-independent behavior on Hardware Grid problems, but performance degradation for compiled non-native graphs, underscoring the challenge of real-world connectivity.

  • V. CONCLUSION: Discrete optimization is attractive for near-term quantum devices because solutions may be valuable and QAOA is viable at low circuit depth.QAOA on prototypical problems also serves as a benchmark for comparing quantum hardware platforms.
  • V. CONCLUSION: Hardware Grid experiments show robust performance at large qubit counts, variational optimization under noisy objectives, and n-independent noise in approximation ratios.The study reports clear performance maximization at p = 3 for Hardware Grid problems.
  • V. CONCLUSION: Compiled fully connected SK instances retain non-negligible performance at n = 17 and p = 3, but performance degrades as problem size increases.Real-world combinatorial optimization graphs generally require routing with swap networks and significant additional resources.
  • V. CONCLUSION: The results underscore the challenges of applying quantum optimization algorithms beyond hardware-native interaction graphs.The conclusion frames progress on a real device alongside the need to move beyond contrived low-depth problems.

Code and Data Availability

The experiment’s code and data are publicly available through the cited repository and Figshare record.

  • Code and Data Availability: Experimental code is available in the ReCirq GitHub repository.The passage identifies the repository URL as https://github.com/quantumlib/ReCirq.
  • Code and Data Availability: Experimental data are available on Figshare through reference 38.

Appendix A: Hardware and Compilation Details

The appendix describes compiling QAOA interactions into Sycamore’s native gates using routing, swap networks, and gate synthesis. Non-native interactions require additional swaps, while native gates and commuting structure help organize circuit depth.

  • ZZ(γ) interactions use 2 syc layers plus 2+1 associated single-qubit PhX layers.The extra single-qubit layer can be merged with neighboring interaction layers.
  • The syc gate is an fSim(π/2,π/6) decomposed into cphase(π/6), cz, swap, and two S gates.
  • A swap requires three syc gates, while e−iγwZZ followed by swap also uses three syc gates plus one Rx and two Rz gates.The swap compilation is used for 3-regular MaxCut, and the composite interaction is used for SK-model circuits.
  • The fully connected swap network alternates even- and odd-qubit interaction layers, enabling all-to-all interactions through repeated nearest-neighbor swaps.Because the required interactions commute, their order can be rearranged to minimize compiled depth.
  • The 23-qubit device’s linear-connectivity requirement limits the SK-model swap network to n = 17.

Appendix B: Prior Work

Prior QAOA experiments demonstrated landscapes, parameter optimization, or improved bitstring probabilities on superconducting, ion-trap, and photonic processors. The studies varied substantially in topology, qubit count, and circuit depth.

  • Prior experiments span superconducting, ion-trap, and photonic processors, with demonstrations including landscapes and variational optimization.
  • Otterbach et al. demonstrated Bayesian optimization at p = 1 on a 19-bit hardware-native Ising graph, exceeding random guessing.
  • Qiang et al. demonstrated n = 2, p = 1 Max2Xor landscapes and high probability of obtaining the correct bitstrings.
  • Pagano et al. applied QAOA to fully connected antiferromagnetic 1D-chain problems on two ion-trap processors.
  • Willsch et al. studied an 8-bit 2SAT problem matching IBM’s 16Q Melbourne topology and compared experimental with theoretical landscapes.
  • Abrams et al. compared cz and cz-plus-iswap compilation strategies for 4-bit ring and fully connected problems implemented with linear connectivity.
  • Bengtsson et al. observed that increasing depth from p = 1 to p = 2 increased the probability of observing the correct bitstring for n = 2.

Appendix C: Readout correction

Readout correction models measurement errors as classical bit flips and uses calibrated transition probabilities to recover corrected observables. The appendix also documents calibration drift and scope-specific limitations of correction procedures.

  • Readout error is modeled as a classical bit-flip channel with probabilities p0,i for 0→1 and p1,i for 1→0.
  • The corrected two-qubit observable ZiZj is obtained by rescaling measured observables using the factors 1/(1 − p1,i − p0,i).
  • Averaging p0 and p1 is possible when half the measurements apply X gates immediately before measurement and the results are then flipped.
  • Each p0,i and p1,i estimate used 1,000,000 preparations and measurements, with periodic estimation during Figure 3 data collection to track drift.
  • Correlated readout errors from frequency collisions motivated a later calibration that optimized qubit detunings during simultaneous readout.
  • Figures 4 and 5 used data collected on a different date, with median isolated readout error of 4.1%, and did not use readout correction.
  • Automated calibration remains bounded by inevitable analog-signal drift, while tailored calibration can perform better when reading only a qubit subset.

Appendix D: Optimizer Details

The appendix presents Model Gradient Descent, which estimates local gradients by fitting quadratic models to sampled objective values. The optimizer iteratively updates parameters until a gradient-based tolerance or evaluation limit is reached.

  • Model Gradient Descent samples points near the current iterate, fits a local quadratic model, and uses its gradient as a surrogate for the true gradient.
  • The optimizer’s inputs include an initial point, learning rate, sample radius, sample number, decay exponents, stability constant, tolerance, and evaluation limit.
  • The sample radius decays with iteration as δ′ = δ/(m + 1)^ξ, narrowing the neighborhood used for local modeling.
  • At each iteration, sampled and previously evaluated points within the current neighborhood are retained for least-squares quadratic fitting.
  • The algorithm updates parameters by x ← x − γ′ · g and returns when γ′ · |g| < ε or the evaluation budget is exhausted.

1. Analysis of Noise

Noise affects the three problem classes through fault propagation and circuit-depth fidelity decay, with problem structure determining which effects dominate. A global depolarizing model fits compiled SK and MaxCut results but is inappropriate for Hardware Grid problems.

  • Fault propagation is limited on low-degree Hardware Grid and 3-Regular MaxCut problems but grows with system size for extensive-degree SK instances.Compiled 3-Regular MaxCut circuits also introduce SWAPs that propagate faults through otherwise nonadjacent problem-graph nodes.
  • The exponential depolarizing model reasonably fits compiled SK Model and 3-Regular MaxCut performance because their circuits are extensive and faults are rapidly mixed.The fit is stronger for the high-degree SK model, where faults are rapidly mixed.
  • The depolarizing model is inappropriate for Hardware Grid problems because limited fault propagation and fixed circuit depth produce an approximately size-independent noise signature.Hardware Grid problems have low graph degree and simple compilation.
  • The fitted channel models the experimental objective as a fidelity-scaled noiseless objective, with circuit fidelity parameterized as fc = f^n × f0.Here, f represents per-qubit fidelity and f0 a qubit-independent offset.
  • Figures S8–S10 compare noiseless and experimental QAOA performance across depth and problem size for random couplings, SK, and 3-Regular MaxCut instances.The plotted ranges are p ∈[1, 5], n ∈[2, 23] for random couplings; p ∈[1, 3], n ∈[3, 17] for SK; and p ∈[1, 3], n ∈[4, 22] for 3-Regular MaxCut.
Loading 2004.04197v3…