PaperlayerView exact revision on arXiv

Source-linked AI summary

Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem

Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, Marco Pistoia

arXiv:2308.02342v2quant-phcond-mat.stat-mechcs.ET

TL;DR

The paper asks whether QAOA can provide a scaling advantage on classically intractable optimization problems. It studies fixed-schedule QAOA on LABS through noiseless simulations and trapped-ion experiments, finding better empirical scaling than classical heuristics, with further improvement from quantum minimum-finding.

  • Problem

    Little is known about whether QAOA provides a scaling advantage over classical solvers, motivating tests on the classically difficult LABS problem.

  • Method

    The authors perform noiseless exact simulations of fixed-schedule QAOA on LABS and implement QAOA with algorithm-specific error detection on Quantinuum trapped-ion processors.

  • Results

    QAOA TTS scales as 1.46^N at p = 12 and 1.21^N with quantum minimum-finding, compared with 1.34^N for the best classical heuristic; error detection reduces noise impact by up to 65%.

  • Takeaways & Limitations

    The results provide evidence that QAOA can serve as an algorithmic component for speedups on an idealized fault-tolerant quantum computer.

  • Takeaways & Limitations

    The numerical evidence covers only instances with N ≤40, and further hardware and error-correction improvements are necessary for quantum minimum-finding augmented with QAOA.

Abstract

from arXiv · show

The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. We perform noiseless simulations with up to 40 qubits and observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. Our results provide evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.

INTRODUCTION

This study evaluates fixed-parameter QAOA on the classically difficult LABS optimization problem, combining noiseless scaling simulations with an initial trapped-ion implementation. The results indicate improved scaling over classical heuristics, especially when QAOA is combined with quantum minimum-finding.

  • QAOA approach: QAOA alternates problem and mixing operators for p layers, using fixed schedules to study runtime scaling at constant depth.The phase operator encodes the optimization problem in a diagonal Hamiltonian, while the mixing operator uses a transverse-field Hamiltonian.
  • LABS problem: LABS minimizes a quartic sidelobe-energy objective over N-bit sequences and is harder than commonly studied problems such as MaxCut.Its objective contains degree-2 and degree-4 terms, while weak correlation between Hamming distance and objective indicates limited exploitable structure.
  • Experimental progress: Experiments on Quantinuum trapped-ion processors reached N = 18, while algorithm-specific error detection reduced noise impact on solution quality by up to 65%.The implementation represents initial experimental progress toward executing QAOA for LABS.
  • QAOA dynamics: Increasing QAOA depth beyond p ≈12 does not improve TTS scaling, and parameters optimized for energy can differ substantially from those optimized for optimal-solution probability.The scaling fit is robust when including instances with N ≥28.
  • Classical baselines: Classical LABS solvers show exponential runtime scaling, with branch-and-bound exact solvers scaling as 1.73^N and Memetic Tabu scaling as 1.34^N.The branch-and-bound comparison is based on commercial solver experiments whose optimality-certificate scaling agrees with the literature.

Scaling of Quantum Time-to-Solution for LABS

Noiseless simulations indicate that fixed-parameter QAOA has favorable LABS runtime scaling, with quantum minimum-finding improving it further. Experiments on trapped-ion processors extend QAOA to 18 qubits and show that algorithm-specific parity checks can substantially reduce noise effects, while larger hard instances remain hardware-limited.

  • Numerical scaling: Table 1 reports better time-to-solution scaling for constant-depth p = 12 QAOA plus quantum minimum-finding than for the best known classical heuristics.The table also distinguishes branch-and-bound time to certify optimality from the shorter time to find an optimal solution.
  • Numerical scaling: 1.46^N: QAOA with constant depth p = 12 has this time-to-solution scaling in exact noiseless simulations.The scaling analysis evaluates QAOA once with fixed β, γ and no parameter-optimization overhead.
  • Numerical scaling: 1.21^N: augmenting p = 12 QAOA with quantum minimum-finding improves the time-to-solution scaling.Quantum minimum-finding is presented as a fault-tolerant enhancement of constant-depth QAOA.
  • Numerical scaling: Beyond p ≈12, increasing QAOA depth does not improve time-to-solution scaling and gives no advantage over amplitude amplification.At small p, QAOA layers can produce much larger increases in success probability than amplitude-amplification steps.
  • Experiments on trapped-ion system: Up to 18 qubits, trapped-ion experiments execute p = 1 QAOA circuits, while implementing the phase operator requires decomposed four-body interactions and many two-qubit gates.The estimated two-qubit gate count reaches approximately 7.5 × 10^5 at N = 67 and p = 12.
  • Experiments on trapped-ion system: 54% on average and up to 65% for specific N: parity-check postselection reduces the difference between experimental and noiseless-simulation merit factors.The scheme uses problem symmetries to detect some errors in the phase-operator portion of the circuit.

