Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Applying the quantum approximate optimization algorithm to general constraint satisfaction problems

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read A single classical formula now predicts one-layer QAOA success on any random Boolean constraint problem.

desk verdict Solid fixed-k formulas for p=1 QAOA on random CSPs, but the advertised O(k^7) complexity for general truth tables is unsupported. read the letter →

arxiv 2411.17442 v1 pith:X4POSCNU submitted 2024-11-26 quant-ph

Sami Boulebnane , Maria Ciudad-Alañón , Lana Mineh , Ashley Montanaro , Niam Vaishnav This is my paper · ORCID
classification quant-ph MSC 68Q1281P68 PACS 03.67.Ac
keywords QAOAconstraintsatisfactionproblemsrandomk-SATsatisfiabilitythresholdconfigurationbasisnumberssingle-clausepolynomialMapleSATquantum-classicalseparation
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

This paper shows that the performance of one-layer QAOA on randomly generated constraint satisfaction problems is predictable by a classical formula. The authors derive a general expression for the instance-averaged success probability in terms of a single-clause polynomial, computable in time $O(k^7)$ for any Boolean constraint on $k$ bits, followed by an $O(n^3)$ summation. They apply it to every 3-bit constraint type and many 4- and 5-bit types at the satisfiability threshold, obtaining exponential runtime scalings for QAOA. Comparing those scalings with the classical solver MapleSAT, they find that MapleSAT's scaling is more efficient for all problems studied, and that random $k$-SAT is the family where QAOA would most plausibly first overtake classical solving if the comparison persists at higher depth.

What carries the argument

Configuration basis numbers are the central object: they count, for three $n$-bit strings, how many coordinates fall into each of the eight possible joint bit patterns, generalizing the Hamming weight from one string to three. Reduced configuration basis numbers merge patterns that differ by flipping every bit, which is what brings the final summation down to $O(n^3)$ terms. The single-clause polynomial $P_{\mathrm{single}}$ encodes all random-clause averages of the QAOA phase factor and is evaluated explicitly for a general truth table using the cardinalities $|Z(y,k)|$ of bitstring triplets grouped by joint truth value and configuration. Together these objects convert the average over random instances into a multinomial-coefficient sum that can be evaluated pointwise and then fitted to an exponential $c\cdot 2^{\alpha n}$.

What would settle it

Evaluate the same 3-SAT truth table at $n=24$ using the well-established asymptotic threshold $r\approx4.267$ instead of the $n=12$ estimate, recompute the QAOA success probability formula, and check it against direct statevector simulation; a mismatch beyond statistical error, or a change in the ordering of scaling exponents among truth tables, would show that the small-instance threshold estimate is the source of bias.

Watch

Extended reading notes

Core claim

For any Boolean CSP whose clauses are i.i.d. random $k$-literal constraints, the expected success probability of $p=1$ QAOA with fixed angles equals a finite sum over reduced configuration basis numbers. The paper proves this as Proposition 1 and supplies constructive formulas for the single-clause polynomial: Proposition 2 for Hamming-weight truth tables and Proposition 4 for fully general truth tables, with each formula a polynomial in configuration counts. The consequence is that average-case QAOA analysis reduces from exponential-in-$n$ sums over bitstrings to a sum with $O(n^3)$ terms, enabling systematic comparison of all truth tables at $k=3$ and a large selection at $k=4,5$. Applying this machinery at the empirically estimated satisfiability threshold, the paper obtains for every studied CSP the quantum runtime scaling exponent and compares it with the corresponding MapleSAT exponent.

Load-bearing premise

The load-bearing premise is that the satisfiability threshold measured by brute force on 200 random instances of only 12 variables is the correct asymptotic clause density for comparing exponents; if the true large-$n$ thresholds differ systematically, the computed QAOA and MapleSAT scalings and their comparison would be biased.

Editorial extensions

If this is right

  • Instance-averaged $p=1$ QAOA success probabilities can be computed in polynomial time for any random CSP with $k$-ary constraints, including truth tables lacking Hamming-weight symmetry.
  • The runtime scaling exponent of QAOA at $p=1$ can now be compared against a classical solver for thousands of constraint types, not just $k$-SAT.
  • For all CSPs considered at $k=3,4,5$, MapleSAT's scaling exponent is smaller than QAOA's at $p=1$, so no quantum speedup is evidenced at this depth.
  • Random $k$-SAT stands out as the family where QAOA's exponent is smallest relative to the classical baseline, making it the best candidate for a separation at higher $p$.
  • The observed linear dependence of QAOA's exponent on clause density $r$ means that accurate threshold estimates are essential when predicting where a separation would occur.

