PaperlayerView exact revision on arXiv

Source-linked AI summary

Benchmarking the Quantum Approximate Optimization Algorithm

Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt, Kristel Michielsen

arXiv:1907.02359v2quant-ph

TL;DR

The paper asks how well QAOA performs across combinatorial-optimization instances and against quantum annealing. It benchmarks QAOA on weighted MaxCut and 2-SAT using simulations and IBM hardware, then compares results with D-Wave 2000Q. Overall performance varies strongly by instance, and D-Wave outperforms simulated QAOA on the studied success-probability comparisons.

  • Problem

    The paper examines the limited evidence about QAOA performance across problem instances and against quantum annealing on representative optimization problems.

  • Method

    The study benchmarks QAOA on weighted MaxCut and 2-SAT using simulators and IBM Q Experience data, comparing the results with D-Wave 2000Q data.

  • Results

    QAOA performance depends strongly on the problem instance, while D-Wave outperforms simulator-executed QAOA in the studied success-probability comparison.

  • Takeaways & Limitations

    QAOA performance varies with the instance, parameter count, and initialization, complicating development of a general parameter-optimization strategy.

Abstract

from arXiv · show

The performance of the quantum approximate optimization algorithm is evaluated by using three different measures: the probability of finding the ground state, the energy expectation value, and a ratio closely related to the approximation ratio. The set of problem instances studied consists of weighted MaxCut problems and 2-satisfiability problems. The Ising model representations of the latter possess unique ground states and highly-degenerate first excited states. The quantum approximate optimization algorithm is executed on quantum computer simulators and on the IBM Q Experience. Additionally, data obtained from the D-Wave 2000Q quantum annealer is used for comparison, and it is found that the D-Wave machine outperforms the quantum approximate optimization algorithm executed on a simulator. The overall performance of the quantum approximate optimization algorithm is found to strongly depend on the problem instance.

I. INTRODUCTION

The paper critically assesses QAOA for combinatorial optimization through simulations, quantum-device execution, and comparison with quantum annealing. It benchmarks 2-SAT and weighted MaxCut instances using multiple performance measures, finding that success depends strongly on the problem instance.

  • Motivation and scope: QAOA is a variational gate-based method that approximates a cost-function ground state using a circuit with 2p parameters optimized classically.It can also be viewed as discrete-time quantum annealing, with p controlling the number of variational layers.
  • Motivation and scope: The study critically assesses QAOA using simulations, the IBM Q Experience, and comparison with D-Wave 2000Q quantum annealing.
  • Benchmark design: The benchmark covers 2-SAT problems with up to 18 variables and weighted MaxCut problems with 16 variables, evaluated by energy, a related ratio, and success probability.
  • Paper organization: The paper introduces the benchmark problems and QAOA background before describing performance assessment and comparisons with quantum annealing.
  • Benchmark design: The selected 2-SAT Ising models have unique ground states and highly degenerate first-excited states, and are chosen to permit direct mapping onto the Chimera graph.

B. The MaxCut Problem

MaxCut partitions graph vertices into two disjoint subsets while maximizing crossing edges; weighted MaxCut assigns weights to edges. The paper connects these problems to Ising Hamiltonians and quantum annealing, which approaches the problem ground state under sufficiently slow evolution.

  • MaxCut formulation: MaxCut seeks two disjoint vertex subsets whose crossing-edge count is as large as possible.
  • MaxCut formulation: Weighted MaxCut extends this objective by assigning weights w_ij to graph edges, with the corresponding Hamiltonian as a special case of the 2-SAT mapping.
  • Quantum annealing: Quantum annealing starts in the ground state of an initial Hamiltonian and changes the Hamiltonian toward H_C, the optimization Hamiltonian.The schedule uses H_init and H_C with coefficients A(s) and B(s).
  • Quantum annealing: In the adiabatic limit, sufficiently smooth evolution over infinitely long annealing time approaches the ground state of H_C.
  • Quantum annealing: The experiments use the D-Wave 2000Q quantum annealer for the quantum-annealing comparison.

D. Quantum Approximate Optimization Algorithm

QAOA prepares a uniform superposition, applies a finite-p variational circuit, and classically optimizes its parameters using sampled or simulator-computed cost estimates. Measurements then produce candidate computational-basis solutions.

  • Algorithm construction: QAOA formulates the objective C(z) as an Ising Hamiltonian whose ground-state energy corresponds to the minimum cost.
  • Algorithm construction: The quantum computer begins in the uniform state |+⟩^⊗N, then constructs a variational ansatz with parameter vectors γ and β.
  • Algorithm construction: The parameter p determines the number of independent variational parameters, while weighted MaxCut can prevent restricting γ_i to [0, 2π].
  • Classical optimization: The parameters are optimized by minimizing the expectation value of H_C on a conventional computer, although numerical minimization may find only a local minimum.
  • Sampling and outputs: Measurements sample computational-basis strings from the optimized state; even when it is not the ground state, QAOA can produce solutions with cost no greater than the optimized expectation value.
  • Relation to annealing: Finite-p QAOA relaxes the annealing schedule constraints and treats γ_j and β_j as freely chosen variational parameters.

