Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

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

Published Jul 27, 2023• 0 citations
Publisher

Abstract

Data from the paper "Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem"
DOI
10.5281/zenodo.8190274

Related papers

Advances for Quantum-Inspired Optimization (abstract only)

Fred Glover, Gary A. Kochenberger

•Oct 1, 2022•0 citations

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

Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti +26 more

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.

arXiv:2308.02342•Science Advances•May 29, 2024•120 citations

Quantum approximate optimization algorithm: a review study and problems

Laith Abualigah, Saif AlNajdawi, Abiodun Motunrayo Ikotun +7 more

Elsevier eBooks•Jan 1, 2024•16 citations

Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers

Quanfeng Lu, Shijie Wei, Keren Li +6 more

Achieving quantum advantage remains a milestone in the noisy intermediate-scale quantum era. Without complexity proofs, scaling advantage—where quantum resource requirements grow more slowly than their classical counterparts—is the primary indicator. However, direct applications of quantum optimization algorithms to classically intractable problems have yet to demonstrate this advantage. Here we develop enhanced quantum solvers for the NP-complete one-in-three Boolean satisfiability problem. We propose a restricting space reduction algorithm that achieves optimal search-space dimensionality under mod-2 arithmetic, thereby reducing qubit requirements and time complexity. Numerical studies on instances with up to 70 variables demonstrate that our enhanced quantum approximate optimization algorithm- and quantum adiabatic algorithm-based solvers outperform state-of-the-art classical solvers; the quantum adiabatic algorithm-based solver serves as a lower-bound reference while retaining scaling advantage. Furthermore, experiments on a 13-qubit superconducting processor confirm the predicted improvements. Collectively, our results provide empirical evidence of quantum speedup for an NP-complete problem. This study develops enhanced quantum solvers for an NP-complete Boolean satisfiability problem and reports empirical scaling advantages over leading classical solvers in large-scale simulations, with supporting validation on a superconducting quantum processor.

arXiv:2508.08869•Nature Computational Science•Jun 19, 2026•1 citation

$κ$-Parametrized Boltzmann Distribution Sampling on Quantum Approximate Optimization Algorithm

João Marcos Cavalcanti de Albuquerque Neto, Gustavo Castro do Amaral, Guilherme Penello Temporão

Generative models use training data to produce new samples that resemble the original, with applications in classification and recommendation systems. Restricted Boltzmann Machines (RBMs) are at the core of generative models but suffer from the computational intractability of training, which relies on sampling an unknown Boltzmann Distribution (BD). The Quantum Approximate Optimization Algorithm (QAOA) can assist RBM training, potentially providing benefits over strictly classical strategies. One particular problem is determining the quantum circuit depth for an arbitrary problem size that yields the expected sampling results. In this study, we evaluate QAOA-assisted sampling of BDs using Qiskit's Aer Simulator by analysing the inverse effective temperature of the distribution, $κ$, for tractable problem sizes. The results provide numerical evidence, based on Qiskit Aer simulations, that parameterized annealing-scheduled QAOA (PAQ-QAOA) can approximate RBM Boltzmann sampling for the tractable instances considered, while hardware performance and scaling remain open questions.

quant-pharXiv:2610.35665•Oct 27, 2026•0 citations

The computational power of quantum approximate optimization algorithms

Ryan Maamer

info:eu-repo/semantics/nonPublished

•Jan 1, 2022•0 citations
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.
Achieving quantum advantage remains a milestone in the noisy intermediate-scale quantum era. Without complexity proofs, scaling advantage—where quantum resource requirements grow more slowly than their classical counterparts—is the primary indicator. However, direct applications of quantum optimization algorithms to classically intractable problems have yet to demonstrate this advantage. Here we develop enhanced quantum solvers for the NP-complete one-in-three Boolean satisfiability problem. We propose a restricting space reduction algorithm that achieves optimal search-space dimensionality under mod-2 arithmetic, thereby reducing qubit requirements and time complexity. Numerical studies on instances with up to 70 variables demonstrate that our enhanced quantum approximate optimization algorithm- and quantum adiabatic algorithm-based solvers outperform state-of-the-art classical solvers; the quantum adiabatic algorithm-based solver serves as a lower-bound reference while retaining scaling advantage. Furthermore, experiments on a 13-qubit superconducting processor confirm the predicted improvements. Collectively, our results provide empirical evidence of quantum speedup for an NP-complete problem. This study develops enhanced quantum solvers for an NP-complete Boolean satisfiability problem and reports empirical scaling advantages over leading classical solvers in large-scale simulations, with supporting validation on a superconducting quantum processor.
κκκ-Parametrized Boltzmann Distribution Sampling on Quantum Approximate Optimization Algorithm
Generative models use training data to produce new samples that resemble the original, with applications in classification and recommendation systems. Restricted Boltzmann Machines (RBMs) are at the core of generative models but suffer from the computational intractability of training, which relies on sampling an unknown Boltzmann Distribution (BD). The Quantum Approximate Optimization Algorithm (QAOA) can assist RBM training, potentially providing benefits over strictly classical strategies. One particular problem is determining the quantum circuit depth for an arbitrary problem size that yields the expected sampling results. In this study, we evaluate QAOA-assisted sampling of BDs using Qiskit's Aer Simulator by analysing the inverse effective temperature of the distribution, κκκ, for tractable problem sizes. The results provide numerical evidence, based on Qiskit Aer simulations, that parameterized annealing-scheduled QAOA (PAQ-QAOA) can approximate RBM Boltzmann sampling for the tractable instances considered, while hardware performance and scaling remain open questions.