Reading between the lines

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

  • If the $p=1$ ranking persists at higher $p$—a step the paper explicitly leaves open—then demonstrations of quantum advantage on random CSPs should target $k$-SAT rather than NAE-SAT or 1-in-$k$-SAT.
  • The $O(k^7)$ precomputation suggests a practical window around $k\le 5$ and $n\le 30$; an analytic large-$n$ limit via a generalized multinomial theorem would be the natural next step to remove the finite-size fit.
  • Because MapleSAT's measured exponent barely depends on $r$ for small instances while QAOA's exponent does, a systematic error in the $n=12$ threshold estimate would bias the quantum scaling more than the classical scaling, tilting the comparison.
  • The same formulas can be reused as a fast parameter-optimization tool: once $P_{\mathrm{single}}$ is computed for a fixed truth table, the success probability at any angles $\gamma,\beta$ costs only $O(n^3)$ to evaluate.
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

3 major / 5 minor

Summary. The paper develops a classical algorithm for computing the instance-averaged success probability of one-layer QAOA applied to random Boolean CSPs. The central theoretical result, Proposition 1, expresses this probability as a sum over O(n^3) reduced configuration-basis numbers, provided the single-clause polynomial P_single is available. The authors derive P_single for Hamming-weight truth tables (Proposition 2) and for general truth tables (Proposition 4), then use the resulting formula to compute QAOA runtime scaling exponents for all k=3 truth tables and selected k=4,5 tables. These exponents are compared with MapleSAT exponents, and the paper concludes that random k-SAT appears the most promising CSP among those considered for demonstrating a quantum-classical separation using QAOA.

Significance. If the advertised complexity claim were fully established, this would be a valuable generalization of the k-SAT analysis in [7] to arbitrary Boolean CSPs, and a useful technique for predicting p=1 QAOA performance. The derivation of Proposition 1 is careful, and the analytic formulas for NAE-SAT and 1-in-k-SAT are validated against independent state-vector simulations, which is a genuine strength. The paper is also appropriately cautious about the limitation to p=1. However, the claimed O(k^7) precomputation for fully general truth tables is not substantiated, and the numerical comparison relies on several heuristic estimates without uncertainty quantification. These issues affect the central advertised contribution and the headline comparison, so they need to be addressed before the paper can be accepted as stated.

major comments (3)
  1. [Introduction item 1; Section III; Definition 13; Proposition 4] The claim that the single-clause probabilities for a general truth table can be computed in O(k^7) time is not supported. Proposition 4 sums over y and k in P(k) using coefficients |Z(y,k)| defined in Definition 13, but the paper gives no algorithm for computing these coefficients. The only evident method is exhaustive enumeration of all 2^{3k} bitstring triples, and since a general truth table has 2^k entries, any exact algorithm that reads the table must take time at least 2^k. Thus the advertised polynomial-in-k precomputation for general CSPs does not follow as stated. This does not invalidate the numerical results for k=3,4,5, where enumeration is feasible, but it undermines the main generalization claim. Please either provide a genuine polynomial-time algorithm for |Z(y,k)| under a clearly stated compact input model, or revise the abstract and introduction so that the polynomial-time claim is restricted to Hamming-weight truth tables or to fixed k, with the exponential cost of the general case made explicit.
  2. [Section V.A; Figures 1 and 2] The clause-to-variable ratio r used for both the QAOA and MapleSAT calculations is estimated by binary search at n=12 using only 200 random instances per truth table. Figure 1's caption itself notes that statistical noise produced different ratios for equivalent truth tables. Since the success probability formula in Proposition 1 contains exp(rn(P_single(n')-1)), and Figure 9 shows that the QAOA scaling exponent depends roughly linearly on r, the estimated thresholds are load-bearing for the reported exponents and rankings. Please provide error bars or confidence intervals for r, and demonstrate that the main conclusions, especially the identification of k-SAT as the most promising problem, are robust within those uncertainties. Where known asymptotic satisfiability thresholds are available, the authors should compare against them.
  3. [Section V.B; Section V.C; Figures 5-8] The statement that 'for all problems considered, the scaling of MapleSAT appears to be more efficient than the scaling of QAOA' is based on fitted scaling exponents, but the authors themselves observe in Section V.B that for many truth tables the MapleSAT data do not yet show clear exponential scaling in the n ranges used; only the one-false-value tables behave clearly exponentially. For those other problems, the fitted exponent is not a reliable asymptotic estimate, so the comparison in Figures 7 and 8 may overstate the universality of the conclusion. Please quantify the quality of the exponential fits (for example with goodness-of-fit measures or residual analysis) and either restrict the comparison to the problems where exponential scaling is actually observed, or qualify the claim accordingly.
