{"id":"371d2489-97d7-4a76-b559-3baeeb2dfe7f","arxiv_id":"2411.19388","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Numerical simulations of random Max-kXOR with k=3 to 10 show the classical MF-AOA benchmark matches or outperforms the QAOA on average, and reaching high approximation ratios would require very large circuit depths.","lead":"This paper tests how well two algorithms, the quantum QAOA and a classical mean-field approximation, solve random constraint-satisfaction problems where each clause links k variables. It finds the classical baseline matches or beats the quantum algorithm, and that reaching near-optimal answers would need very deep quantum circuits.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'extremely large p' conclusion rests on linear-interpolation angle optimization that the paper itself reports as saturating; better optimization (Fourier-based) may yield faster M_p growth, invalidating the extrapolated p estimates.","rationale":"Reader's verdict is CONDITIONAL with medium correctness risk, identifying exactly the angle-optimization heuristic as the weakest assumption. My independent read reaches the same conclusion: the paper's quantitative extrapolation—the backbone of its 'extremely large p' message—is produced from data where p > 3 angles come from a heuristic that the authors admit saturates after p = 30 and is inferior to Fourier-based optimization. Because the QAOA's true performance for a fixed p is independent of the optimization routine, the reported M_p curve is a lower bound, and a better optimizer could raise it substantially. This does not refute the paper's qualitative conclusion, but it makes the strong quantitative claims (p ~ 50–770 for 99%) less secure. The MF-AOA comparison and the qualitative decline of M_p with k are less affected, but they do not rescue the extrapolated p scales. Thus the appropriate verdict remains CONDITIONAL: the numerical evidence should be reproduced with better angle optimization before asserting that high satisfaction requires 'extremely large p.' No change from the reader's verdict.","tokens_in":11432,"tokens_out":3045,"duration_ms":25866,"concrete_test":"Run a controlled comparison at N = 18, r = 1.5, k = 10 (and k = 3 as a check): optimize QAOA angles using the Fourier-based parameterization from Zhou et al. (or a global optimizer with many restarts) for p = 30, 40, 50, 60, 80 on the same 100 random instances used in Fig. 4, and compute ensemble-averaged M_p. If the resulting M_p grows with p (e.g., slope larger than c = 0.06 or M_p at p = 60 exceeds the log-extrapolation by more than a few percent), the 'extremely large p' estimate is an optimization artifact.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that reaching high satisfaction levels requires extremely large p—is inferred by fitting M_p for p=1..30 (Fig. 4) to a logarithmic curve and extrapolating to M_p = 0.90/0.99. For p > 3, angles are optimized with the linear-interpolation heuristic of Zhou et al.; Section IV.D states that 'Beyond p = 30, the linear-interpolation method shows no further improvement. In contrast, the Fourier-based approach... demonstrates promising performance for p > 30.' Because the QAOA's true approximation ratio for fixed p is the maximum over all angles, any heuristic returning suboptimal angles yields a lower bound on true QAOA performance. The slow improvement and saturation with p may therefore be an artifact of the optimizer, not an intrinsic property of the QAOA family. Since the extrapolated p values (e.g., p ≈ 770 for k = 10) are the quantitative basis for the negative conclusion, this is load-bearing. The paper's own text identifies the avenue that could falsify it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes the Quantum Approximate Optimization Algorithm (QAOA) on random Max-kXOR instances for k=3,...,10, using k-local Pauli-Z cost Hamiltonians and comparing against the classical Mean-Field Approximate Optimization Algorithm (MF-AOA). The authors study the approximation ratio as a function of the clause-to-variable ratio r, the locality k, and the QAOA layer count p, mostly at N=18. They report that MF-AOA matches or exceeds QAOA on average, that QAOA's approximation ratio decreases with k, and that parameters optimized at N=18 transfer to larger system sizes. The central quantitative claim is obtained by fitting the numerical Mp(p) data for p up to 30 to a logarithmic ansatz and extrapolating to estimate the p needed to reach 90% and 99% approximation ratios: about p=50 for k=3 and p=770 for k=10. From this they conclude that reaching high satisfaction levels would require extremely large p and that QAOA might not show an advantage over classical algorithms on these problems.","tokens_in":11762,"tokens_out":4737,"duration_ms":44822,"significance":"If the extrapolated conclusion were reliable, the paper would provide useful numerical evidence against a QAOA advantage for generic higher-order constraint-satisfaction problems, complementing analytic overlap-gap results for even k. The work has notable strengths: it covers both odd and even k in a systematic way, uses publicly available data, and makes a concrete comparison with a classical mean-field benchmark, including the observation that optimized QAOA parameters appear to transfer across system sizes. The significance is currently conditional, however, because the paper's main quantitative prediction rests on a heuristic extrapolation and on angle optimization that the paper itself reports as saturating. The paper is likely to be of interest to the quantum-optimization community, but the central claim needs substantially more statistical and algorithmic support before it can be accepted at face value.","major_comments":[{"comment":"The central quantitative claim—that reaching high approximation ratios requires p approximately 50 for k=3 and p approximately 770 for k=10—rests on fitting Mp(p) for p=1,...,30 to a logarithmic ansatz and extrapolating. The text reports no confidence intervals, no residual analysis, and no sensitivity study for this extrapolation. With only 30 data points and an extrapolation by more than an order of magnitude, the logarithmic form is an unsupported assumption beyond the fitted range. The authors should report fit parameters with uncertainties, prediction bands, and the sensitivity of the estimated p-values to the choice of ansatz and to the exclusion of the p=1 data point.","section":"Section IV.D, Figures 4 and 6"},{"comment":"Mp is defined in Eq. (12) as the maximum over the variational parameters, but for p>3 the reported values are not global maxima: the text states that the linear-interpolation strategy of Zhou et al. is used and that beyond p=30 this method shows no further improvement, while the Fourier-based approach 'demonstrates promising performance for p>30.' Since any heuristic angle optimization gives a lower bound on the true QAOA approximation ratio, the extrapolated p-values are upper bounds on the depth actually needed, not evidence that extremely large p is necessary. To support the paper's negative conclusion, the authors must either optimize the angles more thoroughly (e.g., with the Fourier-based parameterization) for the extrapolation range, or explicitly reframe the claim as an upper-bound estimate.","section":"Section IV.D and Eq. (12)"},{"comment":"The classical MF-AOA benchmark depends on the catalyst standard deviation sigma, which is chosen per k and r in Table II, and the authors acknowledge that sampling more random catalysts could improve MF-AOA. The claim that MF-AOA performs better than or equal to QAOA on average is therefore conditional on an ad hoc tuning choice, and no time-to-solution or computational-resource comparison is provided. Since the conclusion is framed as a possible absence of quantum advantage, a fair classical benchmark should include a defined resource budget (number of catalyst samples, wall-clock time, or equivalent) and a sensitivity analysis with respect to the catalyst distribution.","section":"Section IV.F, Table II and Eq. (17)"},{"comment":"All high-depth QAOA simulations are performed at N=18, and the extrapolated p-values are therefore specific to N=18 and r=1.5. The transfer of angles from N=18 to larger N in Figure 7 tests parameter universality but does not test the actual optimized QAOA approximation ratio at larger N. The abstract's language about 'generic' higher-order constraint-satisfaction problems goes beyond what the numerical evidence directly supports; the extrapolation should be clearly restricted to the studied instance ensemble, or additional data at larger N should be provided.","section":"Section IV.E and Figure 7"}],"minor_comments":[{"comment":"The caption contains a typo: 'ensemble-averade' should be 'ensemble-averaged'.","section":"Figure 5 caption"},{"comment":"The text refers to 'Table III B' when the relevant table is Table II; the cross-reference should be corrected.","section":"Section III.B, Table II"},{"comment":"The phrase 'circuit depth p' is potentially misleading: for k-local Max-kXOR Hamiltonians, the physical circuit depth includes the decomposition of k-body Pauli-Z strings into two-qubit gates, which is more than p layers. The paper should distinguish the QAOA layer count p from the physical circuit depth.","section":"Section IV.D"},{"comment":"The exponential and polynomial fits shown as dotted curves are not described by explicit equations, fit parameters, or uncertainties, making the reported RMSE values impossible to verify.","section":"Figure 6"},{"comment":"The decision to exclude the p=1 data point from the logarithmic fit is not justified. The authors should report how the extrapolated p-values change when p=1 is included, since this affects the central estimate.","section":"Section IV.D"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a timely and important question, and the numerical study is a useful contribution. My main concern is that the abstract and conclusion present the extrapolated p-values as predictive lower bounds on the required circuit depth, whereas the heuristically optimized angles make them upper bounds that could be severe overestimates. The revision should focus on reframing the claims, adding uncertainty quantification, and strengthening the MF-AOA benchmark comparison. I see no evidence of misconduct; the issues are statistical and methodological."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe main new thing here is numerical evidence on QAOA for random Max-kXOR with odd k and k up to 10, which complements the analytic even-k results of Basso et al. The paper also introduces a generalized mean-field classical benchmark (MF-AOA) for arbitrary k-spin interactions and makes all data public. That is genuinely useful.\n\nThe paper does several things carefully. The instance generation correctly handles the parity-sign redundancy in XOR clauses. They map out the r-dependence and identify the hard regime around r=1.5. The observation that parameters optimized at N=18 transfer well to larger sizes is interesting and practically relevant. They are also honest about limitations, explicitly noting that their linear-interpolation optimizer saturates beyond p=30 while a Fourier-based approach looks more promising, and that MF-AOA could be improved by sampling more catalyst instantiations.\n\nThe soft spots are real, though. The headline quantitative claim—that reaching 99% approximation requires p≈770 for k=10—comes from fitting Mp(p) for p up to 30 and extrapolating to p in the hundreds, with no confidence intervals. More importantly, for p>3 they use the Zhou linear-interpolation heuristic, which the paper itself admits is suboptimal. Since Mp is a maximum over angles, every measured point is a lower bound on true QAOA performance. If a better optimizer gives a faster-growing Mp(p), the extrapolated p-values would be too pessimistic. That does not kill the qualitative conclusion—the downward trend with k is consistent with Basso et al.'s analytic work—but it means the specific p-numbers in the abstract should not be taken at face value. The same caution applies to the QAOA vs MF-AOA comparison: the catalyst sigma is hand-tuned, though they rightly note that more sampling could only improve the classical side.\n\nWho should read this? Anyone benchmarking QAOA on CSPs or studying classical simulation of variational algorithms. It is a competent numerical study with a clear negative message, but the message is based on extrapolation and an optimizer that is known to be suboptimal. I would send it to peer review, with a request for confidence intervals and either a better optimizer for p>30 or a softened claim in the abstract. The data being public makes it a useful reference regardless.","headline":"A useful numerical complement to the even-k analytic results on Max-kXOR, with a reasonable classical baseline, but the headline p-extrapolation is the weak link and should be treated as suggestive rather than quantitative.","tokens_in":12199,"tokens_out":3095,"would_cite":true,"duration_ms":28092,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper argues that the QAOA would need prohibitively deep circuits to outperform a classical mean-field benchmark on random Max-kXOR problems.","keywords":["QAOA","Max-kXOR","constraint satisfaction","approximation ratio","mean-field optimization","clause-to-variable ratio","circuit depth","quantum optimization advantage"],"falsifier":"Run the same random Max-kXOR ensembles at $r = 1.5$ for $k = 3$ to 10, optimize the QAOA angles up to $p = 100$ with a global or Fourier-based strategy, and check whether the ensemble-averaged approximation ratio rises faster than logarithmically in $p$; a visible speedup would invalidate the extrapolated $p \\approx 50$ to 770 depth requirements.","tokens_in":11197,"feed_emoji":"⚛️","tokens_out":9173,"duration_ms":71192,"temperature":0.7,"pith_summary":"This paper asks whether the Quantum Approximate Optimization Algorithm (QAOA) can outperform classical methods on random Max-kXOR problems, a family of higher-order constraint-satisfaction problems where each clause is an exclusive OR of $k$ variables and the goal is to maximize the number of satisfied clauses. The authors compare the QAOA against a classical mean-field approximate optimization algorithm (MF-AOA) across clause-to-variable ratios and clause sizes $k$ from 3 to 10. They find that the QAOA matches or falls behind the classical benchmark on average, with its approximation ratio improving only logarithmically with the number of layers $p$. Extrapolating that trend, reaching 99 percent of the ground-state energy would require roughly $p = 50$ layers for $k = 3$ and $p = 770$ layers for $k = 10$, depths that are impractical on near-term noisy hardware. The paper concludes that a QAOA advantage on generic random Max-kXOR instances is unlikely.","feed_headline":"770 layers: QAOA's estimated depth for hard random Max-kXOR","feed_subtitle":"A cheap classical mean-field benchmark matches or beats the quantum optimizer across instance ratios and clause orders.","key_machinery":"The cost function of a Max-kXOR instance maps to a sum of $k$-local Pauli-Z strings, so the QAOA phase separator is $\\exp(-i\\gamma \\hat{Z}_{i_1}\\cdots\\hat{Z}_{i_k})$ and its driver is a single-qubit $X$ field. The comparison is carried by the ensemble-averaged approximation ratio $M_p$, the optimized expectation value normalized between the minimum and maximum cost. As a classical benchmark, the paper generalizes mean-field approximate optimization to $k$-spin interactions: classical Bloch vectors evolve under the mean-field equations of motion of an adiabatic Hamiltonian, with a random catalyst field that breaks $\\mathbb{Z}_2$ symmetry. The central quantitative device is the logarithmic fit of $M_p$ versus $p$, from which the number of layers needed to reach 90 and 99 percent approximation is extrapolated.","core_discovery":"On random Max-kXOR instances with $N = 18$, the ensemble-averaged QAOA approximation ratio decreases as the clause-to-variable ratio $r$ grows and as the clause size $k$ grows, and increasing $p$ mostly shifts the curve upward rather than improving its scaling. Averaged over instances, the classical MF-AOA performs better than or equal to the QAOA, while the QAOA overtakes it only at circuit depths that grow quickly with $k$. Fitting the $p$-dependence as logarithmic and extrapolating gives $p \\approx 50$ for $k = 3$ and $p \\approx 770$ for $k = 10$ to reach a 99 percent approximation ratio at $r = 1.5$, and the required depth grows steeply with $k$. The paper takes this as numerical evidence that the limitation previously shown analytically for even $k$ extends to odd $k$ as well.","pith_inferences":["If a more thorough global angle optimization strategy for $p > 30$ (for example the Fourier-based strategy that the paper notes performs better at depth) yields faster-than-logarithmic growth in the approximation ratio, the extrapolated layer counts would be too pessimistic; the paper's own comparison flags this as a real possibility.","The contrast with earlier uniform-instance studies, where the QAOA's approximation ratio improves with $k$, suggests that the presence or absence of random structure in the clause ensemble may be the deciding factor for whether QAOA helps.","Because the MF-AOA is a cheap classical baseline, this comparison suggests that future QAOA advantage claims should be measured against mean-field-style classical dynamics, not only against specialized solvers.","The observed parameter universality across system sizes yields a testable prediction: the optimal angles found at $N = 18$ should keep working on much larger random Max-kXOR instances, which could be checked with tensor-network simulations or hardware."],"forward_implications":["For hard random Max-kXOR instances, the QAOA's approximation ratio improves only logarithmically with the number of layers $p$, so reaching high approximation ratios requires circuit depths that grow steeply with $k$.","A classical mean-field algorithm with negligible computational cost matches or beats the QAOA on average for $k$ from 3 to 10 at $r = 1.5$, so any practical QAOA advantage would require deep circuits and expensive angle optimization.","The QAOA's optimized parameters transfer from $N = 18$ to larger systems, keeping the approximation ratio nearly constant, which indicates that the depth requirements are not a small-system-size artifact.","The inefficiency previously established analytically for even $k$ appears, on this numerical evidence, to hold for odd $k$ as well."],"supporting_citations":[{"why":"Defines the QAOA ansatz whose performance on Max-kXOR is the subject of the paper.","marker":"[2]"},{"why":"Provides the recent 8-SAT scaling-advantage claim that motivates testing whether similar advantages appear for Max-kXOR.","marker":"[4]"},{"why":"Establishes limitations of local quantum algorithms on random Max-kXOR, which the paper extends numerically to odd k.","marker":"[21]"},{"why":"Gives the analytic even-k result that the paper's numerical evidence generalizes to all k.","marker":"[23]"},{"why":"Reports better QAOA performance on uniform Max-kXOR instances, the contrast case for the paper's random-instance results.","marker":"[19]"},{"why":"Introduces the mean-field approximate optimization algorithm used as the classical benchmark.","marker":"[28]"},{"why":"Supplies the linear-interpolation and Fourier-based angle-optimization methods used for p > 3, including the high-depth extrapolation.","marker":"[34]"},{"why":"Supports the paper's observation that parameters optimized at one system size carry over to larger instances.","marker":"[13]"},{"why":"Motivates the practical conclusion that deep circuits are infeasible on near-term devices because of limits on error mitigation.","marker":"[6]"}],"fun_headline_variants":["Classical mean-field matches or beats QAOA on Max-kXOR","QAOA needs ~770 layers to match classical on Max-kXOR","Extrapolated QAOA depth: 770 layers for hard Max-kXOR","Quantum optimizer lags classical mean-field on Max-kXOR","Hard Max-kXOR: QAOA requires enormous circuit depth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The conclusion that reaching high satisfaction levels needs extremely large $p$ rests on extrapolating the approximation-ratio growth from simulations in which the QAOA angles for $p > 3$ were chosen by a linear-interpolation heuristic rather than by a global optimization search; if better angle optimization makes the ratio grow faster in $p$, the extrapolated layer counts are too pessimistic.","fun_headline_variants_meta":{"raw":{"variants":["Classical mean-field matches or beats QAOA on Max-kXOR","QAOA needs ~770 layers to match classical on Max-kXOR","Extrapolated QAOA depth: 770 layers for hard Max-kXOR","Quantum optimizer lags classical mean-field on Max-kXOR","Hard Max-kXOR: QAOA requires enormous circuit depth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000279,"raw_usage":{"total_tokens":1647,"prompt_tokens":926,"completion_tokens":721,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":627}},"tokens_in":542,"tokens_out":721,"duration_ms":6198,"temperature":1.0,"reasoning_tokens":627,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:12:45.730998+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same random Max-kXOR ensembles at $r = 1.5$ for $k = 3$ to 10, optimize the QAOA angles up to $p = 100$ with a global or Fourier-based strategy, and check whether the ensemble-averaged approximation ratio rises faster than logarithmically in $p$; a visible speedup would invalidate the extrapolated $p \\approx 50$ to 770 depth requirements.","supporting_citations":[{"cited_title":"Boulebnane and A","cited_arxiv_id":null,"evidence_quote":"Provides the recent 8-SAT scaling-advantage claim that motivates testing whether similar advantages appear for Max-kXOR."},{"cited_title":"Basso, D","cited_arxiv_id":null,"evidence_quote":"Gives the analytic even-k result that the paper's numerical evidence generalizes to all k."},{"cited_title":"Marwaha and S","cited_arxiv_id":null,"evidence_quote":"Reports better QAOA performance on uniform Max-kXOR instances, the contrast case for the paper's random-instance results."},{"cited_title":"Misra-Spieldenner, T","cited_arxiv_id":null,"evidence_quote":"Introduces the mean-field approximate optimization algorithm used as the classical benchmark."},{"cited_title":"Zhou, S.-T","cited_arxiv_id":null,"evidence_quote":"Supplies the linear-interpolation and Fourier-based angle-optimization methods used for p > 3, including the high-depth extrapolation."},{"cited_title":"Farhi, J","cited_arxiv_id":null,"evidence_quote":"Supports the paper's observation that parameters optimized at one system size carry over to larger instances."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Motivates the practical conclusion that deep circuits are infeasible on near-term devices because of limits on error mitigation."}],"review_version":1}