Student or educator? Sign up with your school email and get 6 months of Pro free.

The DOI matches its Crossref record; 86 of the 86 references it cites were found in a registry or an index; 23 of the 32 sources its claims cite were checked for support.

Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem

Open access

Abstract

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.

Overview

CoChat Summary

TL;DR

This paper reports noiseless-simulation evidence that constant-depth QAOA scales better than the best-known classical solvers on the low autocorrelation binary sequences (LABS) problem, and that adding quantum minimum finding improves the scaling further. It also demonstrates a hardware step on Quantinuum trapped-ion processors, where symmetry-based error detection improved measured performance.

Key findings

  • In noiseless simulations, QAOA at depth \(p=12\) has time-to-solution (TTS) scaling of \(1.46^N\), and QAOA combined with quantum minimum finding (“QAOA+QMF”) scales as \(1.21^N\).
  • The best-known classical heuristic benchmarked in the paper, Memetic Tabu, scales as \(1.35^N\) with a 95% confidence interval of \((1.33, 1.38)\); commercial branch-and-bound with an optimality stop rule scales as \(1.615^N\) for Gurobi with 95% CI \((1.571, 1.659)\).
  • The paper reports \(R^2 > 0.94\) for the QAOA TTS fit when using only sizes \(N \ge 28\).
  • On trapped-ion hardware, using up to three parity checks reduced the difference between experimental results and noiseless simulation by 54% on average and up to 65% for specific \(N\); in all cases, the optimal bitstring was found within the total sample, and in all but two cases within the postselected sample.

Methods

  • The study targets the LABS problem, encoded as a diagonal Hamiltonian; QAOA is run with fixed parameters \((\beta,\gamma)\) chosen by optimizing small instances and then averaging/rescaling them for larger \(N\) (using \(24 \le N_j \le 31\), \(M=8\)).
  • Numerical results come from exact noiseless simulations up to 40 qubits on the Polaris supercomputer; the main analysis fits exponential scaling of TTS versus problem size and compares it to branch-and-bound and Memetic Tabu.
  • For the hardware study, the authors ran \(p=1\) QAOA circuits on Quantinuum H-series trapped-ion processors for instances up to \(N=18\), with an algorithm-specific symmetry-verification error-detection scheme using parity checks and postselection.

Limitations

  • The paper states that the numerical scaling evidence is obtained only up to \(N \le 40\); it also notes that TTS can only be evaluated where the solution is known, which for LABS is up to 66 variables.
  • The authors say the hardware experiments were limited to \(p=1\), and that implementing QAOA for LABS instances hard for classical solvers would likely require error correction; they estimate a two-qubit gate count of \(\approx 7.5 \times 10^5\) already at \(N=67\) and \(p=12\).
  • Evident from the text: the main scaling claim is based on noiseless simulation with fixed, non-optimized parameters for larger instances, so the result is evidence from an idealized setting rather than a demonstrated end-to-end hardware speedup.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1126/sciadv.adm6761

Cites

86 of 86 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Figures

