Solving Boolean Satisfiability Problems With The Quantum Approximate Optimization Algorithm
Open accessPublished version of a preprint
Abstract
One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers. The quantum approximate optimization algorithm (QAOA) is designed for near-term quantum computers, yet previous work has shown strong limitations on the ability of QAOA to outperform classical algorithms for optimization problems. Here we instead apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. We analytically characterize the average success probability of QAOA on a constraint satisfaction problem commonly studied using statistical physics methods: random k -SAT at the threshold for satisfiability, as the number of variables n goes to infinity. We complement these theoretical results with numerical experiments on the performance of QAOA for small n , which match the limiting theoretical bounds closely. We then compare QAOA with leading classical solvers. For random 8-SAT, we find that for more than 14 quantum circuit layers, QAOA achieves more efficient scaling than the highest-performance classical solver we tested, WalkSATlm. Our results suggest that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts. Published by the American Physical Society 2024
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
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 study adopts a fixed-parameter protocol to enhance the reliability of the scaling analysis.
“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 [11]
Data for different solvers are collected up to different maximum problem sizes and are truncated appropriately to mitigate finite-size effects.
“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 [11]
Cites
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · see citing works
Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales
Banach, S. (1922) · Fundamenta Mathematicae · doi:10.4064/fm-3-1-133-181 · Cited by 4,029 · see citing works
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 1,726 · see citing works
Improving 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 · see citing works
Farhi, E., Goldstone, J., Gutmann, S., & Zhou, L. (2022) · Quantum · doi:10.22331/q-2022-07-07-759 · Cited by 226 · see citing works
Threshold values of random K‐SAT from the cavity method
Mertens, S., Mézard, M., & Zecchina, R. (2005) · Random Structures and Algorithms · doi:10.1002/rsa.20090 · Cited by 210 · see citing works
Random k ‐SAT: Two Moments Suffice to Cross a Sharp Threshold
Achlioptas, D., & Moore, C. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539703434231 · Cited by 164 · see citing works
Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design
Luo, X.-Z., Liu, J.-G., Zhang, P., & Wang, L. (2020) · Quantum · doi:10.22331/q-2020-10-11-341 · Cited by 157 · see citing works
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 · see citing works
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 · see citing works
Applying quantum algorithms to constraint satisfaction problems
Campbell, E. T., Khurana, A., & Montanaro, A. (2019) · Quantum · doi:10.22331/q-2019-07-18-167 · Cited by 75 · see citing works
Self-citationHogg, T. (2000) · Physical Review A · doi:10.1103/physreva.61.052311 · Cited by 70 · see citing works
Applying quantum algorithms to constraint satisfaction problems
Campbell, E. T., Khurana, A., & Montanaro, A. (2018) · White Rose Research Online (University of Leeds, The University of Sheffield, University of York) · doi:10.48550/arxiv.1810.05582 · Cited by 57 · see citing works
Self-citationThe backtracking survey propagation algorithm for solving random K-SAT problems
Marino, R., Giorgio Parisi, A., & Ricci‐Tersenghi, F. (2016) · Nature Communications · doi:10.1038/ncomms12996 · Cited by 56 · see citing works
Jensen's inequality for medians
Merkle, M. J. (2004) · Statistics & Probability Letters · doi:10.1016/j.spl.2004.11.010 · Cited by 25 · see citing works
Improving WalkSAT By Effective Tie-Breaking and Efficient Implementation
Cai, S., Luo, C. W., & Su, K. (2014) · The Computer Journal · doi:10.1093/comjnl/bxu135 · Cited by 19 · see citing works
Random Constraint Satisfaction Problems
Coja‐Oghlan, A. (2009) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.9.4 · Cited by 8 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
A review on Quantum Approximate Optimization Algorithm and its variants
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 444 · see citing works
Barren plateaus in variational quantum computing
Larocca, M., Thanasilp, S., Wang, S., Sharma, K., Biamonte, J., Coles, P. J., Cincio, Ł., McClean, J. R., Holmes, Z., & Cerezo, M. (2025) · Nature Reviews Physics · doi:10.1038/s42254-025-00813-9 · Cited by 318 · see citing works
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 · see citing works
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 43 · see citing works
Montañez-Barrera, J. A., & Michielsen, K. (2025) · npj Quantum Information · doi:10.1038/s41534-025-01082-1 · Cited by 34 · see citing works
Basso, J., Gamarnik, D., Mei, S., & Zhou, L. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00039 · Cited by 24 · see citing works
Golden, J. K., Bärtschi, A., O’Malley, D., & Eidenbenz, S. (2023) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00063 · Cited by 31 · see citing works
Augmenting an electronic Ising machine to effectively solve boolean satisfiability
Sharma, A., Burns, M., Hahn, A., & Huang, M. C. Y. (2023) · Scientific Reports · doi:10.1038/s41598-023-49966-6 · Cited by 20 · see citing works
Maciejewski, F. B., Hadfield, S., Hall, B., Hodson, M. J., Dupont, M., Evert, B., Sud, J., Alam, M. S., Wang, Z., Jeffrey, S., et al. (2024) · Physical Review Applied · doi:10.1103/physrevapplied.22.044074 · Cited by 22 · see citing works
Bias-field digitized counterdiabatic quantum algorithm for higher-order binary optimization
Romero, S. V., Visuri, A.-M., Cadavid, A. G., Simen, A., Solano, E., & Hegade, N. N. (2025) · Communications Physics · doi:10.1038/s42005-025-02270-3 · Cited by 18 · see citing works
Variational quantum solutions to the Shortest Vector Problem
Albrecht, M. R., Prokop, M., Shen, Y., & Wallden, P. (2023) · Quantum · doi:10.22331/q-2023-03-02-933 · Cited by 16 · see citing works
Encoding-independent optimization problem formulation for quantum computing
Dominguez, F., Unger, J., Traube, M., Mant, B. P., Ertler, C., & Lechner, W. (2023) · Frontiers in Quantum Science and Technology · doi:10.3389/frqst.2023.1229471 · Cited by 15 · see citing works
Efficient qudit based scheme for photonic quantum computing
Karácsony, M., Oroszlány, L., & Zimborás, Z. (2024) · SciPost Physics Core · doi:10.21468/scipostphyscore.7.2.032 · Cited by 16 · see citing works
Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
Bakó, B., Glos, A., Salehi, Ö., & Zimborás, Z. (2025) · Quantum · doi:10.22331/q-2025-03-20-1663 · Cited by 15 · see citing works
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 · see citing works
Performance of quantum approximate optimization with quantum error detection
He, Z., Amaro, D., Shaydulin, R., & Pistoia, M. (2025) · Communications Physics · doi:10.1038/s42005-025-02136-8 · Cited by 15 · see citing works
Trainability Barriers in Low-Depth QAOA Landscapes
Rajakumar, J., Golden, J. K., Bärtschi, A., & Eidenbenz, S. (2024) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/3649153.3649204 · Cited by 11 · see citing works
Grand Challenge of Quantum Applications
Babbush, R., King, R., Boixo, S., Huggins, W. J., Khattar, T., Low, G. H., McClean, J. R., O’Brien, T. E., & Rubin, N. C. (2026) · PRX Quantum · doi:10.1103/6r9l-lynr · Cited by 13 · see citing works
Bias-field digitized counterdiabatic quantum optimization
Cadavid, A. G., Dalal, A., Simen, A., Solano, E., & Hegade, N. N. (2025) · Physical Review Research · doi:10.1103/physrevresearch.7.l022010 · Cited by 10 · see citing works
Cadavid, A. G., Montalban, I., Dalal, A., Solano, E., & Hegade, N. N. (2024) · Physical Review Applied · doi:10.1103/physrevapplied.22.054037 · Cited by 9 · see citing works
Quantum computing approach for multi-objective routing and spectrum assignment optimization
Bouchmal, O., Cimoli, B., Stabile, R., Olmos, J. J. V., Hernández-Chulde, C., Martínez, R., Casellas, R., & Monroy, I. T. (2025) · Journal of Optical Communications and Networking · doi:10.1364/jocn.552061 · Cited by 7 · see citing works
Verifiable Quantum Homomorphic Encryption
Li, Q., Wang, Y., Chen, L., & Li, L. (2025) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2025.3568057 · Cited by 5 · see citing works
Yang, M., Gao, F., Dai, W., Huang, D., Gao, Q. Z., & Shuang, F. (2024) · Advanced Quantum Technologies · doi:10.1002/qute.202400286 · Cited by 5 · see citing works
Müller, T., Singh, A., Wilhelm, F. K., & Bode, T. (2024) · arXiv · doi:10.48550/arxiv.2411.19388 · Cited by 5 · see citing works
Hierarchical Multigrid Ansatz for Variational Quantum Algorithms
Keller, C. M., Eidenbenz, S., Bärtschi, A., O’Malley, D., Golden, J. K., & Misra, S. (2024) · ISC High Performance (ISC) · doi:10.23919/isc.2024.10528934 · Cited by 5 · see citing works
Non-variational quantum random access optimization with alternating operator ansatz
He, Z., Raymond, R., Shaydulin, R., & Pistoia, M. (2025) · Scientific Reports · doi:10.1038/s41598-025-13543-w · Cited by 4 · see citing works
Hao, T., He, Z., Shaydulin, R., Larson, J. M., & Pistoia, M. (2025) · Physical Review Research · doi:10.1103/24gg-7p8z · Cited by 3 · see citing works
Benchasattabuse, N., Bärtschi, A., García-Pintos, L. P., Golden, J. K., Lemons, N., & Eidenbenz, S. (2025) · Physical Review A · doi:10.1103/physreva.111.062411 · Cited by 13 · see citing works
Implementing Homomorphic Encryption-Based Logic Locking in System-On-Chip Designs
Ziyang, Y., & Ikeda, M. (2025) · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · doi:10.1109/tvlsi.2025.3556241 · Cited by 2 · see citing works
Quantum-based and robust-enhanced ADMM for thermal-wind-storage coordinated optimization scheduling
Yang, M., Gao, F., Dai, W., Jiang, S., & Zhai, H. (2025) · Electric Power Systems Research · doi:10.1016/j.epsr.2025.112148 · Cited by 2 · see citing works
Dehn, V., Zaefferer, M., Hellstern, G., Jayadevan, K., Reiter, F., & Wellens, T. (2026) · Physical Review A · doi:10.1103/l5r4-zcqv · Cited by 2 · see citing works
Constraint-aware quantum optimization via Hamming weight operators
Hao, Y., Ding, Q., Yuan, X., & Wang, X. (2026) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-025-2895-4 · Cited by 2 · see citing works
CUAOA: A Novel CUDA-Accelerated Simulation Framework for the QAOA
Stein, J., Blenninger, J., Bucher, D., Eder, P. J., Çetiner, E., Zorn, M., & Linnhoff–Popien, C. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.10292 · Cited by 2 · see citing works
“…of many results about improved scaling performance of the QAOA for important optimization problems compared to classical state-of-the-art solvers [5]– [7], much scientific effort goes into achieving large scale numerical simulations to explore possible quantum advantages empirically [8]–[10].”
Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
Prokop, M., & Wallden, P. (2025) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2025.3620104 · Cited by 2 · see citing works
Pelofske, E., Rams, M. M., Bärtschi, A., Czarnik, P., Braccia, P., Cincio, Ł., & Eidenbenz, S. (2026) · Physical Review Research · doi:10.1103/p2lg-z4kn · Cited by 1 · see citing works
On the Potential of Quantum Computing in Classical Program Analysis
Guang, Y., Zanotta, P., Zhou, K., Chen, Y., & Ayanzadeh, R. (2025) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce65121.2025.00257 · Cited by 2 · see citing works
Quantum optimization with classical chaos
Gaye, M. A., Shehab, O., Titum, P., & Quiroz, G. (2026) · Quantum Science and Technology · doi:10.1088/2058-9565/ae59ad · Cited by 1 · see citing works
Space-efficient quantum solvers for Boolean satisfiability problems via structural reduction
Lu, Q., Wei, S., Zeng, J., Yang, W., Zheng, M., 常培杰, Ruan, D., Wang, Z., & Long, G. (2026) · Physical Review A · doi:10.1103/r3c5-4ldp · Cited by 1 · see citing works
Compressed sensing enhanced by a quantum approximate optimization algorithm
Chevalier, B., Roga, W., & Takeoka, M. (2024) · Physical Review A · doi:10.1103/physreva.110.062410 · Cited by 2 · see citing works
Variational Quantum Algorithm Landscape Reconstruction by Low-Rank Tensor Completion
Hao, T., He, Z., Shaydulin, R., Pistoia, M., & Tannu, S. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00139 · Cited by 2 · see citing works
“QAOA has been shown to provide an asymptotic algorithmic speedup on some problems [24, 25], motivating its study.”
Digitized counterdiabatic quantum optimization for bin packing problem
Xu, R., Romero, S. V., Tang, J., Ban, Y., & Chen, X. (2025) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-025-00402-w · Cited by 1 · see citing works
Anonymous, Kulikov, D. A., Bantysh, B. I., Bogdanov, Y. I., Fedorov, A. K., & Kiktenko, E. O. (2026) · Physical Review A · doi:10.1103/x32d-wx13 · Cited by 1 · see citing works
Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers
Lu, Q., Wei, S., Li, K., Gao, P., Yan, B., Zheng, M., Zhang, H., Zeng, J., & Long, G.-L. (2026) · Nature Computational Science · doi:10.1038/s43588-026-01007-8 · Cited by 1 · see citing works
Using deep learning to construct stochastic local search SAT solvers with performance bounds
Kramer, M. J., Boës, P., & Eisert, J. (2026) · Machine Learning Science and Technology · doi:10.1088/2632-2153/ae5b23
Report on scipost_202304_00012v1
Karácsony, M., Oroszlány, L., & Zimborás, Z. (2023) · SciPost Physics Core · doi:10.21468/scipost.report.7589
Bode, T., Ramesh, K., & Stollenwerk, T. (2025) · Physical Review A · doi:10.1103/physreva.111.032411
Agarwal, P., Ali, N., & Hillery, M. S. (2025) · International Journal of Quantum Information · doi:10.1142/s0219749925500248
iSwitch: QEC on Demand via In-Situ Encoding of Bare Qubits for Ion Trap Architectures
Yin, K., Fang, X., Chen, Z., Hayes, D., Kaur, E., Nejabati, R., Häffner, H., Campbell, W. C., Hudson, E. R., Palsberg, J., et al. (2026) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3779212.3790177
Hybrid PSO-GA Metaheuristic Optimization for Comprehensive Student Performance Enhancement
PhaniKumar, P. P. N. G., Jena, J. J., Srinadhraju, S., & Sagiraju, S. (2025) · F1000Research · doi:10.12688/f1000research.171008.1
Hao, Y. (2025) · 2025 5th International Conference on Electronic Information Engineering and Computer Technology (EIECT) · doi:10.1109/eiect68017.2025.11331653
Optimizing teacher evaluation with fuzzy metaheuristic algorithm
PhaniKumar, P. P. N. G., & Jena, J. J. (2026) · Engineering Research Express · doi:10.1088/2631-8695/ae3f79
Implementing low-performance-overhead logic locking in SoCs via homomorphic feedback
Ziyang, Y., & IKEDA, M. (2026) · IEICE Electronics Express · doi:10.1587/elex.23.20250738
Knowledge Graphs and Quantum Computing: First Blood
Tzitzikas, Y., & Kondylakis, H. (2026) · Lecture notes in computer science · doi:10.1007/978-981-95-5009-8_1
QAOA for Hard-to-solve Instances of Maximum Independent Set ProblemPreprint
Li, X., Hu, S., Liu, W., He, X., Wang, D., & Liu, Z. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.6669349
Two-point quantum approximate optimization algorithm gradients in the frequency domain
Song, Z., Zhang, W., Cao, J., Yi, X., & Wang, H. (2026) · Physical Review A · doi:10.1103/gwgf-vy53
Sharma, A. K., Boehme, C., & Kunkel, J. M. (2026) · ISC High Performance 2026 Research Paper Proceedings (41st International Conference) · doi:10.23919/isc.2026.11520475 · Cited by 1 · see citing works
Quantum scaling advantage using reduced search in an NP-complete problem
(2026) · Nature Computational Science · doi:10.1038/s43588-026-01033-6
- Authors
- Boulebnane, S., & Montanaro, A.
- Affiliations
- Phasecraft Ltd. (United Kingdom) (GB)
- Venue
- PRX Quantum
- Publisher
- American Physical Society (APS)
- Published
- 2024-09-10
- Volume
- 5
- Issue
- 3
- ISSN
- 2691-3399 (ISSN-L)
- OpenAlex
- W4402412287
- Cited by
- 57
- References
- 16
- Citations by year
- 2026: 17 · 2025: 21 · 2024: 11 · 2023: 7 · 2022: 1
- FWCI
- 7.23
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- Locations
- PRX Quantum (publishedVersion, cc-by)
- Bristol Research (University of Bristol) (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- arXiv (Cornell University)
- Funders
- European Research Council (817581)
- EPSRC Centre for Doctoral Training in Delivering Quantum Technologies (EP/S021582/1)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computer Networks and Communications › Constraint Satisfaction and Optimization
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum approximate optimization algorithm, Boolean satisfiability, random k-SAT, constraint satisfaction, satisfiability threshold, WalkSAT, quantum advantage
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.
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
