Pith. sign in

REVIEW 6 minor 58 references

Evaluating QAOA expectation values can be as hard as counting optimal solutions

T0 review · 0 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Evaluating depth-2 QAOA expectation values is #P-hard: it reveals the number of maximum cuts.

desk verdict This paper upgrades QAOA expectation-value hardness from NP-hard to #P-hard with a clean gadget, and the key technical step survives independent checking; it deserves serious peer review. read the letter →

arxiv 2608.11385 v1 pith:EK7OYOYW submitted 2026-08-11 quant-ph cs.CC

Stuart Hadfield This is my paper · ORCID
classification quant-phcs.CC MSC 68Q1781P68
keywords QAOAMaxCut#P-hardnessexpectationvalueLaurentpolynomialcountingmaximumcutsvariationalquantumalgorithmscomputationalcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a sharp complexity dichotomy for the Quantum Approximate Optimization Algorithm (QAOA) on MaxCut: at depth one the expected cut value is given by a closed formula computable in polynomial time for every graph, while from depth two onward exactly evaluating that expectation is as hard as counting the number of maximum cuts. Counting maximum cuts is a #P-hard problem, believed to be strictly harder than merely finding an optimal cut. Hardness remains even when the observable is a single two-qubit correlator and when almost all QAOA angles are fixed to constants. If the result is correct, no polynomial-time classical algorithm can evaluate these quantities exactly or to exponentially small error unless the polynomial hierarchy collapses, which would affect variational quantum algorithms that rely on such expectation values.

What carries the argument

The load-bearing object is the Laurent polynomial obtained from the depth-two expectation value when the two cost angles are tied, $\gamma_1=\gamma_2=\varphi$, and the mixer angles are fixed: writing $z=e^{i\varphi}$, the expectation is a Laurent polynomial $\sum_k a_k z^k$ whose maximal exponent is $D_\star=\mathrm{MC}(G)+2N-4$. The paper constructs a counting gadget $G(H)$ from any input graph $H$ using complete-bipartite $K_{L,L}$ variable gadgets and two universal anchor vertices; Lemma 2.1 shows every maximum cut of $G(H)$ splits each gadget properly, yielding $|\#\mathrm{MC}(G(H))|=2|\#\mathrm{MC}(H)|$. The extreme coefficient $a_{D_\star}$ is evaluated in closed form (Theorem 2.4) as $-2^{1-N}|\#\mathrm{MC}(G)|c^{N/2}(is)^{N/2}[c^N+(-is)^N]$, a nonzero algebraic number for $\tan\beta=1/2$. Coefficient recovery uses an inverse discrete Fourier transform over $Q=4|E(G)|+1$ roots of unity, giving a polynomial-time Turing reduction from counting maximum cuts to evaluating the QAOA expectation value.

What would settle it

Run an exact statevector simulation of the depth-two QAOA circuit on the paper's 56-vertex graph $G(K_3)$ at the fixed angles $\beta_1=\arctan(1/2)$, $\beta_2=\pi/4$, $\gamma_1=\gamma_2=\varphi$ for enough values of $\varphi$ to invert the discrete Fourier transform; the recovered coefficient at the predicted maximal exponent $D_\star$ must equal $-2^{1-56}\cdot 12\cdot c^{28}(is)^{28}[c^{56}+(-is)^{56}]$ with $c=2/\sqrt{5}$, $s=1/\sqrt{5}$. Any deviation disproves the central identity.

Watch

Extended reading notes

Core claim

The central claim is a complexity dichotomy for the QAOA MaxCut cost function on unweighted simple graphs. For $p=1$, the expected cut value $F_1(G;\gamma,\beta)$ is given by a closed formula and is computable in polynomial time ($\mathrm{Eval}_1^{\mathrm{MC}}\in\mathrm{FP}$). For every fixed depth $p\ge 2$, exact evaluation of $F_p$ is $\#\mathrm{P}$-hard under deterministic polynomial-time Turing reductions, and this remains true if only one two-qubit correlator $\langle Z_rZ_s\rangle$ is evaluated and if the parameters are restricted to $\gamma_1=\gamma_2$, $\beta_1=\arctan(1/2)$, $\beta_2=\pi/4$, with all later angles zero. The proof recovers not only the maximum cut value but the full count $|\#\mathrm{MC}(G)|$ from the extreme Laurent coefficient of the expectation value, so the transition from $p=1$ to $p=2$ is a jump from tractability to counting hardness.

