{"id":"fbe6a72e-7d7f-4682-b9c4-c0b795da0549","arxiv_id":"2608.11385","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"QAOA MaxCut expectation values at depth p≥2 are #P-hard to evaluate exactly or to exponential precision, because their extreme Laurent coefficient encodes the maximum-cut count.","lead":"This paper proves that evaluating the expectation value of a depth-2 QAOA circuit for MaxCut is exactly as hard as counting the number of maximum cuts, not merely finding one. The result upgrades a known NP-hardness bound to #P-hardness and also applies to single correlators and to derivatives of the QAOA objective.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Lemma 2.2's reduced path-sum identity survives independent verification.","rationale":"The reader's ACCEPT verdict rests on Lemma 2.2 being sound, and that is exactly where I focused. I verified the identity by direct expansion: writing the depth-two QAOA state with gamma_1 = gamma_2 = phi and beta_2 = pi/4 in the computational basis, the bra and ket amplitudes contain z^{c(x')+c(y')-c(x)-c(y)} with beta-mixing factors K^+_beta(x',y') K^-_beta(y,x). Summing over the final-basis index gives delta_{y'_w,y_w} for w not in e and -i y'_w delta_{y'_w,-y_w} for w in e, yielding y' = T_e y and the overall factor -y_u y_v. Relabeling X = x', Y = T_e y, and T = x transforms the exponent into c(X)-c(T)+c(Y)-c(T_e Y) and the mixing product into exactly Eq. (16). I also checked the equality analysis: R_{e*} = 2N-4 is attained only by q^sigma, the zero-cut assignments are the two constant assignments, and every maximum cut x is at Hamming distance N/2 from both q^sigma. The coefficient a_{D*} then factorizes as stated, and tan beta = 1/2 gives c^N > s^N, so it is nonzero. No unsupported step is load-bearing; the duplicated text in Lemma 2.1 is a copy-paste artifact, and the sign conventions around kappa_N in Corollary 2.8 are absorbable into the known nonzero factor. The verdict should remain ACCEPT.","tokens_in":15194,"tokens_out":39065,"duration_ms":358947,"concrete_test":"Independently re-derive Eq. (16) from the full depth-two path sum and test the simplest nontrivial case: with beta_1 = 0, beta_2 = pi/4, and G a single edge on two vertices, Eq. (16) must evaluate to <Z_1 Z_2> = (1 - e^{2i phi})/2. If the computed Laurent polynomial matches this closed form, the sign and phase structure of the linchpin identity are confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I attempted to find a load-bearing flaw and did not. The linchpin flagged by the reader is Lemma 2.2, Eq. (16). Expanding <psi_2|Z_u Z_v|psi_2> in the computational basis and summing the final-mixer index gives exactly the stated identity: the endpoint sum contributes -y_u y_v and forces the bra intermediate spin to be T_e y; the relabeling X = x_bra, Y = T_e y_ket, T = x_ket reproduces the exponent c(X)-c(T)+c(Y)-c(T_e Y) and the factors K^+_beta(X,Y) K^-_beta(T_e Y,T). The subsequent extreme-coefficient analysis also checks: Lemma 2.3's uniqueness of q^sigma is correct (both anchors must equal sigma and every W-vertex must be -sigma to attain 2N-4), and the coefficient factorization in Theorem 2.4, including the factor c^{N/2}(is)^{N/2}[c^N+(-is)^N], is sign-consistent. The only defects I found are presentational: a duplicated paragraph and an incomplete sentence in Lemma 2.1, and a harmless sign-convention ambiguity for kappa_N in Corollary 2.8. None of these affects the correctness of the #P-hardness reduction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15407,"tokens_out":23767,"duration_ms":195470,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 2, Lemma 2.1"},{"comment":"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.","section":"Section 2.1, Lemma 2.2"},{"comment":"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.","section":"Definition 1.1"},{"comment":"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.","section":"Corollary 2.8, Eq. (35)"},{"comment":"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.","section":"Section 4"},{"comment":"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.","section":"Theorem 2.4"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically sound to the best of my reading. The only substantive risk is the compressed derivation of Lemma 2.2, which I verified independently; an expanded derivation would help future readers. The definitional ambiguity about the input representation of QAOA angles (Definition 1.1) should be resolved before publication. I do not see grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper is the real thing. It takes Wang et al.'s NP-hardness result for evaluating depth-p≥2 QAOA MaxCut expectation values and sharpens it to #P-hardness, under deterministic poly-time Turing reductions. The main construction is a strikingly simple gadget: balanced K_{L,L} blocks plus two universal anchor vertices, and the proof recovers both the maximum cut value and the number of maximum cuts from an extreme Laurent coefficient. That is genuinely new, not just a tweak. The paper also shows hardness for a single ZZ correlator, for fixed angle restrictions, and for gradients and Hessians, none of which were in the prior literature.\n\nI read the proof closely and I am fairly confident it is correct. The gadget rigidity lemma (Lemma 2.1) is sound—the counting argument forcing each K_{L,L} to be properly oriented works because L is chosen large enough relative to max degree. The extreme-coefficient identity (Theorem 2.4) is explicit, and the interpolation/rounding arguments are clean. I specifically checked the reduced path-sum identity in Lemma 2.2, which the reader flagged as the linchpin. It checks out: the internal spin sums produce the claimed Laurent polynomial, and the extreme-coefficient analysis is sign-consistent. The reduction is not circular; it builds on the externally established #P-hardness of counting maximum cuts, and the author's own prior work is only cited for the p=1 formula.\n\nThe soft spots are mostly presentational. The derivation of Lemma 2.2 is compressed into one paragraph; a careful referee will want it expanded. There are a few typos, including 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 affect correctness. The paper is also appropriately honest about scope: the hardness requires exact or exponentially precise evaluation, uses high-degree graphs, and does not speak to constant-error approximation or physical gate-depth. The discussion section says so plainly.\n\nBottom line: this is a meaningful structural result, and the main proof survives scrutiny. I would bring it to a reading group and I would cite it. It absolutely deserves a serious referee rather than a desk reject. Send it out.","headline":"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.","tokens_in":15937,"tokens_out":1264,"would_cite":true,"duration_ms":14096,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"Evaluating depth-2 QAOA expectation values is #P-hard: it reveals the number of maximum cuts.","keywords":["QAOA","MaxCut","#P-hardness","expectation value","Laurent polynomial","counting maximum cuts","variational quantum algorithms","computational complexity"],"falsifier":"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.","tokens_in":14969,"feed_emoji":"🧮","tokens_out":9983,"duration_ms":86763,"temperature":0.7,"pith_summary":"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.","feed_headline":"Depth-2 QAOA evaluation is as hard as counting optimal cuts","feed_subtitle":"Computing depth-2 QAOA expectation values recovers MaxCut solution counts, a #P-hard task.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the earlier NP-hardness of $p\\ge 2$ QAOA evaluation via Laurent-polynomial exponents; the new proof refines this approach.","marker":"[5]"},{"why":"Proves $\\#\\mathrm{P}$-hardness of counting maximum cuts, the source problem the Turing reduction starts from.","marker":"[8]"},{"why":"Defines the QAOA circuit, cost and mixer Hamiltonians, and the expectation value studied throughout.","marker":"[2]"},{"why":"Gives the depth-one analytic formulas for edge correlators that put $p=1$ evaluation in $\\mathrm{FP}$.","marker":"[4]"},{"why":"Toda's theorem, used to derive polynomial-hierarchy collapse if exact evaluation were polynomial-time.","marker":"[16]"},{"why":"Introduces the class $\\#\\mathrm{P}$ and the notion of counting hardness that the main theorem targets.","marker":"[6]"}],"fun_headline_variants":["Depth-2 QAOA evaluation is #P-hard: as hard as counting cuts","Counting MaxCut solutions from QAOA expectation values at p=2","QAOA hardness jumps from easy to #P-hard at depth 2","Even a single correlator is #P-hard in p=2 QAOA","Expectation values at p=2: same hardness as counting solutions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Depth-2 QAOA evaluation is #P-hard: as hard as counting cuts","Counting MaxCut solutions from QAOA expectation values at p=2","QAOA hardness jumps from easy to #P-hard at depth 2","Even a single correlator is #P-hard in p=2 QAOA","Expectation values at p=2: same hardness as counting solutions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000484,"raw_usage":{"total_tokens":2440,"prompt_tokens":1048,"completion_tokens":1392,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":664,"completion_tokens_details":{"reasoning_tokens":1295}},"tokens_in":664,"tokens_out":1392,"duration_ms":10768,"temperature":1.0,"reasoning_tokens":1295,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:15:06.817447+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Polynomial-time approximation algorithms for the Ising model","cited_arxiv_id":null,"evidence_quote":"Proves $\\#\\mathrm{P}$-hardness of counting maximum cuts, the source problem the Turing reduction starts from."},{"cited_title":"Quantum approximate optimization algorithm for MaxCut: A fermionic view.Physical Review A, 97(2):022304, 2018","cited_arxiv_id":null,"evidence_quote":"Gives the depth-one analytic formulas for edge correlators that put $p=1$ evaluation in $\\mathrm{FP}$."},{"cited_title":"1.2 can all be performed in polynomial time and with polynomially scaling number of bits [55–57]","cited_arxiv_id":null,"evidence_quote":"Toda's theorem, used to derive polynomial-hierarchy collapse if exact evaluation were polynomial-time."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the class $\\#\\mathrm{P}$ and the notion of counting hardness that the main theorem targets."}],"review_version":1}