Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem
Open accessThe DOI matches its Crossref record; 87 of the 87 references it cites were found in a registry or an index; 23 of the 32 sources its claims cite were checked for support.
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
Cites
Statistics
Figures





Verification
Claims the paper makes
14 Valid · 7 Not valid · 1 Not checked · 36 Own results and interpretations
The cited sources that could be checked couldn’t confirm or dispute this claim.
In the paper
“A recent numerical study (13) of random 8-SAT with N ≤ 20 variables has shown that the time to solution (TTS) of QAOA with fixed parameters and constant depth grows as 1.23N.”
§ Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem > INTRODUCTION
What the sources say
- Could not verifycites [13] sourceExperimental — accuracy not yet measured
The quantum approximate optimization algorithm section reports fixed-depth QAOA results for self-avoiding walks, not random 8-SAT. Searches for 8-SAT, time to solution, and the 1.23^N scaling found no passage addressing the attributed result; the paper gives no page numbers in our copy. (LLM, conf=0.76)
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Could not verify
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“First, the complexity of LABS grows rapidly, with optimal solutions known only for N ≤ 66 and the best heuristics producing approximate solutions of quality decaying with N for N200 (20, 21).”
§ Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem > INTRODUCTION
What the sources say
- Not matchedcites [20]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Supportedcites [21] source
In “What is known” (p. 2), the paper says its exact algorithms solved LABS up to N ≤ 66. “Results and Conclusions” (p. 11) confirms that the authors computed all maximum-merit-factor sequences through N = 66 and describes solving larger systems as future work. (LLM, conf=0.93)
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Not matched
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“Second, the performance of classical solvers for LABS has been benchmarked (20, 21) in terms of the scaling of their TTS with problem size.”
§ Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem > INTRODUCTION
What the sources say
- Not matchedcites [20]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Supportedcites [21] source
Section 3.1 (pp. 6, 9) compares the running-time scaling of classical branch-and-bound approaches as LABS sequence length N increases. Section 4 (p. 11) also reports performance measurements across problem sizes, supporting the claim's description of benchmarking time to solution. (LLM, conf=0.90)
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Not matched
The cited sources that could be checked couldn’t confirm or dispute this claim.
In the paper
“When QAOA is combined with amplitude amplification, the quantum TTS grows as 1.11N (13), whereas the best classical heuristic has TTS that grows as 1.25N (13).”
§ Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem > INTRODUCTION
What the sources say
- Could not verifycites [13] sourceExperimental — accuracy not yet measured
In “The quantum approximate optimization algorithm” (page unavailable), the paper compares QAOA with amplitude amplification for self-avoiding walks; it does not report their combined time to solution. Searches for random 8-SAT and the 1.11^N and 1.25^N scaling figures found no passage addressing those claims. (LLM, conf=0.76)
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Could not verify
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“First, the complexity of LABS grows rapidly, with optimal solutions known only for N ≤ 66 and the best heuristics producing approximate solutions of quality decaying with N for N200 (20, 21).”
§ Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem > INTRODUCTION
What the sources say
- Not matchedcites [20]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Supportedcites [21] source
Section 2, “What is known” (p. 3), reports a significant drop in the best-known merit factors for N > 200 and attributes it to sophisticated search heuristics failing on larger LABS problems. This supports the claim that heuristic solution quality declines beyond that size. (LLM, conf=0.94)
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Not matched
32 more claims · 7 with their cited sources checked
Create a free account to see all 58 claims and every source verdict.
- Probably not a substantial claim. 6
- It may state two separate claims as one. 16
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?
The cited source says what the claim attributes to it.
In the citing paper
“Data for different solvers are collected up to different maximum problem sizes and are truncated appropriately to mitigate finite-size effects11,12.”
From Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers (2026) · cites this paper as [12]
The cited source says what the claim attributes to it.
In the citing paper
“Throughout this work, we adopt a fixed-parameter protocol to enhance the reliability of the scaling analysis11,12.”
From Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers (2026) · cites this paper as [12]
Citations
Cites
Glover, F., & Laguna, M. (1997) · doi:10.1007/978-1-4615-6089-0 · Cited by 3,001 · cited 1×
“…algorithm is used to find initializations for tabu search, a metaheuristic that augments local neighborhood search with a data structure (known as the tabu list) that filters possible local moves if the potential solutions have been recently visited or diversification rules are violated (48).”
MethodA Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680 · cited 1×
“(44)) .”
The BOBYQA algorithm for bound constrained optimization without derivatives
Powell, M. J. D. (2009) · Cited by 1,094
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913 · cited 2×
“While QAOA has been studied extensively (11–14), little is known about its potential to provide a scaling advantage over classical solvers.”
BackgroundSynthesis of low-peak-factor signals and binary sequences with low autocorrelation (Corresp.)
Schroeder, M. (1970) · IEEE Transactions on Information Theory · doi:10.1109/tit.1970.1054411 · Cited by 740 · cited 1×
“We study the scaling of QAOA TTS with the problem size on the Low Autocorrelation Binary Sequences (LABS) problem (15, 16), also known as the Bernasconi model in statistical physics (17, 18).”
MethodDemonstration of the trapped-ion quantum CCD computer architecture
Pino, J. M., Dreiling, J. M., Figgatt, C., Gaebler, J. P., Moses, S. A., Allman, M. S., Baldwin, C. H., Foss-Feig, M., Hayes, D., Mayer, K., et al. (2021) · Nature · doi:10.1038/s41586-021-03318-4 · Cited by 547 · cited 5×
“As a first step toward execution of QAOA for the LABS problem, we implement QAOA on Quantinuum trapped-ion quantum processors (26, 27) on problems with up to N = 18.”
BackgroundMethodInfluentialSelf-citationt|ket⟩: a retargetable compiler for NISQ devices
Sivarajah, S., Dilkes, S., Cowtan, A., Simmons, W., Edgington, A., & Duncan, R. (2021) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8e92 · Cited by 475
A Race-Track Trapped-Ion Quantum Processor
Moses, S. A., Baldwin, C. H., Allman, M. S., Ancona, R., Ascarrunz, L., Barnes, C., Bartolotta, J., Bjork, B., Blanchard, P., Bohn, M., et al. (2023) · Physical Review X · doi:10.1103/physrevx.13.041052 · Cited by 391 · cited 6×
“As a first step toward execution of QAOA for the LABS problem, we implement QAOA on Quantinuum trapped-ion quantum processors (26, 27) on problems with up to N = 18.”
BackgroundMethodInfluentialSelf-citationA Quantum Algorithm for Finding the Minimum
Durr, C., & Hoyer, P. (1996) · arXiv · doi:10.48550/arxiv.quant-ph/9607014 · Cited by 359
Quantum approximate optimization algorithm for MaxCut: A fermionic view
Wang, Z., Hadfield, S., Jiang, Z., & Rieffel, E. G. (2018) · Physical Review A · doi:10.1103/physreva.97.022304 · Cited by 353
Obstacles to State Preparation and Variational Optimization from Symmetry Protection
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2019) · arXiv · doi:10.48550/arxiv.1910.08980 · Cited by 279
Obstacles to Variational Quantum Optimization from Symmetry Protection
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.260505 · Cited by 278 · cited 1×
“Due to QAOA preserving the D 4 symmetry of the problem (80), this is a highly entangled state, which is hard to prepare (81).”
BackgroundImproving Variational Quantum Optimization using CVaR
Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I., & Woerner, S. (2020) · Quantum · doi:10.22331/q-2020-04-20-256 · Cited by 263 · cited 1×
“(78 and 79), though the difference observed between the two figures of merit is more drastic in our case due to the hardness of the problem considered.”
BackgroundSieves for low autocorrelation binary sequences
Golay, M. (1977) · IEEE Transactions on Information Theory · doi:10.1109/tit.1977.1055653 · Cited by 225 · cited 3×
“(14) In LABS, the energy E sidelobe ( s ) grows as N 2 , so γ ∗ decreases as 1 N .”
MethodQuantum SDP-Solvers: Better upper and lower bounds
van Apeldoorn, J., Gilyén, A., Gribling, S., & de Wolf, R. (2020) · Quantum · doi:10.22331/q-2020-02-14-230 · Cited by 225 · cited 5×
“Implementation of the phase operator is especially challenging for currently available quantum processors.”
BackgroundMethodInfluentialThe merit factor of long low autocorrelation binary sequences (Corresp.)
Golay, M. (1982) · IEEE Transactions on Information Theory · doi:10.1109/tit.1982.1056505 · Cited by 195
Unified Matrix Treatment of the Fast Walsh-Hadamard Transform
Fino, & Algazi (1976) · IEEE Transactions on Computers · doi:10.1109/tc.1976.1674569 · Cited by 193 · cited 1×
“The grouping in the mixing operator depends on index i of the operator x i analogous to the grouping in the fast Walsh–Hadamard transform (49).”
MethodLow autocorrelation binary sequences : statistical mechanics and configuration space analysis
Bernasconi, J. (1987) · Journal de Physique · doi:10.1051/jphys:01987004804055900 · Cited by 188 · cited 2×
“We study the scaling of QAOA TTS with the problem size on the Low Autocorrelation Binary Sequences (LABS) problem (15, 16), also known as the Bernasconi model in statistical physics (17, 18).”
BackgroundMethodParameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
Shaydulin, R., Lotshaw, P. C., Larson, J. M., Ostrowski, J., & Humble, T. S. (2023) · ACM Transactions on Quantum Computing · doi:10.1145/3584706 · Cited by 179
Self-citationQuantum Simulations of Classical Annealing Processes
Somma, R. D., Boixo, S., Barnum, H., & Knill, E. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.130504 · Cited by 173 · cited 2×
“We find that the TTS of QAOA with number of layers p = 12 grows as 1 .”
BackgroundBinary sequences up to length 40 with best possible autocorrelation function
Lindner, J. (1975) · Electronics Letters · doi:10.1049/el:19750391 · Cited by 166
Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
Crooks, G. E. (2018) · arXiv · doi:10.48550/arxiv.1811.08419 · Cited by 158
Quantum walk speedup of backtracking algorithms
Montanaro, A. (2018) · Theory of Computing · doi:10.4086/toc.2018.v014a015 · Cited by 154
Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage
Babbush, R., McClean, J. R., Newman, M., Gidney, C., Boixo, S., & Neven, H. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.010103 · Cited by 148
Quantum annealing initialization of the quantum approximate optimization algorithm
Sack, S. H., & Serbyn, M. (2021) · Quantum · doi:10.22331/q-2021-07-01-491 · Cited by 146
Binary pulse compression codes
Boehmer, A. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1053969 · Cited by 136 · cited 2×
“We study the scaling of QAOA TTS with the problem size on the Low Autocorrelation Binary Sequences (LABS) problem (15, 16), also known as the Bernasconi model in statistical physics (17, 18).”
MethodWocjan, P., & Abeyesinghe, A. (2008) · Physical Review A · doi:10.1103/physreva.78.042336 · Cited by 128 · cited 1×
“These include amplitude amplification (1), quantum walks (2–4) and quantum Markov Chain algorithms (5, 6), as well as the recently introduced short path algorithm (7, 8).”
BackgroundTraining the quantum approximate optimization algorithm without access to a quantum processing unit
Streif, M., & Leib, M. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8c2b · Cited by 125
Hogg, T., & Portnov, D. (2000) · Information Sciences · doi:10.1016/s0020-0255(00)00052-9 · Cited by 111 · cited 2×
“A leading candidate for demonstrating a heuristic speedup in quantum optimization is the quantum approximate optimization algorithm (QAOA) (9, 10).”
BackgroundMethodMultistart Methods for Quantum Approximate optimization
Shaydulin, R., Safro, I., & Larson, J. (2019) · 2019 IEEE High Performance Extreme Computing Conference (HPEC) · doi:10.1109/hpec.2019.8916288 · Cited by 110
Self-citationClassical symmetries and the Quantum Approximate Optimization Algorithm
Shaydulin, R., Hadfield, S., Hogg, T., & Safro, I. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03298-4 · Cited by 109 · cited 1×
“Due to QAOA preserving the D 4 symmetry of the problem (80), this is a highly entangled state, which is hard to prepare (81).”
BackgroundSelf-citationCompilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
Sanders, Y. R., Berry, D. W., Costa, P. C. S., Tessler, L. W., Wiebe, N., Gidney, C., Neven, H., & Babbush, R. (2020) · PRX Quantum · doi:10.1103/prxquantum.1.020312 · Cited by 103 · cited 2×
“(13) rig-orously shows that, for random k -SAT, the runtime of constant-depth QAOA grows exponentially with N at any fixed p , with the scaling exponent depending on p .”
BackgroundA class of finite binary sequences with alternate auto-correlation values equal to zero (Corresp.)
Golay, M. (1972) · IEEE Transactions on Information Theory · doi:10.1109/tit.1972.1054797 · Cited by 98
Quantum optimization with a novel Gibbs objective function and ansatz architecture search
Li, L., Fan, M., Coram, M., Riley, P., & Leichenauer, S. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.023074 · Cited by 98 · cited 1×
“(78 and 79), though the difference observed between the two figures of merit is more drastic in our case due to the hardness of the problem considered.”
BackgroundClassical and quantum bounded depth approximation algorithms
Hastings, M. B. (2019) · quantum Information and Computation · doi:10.26421/qic19.13-14-3 · Cited by 96 · cited 1×
“For example, this is the setting used in recent results ruling out quantum advantage in approximation with log-depth local quantum algorithms like QAOA (67–69).”
MethodExhaustive search for low-autocorrelation binary sequences
Mertens, S. (1996) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/29/18/005 · Cited by 91
Demonstration of the trapped-ion quantum CCD computer architecture
Pino, J. M., Dreiling, J., Figgatt, C., Gaebler, J., Moses, S. A., Allman, M. S., Baldwin, C. H., Foss‐Feig, M., Hayes, D., Mayer, K., et al. (2021) · RePEc: Research Papers in Economics · Cited by 87
Self-citationBasso, J., Gamarnik, D., Mei, S., & Zhou, L. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00039 · Cited by 79 · cited 2×
“(42) Even in the regime where the expected solution quality of QAOA is bounded, it can be still useful as a tool to obtain a high probability of measuring the exact optimal solution.”
MethodEfficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
Lemieux, J., Heim, B., Poulin, D., Svore, K. M., & Troyer, M. (2020) · Quantum · doi:10.22331/q-2020-06-29-287 · Cited by 77 · cited 1×
“In particular, it may be possible to quadratically accelerate the best-known classical heuristic (Memetic Tabu (23)) by applying ideas similar to those used in quantum simulated annealing (5, 24, 25).”
MethodLow autocorrelation binary sequences
Packebusch, T., & Mertens, S. (2016) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8113/49/16/165001 · Cited by 64 · cited 7×
“Second, the performance of classical solvers for LABS has been benchmarked (20, 21) in terms of the scaling of their TTS with problem size.”
BackgroundMethodInfluentialFinding low autocorrelation binary sequences with memetic algorithms
Gallardo, J. E., Cotta, C., & Fernández, A. J. (2009) · Applied Soft Computing · doi:10.1016/j.asoc.2009.03.005 · Cited by 59 · cited 3×
“In particular, it may be possible to quadratically accelerate the best-known classical heuristic (Memetic Tabu (23)) by applying ideas similar to those used in quantum simulated annealing (5, 24, 25).”
MethodEmpirical performance bounds for quantum approximate optimization
Lotshaw, P. C., Humble, T. S., Herrman, R., Ostrowski, J., & Siopsis, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03342-3 · Cited by 59 · cited 1×
“(76, 77) Similar observations have been made in Refs.”
ResultConstrained quantum optimization for extractive summarization on a trapped-ion quantum computer
Niroula, P., Shaydulin, R., Yalovetzky, R., Minssen, P., Herman, D., Hu, S., & Pistoia, M. (2022) · Scientific Reports · doi:10.1038/s41598-022-20853-w · Cited by 59 · cited 1×
“( 34– 38) In this work we execute QAOA circuits with p = 1 using parameters β , γ optimized in noiseless simulation, followed by a projective measurement in the computational basis.”
MethodSelf-citationA new search for skewsymmetric binary sequences with optimal merit factors
Golay, M. J. E., & Harris, D. B. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.57219 · Cited by 56
Boulebnane, S., & Montanaro, A. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.10685 · Cited by 56
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.01041 · Cited by 54 · cited 2×
“While QAOA has been studied extensively (11–14), little is known about its potential to provide a scaling advantage over classical solvers.”
BackgroundEvaluation of QAOA based on the approximation ratio of individual samples
Larkin, J. M., Jonsson, M., Justice, D., & Guerreschi, G. G. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac6973 · Cited by 54 · cited 1×
“(76, 77) Similar observations have been made in Refs.”
ResultQuantum speedup of branch-and-bound algorithms
Montanaro, A. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.013056 · Cited by 53
Alignment between initial state and mixer improves QAOA performance for constrained optimization
He, Z., Shaydulin, R., Chakrabarti, S., Herman, D., Li, C., Sun, Y., & Pistoia, M. (2023) · npj Quantum Information · doi:10.1038/s41534-023-00787-5 · Cited by 48 · cited 1×
“While our numerical evidence is only obtained by fitting instances with N ≤ 40, there are three observations that make us optimistic the observed scaling will hold for larger N .”
MethodSelf-citationQuantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
Pelofske, E., Bärtschi, A., & Eidenbenz, S. (2023) · Lecture Notes in Computer Science · doi:10.1007/978-3-031-32041-5_13 · Cited by 47
Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
Lee, X., Saito, Y., Cai, D., & Asai, N. (2021) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce52317.2021.00016 · Cited by 46
Parameter Setting in Quantum Approximate Optimization of Weighted Problems
Sureshbabu, S. H., Herman, D., Shaydulin, R., Basso, J., Chakrabarti, S., Sun, Y., & Pistoia, M. (2024) · Quantum · doi:10.22331/q-2024-01-18-1231 · Cited by 41 · cited 1×
“While QAOA has been studied extensively (11–14), little is known about its potential to provide a scaling advantage over classical solvers.”
BackgroundSelf-citationBrest, J., & Boškovič, B. (2018) · IEEE Access · doi:10.1109/access.2018.2789916 · Cited by 40
Circuit depth scaling for quantum approximate optimization
Akshay, V., Philathong, H., Campos, E., Rabinovich, D., Zacharov, I., Zhang, X., & Biamonte, J. (2022) · Physical Review A · doi:10.1103/physreva.106.042438 · Cited by 38
Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End
Dalzell, A. M., Pancotti, N., Campbell, E. T., & Brandão, F. G. S. L. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585203 · Cited by 37 · cited 1×
“These include amplitude amplification (1), quantum walks (2–4) and quantum Markov Chain algorithms (5, 6), as well as the recently introduced short path algorithm (7, 8).”
BackgroundUniversal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search AlgorithmsPreprint
Chakrabarti, S., Minssen, P., Yalovetzky, R., & Pistoia, M. (2022) · RePEc: Research Papers in Economics · doi:10.48550/arxiv.2210.03210 · Cited by 37
Self-citationAdvances in the merit factor problem for binary sequences
Jedwab, J., Katz, D. J., & Schmidt, K.-U. (2013) · Journal of Combinatorial Theory, Series A · doi:10.1016/j.jcta.2013.01.010 · Cited by 36 · cited 1×
“We observe that as N grows, QAOA at p = 100 achieves an expected merit factor ⟨ C ⟩ MF of less than 5. we Note that explicit analytical sequences achieving merit factor > 6 are known (53).”
BackgroundExtended flag gadgets for low-overhead circuit verification
Debroy, D. M., & Brown, K. R. (2020) · Physical Review A · doi:10.1103/physreva.102.052409 · Cited by 36 · cited 1×
“Instead, we study a general quantum optimization heuristic with broad applicability (namely, QAOA) and make no specific modifications to adapt it to the LABS problem.”
BackgroundA Short Path Quantum Algorithm for Exact Optimization
Hastings, M. B. (2018) · Quantum · doi:10.22331/q-2018-07-26-78 · Cited by 35 · cited 1×
“These include amplitude amplification (1), quantum walks (2–4) and quantum Markov Chain algorithms (5, 6), as well as the recently introduced short path algorithm (7, 8).”
BackgroundApproximate Boltzmann distributions in quantum approximate optimization
Lotshaw, P. C., Siopsis, G., Ostrowski, J., Herrman, R., Alam, R., Powers, S., & Humble, T. S. (2023) · Physical Review A · doi:10.1103/physreva.108.042411 · Cited by 35
On the ground states of the Bernasconi model
Mertens, S., & Bessenrodt, C. (1998) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/31/16/004 · Cited by 33 · cited 1×
“We study the scaling of QAOA TTS with the problem size on the Low Autocorrelation Binary Sequences (LABS) problem (15, 16), also known as the Bernasconi model in statistical physics (17, 18).”
MethodPeptide conformational sampling using the Quantum Approximate Optimization Algorithm
Boulebnane, S., Lucas, X., Meyder, A., Adaszewski, S., & Montanaro, A. (2023) · npj Quantum Information · doi:10.1038/s41534-023-00733-5 · Cited by 32
Bošković, B., Brglez, F., & Brest, J. (2017) · Applied Soft Computing · doi:10.1016/j.asoc.2017.02.024 · Cited by 31 · cited 2×
“34 N (30).”
Protecting expressive circuits with a quantum error detection code
Self, C. N., Benedetti, M., & Amaro, D. (2024) · Nature Physics · doi:10.1038/s41567-023-02282-2 · Cited by 31
Landscape statistics of the low-autocorrelation binary string problem
Ferreira, F. F., Fontanari, J. F., & Stadler, P. F. (2000) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/33/48/304 · Cited by 30 · cited 1×
“(17, 55) and plain evolutionary algorithms (66) fail to obtain good solutions.”
BackgroundFast quantum methods for optimization
Boixo, S., Ortíz, G., & Somma, R. D. (2015) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2015-02341-5 · Cited by 29 · cited 1×
“In particular, it may be possible to quadratically accelerate the best-known classical heuristic (Memetic Tabu (23)) by applying ideas similar to those used in quantum simulated annealing (5, 24, 25).”
MethodFast Simulation of High-Depth QAOA Circuits
Lykov, D., Shaydulin, R., Sun, Y., Alexeev, Y., & Pistoia, M. (2023) · Proceedings of the SC '23 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis · doi:10.1145/3624062.3624216 · Cited by 27 · cited 3×
“Our results are enabled by a custom algorithm-specific GPU simulator (22), which we execute using up to 1,024 GPUs per simulation on the Polaris supercomputer accessed through the Argonne Leadership Computing Facility.”
MethodInfluentialSelf-citationQuantum error mitigation by Pauli check sandwiching
Gonzales, A., Shaydulin, R., Saleem, Z. H., & Suchara, M. (2023) · Scientific Reports · doi:10.1038/s41598-023-28109-x · Cited by 26 · cited 3×
“(28), which uses pairs of parity checks to detect some but not necessarily all errors that occur in a given part of the circuit.”
BackgroundMethodInfluentialSelf-citationA Note on Low Autocorrelation Binary Sequences
Dotú, I., & Hentenryck, P. V. (2006) · Lecture notes in computer science · doi:10.1007/11889205_51 · Cited by 25
Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
Shaydulin, R., & Galda, A. (2021) · 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce52317.2021.00046 · Cited by 24 · cited 1×
“In particular, the overheads of fault-tolerance (43) must be substantially reduced to realize the quantum speedup.”
BackgroundSelf-citationA memetic algorithm for the low autocorrelation binary sequence problem
Gallardo, J. E., Cotta, C., & Fernández, A. J. (2007) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/1276958.1277195 · Cited by 22
Characterizing Error Mitigation by Symmetry Verification in QAOA
Kakkar, A., Larson, J. M., Galda, A., & Shaydulin, R. (2022) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce53715.2022.00086 · Cited by 20 · cited 1×
“In particular, the overheads of fault-tolerance (43) must be substantially reduced to realize the quantum speedup.”
BackgroundSelf-citationImproved Branch-and-Bound for Low Autocorrelation Binary SequencesPreprint
Prestwich, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.6187 · Cited by 18
High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
Pelofske, E., Bärtschi, A., Golden, J., & Eidenbenz, S. (2023) · 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00064 · Cited by 15
Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond
Chou, C.-N., Love, P. J., Sandhu, J. S., & Shi, J. (2021) · arXiv · doi:10.48550/arxiv.2108.06049 · Cited by 13
Low Autocorrelation Binary Sequences: Best-Known Peak Sidelobe Level Values
Brest, J., & Boškovič, B. (2021) · IEEE Access · doi:10.1109/access.2021.3077541 · Cited by 12
Low-depth Circuit Implementation of Parity Constraints for Quantum OptimizationPreprint
Unger, J., Messinger, A., Niehoff, B. E., FELLNER, M. J., & Lechner, W. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2211.11287 · Cited by 12
On the Generation of Long Binary Sequences With Record-Breaking PSL Values
Dimitrov, M., Baitcheva, T., & Nikolov, N. (2020) · IEEE Signal Processing Letters · doi:10.1109/lsp.2020.3031463 · Cited by 11
FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot NodesPreprint
Ayanzadeh, R., Alavisamani, N., Das, P., & Qureshi, M. K. (2022) · Research Square · doi:10.21203/rs.3.rs-2252963/v1 · Cited by 6
Iterative-Free Quantum Approximate Optimization Algorithm Using Neural NetworksPreprint
Amosy, O., Danzig, T., Porat, E., et al. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2208.09888 · Cited by 6
A Mixed Integer Quadratic Programming Model for the Low Autocorrelation Binary Sequence Problem
Kratica, J. (2013) · Serdica Journal of Computing · doi:10.55630/sjc.2012.6.385-400 · Cited by 5
Data from "QAOA with N · p ≥ 200"Preprint
Shaydulin, R., & Pistoia, M. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2303.02064 · Cited by 3
Self-citation(1998) · doi:10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p
Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs
Chen, A., Huang, N., & Marwaha, K. (2023) · arXiv · doi:10.48550/arxiv.2310.01563
Protecting Expressive Circuits with a Quantum Error Detection Code
Self, C. N., Benedetti, M., & Amaro, D. (2022) · arXiv · doi:10.48550/arxiv.2211.06703
Two-phase Optimization of Binary Sequences with Low Peak Sidelobe Level Value
Bošković, B., & Brest, J. (2021) · arXiv · doi:10.48550/arxiv.2107.09801
Research works printed but not linked: 3
- 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.
- 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).
- 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
Challenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201
“Still, combining Grover Search with other quantum or classical algorithms can lead to an overall quadratic speedup in specific cases 209 .”
Alexeev, Y., Amsler, M., Barroca, M. A., Bassini, S., Battelle, T., Camps, D., Casanova, D., Choi, Y. J., Chong, F. T., Chung, C., et al. (2024) · Future Generation Computer Systems · doi:10.1016/j.future.2024.04.060 · Cited by 191
Self-citationQuantum Optimization: Potential, Challenges, and the Path Forward
Abbas, A., (NNSA), U. N. N. S. A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D., et al. (2023) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/2229681 · Cited by 67
Constrained optimization via quantum Zeno dynamics
Herman, D., Shaydulin, R., Sun, Y., Chakrabarti, S., Hu, S., Minssen, P., Rattew, A. G., Yalovetzky, R., & Pistoia, M. (2023) · Communications Physics · doi:10.1038/s42005-023-01331-9 · Cited by 75
“While these algorithms are often discussed as promising approaches for noisy near-term devices [5, 6], many results supporting their potential are analytically derived or numerically demonstrated in the fault-tolerant regime [7–9].”
BackgroundSelf-citationQuantum-enhanced greedy combinatorial optimization solver
Dupont, M., Evert, B., Hodson, M. J., Sundar, B., Jeffrey, S., Yamaguchi, Y., Feng, D., Maciejewski, F. B., Hadfield, S., Alam, M. S., et al. (2023) · Science Advances · doi:10.1126/sciadv.adi0487 · Cited by 77
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
- ORCID
- Shaydulin, Ruslan
- Li, Changhao
- Chakrabarti, Shouvanik
- DeCross, Matthew
- Herman, Dylan
- Kumar, Niraj
- Larson, Jeffrey
- Lykov, Danylo
- Minssen, Pierre
- Sun, Yue
- Alexeev, Yuri
- Dreiling, Joan M.
- Gaebler, John P.
- Gatterman, Thomas M.
- Gerber, Justin A.
- Gilmore, Kevin
- Hewitt, Nathan
- Horst, Chandler V.
- Hu, Shaohan
- Matheny, Mitchell
- Mills, Michael
- Moses, Steven A.
- Neyenhuis, Brian
- Siegfried, Peter
- Yalovetzky, Romina
- Pistoia, Marco
- Venue
- Science Advances
- Published
- 2024-05-31
- Volume
- 10
- Issue
- 22
- Pages
- eadm6761-eadm6761
- ISSN
- 2375-2548 (ISSN-L)
- PMC
- PMC11135426
- 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
- gold
- doi.org
- 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.