Load-bearing premise

The reduction holds together at the point where the depth-two path sum is collapsed to a Laurent polynomial (Lemma 2.2): if that identity contains a sign or phase error, the closed form for the extreme coefficient and the entire counting reduction fail.

Editorial extensions

If this is right

  • For every fixed $p\ge 2$, exact evaluation of the MaxCut QAOA expectation value on unweighted simple graphs is $\#\mathrm{P}$-hard under deterministic polynomial-time Turing reductions.
  • Hardness survives even when the oracle returns a single designated two-qubit correlator $\langle Z_rZ_s\rangle$ instead of the full cost expectation value.
  • Hardness survives under exponentially small additive error: there is a constant $\alpha>0$ such that returning $F_G(\varphi)$ to error $2^{-\alpha N}$ is still $\#\mathrm{P}$-hard.
  • Exact computation of the tied-phase gradient and Hessian of the QAOA objective is also $\#\mathrm{P}$-hard, so training landscapes inherit the counting hardness.
  • At $p=1$, by contrast, exact evaluation is in $\mathrm{FP}$ via the explicit edge formula.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The hard graph family has diameter two but unbounded vertex degree, so the result says nothing about bounded-degree MaxCut instances; a natural next question is whether the $p=2$ counting hardness appears there at all.
  • The reduction's polynomial-time oracle calls use only roots of unity and fixed quadratic algebraic angles, suggesting that the same interpolation strategy might be adapted to other Ising-type cost functions; whether such counting gadgets exist for weighted MaxCut or Max-2-SAT is left open.
  • Because the hardness is for exact or exponentially precise values, variational workflows that tolerate constant additive error in expectation estimates may evade the barrier entirely; the paper notes this limitation explicitly.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies the complexity of exactly evaluating expectation values of the Quantum Approximate Optimization Algorithm (QAOA) applied to MaxCut. It proves that for every fixed depth p≥2, exact evaluation (and evaluation to exponentially small additive error) of the standard QAOA cost expectation is #P-hard under deterministic polynomial-time Turing reductions, for unweighted simple graphs. The reduction constructs, from an input graph H, a graph G with balanced K_{L,L} gadgets and two universal anchor vertices; the p=2 expectation value, expressed as a Laurent polynomial in a phase variable, has an extreme coefficient proportional to the number of maximum cuts of H. The coefficient is extracted via inverse discrete Fourier transform over polynomially many roots of unity. Hardness persists for a single designated two-qubit correlator, for the fixed mixer angles β1=arctan(1/2) and β2=π/4 with tied cost phases, and for depth p>2 by adding identity layers. The paper also derives #P-hardness for phase derivatives, gradients, and Hessians. In contrast, the p=1 case is tractable by the standard closed-form formula.

Significance. If the result is correct, it sharpens the previously known NP-hardness for p≥2 (Wang et al.) to counting hardness, establishing a clean depth-1 versus depth-2 dichotomy for QAOA expectation evaluation. The proof is self-contained: the gadget rigidity lemma and the extreme-coefficient identity are explicit, with constant mixer angles independent of the input. The paper is careful in stating the worst-case, exact-or-exponentially-precise nature of the results and in distinguishing them from sampling hardness and from constant-error estimation. The extension to gradients and Hessians is a natural and useful corollary. The main technical linchpin, the reduced path-sum identity in Lemma 2.2, is compressed but appears correct; the rest of the reduction, interpolation, and rounding arguments are sound. I could not identify a load-bearing error.

