Algorithms · QAOA
QAOA scaling on the low autocorrelation binary sequences (LABS) problem
Given the low autocorrelation binary sequences (LABS) problem, an optimization problem that is classically intractable even for moderately sized instances, determine whether QAOA can act as an algorithmic component that provides an advantage over the best classical exact solvers.
Attested & literatureUpdated
Open on the mapView frozen graph
A small worked example, computed in your browser. It is not a result from this record's papers.
QAOA, p=1, MaxCut on a 4-cycle
4 qubits on a 4-cycle (edges 0-1, 1-2, 2-3, 3-0), one QAOA layer with gamma=pi/8, beta=3*pi/8.
Step 1 of 2 · Hadamard layer(4)
Probability of each outcome after this step
- 00006%
- 00016%
- 00106%
- 00116%
- 01006%
- 01016%
- 01106%
- 01116%
- 8 more outcomes50%
Starts from the uniform superposition over all 16 possible cuts.
Probability spreads from 1 outcome to 16. All 16 are equally likely.
The cost layer (RZZ(2*gamma) on each of the 4 edges) rewards cuts that separate connected qubits, then the mixer (RX(2*beta) on every qubit) lets amplitude move between cuts.
Probability moves between the same 16 outcomes. Up: 0101 6.3% → 26.6%, 1010 6.3% → 26.6%. Down: 0001 6.3% → 1.6%. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
Readout 0101 and 1010 are the two optimal cuts of a 4-cycle (alternating around the ring); at these angles measuring the register returns one of them clearly more often than any other cut.
Open in Studio- Record typeLiterature reference
- Reference implementationlow_autocorrelation_binary_sequences_problem
- Reported costNot stated by the sources read
- Papers1
Given the low autocorrelation binary sequences (LABS) problem, an optimization problem that is classically intractable even for moderately sized instances, determine whether QAOA can act as an algorithmic component that provides an advantage over the best classical exact solvers. Shaydulin et al. investigate numerically whether QAOA can tackle classically intractable problems, an open question they say remains unclear despite QAOA's standing as a leading candidate algorithm for optimization on quantum computers. They target the low autocorrelation binary sequences (LABS) problem, which they describe as classically intractable even for moderately sized instances, and run noiseless simulations with up to 40 qubits. From those simulations they observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which they identify as the state-of-the-art exact solvers for LABS, and they report that combining QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem that they compare against. Beyond simulation, they report experimental progress executing QAOA for the LABS problem on Quantinuum trapped-ion processors, using an algorithm-specific error detection scheme. They summarize all of this as evidence for the utility of QAOA as an algorithmic component that enables quantum speedups, framing it as evidence rather than as a proof.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Shaydulin et al. investigate numerically whether QAOA can tackle classically intractable problems, an open question they say remains unclear despite QAOA's standing as a leading candidate algorithm for optimization on quantum computers. They target the low autocorrelation binary sequences (LABS) problem, which they describe as classically intractable even for moderately sized instances, and run noiseless simulations with up to 40 qubits. From those simulations they observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which they identify as the state-of-the-art exact solvers for LABS, and they report that combining QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem that they compare against. Beyond simulation, they report experimental progress executing QAOA for the LABS problem on Quantinuum trapped-ion processors, using an algorithm-specific error detection scheme. They summarize all of this as evidence for the utility of QAOA as an algorithmic component that enables quantum speedups, framing it as evidence rather than as a proof. The sources read state no complexity bound for this record (The abstract of arXiv:2308.02342, the only source read for this record, states no complexity expression, no big-O bound and no formula for how the runtime scales; its scaling claims are empirical observations from simulation. It states the task and its classical difficulty as: "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." Its central runtime claim is: "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." This is a comparison against a named state of the art, not a proven bound on either side, and the abstract names branch-and-bound solvers as that state of the art rather than stating their complexity. A second, related claim is that "The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem" — again an empirical scaling claim, not a formula, and "best" is relative to the algorithms compared, which the abstract does not enumerate. The abstract separately reports a hardware result: "We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors." It summarizes all of the above as "evidence for the utility of QAOA as an algorithmic component that enables quantum speedups" — evidence, in the abstract's own word, not a proof. No qubit-count formula, no big-O expression, and no constant factor is quoted anywhere in the abstract; the largest simulated size it states is up to 40 qubits. The demonstration this record covers states no complexity bound of its own. The field is left empty on purpose rather than filled with a bound written from memory.).
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Reference implementation
- low_autocorrelation_binary_sequences_problem
- Reported cost
- Not stated by the sources read
- Complexity basis
- The abstract of arXiv:2308.02342, the only source read for this record, states no complexity expression, no big-O bound and no formula for how the runtime scales; its scaling claims are empirical observations from simulation. It states the task and its classical difficulty as: "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." Its central runtime claim is: "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." This is a comparison against a named state of the art, not a proven bound on either side, and the abstract names branch-and-bound solvers as that state of the art rather than stating their complexity. A second, related claim is that "The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem" — again an empirical scaling claim, not a formula, and "best" is relative to the algorithms compared, which the abstract does not enumerate. The abstract separately reports a hardware result: "We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors." It summarizes all of the above as "evidence for the utility of QAOA as an algorithmic component that enables quantum speedups" — evidence, in the abstract's own word, not a proof. No qubit-count formula, no big-O expression, and no constant factor is quoted anywhere in the abstract; the largest simulated size it states is up to 40 qubits. The demonstration this record covers states no complexity bound of its own. The field is left empty on purpose rather than filled with a bound written from memory.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare QAOA with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: QAOA scaling on the low autocorrelation binary sequences (LABS) problem
PROBLEM: Given the low autocorrelation binary sequences (LABS) problem, an optimization problem that is classically intractable even for moderately sized instances, determine whether QAOA can act as an algorithmic component that provides an advantage over the best classical exact solvers.
IDEA: Shaydulin et al. investigate numerically whether QAOA can tackle classically intractable problems, an open question they say remains unclear despite QAOA's standing as a leading candidate algorithm for optimization on quantum computers. They target the low autocorrelation binary sequences (LABS) problem, which they describe as classically intractable even for moderately sized instances, and run noiseless simulations with up to 40 qubits. From those simulations they observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which they identify as the state-of-the-art exact solvers for LABS, and they report that combining QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem that they compare against. Beyond simulation, they report experimental progress executing QAOA for the LABS problem on Quantinuum trapped-ion processors, using an algorithm-specific error detection scheme. They summarize all of this as evidence for the utility of QAOA as an algorithmic component that enables quantum speedups, framing it as evidence rather than as a proof.
REPORTED COST: Not stated by the sources read
BASIS: The abstract of arXiv:2308.02342, the only source read for this record, states no complexity expression, no big-O bound and no formula for how the runtime scales; its scaling claims are empirical observations from simulation. It states the task and its classical difficulty as: "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." Its central runtime claim is: "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." This is a comparison against a named state of the art, not a proven bound on either side, and the abstract names branch-and-bound solvers as that state of the art rather than stating their complexity. A second, related claim is that "The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem" — again an empirical scaling claim, not a formula, and "best" is relative to the algorithms compared, which the abstract does not enumerate. The abstract separately reports a hardware result: "We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors." It summarizes all of the above as "evidence for the utility of QAOA as an algorithmic component that enables quantum speedups" — evidence, in the abstract's own word, not a proof. No qubit-count formula, no big-O expression, and no constant factor is quoted anywhere in the abstract; the largest simulated size it states is up to 40 qubits. The demonstration this record covers states no complexity bound of its own. The field is left empty on purpose rather than filled with a bound written from memory.
PRIMARY SOURCE: 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 (2023), Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem — https://arxiv.org/abs/2308.02342
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Where this sits
This record is named by the layer graph at:
- Alternate a cost unitary with a mixer, p times Method
Takes An Ising or QUBO operator, diagonal in the computational basis, whose extremal eigenvector encodes the problem's solution — given, for QAOA, as a sum of clause terms over bits and clauses; given, for adiabatic evolution, as the final Hamiltonian of an interpolation whose starting point has an easily-constructed ground state. Neither method is told how the operator was built, or by which encoding. Returns A bit string read off the computational basis — the assignment — together with the objective value it achieves, or, for the adiabatic route, the stated promise that this string is (with fidelity approaching 1, for a long enough evolution time) the true minimiser. Neither route returns an energy with an error bar; both return a string.
Related entries
- QAOA MaxCut on a 5-node ring
Algorithms
- Ising cost Hamiltonian
Operators
- Ising formulations of NP-complete and NP-hard problems
Algorithms
- Quantum simulated annealing
Algorithms
References
- 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 · 2023
Primary source: it runs noiseless simulations of QAOA with up to 40 qubits on the LABS problem, reports that fixed-parameter QAOA's runtime scales better than branch-and-bound solvers (the state-of-the-art exact LABS solvers), reports that combining QAOA with quantum minimum finding gives the best empirical scaling among the algorithms it compares, and reports experimental progress executing QAOA for LABS on Quantinuum trapped-ion processors with an algorithm-specific error detection scheme. Consult it for the scaling data itself, the sizes at which each comparison was measured, and the error detection scheme, none of which the abstract quotes numerically.