Fig. 1. Classical and quantum algorithms applied to the LABS problem. (A) Diagram of the LABS problem (with example of N = 5). The problem involves nonlocal two-body (black lines) and four-body (blue lines) interactions. (B) Time to solution (TTS) of classical solvers. For the sizes considered, we observe clear exponential scaling with exponents matching their asymptotic values reported in the literature (see Table 1). (C) Diagram of QAOA circuit for a five-qubit example. Starting from a uniform superposition of the computational basis states, we apply p layers of phase and mixing operators, followed by measurement in the computational basis. (D) Distribution over 21 ≤ N ≤ 31 (for LABS) and 34 random instances (for MaxCut on random three-regular graphs with 20 nodes) of Pearson product-moment correlation coefficients relating the Hamming distance of bitstrings from the optimal solution with the objective value ofthe bitstring. LABS has a much lower correlation between the Hamming distance and objective, indicating that it is much harder than the commonly considered MaxCut problem.
Fig. 1. Classical and quantum algorithms applied to the LABS problem. (A) Diagram of the LABS problem (with example of N = 5). The problem involves nonlocal two-body (black lines) and four-body (blue lines) interactions. (B) Time to solution (TTS) of classical solvers. For the sizes considered, we observe clear exponential scaling with exponents matching their asymptotic values reported in the literature (see Table 1). (C) Diagram of QAOA circuit for a five-qubit example. Starting from a uniform superposition of the computational basis states, we apply p layers of phase and mixing operators, followed by measurement in the computational basis. (D) Distribution over 21 ≤ N ≤ 31 (for LABS) and 34 random instances (for MaxCut on random three-regular graphs with 20 nodes) of Pearson product-moment correlation coefficients relating the Hamming distance of bitstrings from the optimal solution with the objective value ofthe bitstring. LABS has a much lower correlation between the Hamming distance and objective, indicating that it is much harder than the commonly considered MaxCut problem.CC BY · PubMed Central
Fig. 2. QAOA runtime scaling. (A) Quality of the exponential fit for different choices of minimum N to include in the fit. N ≥ 28 results in a robust fit, the quality of which does not deteriorate with p. N = 40 is omitted as it was only simulated up to p = 22. (B) TTS of QAOA at p = 12. Clear exponential scaling is observed. (C) Scaling exponent of QAOA runtime for different QAOA depths p. Shaded area shows 95% confidence interval. Increasing p beyond p ≈ 12 does not lead to better scaling.
Fig. 2. QAOA runtime scaling. (A) Quality of the exponential fit for different choices of minimum N to include in the fit. N ≥ 28 results in a robust fit, the quality of which does not deteriorate with p. N = 40 is omitted as it was only simulated up to p = 22. (B) TTS of QAOA at p = 12. Clear exponential scaling is observed. (C) Scaling exponent of QAOA runtime for different QAOA depths p. Shaded area shows 95% confidence interval. Increasing p beyond p ≈ 12 does not lead to better scaling.CC BY · PubMed Central
Fig. 3. QAOA dynamics under different parameter schedules. (A) Gain in success probability popt from applying step p of QAOA and amplitude amplification (AA). The gain is defined as patstepp^opt/patstep(p−1)^opt . The gain at p = 1 is over the random guess. Only one line is plotted for amplitude amplification since the lines for the values of N considered are visually indistinguishable. For small p, a QAOA layer gives orders of magnitude larger gain than a step of AA. (B) Fixed QAOA parameters for p = 30 chosen with respect to the QAOA energy 〈C〉MF (“MF”) and probability of sampling the optimal solution (“popt”). Different choice of optimization objective gives different resulting parameters. (C) Probability of obtaining a binary string corresponding to a given energy level of the LABS problem (the zeroth energy level is the ground state or optimal solution; lower is better). When parameters are optimized with respect to the expected merit factor (labeled “MF”), the QAOA output state is concentrated around the mean and fails to obtain a high overlap with the ground state. On the other hand, when parameters are optimized with respect to popt (labeled “popt”), the QAOA state has a high overlap with both the ground state and higher energy states. The probability of obtaining the ground state is 27.3 times greater for QAOA with parameters optimized with respect to popt at p = 40.
Fig. 3. QAOA dynamics under different parameter schedules. (A) Gain in success probability popt from applying step p of QAOA and amplitude amplification (AA). The gain is defined as patstepp^opt/patstep(p−1)^opt . The gain at p = 1 is over the random guess. Only one line is plotted for amplitude amplification since the lines for the values of N considered are visually indistinguishable. For small p, a QAOA layer gives orders of magnitude larger gain than a step of AA. (B) Fixed QAOA parameters for p = 30 chosen with respect to the QAOA energy 〈C〉MF (“MF”) and probability of sampling the optimal solution (“popt”). Different choice of optimization objective gives different resulting parameters. (C) Probability of obtaining a binary string corresponding to a given energy level of the LABS problem (the zeroth energy level is the ground state or optimal solution; lower is better). When parameters are optimized with respect to the expected merit factor (labeled “MF”), the QAOA output state is concentrated around the mean and fails to obtain a high overlap with the ground state. On the other hand, when parameters are optimized with respect to popt (labeled “popt”), the QAOA state has a high overlap with both the ground state and higher energy states. The probability of obtaining the ground state is 27.3 times greater for QAOA with parameters optimized with respect to popt at p = 40.CC BY · PubMed Central
Fig. 4. Experimental results on trapped-ion system. (A) Decomposition of four-body interaction terms into a two-body Rzz gate and four two-body cnot gates, which can be realized via native Rzz gates. (B) Energy density plot from experimental measured bitstrings for N = 13. Energy index is arranged in energy ascending order. As a comparison, the distributions for noiseless p = 1 QAOA simulation and random guess (assuming uniform distribution of all possible bitstrings) are shown. (C) Experimental results up to 18 qubits on a trapped-ion quantum device (H1-1) with QAOA layer p = 1 with optimized QAOA parameters. The error bars are calculated with 99% confidence intervals hereafter. (D) Illustration of parity check circuit. The z and x parities of states are mapped to ancillary qubits after implementation of full (or part of) phase operators via cz and cnot gates, respectively, followedby mid-circuit measurement on the ancillary qubits to extract the parity syndrome result. (E) Experimental results for circuit with parity check. Three mid-circuit z-parity and x-parity checks were performed using six ancillary qubits. The ancillae can also be reused after appropriate reset during the circuit. The red data points were run on the Quantinuum H2 hardware, while the blue data were from the H1-1 device. Data run on the H1-1 device without any ancillary qubits are shown in gray. Circles (diamonds) are the data without (with) postselection. The abbreviation ED refers to the error detection via the parity checks. Number of mid-circuit parity checks is fixed to be two for N = 10,11 and three for all other N. Improvement in expected merit factor after postselection according to parity syndrome measurement is observed.
Fig. 4. Experimental results on trapped-ion system. (A) Decomposition of four-body interaction terms into a two-body Rzz gate and four two-body cnot gates, which can be realized via native Rzz gates. (B) Energy density plot from experimental measured bitstrings for N = 13. Energy index is arranged in energy ascending order. As a comparison, the distributions for noiseless p = 1 QAOA simulation and random guess (assuming uniform distribution of all possible bitstrings) are shown. (C) Experimental results up to 18 qubits on a trapped-ion quantum device (H1-1) with QAOA layer p = 1 with optimized QAOA parameters. The error bars are calculated with 99% confidence intervals hereafter. (D) Illustration of parity check circuit. The z and x parities of states are mapped to ancillary qubits after implementation of full (or part of) phase operators via cz and cnot gates, respectively, followedby mid-circuit measurement on the ancillary qubits to extract the parity syndrome result. (E) Experimental results for circuit with parity check. Three mid-circuit z-parity and x-parity checks were performed using six ancillary qubits. The ancillae can also be reused after appropriate reset during the circuit. The red data points were run on the Quantinuum H2 hardware, while the blue data were from the H1-1 device. Data run on the H1-1 device without any ancillary qubits are shown in gray. Circles (diamonds) are the data without (with) postselection. The abbreviation ED refers to the error detection via the parity checks. Number of mid-circuit parity checks is fixed to be two for N = 10,11 and three for all other N. Improvement in expected merit factor after postselection according to parity syndrome measurement is observed.CC BY · PubMed Central
Fig. 5. Visualization of how the fixed parameters are obtained. (A) Optimized QAOA parameters β (top lines) and γ (bottom lines) for p = 21. γ is multiplied by N/24 (constant factor of 1/4 added for figure readability in both subfigures). (B) Fixed parameters obtained by taking the arithmetic mean over the optimized parameters.
Fig. 5. Visualization of how the fixed parameters are obtained. (A) Optimized QAOA parameters β (top lines) and γ (bottom lines) for p = 21. γ is multiplied by N/24 (constant factor of 1/4 added for figure readability in both subfigures). (B) Fixed parameters obtained by taking the arithmetic mean over the optimized parameters.CC BY · PubMed Central