DISCUSSION

The paper finds that QAOA combined with quantum minimum-finding scales better than classical heuristics for LABS, while practical realization remains limited by fault-tolerance overheads and finite-size evidence.

  • QAOA combined with quantum minimum-finding scales better than the best known classical heuristics for LABS.
  • The numerical evidence is fitted only for instances with N ≤40, although the authors compare against classical scaling reported up to N ≤66.
  • Substantial reductions in fault-tolerance overhead are necessary before the QAOA-augmented quantum minimum-finding speedup can be realized.
  • Quantum minimum-finding reduces the scaling exponent by half compared with directly sampling QAOA output.
  • The method converts optimization into feasibility by thresholding the cost and using amplitude amplification within a binary search.
  • QAOA prepares an initial state with larger and more favorably scaling overlap with the optimal state than a uniform superposition.

Choice of QAOA parameters β, γ

The experiments use parameters optimized on small LABS instances, averaged into fixed schedules, and rescaled for larger problem sizes; classical solver comparisons provide the scaling baseline.

  • QAOA parameters are optimized for small N with the FOURIER reparameterization scheme, then converted into fixed parameters for larger N.
  • The parameters used at size N rescale γ by N, using eight optimized instances with 24 ≤ N_j ≤31.
  • The fixed parameters are obtained by taking the arithmetic mean of optimized parameters across small instances.
  • The error-detection scheme exploits phase-operator symmetry by measuring parity syndromes and postselecting outcomes in the correct eigenspace.
  • The phase operator is divided into m approximately equal two-qubit-gate splits, with syndrome checks performed after each split.
  • Branch-and-bound solvers are used as exact-solver baselines, while Memetic Tabu supplies the heuristic comparison.

High-performance simulation of QAOA

The study uses a custom high-performance statevector simulator that exploits the structure of QAOA operations and distributes computation across GPUs on Polaris.

  • A custom scalable, algorithm-specific QAOA simulator enables the numerical results.
  • The simulator directly propagates the full quantum state to evaluate the cost expectation and exponentially small optimal-solution probability.
  • Diagonal phase separation is simulated by elementwise multiplication with precomputed cost values, enabling local parallelization.
  • The mixing operator is implemented through fixed 2 × 2 unitary matrices applied to reshaped statevector index groups.
  • The simulations distribute statevector and cost-operator chunks across 256 Polaris nodes, each containing four NVIDIA A100 GPUs.

S1. BACKGROUND ON THE LABS PROBLEM

LABS concerns binary sequences with low autocorrelation, has applications in radar-pulse design, and becomes difficult as general-instance size grows; classical methods exploit restricted structure when available.

  • LABS seeks binary sequences with low sidelobe energy, using merit factor as the ratio of central to sidelobe energy.
  • Skew-symmetric sequences reduce the search space from 2^N to 2^(N/2), improving runtime scaling for solvers restricted to that subspace.
  • The study targets general LABS and excludes solvers capable only of handling skew-symmetric instances.
  • Prior classical-solver results distinguish general from skew-symmetric LABS and report N_max as the largest size tackled, not necessarily solved exactly.
  • The literature review excludes negative results showing that simulated annealing and plain evolutionary algorithms fail to obtain good solutions.

S2. QAOA AS AN EXACT AND APPROXIMATE OPTIMIZATION ALGORITHM

The paper distinguishes QAOA used for approximate solution quality from QAOA used as an exact solver targeting time to solution. On LABS, QAOA can perform poorly under the expected-merit-factor objective while achieving high overlap with optimal solutions under the probability objective.

  • Objective-dependent parameters: QAOA parameters optimized for expected merit factor and optimal-solution probability differ substantially, and each performs poorly on the other metric.The distinction is especially pronounced for β; interpolating between the two parameter sets gives poor performance at opposite endpoints.
  • Approximate optimization: At p = 100, QAOA achieves expected merit factor below 5 as N grows, failing to outperform simple classical techniques.The expected merit factor also grows increasingly slowly with N and p, suggesting high approximation quality would require very large depth.
  • Exact optimization: For N = 25, QAOA optimized for popt has high overlap with the ground state while allowing substantial probability on higher-energy levels.At p = 40, the ground-state probability is 27.3 times greater for QAOA optimized for popt than for QAOA optimized for expected merit factor.
  • Exact optimization: QAOA reaches high overlap with optimal LABS solutions for N ≤40, motivating time to solution as the exact-solver evaluation metric.For N = 39 and p = 33, the expected number of shots is 1.2 × 10^4, a 5.4 × 10^6 improvement over random guessing.
  • Interpretation: The results indicate that bounded expected solution quality does not preclude QAOA from obtaining exact optimal solutions with high measurement probability.This provides a caveat to approximation-focused bounds for constant-depth QAOA.