minor comments (5)
  1. [Definition 3] The text says 'each negation ν_{j,0} independently', but it should be ν_{j,q} for q in [k], since every literal has its own negation bit.
  2. [Definition 11] The definition of a Hamming-weight truth table writes T(x_0,...,x_{n-1}), but the truth table is defined on k bits; this appears to be a typo for x_0,...,x_{k-1}.
  3. [Appendix A.1, equations (A13)-(A15)] Three different cases in the 3-bitstring calculation are labelled with the same set notation '{1,-1} ⊔ {0}'; one should be '{0,-1} ⊔ {1}' and one should be '{1} ⊔ {0} ⊔ {-1}'.
  4. [Figure 1 caption and Section V.B] The garbled strings '22k' and 'B2k' presumably denote 2^{2^k} and B^{2^k}; these should be typeset correctly.
  5. [Section V.A] The angles β and γ are selected from a coarse uniform grid of 50 values per angle with no convergence check. Since the reported scaling exponents depend on the chosen angles, a brief sensitivity analysis (for example, comparing with a finer grid for a few representative truth tables) would increase confidence in the numerical comparison.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the instance-averaged QAOA success probability is derived from first principles, and the few self-citations are not load-bearing.

full rationale

The central derivation chain is self-contained. Proposition 1 starts from the path-integral expression for the p=1 QAOA success probability and reduces the 8^n bitstring-triplet sum to a sum over O(n^3) reduced configuration-basis numbers using Lemma 1 and Lemma 4; the single-clause average Psingle is then computed independently. For Hamming-weight truth tables, Lemma 5 and Proposition 2 give an explicit multinomial formula for Psingle in terms of the truth table T and configuration counts, with no fitted parameter. For general truth tables, Proposition 3 and Proposition 4 express the single-clause expectation as a weighted sum over the combinatorial sets Z(y,k); although the paper does not supply an algorithm for computing |Z(y,k)| in O(k^7) (a correctness/complexity gap, not a circularity), the formula itself is a derivation, not an assumption of the result. The numerical comparisons use the clause ratio r (estimated by brute-force satisfiability checks at n=12) and QAOA angles (found by grid search) as inputs, and they are not fitted to the predicted success probabilities; the NAE-SAT and 1-in-k-SAT predictions are checked against independent statevector simulations. The closest thing to a variational feedback loop is choosing angles that maximize the same formula whose scaling is later reported, but that is legitimate parameter optimization for QAOA, not a fit disguised as a prediction. The self-citations to [7] and [10], both by subsets of the present authors, are used for background and for the k-SAT larger-p result, but the load-bearing p=1 formulas and k-SAT scaling exponents are derived and computed here, so the self-citations are not load-bearing. Overall, no step of the derivation is equivalent to its own input by construction.

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

The central derivation rests on the random clause model (Definition 3), the runtime proxy 1/p(n), and the empirically estimated satisfiability threshold. No new physical entities are introduced; configuration basis numbers are a combinatorial tool.

free parameters (3)
  • QAOA angles (gamma, beta) = varies per truth table and k; exact values in Tables I and II for special cases
    Section V.A chooses angles by uniformly sampling 50 values each from [0,2pi) and picking the pair that maximizes the success probability; no optimality guarantee.
  • Clauses-to-variables ratio r = plotted in Figures 1 and 2; exact values not tabulated for all tables
    Estimated by binary search on n=12 with 200 random instances to make satisfiability probability close to 1/2; this is a data-fitted input to both QAOA and MapleSAT comparisons.
  • Runtime scaling exponents alpha (QAOA and MapleSAT) = plotted in Figures 7 and 8; not tabulated
    Obtained by fitting T(n)=c*2^{alpha n} to computed/simulated runtime data; the comparison of these alpha values is the basis for the main conclusion.
