The Quantum Alternating Operator Ansatz for Satisfiability Problems
Open accessAbstract
We comparatively study, through large-scale numerical simulation, the performance across a large set of Quantum Alternating Operator Ansatz (QAOA) implementations for finding approximate and optimum solutions to unconstrained combinatorial optimization problems. Our survey includes over 100 different mixing unitaries, and we combine each mixer with both the standard phase separator unitary representing the objective function and a thresholded version. Our numerical tests for randomly chosen instances of the unconstrained optimization problems Max 2-SAT and Max 3-SAT reveal that the traditional transverse-field mixer with the standard phase separator performs best for problem sizes of 8 through 14 variables, while the recently introduced Grover mixer with thresholding wins at problems of size 6. This result (i) corrects earlier work suggesting that the Grover mixer is a superior mixer based only on results from problems of size 6, thus illustrating the need to push numerical simulation to larger problem sizes to more accurately predict performance; and (ii) it suggests that more complicated mixers and phase separators may not improve QAOA performance.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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?
A clause density of 4 is right at the start of the plateau of 3-SAT problems being hard.
“We chose a clause density of 4 based on ref. [23], which shows that a clause density of 4 is right at the start of the plateau of the 3-SAT problems being hard, which makes the problems hard in general to solve exactly and minimizes the number of circuit operations.”
From High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices (2023) · cites this paper as [23]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789 · cited 5× · see citing works
“Combinatorial optimization is widely viewed to be a promising application domain for quantum computing, and the Quantum Approximate Optimization Algorithm [5] and its generalization the Quantum Alternate Operator Ansatz [9] – both abbreviated as QAOA – are the most prominent algorithms for this application.”
BackgroundMethodInfluentialFrom the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772 · cited 2× · see citing works
“Combinatorial optimization is widely viewed to be a promising application domain for quantum computing, and the Quantum Approximate Optimization Algorithm [5] and its generalization the Quantum Alternate Operator Ansatz [9] – both abbreviated as QAOA – are the most prominent algorithms for this application.”
BackgroundWarm-starting quantum optimization
Egger, D. J., Mareček, J., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-06-17-479 · Cited by 269 · cited 1× · see citing works
“Recent work has argued in favor of using classical algorithms to generate initial states which are weighted in favor of likely good solutions [6, 7], and the effect of this”
MethodReachability Deficits in Quantum Approximate Optimization
Akshay, V., Philathong, H., Morales, M. E. S., & Biamonte, J. D. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.090504 · Cited by 151 · cited 9× · see citing works
“This metric is important in the context of [1], as their “reachability deficits” are defined in relation to this goal.”
BackgroundMethodResultInfluentialGrover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
Bartschi, A., & Eidenbenz, S. (2020) · 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00020 · Cited by 122 · see citing works
Self-citationCounterdiabaticity and the quantum approximate optimization algorithm
Wurtz, J., & Love, P. J. (2022) · Quantum · doi:10.22331/q-2022-01-27-635 · Cited by 103 · cited 1× · see citing works
“Many different techniques exist for determining the angles β and γ, including fixed angles [9], interpolation [10, 11], and unsupervised learning [12].”
MethodThe Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
Cook, J., Eidenbenz, S., & Bärtschi, A. (2020) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00021 · Cited by 74 · cited 1× · see citing works
“Many different techniques exist for determining the angles β and γ, including fixed angles [9], interpolation [10, 11], and unsupervised learning [12].”
Self-citationBridging Classical and Quantum with SDP initialized warm-starts for QAOA
Tate, R., Farhadi, M., Herold, C. D., Mohler, G., & Gupta, S. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3549554 · Cited by 64 · cited 1× · see citing works
“Recent work has argued in favor of using classical algorithms to generate initial states which are weighted in favor of likely good solutions [6, 7], and the effect of this”
MethodPhase Transitions and Backbones of 3-SAT and Maximum 3-SAT
Zhang, W. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45578-7_11 · Cited by 62 · cited 1× · see citing works
“The computational resources necessary to solve this problem are known to depend on the clause density, α = m/n, for both classical [13] and quantum [3] solvers.”
BackgroundMoussa, C., Wang, H., Bäck, T., & Dunjko, V. (2022) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-022-00131-4 · Cited by 46 · cited 1× · see citing works
“Many different techniques exist for determining the angles β and γ, including fixed angles [9], interpolation [10, 11], and unsupervised learning [12].”
MethodThreshold-Based Quantum Optimization
Golden, J. K., Bärtschi, A., O’Malley, D., & Eidenbenz, S. (2021) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce52317.2021.00030 · Cited by 27 · cited 1× · see citing works
“We study the traditional objective-value phase separator [5], H P = H C , as well as the threshold-based phase separator [7], , where t is a user-defined threshold and θ ( x ) is the Heaviside step function.”
Self-citationThe fixed angle conjecture for QAOA on regular MaxCut graphsPreprint
Wurtz, J., & Lykov, D. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.00677 · Cited by 4 · cited 1× · see citing works
“Many different techniques exist for determining the angles β and γ , including fixed angles [13], interpolation [3], [12], and unsupervised learning [10].”
The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
Cook, J., Eidenbenz, S., & Bärtschi, A. (2019) · arXiv · doi:10.48550/arxiv.1910.13483
Self-citationFrom the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O'Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2017) · arXiv · doi:10.48550/arxiv.1709.03489
Golden, J., Bärtschi, A., Eidenbenz, S., & O'Malley, D. (2022) · arXiv · doi:10.48550/arxiv.2202.00648
Self-citation
Flagged first, then by citations
Research works printed but not linked: 2
- Golden, 2022, Evidence for super-polynomial advantage of QAOA over unstructured search, arXiv e-prints
- Golden, 2023, Optimal mixing in qaoa
Cited by
Sorted by citations
Short-depth QAOA circuits and quantum annealing on higher-order ising models
Pelofske, E., Bärtschi, A., & Eidenbenz, S. (2024) · npj Quantum Information · doi:10.1038/s41534-024-00825-w · Cited by 49 · see citing works
Self-citationAn expressive ansatz for low-depth quantum approximate optimisation
Vijendran, V., Das, A., Koh, D. E., Assad, S. M., & Lam, P. K. (2024) · Quantum Science and Technology · doi:10.1088/2058-9565/ad200a · Cited by 41 · 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
“In a more recent, related paper [26], we’ve made similar observations for unconstrained problems: An extensive study of different mixers as well as the objective value and threshold phase separators had Grover-Th outperform other combinations up to problems with 2 8 ≈ 250 feasible states, before…”
BackgroundSelf-citationScaling whole-chip QAOA for higher-order ising spin glass models on heavy-hex graphs
Pelofske, E., Bärtschi, A., Cincio, Ł., Golden, J. K., & Eidenbenz, S. (2024) · npj Quantum Information · doi:10.1038/s41534-024-00906-w · Cited by 24 · see citing works
“We expect that these types of parameter transfer protocols will be useful in future implementations of QAOA.”
BackgroundMethodSelf-citationHigh-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
“[22], [23].”
BackgroundMethodSelf-citationGrover-QAOA for 3-SAT: quadratic speedup, fair-sampling, and parameter clustering
Zhang, Z., Paredes, R., Sundar, B., Quiroga, D., Kyrillidis, A., Dueñas‐Osorio, L., Pagano, G., & Hazzard, K. R. A. (2024) · Quantum Science and Technology · doi:10.1088/2058-9565/ad895c · Cited by 17 · see citing works
“This has been recently applied to SAT problems [54, 55] to find solutions, but its scaling with problem size has not yet been studied.”
JuliQAOA: Fast, Flexible QAOA Simulation
Golden, J. K., Bärtschi, A., O’Malley, D., Pelofske, E., & Eidenbenz, S. (2023) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3624062.3624220 · Cited by 11 · see citing works
“JuliQAOA has already enabled robust numerical studies in several publications [17–19, 29”
BackgroundSelf-citationHybrid Gate-Based and Annealing Quantum Computing for Large-Size Ising ProblemsPreprint
Liu, C.-Y., & Goan, H. (2024) · Research Square · doi:10.21203/rs.3.rs-4707131/v1 · Cited by 9 · see citing works
Wang, S., Liu, H., Li, Y., Gao, F., Qin, S., & Wen, Q. (2024) · Advanced Quantum Technologies · doi:10.1002/qute.202400201 · Cited by 6 · 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
“Following Golden et al. [15], we generate hard instances beyond the difficulty phase transition by setting m = 3 n for the k = 2 case and m = 6 n for the k = 3 case.”
MethodSelf-citationLi, G., Wang, S., Xiumei, Z., Gao, F., Qin, S., Guo, F.-Z., & Jin, Z. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04783-w · Cited by 1 · see citing works
Quantum Circuit Design for Decoded Quantum Interferometry
Patamawisut, N., Benchasattabuse, N., Hajdušek, M., & Meter, R. V. (2025) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce65121.2025.00041 · Cited by 1 · see citing works
“Despite promising numerical results for specific problems [7] [8] [9] [10], iterative versions of Grover’s algo-rithm [11] [12] [13] and its variants [14] [15]—designed as quantum brute-force searches—offer only a quadratic speedup.”
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
“Several quantum algorithms have been proposed for solving the SAT problem using various quantum ground state solvers, including quantum annealing 27 , the quantum adiabatic algorithm (QAA) 28–33 and the QAOA 1,34–36 .”
A Statistical Approach to Analyzing the Quantum Alternating Operator Ansatz with Grover Mixer
Bridi, G. A., & Marquezino, F. D. L. (2025) · doi:10.5753/ctd.2025.8022
“Much of the QAOA knowledge is empirical since analytical results are historically uncommon and scattered in the literature, largely due to quantum operators being analytically complex [Golden et al. 2023b].”
Influential
- Authors
- Golden, J., Bärtschi, A., O'Malley, D., & Eidenbenz, S.
- Affiliations
- Los Alamos National Laboratory (US)
- Los Alamos National Laboratory,Computational Earth Sciences (EES-16),Los Alamos,NM,USA,87544
- Venue
- 2023 IEEE International Conference on Quantum Computing and Engineering (QCE)
- Publisher
- IEEE
- Published
- 2023-09-17
- Pages
- 307-312
- OpenAlex
- W4389158919
- Semantic Scholar
- c63e0f64f38a5e82254cc36a1191afc7062a1e21
- Cited by
- 13
- References
- 12
- Citations by year
- 2025: 3 · 2024: 7 · 2023: 3
- FWCI
- 2.31
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- IEEE International Conference on Quantum Computing and Engineering (QCE) (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Keywords
- Quantum Alternating Operator Ansatz, quantum approximate optimization algorithm, combinatorial optimization, satisfiability, MAX-2-SAT, quantum annealing
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