minor comments (6)
  1. [Section 2, Lemma 2.1] The proof of Lemma 2.1 contains a duplicated paragraph: the Hamming-distance correction argument appears twice nearly verbatim, and the second instance ends with an incomplete sentence ('The possible loss is at most (Δ+2)q, ...'). Please remove the duplicate and complete the sentence.
  2. [Section 2.1, Lemma 2.2] The derivation of the reduced path-sum identity, Eq. (16), is compressed into a single paragraph. Because this identity is the linchpin of the extreme-coefficient analysis, I recommend expanding the derivation (e.g., in an appendix) to show the intermediate sums over the final-mixer spins and the endpoint phase factors.
  3. [Definition 1.1] The problem statement defines Eval_MC_p as mapping to 'the exact algebraic number F_p(G;γ,β)' without specifying how the real parameters γ,β are represented on input. For the p=1 tractability claim (Proposition A.1) and for the oracle queries in the reduction, the natural convention is that angles are specified by algebraic values of their sines and cosines, as footnoted in [15]. Please make this convention explicit in Definition 1.1.
  4. [Corollary 2.8, Eq. (35)] In the lower-bound chain for |κ_N|, the displayed expression '(√2/5)^N' should be '(√2/5)^N' rather than '(√(2/5))^N' to be consistent with the following equality '= 2^{-N log_2(5/√2)}'. The final constant α0 is correct, but the intermediate notation is inconsistent.
  5. [Section 4] There is a typo 'at lease' in Section 4; it should be 'at least'. Additionally, the author name 'Abolinš' appears garbled as '¯Abolin,š' in the text; please check the encoding.
  6. [Theorem 2.4] In the sentence 'For tanβ=1/2, the two terms in the bracket always have unequal magnitudes and cannot cancel', a brief justification (e.g., c^N > s^N for N>0) would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the #P-hardness reduction is self-contained and derives its conclusion from an external counting-hardness input.

full rationale

The paper's central claim is a Turing reduction from counting maximum cuts to evaluating QAOA expectation values. The reduction starts from the externally established #P-hardness of counting maximum cuts (Ref. [8], and also [9,10]), so the hard input is not supplied by the paper. The path-sum identity in Lemma 2.2 (Eq. 16) is derived by inserting computational-basis resolutions and summing exactly; it is not assumed to be equal to the conclusion. Theorem 2.4's extreme-coefficient formula (Eq. 27) is a closed-form expression involving only the graph construction, the fixed mixer angle, and the uncomputed count |#MC(H)|; no parameter is fitted to oracle values, and no oracle output is renamed as a prediction. The coefficient recovery step (Eq. 32) uses the inverse discrete Fourier transform to interpolate Laurent coefficients from oracle values, which is a standard and non-circular inversion of the defining analytic expression. The author's earlier work is cited only for the depth-one closed form and for context, not as the load-bearing premise of the hardness argument; the hardness of counting maximum cuts is an external, independent result. The only manuscript-level defects observed are presentational: a duplicated paragraph and an incomplete sentence in the proof of Lemma 2.1, and a harmless sign-convention ambiguity in Corollary 2.8. None of these makes any derivation depend on its own conclusion. The claimed dichotomy therefore has independent mathematical content: it upgrades an existing NP-hardness result to #P-hardness using a new graph gadget and an exact coefficient identity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on the external #P-hardness of counting maximum cuts, on standard algebraic number theory for exact oracle outputs, and on the graph gadgets derived in the paper. There are no fitted parameters and no invoked new physical entities.

assumptions (3)
  • standard math Counting maximum cuts of unweighted simple graphs is #P-hard.
    External hardness source for the reduction, cited to [8, Lemma 13] and [9,10] in Section 1.
  • standard math Exact arithmetic and equality testing in the number field K_Q = Q(ζ_Q, i, √2, √5) can be performed in polynomial time.
    Used in footnote 15 to justify that oracle outputs and the inverse discrete Fourier transform are polynomial-time representable and exact.
  • domain assumption The QAOA expectation oracle returns an exact algebraic number in a standard number-field representation.
    Definition 1.1 and footnote 15 define the function problem this way; the Turing reduction depends on being able to interpolate and zero-test coefficients.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Evaluating QAOA expectation values can be as hard as counting optimal solutions." pith.science (2026). https://pith.science/paper/EK7OYOYW

@misc{pith2026260811385,
  author       = {Pith},
  title        = {Pith review of: Evaluating QAOA expectation values can be as hard as counting optimal solutions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EK7OYOYW}},
  note         = {Machine review of arXiv:2608.11385}
}
abstract