assumptions (3)
  • domain assumption Random CSP instances are generated with i.i.d. literals (with repetition) and Poisson-distributed clause counts (Definition 3)
    The derivations rely on this distribution; the paper notes the alternative without repetition gives comparable results, but the main results use Definition 3.
  • domain assumption Algorithm runtime is modeled as the inverse of the instance-averaged success probability (Section V.A)
    The paper states this is a lower bound by Jensen's inequality, making it a modeling choice rather than an exact equivalence.
  • ad hoc to paper The satisfiability threshold r, estimated at n=12 with 200 instances, is representative of the asymptotic threshold
    Figure 1 shows statistical noise; the extrapolation to n->infinity is not quantified.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Applying the quantum approximate optimization algorithm to general constraint satisfaction problems." pith.science (2026). https://pith.science/paper/X4POSCNU

@misc{pith2026241117442,
  author       = {Pith},
  title        = {Pith review of: Applying the quantum approximate optimization algorithm to general constraint satisfaction problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X4POSCNU}},
  note         = {Machine review of arXiv:2411.17442}
}
abstract

In this work we develop theoretical techniques for analysing the performance of the quantum approximate optimization algorithm (QAOA) when applied to random boolean constraint satisfaction problems (CSPs), and use these techniques to compare the complexity of a variety of CSPs, such as $k$-SAT, 1-in-$k$ SAT, and NAE-SAT. Our techniques allow us to compute the success probability of QAOA with one layer and given parameters, when applied to randomly generated instances of CSPs with $k$ binary variables per constraint, in time polynomial in $n$ and $k$. We apply this algorithm to all boolean CSPs with $k=3$ and a large number of CSPs with $k=4$, $k=5$, and compare the resulting complexity with the complexity of solving the corresponding CSP using the standard solver MapleSAT, determined experimentally. We find that random $k$-SAT seems to be the most promising of these CSPs for demonstrating a quantum-classical separation using QAOA.

Figures

Figures reproduced from arXiv: 2411.17442 by the authors.