A. Optimized QAOA parameters for LABS change with N

The optimized QAOA parameters vary systematically with problem size, so the paper rescales and averages parameters optimized on smaller LABS instances to construct fixed schedules. FOURIER optimization provides nearly the same parameter quality as much more expensive direct optimization.

  • A. Optimized QAOA parameters for LABS change with N: The optimized γ* decreases as 1/N while β* remains roughly constant across problem sizes.After rescaling γ* by N, optimized parameter sets for N = 22 and N = 25 are visually indistinguishable.
  • A. Optimized QAOA parameters for LABS change with N: A decreasing initial optimizer step size of 0.01/N supports robust convergence because QAOA parameters have different scales for different N.The parameter-scale behavior motivates both optimizer initialization and fixed-parameter rescaling.
  • A. Optimized QAOA parameters for LABS change with N: The FOURIER[∞, 0] heuristic matches extensive direct optimization closely, with mean differences below 0.05%.In the worst considered case, FOURIER parameters are less than 0.5% worse than direct optimization.
  • A. Optimized QAOA parameters for LABS change with N: The fixed-parameter scheme averages appropriately rescaled optimized parameters from smaller problem sizes for each figure of merit.The averaging ranges are 20 ≤ N ≤27 for expected merit factor and 24 ≤ N ≤31 for popt.
  • A. Optimized QAOA parameters for LABS change with N: Fixed and directly optimized parameters have visually indistinguishable performance in the reported comparisons.Performance improves monotonically with p, although relative differences grow at higher depth.

E. Evidence of the success of the fixed parameter scheme

The fixed-parameter strategy remains effective across problem sizes, while the QAOA scaling estimate is robust to fit choices but does not improve indefinitely with depth. The paper also combines constant-depth QAOA with quantum minimum-finding to obtain an exact solution.

  • E. Evidence of the success of the fixed parameter scheme: Fixed-parameter performance remains close to directly optimized performance, with good performance at high N and monotonic improvement with p.Further improvements to fixed parameters may yield better QAOA TTS scaling because the performance gap grows at higher p.
  • E. Evidence of the success of the fixed parameter scheme: Averaging fits over 20 ≤ Nmin ≤35 gives QAOA scaling of 1.45^N, close to the main-text estimate of 1.46^N.For sufficiently large p and small Nmin, the exponent changes as Nmin increases, indicating that a larger N regime is needed for stable fitting.
  • E. Evidence of the success of the fixed parameter scheme: Increasing QAOA depth beyond a small constant does not improve LABS scaling, and the coefficient c in TTS = Θ(2^cN) does not follow a power law in p.When the fit quality is high over 28 ≤ N ≤38, the scaling coefficient does not follow a power law.
  • E. Evidence of the success of the fixed parameter scheme: Combining constant-depth QAOA with generalized quantum minimum-finding uses QAOA as a subroutine for finding the minimum-cost LABS solution.Theorem 1 assumes overlap at least 1/√popt and popt ≥1/N, yielding gate complexity O(poly(N) log(1/δ)M) with M ≥1/√popt.
  • E. Evidence of the success of the fixed parameter scheme: For small p, one QAOA layer gives orders-of-magnitude larger gain than one amplitude-amplification step, while at sufficiently high p the gains become similar.The comparison motivates increasing QAOA depth rather than replacing QAOA steps with more amplitude-amplification steps in the reported regime.

J. Details of the classical solver scaling

The paper measures scaling for commercial branch-and-bound solvers and the Memetic Tabu heuristic using repeated runs and fitted runtime-related quantities. The supplementary figures report confidence intervals and fitting procedures for these classical baselines.

  • J. Details of the classical solver scaling: Gurobi and CPLEX branch-and-bound scaling is estimated from repeated random-seed runs, with 100 seeds for N ≤32 and 10 seeds for N >32.Solver settings include Gurobi Cuts=0 and Heuristics=0, with default values for other Gurobi and CPLEX parameters.
  • J. Details of the classical solver scaling: Memetic Tabu scaling uses cost-function evaluations rather than fluctuating execution time, and experiments run single-threaded to avoid race-condition overestimation.This produces a more stable scaling quantity across repeated seeds and runtime environments.
  • J. Details of the classical solver scaling: For Gurobi, the 95% confidence intervals are (1.571, 1.659) for TTS and (1.721, 1.792) for TTO.TTO denotes time to obtain a certificate of optimality.
  • J. Details of the classical solver scaling: For CPLEX, the 95% confidence intervals are (1.609, 1.737) for TTS and (1.693, 1.770) for TTO.The fits report both time to solution and time to optimality.
  • J. Details of the classical solver scaling: Memetic Tabu runtime scaling is fit to the mean, with a 95% confidence interval of (1.325, 1.383).The figure shows minimum and maximum whiskers, quartiles, and the mean as the horizontal line in each box.