E. Performance Measures

The study evaluates QAOA using ground-state probability, energy expectation, and a shifted ratio related to approximation ratios. The first and third measures require known ground states, limiting their practical use outside benchmarking.

  • Measures: The three measures are ground-state success probability, energy expectation E_p, and a ratio r intended to be close to one.
  • Measures: The ratio r is shifted to satisfy 0 ≤ r ≤ 1 and corresponds to the approximation-ratio definition for the selected problem instances.
  • Interpretation: The ratio r is less sensitive than success probability to differences between problem instances, while QAOA ratios are generally below those obtained by quantum annealing.
  • Scope and limitations: Runtime and time-to-solution are excluded because simulator timing may not represent QAOA execution on real devices.
  • Scope and limitations: Success probability and r are useful only for benchmark problems with known ground states; in practical settings, energy expectation is the usable measure.
  • Validation: The analytical p = 1 expectation-value result is used as an independent check on numerical results.

III. PRACTICAL ASPECTS

The study tests QAOA using grid searches for p = 1, iterative classical optimization for p > 1, and parallel quantum-annealing experiments on D-Wave hardware. Practical feasibility depends on repeated energy evaluations and sample requirements, especially on real quantum devices.

  • QAOA evaluation: For p = 1, the authors evaluate QAOA on a regular 2D grid using Qiskit circuits executed on IBM’s simulator and quantum processor.The tested IBM Q Experience instances natively fit the processor architecture without additional SWAP gates.
  • QAOA evaluation: For p > 1, JUQCS returns an energy or success-probability value that a Nelder–Mead optimizer uses to propose new QAOA parameters.The cycle repeats until the objective reaches a stationary value, which may be a local rather than global optimum.
  • Computational cost: The complete optimization depends on the number of cycles required for convergence, although one cycle takes about one second even for p ≈40–50.For 18-variable problems, a single cycle is under a second for small p.
  • Computational cost: Real-device QAOA requires many evaluations and sampled energies, so it is practical only when NS · Nev is much smaller than 2^N.Otherwise, the total work is comparable to exhaustive search over the Hilbert-space basis states.
  • Quantum annealing comparison: D-Wave experiments distribute multiple copies of each Ising instance across the Chimera graph and repeat annealing to estimate success probability and the ratio r.No minor embedding is needed for the studied instances, allowing many copies to run simultaneously.

IV. RESULTS

The p = 1 results show that QAOA performance varies strongly across instances and platforms. Simulators obtain higher success probabilities for the 8-variable 2-SAT instance than for the 16-variable weighted MaxCut instance, while IBM hardware does not qualitatively reproduce the simulator’s success-probability landscape.

  • Simulator results: The simulator achieves about 10% success probability for the 8-variable 2-SAT instance and about 2% for the 16-variable weighted MaxCut instance.High success-probability regions correspond to small energy expectations, but their optimal parameter values differ slightly.
  • Simulator results: Figures 2 and 3 map success probability and E1(γ, β) over γ and β for the 8-variable 2-SAT and 16-variable weighted MaxCut instances.Both plots use p = 1 and IBM Q simulator data.
  • Parameter landscape: For weighted MaxCut, noninteger Hamiltonian eigenvalues remove γ-periodicity and create many local minima in the E1(γ, β) landscape.For the studied case, the largest success probability can still be found with γ ∈[0, 2π].
  • Hardware results: IBM Q Experience success-probability results do not closely resemble simulator results, although the corresponding E1(γ, β) results show some resemblance.The authors interpret this as evidence that current hardware has difficulty producing data qualitatively consistent with the p = 1 solution.
  • Scaling and sampling: For p = 1, QAOA enhances success probability over random sampling, but the largest success probability becomes rather small as the number of variables increases.Figures 6 and 7 compare sampled-energy distributions for parameters maximizing success probability or minimizing E1 against random sampling.

B. QAOA for p > 1