Evaluating expectation values is a critical task for variational quantum eigensolvers, and for parameterized quantum circuits and other quantum algorithms more generally. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\geq 2$ exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at $p\geq 2$ is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from $p=1$ to $p=2$ is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.

Figures

Figures reproduced from arXiv: 2608.11385 by the authors.

Figure 1
Figure 1. The balanced counting gadget for the source instance [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 43 canonical work pages

  1. [1]

    Challenges and opportunities in quantum optimization.Nature Reviews Physics, pages 1–18, 2024

    Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J Egger, Bruce G Elmegreen, et al. Challenges and opportunities in quantum optimization.Nature Reviews Physics, pages 1–18, 2024

    2024

  2. [2]

    A quantum approximate optimization algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014

    arXiv 2014

  3. [3]

    Rieffel, Davide Venturelli, and Rupak Biswas

    Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz.Algorithms, 12(2):34, 2019

    work page 2019

  4. [4]

    Quantum approximate optimization algorithm for MaxCut: A fermionic view.Physical Review A, 97(2):022304, 2018

    Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approximate optimization algorithm for MaxCut: A fermionic view.Physical Review A, 97(2):022304, 2018

    work page 2018

  5. [5]

    A unified complexity- algorithm account of constant-round QAOA expectation computation

    Jingheng Wang, Shengminjie Chen, Xiaoming Sun, and Jialin Zhang. A unified complexity- algorithm account of constant-round QAOA expectation computation. arXiv preprint arXiv:2511.20212, 2025

    arXiv 2025

  6. [6]

    Leslie G. Valiant. The complexity of enumeration and reliability problems.SIAM Journal on Computing, 8(3):410–421, 1979

    work page 1979

  7. [7]

    Mark W. Krentel. The complexity of optimization problems.Journal of Computer and System Sciences, 36(3):490–509, 1988

    work page 1988

  8. [8]

    Polynomial-time approximation algorithms for the Ising model

    Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing, 22(5):1087–1116, 1993

    work page 1993

Show all 58 references
  1. [9]

    The complexity of counting cuts and of computing the probability that a graph is connected.SIAM Journal on Computing, 12(4):777–788, 1983

    J Scott Provan and Michael O Ball. The complexity of counting cuts and of computing the probability that a graph is connected.SIAM Journal on Computing, 12(4):777–788, 1983. 15

    1983

  2. [10]

    Complexity of counting the optimal solutions.Theoretical Computer Science, 410(38-40):3814–3825, 2009

    Miki Hermann and Reinhard Pichler. Complexity of counting the optimal solutions.Theoretical Computer Science, 410(38-40):3814–3825, 2009

    2009

  3. [11]

    Standard implementations ofe−iγCG require at least∆(G)two-qubit gate depth

    Throughout, the QAOA depth parameterp denotes the total number of alternating cost and mixer rounds, rather than the physical gate depth of an implementation. Standard implementations ofe−iγCG require at least∆(G)two-qubit gate depth. The hard instances we construct below have...

  4. [12]

    Quantum algorithms for scientific computing and approximate optimization

    Stuart Andrew Hadfield. Quantum algorithms for scientific computing and approximate optimization. PhD thesis, Columbia University, 2018

    2018

  5. [13]

    Quantum supremacy through the quantum approximate optimization algorithm

    Edward Farhi and Aram W Harrow. Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674, 2016

    2016 arXiv

  6. [14]

    In particular, choosingb =O(N)permits exponentially small error while preserving a polynomial-time reduction

    Here unary encoding ofb ensures that the requested number of accuracy bits is part of the input length. In particular, choosingb =O(N)permits exponentially small error while preserving a polynomial-time reduction

  7. [15]

    1.2 may be formalized as follows

    For completeness, the oracle calls used in the reduction of Thm. 1.2 may be formalized as follows. SetQ = 4m + 1and ζQ =e2πi/Q. The phaseϕj = 2πj/Q is encoded by the integer pair( Q,j ), with the conventioneiϕj = ζj Q, while the fixed mixer angles are encoded by (cosβ 1,sinβ 1...

  8. [16]

    1.2 can all be performed in polynomial time and with polynomially scaling number of bits [55–57]

    Since[ KQ : Q]≤ 8φ(Q)and Q is polynomial in the instance size, exact arithmetic, equality testing, and the inverse discrete Fourier transform in the proof of Thm. 1.2 can all be performed in polynomial time and with polynomially scaling number of bits [55–57]. Any standard exa...

  9. [17]

    PP is as hard as the polynomial-time hierarchy.SIAM Journal on Computing, 20(5):865–877, 1991

    Seinosuke Toda. PP is as hard as the polynomial-time hierarchy.SIAM Journal on Computing, 20(5):865–877, 1991

    1991

  10. [18]

    A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem.arXiv preprintarXiv:1412.6062, 2014

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem.arXiv preprintarXiv:1412.6062, 2014

    2014 arXiv

  11. [19]

    Near-optimal quantum circuit for Grover’s unstructured search using a transverse field.Physical Review A, 95(6):062317, 2017

    Zhang Jiang, Eleanor G Rieffel, and Zhihui Wang. Near-optimal quantum circuit for Grover’s unstructured search using a transverse field.Physical Review A, 95(6):062317, 2017

    2017

  12. [20]

    Obstacles to variational quantum optimization from symmetry protection.Physical Review Letters, 125(26):260505, 2020

    Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection.Physical Review Letters, 125(26):260505, 2020

    2020

  13. [21]

    Classical and quantum bounded depth approximation algorithms.arXiv preprint arXiv:1905.07047, 2019

    Matthew B Hastings. Classical and quantum bounded depth approximation algorithms.arXiv preprint arXiv:1905.07047, 2019

    1905 arXiv

  14. [22]

    Local classical MAX-CUT algorithm outperformsp = 2QAOA on high-girth regular graphs

    Kunal Marwaha. Local classical MAX-CUT algorithm outperformsp = 2QAOA on high-girth regular graphs. Quantum, 5:437, 2021

    2021

  15. [23]

    MaxCut quantum approximate optimization algorithm performance guarantees forp>1

    Jonathan Wurtz and Peter Love. MaxCut quantum approximate optimization algorithm performance guarantees forp>1. Physical Review A, 103(4):042612, 2021. 16

    2021

  16. [24]

    Classical algorithms and quantum limitations for maximum cut on high-girth graphs.arXiv preprint arXiv:2106.05900, 2021

    Boaz Barak and Kunal Marwaha. Classical algorithms and quantum limitations for maximum cut on high-girth graphs.arXiv preprint arXiv:2106.05900, 2021

    2021 arXiv

  17. [25]

    Bounds on approximating MaxkXOR with quantum and classical local algorithms.Quantum, 6:757, 2022

    Kunal Marwaha and Stuart Hadfield. Bounds on approximating MaxkXOR with quantum and classical local algorithms.Quantum, 6:757, 2022

    2022

  18. [26]

    Analytical framework for quantum alternating operator ansätze.Quantum Science and Technology, 8(1):015017, 2022

    Stuart Hadfield, Tad Hogg, and Eleanor G Rieffel. Analytical framework for quantum alternating operator ansätze.Quantum Science and Technology, 8(1):015017, 2022

    2022

  19. [27]

    Expectation values from the single- layer quantum approximate optimization algorithm on Ising problems.Quantum Science and Technology, 7(4):045036, 2022

    Asier Ozaeta, Wim van Dam, and Peter L McMahon. Expectation values from the single- layer quantum approximate optimization algorithm on Ising problems.Quantum Science and Technology, 7(4):045036, 2022

    2022

  20. [28]

    The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model

    Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model. In17th Conference on the Theory of Quantum Computation, Comm...

    2022

  21. [29]

    Predicting parameters for the quantum approx- imate optimization algorithm for MAX-CUT from the infinite-size limit

    Sami Boulebnane and Ashley Montanaro. Predicting parameters for the quantum approx- imate optimization algorithm for MAX-CUT from the infinite-size limit. arXiv preprint arXiv:2110.10685, 2021

    2021 arXiv

  22. [30]

    The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size.Quantum, 6:759, 2022

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size.Quantum, 6:759, 2022

    2022

  23. [31]

    Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models

    Joao Basso, David Gamarnik, Song Mei, and Leo Zhou. Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. In2022 IEEE 63rd Annual Symposium on Foundationsof Computer Science (FOCS), pages 335–343. IEEE, 2022

    2022

  24. [32]

    Spin–boson mapping of the quantum approximate optimization algorithm

    Sami Boulebnane, Abid Khan, Minzhao Liu, Jeffrey Larson, Dylan Herman, Ruslan Shaydulin, and Marco Pistoia. Spin–boson mapping of the quantum approximate optimization algorithm. Physical Review Letters, 136(24):240601, 2026

    2026

  25. [33]

    Training variational quantum algorithms is NP-hard

    Lennart Bittel and Martin Kliesch. Training variational quantum algorithms is NP-hard. Physical Review Letters, 127(12):120502, 2021

    2021

  26. [34]

    Bremner, Richard Jozsa, and Dan J

    Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467(2126):459–472, 2011

    2011

  27. [35]

    A sharp interaction-degree threshold for simulating QAOA

    Ralfs ¯Abolin,š and Andris Ambainis. A sharp interaction-degree threshold for simulating QAOA. arXiv preprint arXiv:2605.22758, 2026

    2026 arXiv

  28. [36]

    Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent.arXiv preprint arXiv:2206.05642, 2022

    Hari Krovi. Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent.arXiv preprint arXiv:2206.05642, 2022

    2022 arXiv

  29. [37]

    How many qubits are needed for quantum computational supremacy?Quantum, 4:264, 2020

    Alexander M Dalzell, Aram W Harrow, Dax Enshan Koh, and Rolando L La Placa. How many qubits are needed for quantum computational supremacy?Quantum, 4:264, 2020. 17

    2020

  30. [38]

    Quantum computational supremacy

    Aram W Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549(7671):203–209, 2017

    2017

  31. [39]

    Classical algorithms for quantum mean values

    Sergey Bravyi, David Gosset, and Ramis Movassagh. Classical algorithms for quantum mean values. Nature Physics, 17(3):337–341, 2021

    2021

  32. [40]

    WhatdoQAOAenergiesrevealaboutgraphs? arXivpreprintarXiv:1912.12277, 2019

    MarioSzegedy. WhatdoQAOAenergiesrevealaboutgraphs? arXivpreprintarXiv:1912.12277, 2019

    1912 arXiv

  33. [41]

    On the representation of Boolean and real functions as Hamiltonians for quantum computing

    Stuart Hadfield. On the representation of Boolean and real functions as Hamiltonians for quantum computing. ACM Transactions on Quantum Computing, 2(4):1–21, 2021

    2021

  34. [42]

    Counting with the quantum alternating operator ansatz

    Julien Drapeau, Shreya Banerjee, and Stefanos Kourtis. Counting with the quantum alternating operator ansatz. arXiv preprint arXiv:2503.07720, 2025

    2025 arXiv

  35. [43]

    The QAOA on the ring of disagrees.arXiv preprint arXiv:2606.29562, 2026

    Kunal Marwaha. The QAOA on the ring of disagrees.arXiv preprint arXiv:2606.29562, 2026

    2026 arXiv

  36. [44]

    A machine-verified proof of a quantum-optimization conjecture

    Uri Kol, Maor Ben-Shahar, Kfir Sulimany, and Dirk Englund. A machine-verified proof of a quantum-optimization conjecture. arXiv preprint arXiv:2606.29687, 2026

    2026 arXiv

  37. [45]

    Parameter setting in quantum approximate optimization of weighted problems.Quantum, 8:1231, 2024

    Shree Hari Sureshbabu, Dylan Herman, Ruslan Shaydulin, Joao Basso, Shouvanik Chakrabarti, Yue Sun, and Marco Pistoia. Parameter setting in quantum approximate optimization of weighted problems.Quantum, 8:1231, 2024

    2024

  38. [46]

    Lower bounding the MaxCut of high-girth 3-regular graphs using the QAOA.arXiv preprint arXiv:2503.12789, 2025

    Edward Farhi, Sam Gutmann, Daniel Ranard, and Benjamin Villalonga. Lower bounding the MaxCut of high-girth 3-regular graphs using the QAOA.arXiv preprint arXiv:2503.12789, 2025

    2025

  39. [47]

    Characterizing local noise in QAOA circuits.IOP SciNotes, 1(2):025208, 2020

    Jeffrey Marshall, Filip Wudarski, Stuart Hadfield, and Tad Hogg. Characterizing local noise in QAOA circuits.IOP SciNotes, 1(2):025208, 2020

    2020

  40. [48]

    Hybrid quantum-classical algorithms for approximate graph coloring.Quantum, 6:678, 2022

    Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Hybrid quantum-classical algorithms for approximate graph coloring.Quantum, 6:678, 2022

    2022

  41. [49]

    Hodson, Bhuvanesh Sundar, Stephen Jeffrey, Yuki Yamaguchi, Dennis Feng, Filip B

    Maxime Dupont, Bram Evert, Mark J. Hodson, Bhuvanesh Sundar, Stephen Jeffrey, Yuki Yamaguchi, Dennis Feng, Filip B. Maciejewski, Stuart Hadfield, M. Sohaib Alam, Zhihui Wang, Shon Grabbe, P. Aaron Lott, Eleanor G. Rieffel, Davide Venturelli, and Matthew J. Reagor. Quantum-enha...

    2023

  42. [50]

    Iterative quantum algorithms for maximum independent set

    Lucas T Brady and Stuart Hadfield. Iterative quantum algorithms for maximum independent set. Physical Review A, 110(5):052435, 2024

    2024

  43. [51]

    Quantum-informed recursive optimization algorithms.PRX Quantum, 5(2):020327, 2024

    Jernej Rudi Finžgar, Aron Kerschbaumer, Martin JA Schuetz, Christian B Mendl, and Helmut G Katzgraber. Quantum-informed recursive optimization algorithms.PRX Quantum, 5(2):020327, 2024

    2024

  44. [52]

    Brady and Stuart Hadfield

    Lucas T. Brady and Stuart Hadfield. Quantum Davis-Putnam-Logemann-Loveland and generalized constraints in iterative quantum algorithms.Physical Review A, 114(2):022404, 2026

    2026

  45. [53]

    A scalable quantum-enhanced greedy algorithm for maximum independent set problems.arXiv preprint arXiv:2601.21923, 2026

    Elisabeth Wybo, Jami Rönkkö, Olli Hirviniemi, Jernej Rudi Finžgar, and Martin Leib. A scalable quantum-enhanced greedy algorithm for maximum independent set problems.arXiv preprint arXiv:2601.21923, 2026. 18

    2026

  46. [54]

    Extendingrelax-and-roundcombinatorialoptimization solvers with quantum correlations.Physical Review A, 109(1):012429, 2024

    MaximeDupontandBhuvaneshSundar. Extendingrelax-and-roundcombinatorialoptimization solvers with quantum correlations.Physical Review A, 109(1):012429, 2024

    2024

  47. [55]

    A multilevel approach for solving large-scale QUBO problems with noisy hybrid quantum approximate optimization

    Filip B Maciejewski, Bao G Bach, Maxime Dupont, P Aaron Lott, Bhuvanesh Sundar, David E Bernal Neira, Ilya Safro, and Davide Venturelli. A multilevel approach for solving large-scale QUBO problems with noisy hybrid quantum approximate optimization. In2024 IEEE High Performance...

  48. [56]

    Lenstra, Hendrik W

    Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982

    1982

  49. [57]

    Algorithms in real algebraic geometry

    Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in real algebraic geometry. Springer, 2006

    2006

  50. [58]

    Springer Science & Business Media, 2013

    Henri Cohen.A course in computational algebraic numbertheory. Springer Science & Business Media, 2013. A Depth one QAOA expectation values are exactly tractable For an edgee ={u,v}, letdu,dv be the endpoint degrees andλuv =|N(u)∩N (v)|. For each single edge termCuv = (I−Z uZv)...

    2013

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.