Verification

Claims the paper makes

14 Valid · 7 Not valid · 1 Not checked · 36 Own results and interpretations

32 more claims · 7 with their cited sources checked

Create a free account to see all 58 claims and every source verdict.

See all claims — free account
  • Probably not a substantial claim. 6
  • It may state two separate claims as one. 16

Create a free account to see these claims.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Citations

Cites

Show all 85 references

Research works printed but not linked: 3

  1. J. Basso E. Farhi K. Marwaha B. Villalonga L. Zhou The quantum approximate optimization algorithm at high depth for MaxCut on large-girth regular graphs and the Sherrington–Kirkpatrick model in Proceedings of the Conference on the Theory of Quantum Computation Communication and Cryptography (Schloss Dagstuhl – Leibniz-Zentrum für Informatik 2022) pp. 7:1–7:21.
  2. G. F. M. Beenker, T. A. C. M. Claasen, P. W. C. Hermens, Binary sequences with a maximally flat amplitude spectrum. Philips J. Res. 40, 289–304 (1985).
  3. F. Brglez X. Y. Li M. F. Stallmann B. Militzer Reliable cost predictions for finding optimal solutions to labs problem: Evolutionary and alternative algorithms in Proceedings of The Fifth International Workshop on Frontiers in Evolutionary Algorithms (FEA’2003) under JCIS’2003 (2003).

Cited by

See all 120

Metadata

Authors
Shaydulin, R., Li, C., Chakrabarti, S., DeCross, M., Herman, D., Kumar, N., Larson, J., Lykov, D., Minssen, P., Sun, Y., Alexeev, Y., Dreiling, J. M., Gaebler, J. P., Gatterman, T. M., Gerber, J. A., Gilmore, K., Gresh, D., Hewitt, N., Horst, C. V., Hu, S., Johansen, J., Matheny, M., Mengle, T., Mills, M., Moses, S. A., Neyenhuis, B., Siegfried, P., Yalovetzky, R., & Pistoia, M.
Affiliations
  • JPMorgan Chase & Co (United States) (US)
  • Quantinuum (United States) (US)
  • Argonne National Laboratory (US)
Corresponding author
Shaydulin, Ruslan
Venue
Science Advances
Published
2024-05-31
Volume
10
Issue
22
Pages
eadm6761-eadm6761
ISSN
2375-2548 (ISSN-L)
OpenAlex
W4399118343
Cited by
120
References
85
Citations by year
2026: 32 · 2025: 58 · 2024: 23
FWCI
16.61
Type
journal article
Language
en
Open access
Licence
cc-by
Locations
  • Science Advances (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • U.S. Department of Energy (DE‐ AC02‐06CH11357, AC02‐06CH11357, 06CH11357, DE-AC02-)
  • Office of Science (AC02‐06CH11357, DE-AC02, 06CH11357, DE-AC02-06CH11357)
  • Advanced Scientific Computing Research (DE-AC02-06CH11357)
  • Argonne National Laboratory
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum approximate optimization algorithm, low autocorrelation binary sequences, quantum advantage, branch and bound comparison, error detection, trapped-ion quantum computer

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

The claim verdicts this report counts are experimental: their accuracy is not yet measured.

A language model drew the claims from the paper on 2026-10-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-10 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Cited sources are checked with a language model’s help (gpt-6-sol).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.