Figure 1
Figure 1. FIG. 1: The clauses-to-variables ratio for all [PITH_FULL_IMAGE:figures/full_fig_p028_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2: The clauses to variables ratio for Hamming weight truth tables with [PITH_FULL_IMAGE:figures/full_fig_p029_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3: The median runtime for QAOA lower bounded by the inverse of the success probability for a subset of truth [PITH_FULL_IMAGE:figures/full_fig_p030_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: FIG. 4: The runtime scaling exponent for QAOA for all Hamming weight truth tables for [PITH_FULL_IMAGE:figures/full_fig_p030_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5: The median runtime of MapleSAT for all [PITH_FULL_IMAGE:figures/full_fig_p031_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6: The median runtime for MapleSAT for truth tables for [PITH_FULL_IMAGE:figures/full_fig_p031_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7: Comparison of the QAOA and MapleSAT runtime scaling exponents for all [PITH_FULL_IMAGE:figures/full_fig_p032_7.png]
Figure 8
Figure 8. Figure 8: FIG. 8: Comparison of the QAOA and MapleSAT runtime scaling exponents for [PITH_FULL_IMAGE:figures/full_fig_p032_8.png]
Figure 9
Figure 9. Figure 9: FIG. 9: The classical and quantum scaling exponents of a sample of truth tables for [PITH_FULL_IMAGE:figures/full_fig_p033_9.png]
Figure 10
Figure 10. Figure 10: FIG. 10: Representation of the prediction for the success probability for [PITH_FULL_IMAGE:figures/full_fig_p037_10.png]
Figure 11
Figure 11. Figure 11: FIG. 11: Representation of the analytical and numerical prediction for the success probability for [PITH_FULL_IMAGE:figures/full_fig_p037_11.png]
Figure 12
Figure 12. Figure 12: FIG. 12: Representation of the numerical and theoretical prediction for the success probability of NAE-SAT for [PITH_FULL_IMAGE:figures/full_fig_p039_12.png]
Figure 13
Figure 13. Figure 13: FIG. 13: Representation of the prediction for the success probability for [PITH_FULL_IMAGE:figures/full_fig_p039_13.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Quantum-informed surrogate sampling for combinatorial optimization

    quant-ph 2026-07 conditional novelty 6.0 of 10

    QISS classically samples a pairwise model built from O(N) low-weight QAOA correlators and outperforms standard QAOA at larger depths on MaxCut and MIS benchmarks.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages · cited by 1 Pith paper

  1. [7]

    Boulebnane and A

    S. Boulebnane and A. Montanaro. Solving boolean satisfiability problems with the quantum approximate optimization algorithm. PRX Quantum, 5:030348, Sep 2024

    work page 2024

  2. [1]

    This amounts to computing the single-clause polynomial, i.e

    1-in-k SAT In this section, we evaluate the instance-averaged success probability ofp = 1 QAOA on 1-in-k-SAT according to the formula stated in proposition 1. This amounts to computing the single-clause polynomial, i.e. Psingle (n′ 000, n′ 001, n′ 010, n′

    work page

  3. [2]

    This results from pairing together original configuration basis numbers adding up to a reeduced configuration basis numbers, i.e

    (53) Proof. This results from pairing together original configuration basis numbers adding up to a reeduced configuration basis numbers, i.e. pairing up q0 s[0] s[−1] , q 1 s[0] s[−1] , (54) where q′ s[0] s[−1] := q0 s[0] s[−1] + q1 s[0] s[−1] . (55) 9 Namely, expanding the multinomial coefficient, the summand reads: q q f (q000 + q111, q001 + q110, q010 ...

    work page

  4. [3]

    Let q ≥ 1 an integer andq ∈ P(q) a weight-q configuration basis number

    (57) One may next for eachs[0], s[−1] ∈ {0, 1} and value ofq′ s[0] s[−1], sum overq0 s[0] s[−1] and q1 s[0] s[−1] such that their sum q′ s[0] s[−1] is fixed; this is done using the standard binomial theorem: X q0 s[0] s[−1] , q1 s[0] s[−1] q0 s[0] s[−1] +q1 s[0] s[−1] =q′ s[0] s[−1] q′ s[0] s[−1] ! q0 s[0] s[−1] !q1 s[0] s[−1] ! = 2q′ s[0] s[−1] (58) The ...

    work page

  5. [4]

    (77) of weight n, and Psingle is the function given by corollary 1, applied to function f x[1], x[0], x[−1] = exp − iγ 2 x[1] − x[−1] 1 − x[0] . (78) More explicitly, Psingle is the unique 4-variate polynomial such that Eσ exp − iγ 2 1 h z[1] ̸⊢ σ i − 1 h z[−1] ̸⊢ σ i 1 − 1 h z[0] ̸⊢ σ i = Eσ exp iγ 2 1 h z[1] ⊢ σ i − 1 h z[−1] ⊢ σ i 1 h z[0] ⊢ σ i = Psin...

    work page

  6. [5]

    Hamming weight

    (94) for brevity. Summing over these variables first, equation 92 becomes: Eσ=(σ0,...,σm−1)⟨Ψ (γ, β,σ) |1 [H [σ] = 0] |Ψ (γ, β,σ)⟩ = 2−n X n′∈P(n) Psingle (n′)m cos2 β 2 n′ 000 sin2 β 2 n′ 010 i sin β 2 n′ 011 − i sin β 2 n′ 001 × X n000, n111 n000+n111=n′ 000 X n001, n110 n001+n100=n′ 001 X n010, n101 n010+n101=n′ 010 X n011, n100 n011+n100=n′ 011 n n000...

    work page

  7. [6]

    Near-term quantum computing for solving hard industrial optimisation problems

    We can approximately estimate this probability by fixing a smalln, in this case 12, generating a large number of random 28 0 1 2 3 4 5 6 7 # true rows in truth table 10 1 100 Clauses-to-Variables Ratio r FIG. 1: The clauses-to-variables ratio for all22k truth tables withk = 3, grouped by the number of true rows in the truth table. Note that statistical no...

    work page

  8. [8]

    = Eσ exp iγ 2 1 h z[1] ⊢ σ i − 1 h z[−1] ⊢ σ i 1 h z[0] ⊢ σ i , (A4) where Eσ denotes a single random clause and z[1], z[0], z[−1] is any bitstring triplet satisfying reduced configuration basis numbers (n′ 000, n′ 001, n′ 010, n′ 011). For the example treated in this section, it will be most convenient to expand the single-clause polynomial as a Boolean ...

    work page

Show all 23 references
  1. [9]

    This problem corresponds to the functionT : {0, 1}k → {0, 1} where T (x) = 1 ⇔ 0 < |x| < k, and |x| denotes the Hamming weight

    NAE-SAT We now study the instance averaged success probability of QAOA on a different constraint satisfaction problem: NAE-SAT (not-all-equal SAT). This problem corresponds to the functionT : {0, 1}k → {0, 1} where T (x) = 1 ⇔ 0 < |x| < k, and |x| denotes the Hamming weight. T...

  2. [10]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm, 2014. 39 12 13 14 15 16 n 0.00050 0.00075 0.00100 0.00125 0.00150 0.00175 0.00200 0.00225Mean Success Probability Analytic formula Fit (analytic formula) Simulations Fit (simulations) FIG. 12...

    2014

  3. [11]

    (49) Similar to notationP(q) introduced in definition 5 for configuration basis numbers, we denote by P ′(q) (50) the set of reduced configuration basis numbers of weightq

    (48) indexed by 2-bit bitstrings s ∈ {0, 1}2 and summing toq: X s∈{0,1}2 q′ s = q′ 00 + q′ 01 + q′ 10 + q′ 11 = q. (49) Similar to notationP(q) introduced in definition 5 for configuration basis numbers, we denote by P ′(q) (50) the set of reduced configuration basis numbers o...

  4. [12]

    Marwaha and S

    K. Marwaha and S. Hadfield. Bounds on approximating MaxkXOR with quantum and classical local algorithms.Quantum, 6:757, July 2022

    2022

  5. [13]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou. The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size.Quantum, 6:759, July 2022

    2022

  6. [14]

    Basso, D

    J. Basso, D. Gamarnik, S. Mei, and L. Zhou. Performance and limitations of the qaoa at constant levels on large sparse hypergraphs and spin glass models. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, October 2022

    2022

  7. [15]

    Basso, E

    J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou. The Quantum Approximate Optimization Algorithm at 40 k r β γ a b 4 4.972710556317915 5.5 1.1 −0.1770989003 −0.5304733689 6 21.583456938459364 5.6 0.9 −0.5625334157 −0.6162079454 8 88.12349051732973 5.7 0.8 −1.04465954...

    2022

  8. [16]

    L. Zhou, J. Basso, and S. Mei. Statistical estimation in the spiked tensor model via the quantum approximate optimization algorithm, 2024

    2024

  9. [17]

    T. Hogg. Quantum search heuristics.Phys. Rev. A, 61:052311, Apr 2000

    2000

  10. [18]

    F. G. S. L. Brandao, M. Broughton, E. Farhi, S. Gutmann, and H. Neven. For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances, 2018

    2018

  11. [19]

    Boulebnane and A

    S. Boulebnane and A. Montanaro. Predicting parameters for the quantum approximate optimization algorithm for max-cut from the infinite-size limit, 2021

    2021

  12. [20]

    Claes and W

    J. Claes and W. v. Dam. Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size.Quantum, 5:542, September 2021

    2021

  13. [21]

    J. H. Liang, V. Ganesh, P. Poupart, and K. Czarnecki. Learning rate based branching heuristic for SAT solvers. InTheory and Applications of Satisfiability Testing - SAT 2016 - 19th International Conference, Bordeaux, France, July 5–8, 2016, Proceedings, pages 123–140, 2016

    2016

  14. [22]

    T. Walsh. The interface between P and NP: COL, XOR, NAE, 1-in-k and Horn SAT. InEighteenth national conference on Artificial intelligence, pages 695–700, 2002

    2002

  15. [23]

    J. Ding, A. Sly, and N. Sun. Satisfiability threshold for random regular nae-sat.Communications in Mathematical Physics, 341(2):435–489, November 2015

    2015

Pith tools

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