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.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
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 →
TakesAn 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 C(z)=∑α=1mCα(z) over n bits and m clauses; given, for adiabatic evolution, as the final Hamiltonian HP of an interpolation whose starting point HB has an easily-constructed ground state. Neither method is told how the operator was built, or by which encoding.ReturnsA bit string z 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.
How it works
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 Classiq library carries this subject under applications · optimization. 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 Classiq index entry this record covers, applications/optimization/low_autocorrelation_binary_sequences_problem, gives a directory path and a file list and states no bound. The field is left empty on purpose rather than filled with a bound written from memory.).
Implementation
Unsupported
low-autocorrelation-binary-sequences-problem.txt
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 Classiq index entry this record covers, applications/optimization/low_autocorrelation_binary_sequences_problem, gives a directory path and a file list and states no bound. The field is left empty on purpose rather than filled with a bound written from memory.
DEMONSTRATED BY: the Classiq library entry applications/optimization/low_autocorrelation_binary_sequences_problem
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.
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.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem2023 · 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
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.