S4. EXPERIMENTS ON TRAPPED-ION SYSTEMS

The experiments use Quantinuum trapped-ion platforms with all-to-all connectivity and native Rzz gates. Mid-circuit measurement and reset are supported but introduce small crosstalk errors.

  • Hardware platform: Quantinuum H1 and H2 platforms use QCCD architectures with separate gate zones for two-qubit operations.The platforms encode qubits in hyperfine states of 171Yb+ ions.
  • Hardware platform: All-to-all connectivity enables two-qubit gates between arbitrary qubit pairs by transporting ions into a common gate zone.This design suppresses crosstalk and supports high-fidelity operations.
  • Gate implementation: The native two-qubit operation is Rzz(γ), implemented using a phase-sensitive Mølmer–Sørensen gate with single-qubit wrapper pulses.The rotation angle is controlled through the Mølmer–Sørensen gate parameters.
  • Hardware limitation: Mid-circuit measurement and reset are available but cause small crosstalk errors from stray measurement and reset laser light.This hardware effect is relevant to experiments using algorithm-specific error detection.

B. Circuit compilation and optimization

The compilation procedure targets two-qubit gate count by ordering diagonal cost terms to maximize CNOT cancellations. Greedy ordering reduces the compiled circuit cost beyond tket optimization alone.

  • Circuit compilation: The compilation procedure prioritizes two-qubit gate count because two-qubit gates are the devices’ highest-error operations.At most five two-qubit gates can execute in parallel, so additional parallelism may offer diminishing returns.
  • Circuit compilation: Four-body Rzzzz(γ) terms are decomposed into four CNOT gates and one Rzz(γ) gate.Rzz(γ) is native to Quantinuum H-series processors.
  • Greedy optimization: 1.7 times: greedy interaction-layout optimization reduces the two-qubit gate count on average compared with tket alone.The method schedules four-body terms to cancel CNOTs and places two-body terms near compatible four-body terms.
  • Greedy optimization: Greedy ordering scores candidate four-body terms according to expected CNOT cancellation and penalizes terms that block future cancellations.The resulting list contains four- and two-body terms in their optimized application order.
  • Cost-operator choice: The alternative absolute-autocorrelation Hamiltonian reduces energy-computation complexity to Θ(N^2) but requires quantum arithmetic beyond current hardware capabilities.The experiments therefore retain the cost operator corresponding to Equation S9.

C. Summary of the error-detection scheme

The error-detection scheme sandwiches portions of the phase operator between parity checks and post-selects outcomes indicating no detected error. Checking both global x and z parities detects every odd-weight Pauli error when checks are noiseless.

  • Scheme overview: The scheme inserts parity checks around a full or partial phase-operator segment Uphase and uses an ancilla initialized in |0⟩.The analysis first treats one parity check and then generalizes to simultaneous x and z checks.
  • Scheme overview: If no error occurs during Uphase, measuring the ancilla always returns 0.This outcome identifies the no-detected-error branch of the check.
  • Single-parity checks: A Pauli error that anticommutes with the checked parity produces ancilla outcome 1 and is detected, whereas a commuting error goes undetected.Detection therefore depends on the error’s commutation relation with the check.
  • Dual-parity checks: Checking both x^⊗N and z^⊗N parities detects every odd-weight Pauli error when the checks are noiseless.More frequent noiseless checks improve fidelity, but noisy checks create a trade-off by introducing errors themselves.

D. Performance of the error-detection scheme

Increasing parity-check frequency improves post-selected QAOA quality up to m = 3, but the resulting acceptance ratio falls sharply with problem size. Mid-circuit discard can reduce the time to obtain a high-quality sample, although those savings are estimated rather than experimentally implemented.

  • Post-selection quality: m = 3: increasing parity-check frequency improves expected merit factor after post-selection.The experiments use three checks to balance repetition overhead against final-result fidelity.
  • Sample quality: Post-selection leaves the best sampled bitstrings with the same merit factor as true optimal bitstrings for all studied instances before and after selection, except for values at N = 13 and N = 17.The figure compares experimentally sampled bitstrings across problem sizes.
  • Post-selection overhead: Below 10%: the post-selection ratio falls at N ≥15 with m = 3.More checks detect more errors but increase the number of discarded shots.
  • Runtime: Mid-circuit checks can reduce time to a high-merit-factor sample by discarding the remaining circuit immediately after detecting an error.This benefit is especially relevant to trapped-ion systems with low clock speeds and long coherence times.
  • Runtime limitation: The reported time savings are estimates because early stopping was not implemented in the hardware experiments.The comparison uses simulations with realistic Quantinuum H2 parameters and m = 3.
Loading 2308.02342v2…