For p > 1, QAOA performance varies strongly with initialization, objective function, and problem instance. The 16-variable weighted MaxCut and 8-variable 2-SAT cases perform well, whereas the 18-variable 2-SAT case is limited.

  • 18-variable 2-SAT: For the 18-variable 2-SAT instance, p = 10 QAOA achieves roughly 40% success probability after Nelder-Mead optimization.The optimization also drives the energy expectation to a stationary value.
  • 18-variable 2-SAT: Changing the initialization from p = 1-derived values to linear annealing reduces success probability from 38.6% to 8.5%.The corresponding energy expectations are Ep=10 ≈−14.22 and Ep=10 ≈−12.16, respectively.
  • Objective function: For the same 18-variable 2-SAT instance, minimizing Ep=10 reaches only 0.1% success probability and can select different local optima than success-probability optimization.The authors suggest that the energy and success-probability landscapes may have misaligned optima.
  • 16-variable weighted MaxCut: For the 16-variable weighted MaxCut instance, minimizing Ep=10 produces approximately 85.6% success probability after 6000 Nelder-Mead iterations.The optimized parameters deviate from, but retain the trends of, the linear annealing initialization.
  • 8-variable 2-SAT: For the 8-variable 2-SAT instance, p = 50 with linear-annealing initialization yields about 82.7% success probability, which further optimization raises to almost one.This supports the value of an initialization that already approximates the ground state.
  • Overall comparison: Overall, QAOA success depends critically on the problem instance: the 8-variable 2-SAT and 16-variable MaxCut cases work well, but the 18-variable 2-SAT case does not.The 18-variable instance is also described as hard for quantum annealing.

C. Quantum annealing on a D-Wave machine

The comparison uses simulator-based QAOA data and D-Wave 2000Q data for 2-SAT instances. D-Wave generally samples ground states more often and obtains higher ratios, while both methods vary across problem instances.

  • Benchmark setup: The comparison evaluates QAOA at p = 1 and p = 5 against D-Wave 2000Q on 2-SAT instances with 8, 12, and 18 variables.It reports success probability and the ratio r at annealing times of 3 µs and 30 µs.
  • Results: D-Wave samples the unique ground state much more often than QAOA executed on a simulator, and its ratio r is also higher.The comparison uses QAOA parameter optimization based on the energy expectation value.
  • Instance dependence: D-Wave’s ratio r varies more strongly by problem instance, whereas QAOA’s ratio for p = 5 appears to increase systematically with problem size.The QAOA increase from p = 1 to p = 5 exceeds D-Wave’s increase from a 3 µs to a 30 µs anneal.
  • Instance dependence: For many 12- and 18-variable instances, QAOA success probabilities at p = 5 are roughly one-tenth of D-Wave probabilities at 3 µs.This indicates that instances hard for D-Wave are also hard for QAOA, although the comparison remains instance-dependent.

V. CONCLUSION

The study finds that QAOA performance varies strongly across problem instances and depends on the performance measure and optimization setting. Compared with quantum annealing, QAOA performs worse on the studied instances when success probability or the ratio r is used.

  • QAOA performance depends strongly on the problem instance across the studied 2-SAT and weighted MaxCut problems.
  • For p = 1, optimizing the QAOA wave function has only a modest effect on success probability across the problem collection.
  • For some 2-SAT instances, p = 5 QAOA achieves success probability much larger than 1% even when optimizing energy expectation rather than success probability.
  • At p = 50, optimized parameters are close to a linear annealing scheme and yield success probability close to one.
  • Using success probability, QAOA cannot compete with quantum annealing when no minor embedding is required, while its ratio r is less sensitive to instance differences and usually remains significantly smaller.

Appendix A: Relation between QAOA and quantum annealing

The appendix connects discrete QAOA steps to a discretized quantum-annealing evolution. A second-order time discretization maps annealing schedules to QAOA parameters with the same number of steps.

  • The annealing Hamiltonian is mapped to QAOA evolution after choosing the initial-state convention so |+⟩⊗N is the ground state of H(s).
  • The annealing evolution is discretized into N time steps of size τ = ta/N, with each step approximated to second order in τ.
  • The discretization uses sn = (n −1/2)/N for n = 1, . . . , N.
  • The QAOA parameters are chosen as γn = τB(sn) and βn = −τ (A(sn+1) + A(sn)) /2 for the corresponding steps.
  • N time steps in the second-order annealing scheme correspond to p = N QAOA steps.

Appendix B: Problem instances

The benchmark uses a 16-variable weighted MaxCut instance and selected 2-SAT instances designed for controlled comparisons across quantum platforms. The instances are chosen to avoid extra hardware-mapping overhead.

  • The appendix includes a 16-variable weighted MaxCut problem instance.
  • The selected 2-SAT problems have unique ground states and highly degenerate first-excited states, making them very hard for simulated annealing.
  • The 2-SAT instances span different difficulty levels for quantum annealing and can be mapped directly onto the IBM Q Melbourne and D-Wave Chimera architectures.
  • Direct mappings are required to avoid additional IBM swap gates and D-Wave minor embedding, which would complicate the comparison by introducing graph-structure effects.
Loading 1907.02359v2…