{"id":"a7364874-2f80-4e19-92c5-7355137122c9","arxiv_id":"2411.17442","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A framework computes one-layer QAOA success probabilities for arbitrary random boolean CSPs, and the comparison singles out random k-SAT as the most promising target for a quantum speedup.","lead":"This paper gives a classical algorithm that computes the average success probability of one-layer QAOA on random boolean constraint satisfaction problems. The comparison of many problem families suggests random k-SAT is the most promising candidate for a quantum-classical separation, although one-layer QAOA does not beat the classical solver MapleSAT.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised O(k^7) precomputation for general truth tables is unsupported: Proposition 4 requires coefficients |Z(y,k)| for which no polynomial-in-k algorithm is given, and the obvious enumeration is exponential in k.","rationale":"The reader's weakest assumption concerns the empirical satisfiability-threshold estimate at n=12 with 200 instances. That is a legitimate quantitative concern and can bias the reported scaling exponents. However, the most load-bearing issue is different: the paper's headline technical contribution is a polynomial-in-k algorithm for general CSPs, and the proof as written stops short of showing how the coefficients |Z(y,k)| in Proposition 4 are computed. For a general truth table, these coefficients count triples of k-bit strings under arbitrary predicates, and the natural computation is exponential in k; because the input truth table itself has 2^k entries, an O(k^7) algorithm is information-theoretically impossible in the standard model unless a compact input representation is assumed, which the paper does not state. This is an internal gap in the central claim, not merely a matter of numerical calibration. The practical comparisons for k=3,4,5 are not necessarily wrong, since exhaustive enumeration is feasible in that regime, and Proposition 1's n-scaling remains O(n^3) once Psingle is known. Therefore the appropriate verdict is CONDITIONAL: the paper should either supply a real polynomial algorithm for the general case, or explicitly restrict the polynomial-in-k claim to the Hamming-weight family (or to fixed k). The reader's threshold concern is real but secondary; it affects the quantitative comparison, not the validity of the core formula. I therefore disagree with the reader's choice of weakest assumption: the O(k^7) precomputation gap is more directly load-bearing for the paper's central claim.","tokens_in":39287,"tokens_out":10232,"duration_ms":105903,"concrete_test":"Implement the general-truth-table precomputation implied by Section IVB for random truth tables with k=6,7,8,9, computing the coefficients |Z(y,k)| by the only method specified (enumeration of all 2^{3k} triples), and fit the wall-clock time as a function of k. If the runtime grows like 8^k rather than k^7, the advertised O(k^7) complexity is refuted. Separately, check whether the manuscript specifies any compact representation of the truth table that would avoid the unavoidable 2^k cost of reading a general table; if no such representation is stated, the polynomial-in-k claim is impossible as written.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central technical claim is that the instance-averaged p=1 QAOA success probability can be computed in time polynomial in n and k, with an O(k^7) precomputation of the single-clause polynomial (abstract, Section III, Proposition 1). This is clean for Hamming-weight truth tables, where Proposition 2 gives an explicit combinatorial expression. For the advertised general-truth-table case, however, Proposition 4 reduces Psingle to a sum over y and k of terms involving |Z(y,k)|, the number of triples of k-bit strings with prescribed truth values T(w1), T(w0), T(w-1) and prescribed joint column counts. The paper never specifies how |Z(y,k)| is computed. The only evident method is exhaustive enumeration over 2^{3k} bitstring triples per truth table, and since a fully general truth table has 2^k entries, any algorithm that reads the table must take time at least 2^k. Thus the stated O(k^7) complexity cannot hold for the general case as formulated. This does not invalidate the numerical results for k=3,4,5, where enumeration is feasible, but it undermines the main advertised generalization: the formula is correct only after an exponential-in-k (or otherwise unspecified) coefficient precomputation. The paper should either provide a genuine polynomial algorithm for |Z(y,k)| under a stated compact input model, or explicitly restrict the polynomial claim to fixed k or to Hamming-weight tables.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":39645,"tokens_out":8028,"duration_ms":95160,"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":[{"comment":"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.","section":"Introduction item 1; Section III; Definition 13; Proposition 4"},{"comment":"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.","section":"Section V.A; Figures 1 and 2"},{"comment":"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.","section":"Section V.B; Section V.C; Figures 5-8"}],"minor_comments":[{"comment":"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.","section":"Definition 3"},{"comment":"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}.","section":"Definition 11"},{"comment":"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}'.","section":"Appendix A.1, equations (A13)-(A15)"},{"comment":"The garbled strings '22k' and 'B2k' presumably denote 2^{2^k} and B^{2^k}; these should be typeset correctly.","section":"Figure 1 caption and Section V.B"},{"comment":"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.","section":"Section V.A"}],"recommendation":"major_revision","confidential_remarks":"The main advertised generalization to fully general truth tables with polynomial-in-k complexity is overstated; the authors should either prove the missing coefficient computation or explicitly restrict the polynomial-time claim. Everything else in the derivation appears sound, and the numerical validation of the special cases is credible, so I see this as a major-revision issue rather than a rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know two things about this paper. The core contribution—formulas for instance-averaged p=1 QAOA success probabilities for arbitrary boolean CSPs—is real and mostly careful. But the advertised O(k^7) complexity for general truth tables is not supported as stated. The count |Z(y,k)| in Proposition 4 requires reading a 2^k-entry truth table unless you restrict to fixed k or Hamming-weight tables. The reader's report missed this. The fixed-k numerical results stand, but the \"polynomial in n and k\" headline overclaims.\n\nWhat's new: Boulebnane et al. extend the configuration-basis technique from k-SAT to all boolean CSPs with k-ary constraints. For Hamming-weight truth tables, Proposition 2 gives an explicit closed form. For general tables, Proposition 4 expresses the single-clause polynomial in terms of counts of bitstring triplets with given truth values and configuration. They compute all k=3 truth tables and selections for k=4,5, and compare QAOA exponents against MapleSAT. The NAE-SAT and 1-in-k-SAT appendix results are checked against state-vector simulations; that is genuine evidence and should count for something.\n\nWhere it gets soft. First, the complexity hole. The general-truth-table formula is correct, but the paper never says how |Z(y,k)| is computed. Since the input is a 2^k-entry table, any procedure that reads the table takes at least 2^k time. The O(k^7) claim in the abstract and Section III cannot hold for the general case unless the input model is compact and a genuine polynomial algorithm is supplied. This doesn't invalidate k=3,4,5 numerics (enumeration is fine there), but it changes the paper's scope claim from \"general CSPs, polynomial in k\" to \"fixed k, polynomial in n.\" That's a significant downgrade.\n\nSecond, the empirical inputs are rougher than the presentation suggests. The satisfiability threshold r is estimated from n=12 and only 200 instances, then used as the clause density for both QAOA and MapleSAT. If the asymptotic threshold differs from this small-instance estimate, the exponent comparison is biased. The QAOA angles are chosen from a 50x50 uniform grid; no guarantee they're optimal. These are acknowledged limits, but they make the \"k-SAT is most promising\" conclusion conditional, which the paper does state.\n\nThird, no code or data is provided. The appendix simulations give confidence, but independent reproduction requires reimplementation.\n\nSo: the paper is worth engaging. For someone benchmarking QAOA against classical solvers on random CSPs, the fixed-k formulas and the k=3 map are useful. The NAE-SAT and 1-in-k-SAT checks are solid. But the complexity claim needs to be corrected before publication, and the exponent comparisons should be framed as estimates. I'd accept it for peer review and ask for those fixes.","headline":"Solid fixed-k formulas for p=1 QAOA on random CSPs, but the advertised O(k^7) complexity for general truth tables is unsupported.","tokens_in":40156,"tokens_out":2685,"would_cite":true,"duration_ms":24994,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":["03.67.Ac"],"model":"deepseek-v4-flash","headline":"A single classical formula now predicts one-layer QAOA success on any random Boolean constraint problem.","keywords":["QAOA","constraint satisfaction problems","random k-SAT","satisfiability threshold","configuration basis numbers","single-clause polynomial","MapleSAT","quantum-classical separation"],"falsifier":"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.","tokens_in":39127,"feed_emoji":"⚛️","tokens_out":3887,"duration_ms":38945,"temperature":0.7,"pith_summary":"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.","feed_headline":"Formula predicts QAOA odds for every random CSP","feed_subtitle":"One-layer quantum search is now comparable across all 3-bit constraint families, pointing to k-SAT as the best bet.","key_machinery":"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}$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces QAOA, the algorithm whose success probability this paper computes.","marker":"[1]"},{"why":"Supplies the configuration-basis-number technique for average-case QAOA analysis, adapted here to general CSPs.","marker":"[3]"},{"why":"Provides the related constant-depth QAOA performance analysis whose complexity scaling motivates the $p>1$ discussion.","marker":"[4]"},{"why":"The prior $k$-SAT QAOA study that this paper generalizes and whose conclusions are the benchmark for quantum-classical separation.","marker":"[7]"},{"why":"MapleSAT is the classical SAT solver whose experimental runtime scaling serves as the classical baseline.","marker":"[12]"},{"why":"Gives satisfiability thresholds for several CSP families used to set the clause density for 1-in-$k$-SAT.","marker":"[13]"},{"why":"Provides the random NAE-SAT threshold used for the appendix simulations and fits.","marker":"[14]"}],"fun_headline_variants":["QAOA odds formula: closed-form for any random CSP","Polynomial-time QAOA success probability for all random CSPs","k-SAT tops QAOA viability among random 3-bit constraints","One-layer QAOA: exact average success odds for every CSP","QAOA vs MapleSAT: random k-SAT shows strongest quantum promise"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["QAOA odds formula: closed-form for any random CSP","Polynomial-time QAOA success probability for all random CSPs","k-SAT tops QAOA viability among random 3-bit constraints","One-layer QAOA: exact average success odds for every CSP","QAOA vs MapleSAT: random k-SAT shows strongest quantum promise"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00024,"raw_usage":{"total_tokens":1490,"prompt_tokens":892,"completion_tokens":598,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":508,"completion_tokens_details":{"reasoning_tokens":510}},"tokens_in":508,"tokens_out":598,"duration_ms":7273,"temperature":1.0,"reasoning_tokens":510,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:06:14.721930+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"This amounts to computing the single-clause polynomial, i.e","cited_arxiv_id":null,"evidence_quote":"Introduces QAOA, the algorithm whose success probability this paper computes."},{"cited_title":"Let q ≥ 1 an integer andq ∈ P(q) a weight-q configuration basis number","cited_arxiv_id":null,"evidence_quote":"Supplies the configuration-basis-number technique for average-case QAOA analysis, adapted here to general CSPs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the related constant-depth QAOA performance analysis whose complexity scaling motivates the $p>1$ discussion."},{"cited_title":"Boulebnane and A","cited_arxiv_id":null,"evidence_quote":"The prior $k$-SAT QAOA study that this paper generalizes and whose conclusions are the benchmark for quantum-classical separation."},{"cited_title":"Marwaha and S","cited_arxiv_id":null,"evidence_quote":"MapleSAT is the classical SAT solver whose experimental runtime scaling serves as the classical baseline."},{"cited_title":"Farhi, J","cited_arxiv_id":null,"evidence_quote":"Gives satisfiability thresholds for several CSP families used to set the clause density for 1-in-$k$-SAT."},{"cited_title":"Basso, D","cited_arxiv_id":null,"evidence_quote":"Provides the random NAE-SAT threshold used for the appendix simulations and fits."}],"review_version":1}