Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems

Ajainderpal Singh; Frank K. Wilhelm; Thorge M\"uller; Tim Bode

REVIEW 4 major objections 5 minor 34 references

Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems

T0 review · 4 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 This paper argues that the QAOA would need prohibitively deep circuits to outperform a classical mean-field benchmark on random Max-kXOR problems.

desk verdict 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. read the letter →

arxiv 2411.19388 v1 pith:UQRFFR72 submitted 2024-11-28 quant-ph

Thorge Müller , Ajainderpal Singh , Frank K. Wilhelm , Tim Bode This is my paper · ORCID

classification quant-ph

keywords QAOAMax-kXORconstraintsatisfactionapproximationratiomean-fieldoptimizationclause-to-variablecircuitdepthquantumadvantage

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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague,

The 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.

The 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.

The 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.

Who 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.

Referee Report

4 major / 5 minor

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.

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 (4)

[Section IV.D, Figures 4 and 6] 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 IV.D and Eq. (12)] 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 IV.F, Table II and Eq. (17)] 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 IV.E and Figure 7] 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.

minor comments (5)

[Figure 5 caption] The caption contains a typo: 'ensemble-averade' should be 'ensemble-averaged'.
[Section III.B, Table II] The text refers to 'Table III B' when the relevant table is Table II; the cross-reference should be corrected.
[Section IV.D] 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.
[Figure 6] 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 IV.D] 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.

Circularity Check

2 steps flagged · score 6.0 of 10

The predicted p-values (e.g., p≈770) are the inverse of the paper's own logarithmic fit, making the 'extremely large p' conclusion statistically forced by the fitted ansatz.

fitted input called prediction [Section IV.D, Figure 6 and following text]
"Specifically, we fit the data from Figure 4 to a logarithmic ansatz (see inset of Figure 4). To improve the accuracy of the fit for higher p values, we exclude the first data point (p = 1). By extrapolating the resulting fits to high p, we can estimate the p-value at which a given Mp is achieved. For lower values of k (e.g., k = 3), a circuit depth of p ≈ 50 is required to reach 99% of the ground-state energy. For larger k (e.g., k = 10), this increases to approximately p = 770 layers."

The reported p-values (p≈50, p≈770) are not independently measured or derived from a first-principles bound; they are obtained by solving the fitted logarithmic curve for the p at which M_p reaches a threshold. This is an algebraic inversion of the fit, so each predicted p is statistically forced by the fitted ansatz and by the M_p(p) data used to fit it. The abstract's 'extremely large p' conclusion therefore reduces, by construction, to the fitted curve and to the angle-optimization heuristic that produced the data. The paper itself notes that the linear-interpolation optimization saturates beyond p=30 while the Fourier-based method 'demonstrates promising performance for p > 30,' so the fitted curve may reflect optimizer limits rather than an intrinsic QAOA approximation-ratio bound.
fitted input called prediction [Section IV.D, text following Figure 6]
"This trend suggests that an exponentially larger number of layers is required to reach the ground state for high values of k. [...] In Figure 6, we plot the required p to reach various ensemble-averaged approximation ratio thresholds Mp as a function of k. The value of p is determined by fitting a logarithmic function to Figure 4. The dotted curves represent exponential and polynomial fits, along with the Root-Mean-Squared Error (RMSE) of each fit."

The 'exponential' growth of required p with k is presented as a trend from the data, but the p-values plotted in Figure 6 are themselves outputs of the logarithmic fits to M_p(p). Fitting an exponential (or polynomial) curve to those extrapolated points and reporting RMSE values compares two fitting ansätze on the same constructed numbers; it does not provide independent evidence for exponential scaling. The exponential claim is thus a second-order fitted prediction, forced by the choice of ansatz rather than derived from the problem structure or from an external benchmark.

full rationale

The quantitative core of the negative conclusion — that reaching 90%/99% approximation requires p≈50 to p≈770 — is obtained by fitting M_p(p) for p=1..30 to a logarithmic ansatz and solving for the p that reaches the threshold. Solving the fitted equation for p is an algebraic inversion of the fit, so these p-values carry no information beyond the fitted curve: the 'prediction' is statistically forced by the ansatz. The same holds for the claim of exponential growth of required p with k, which is an exponential curve fitted to those already-extrapolated p-values. The paper is transparent about this procedure (Section IV.D), and the underlying M_p data and the MF-AOA comparison are self-contained numerical evidence; the MF-AOA self-citation (Ref. [28]) is not load-bearing because the algorithm is implemented and run here. There is no self-citation chain or definitional identification of the conclusion with a premise. However, because the abstract's headline 'extremely large p' rests on these fit-inverted extrapolations, the central quantitative prediction reduces by construction to the fitted ansatz. The paper's own observation that the linear-interpolation angle optimization saturates beyond p=30 while the Fourier-based approach 'demonstrates promising performance for p > 30' further indicates that the fitted data may reflect optimizer limits rather than intrinsic QAOA performance, which compounds the fit-forced extrapolation (a correctness risk, not an additional circularity). Overall: partial circularity in the quantitative predictions, score 6.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical entities. Its central quantitative claims rest on two fitted inputs: the hand-tuned MF-AOA catalyst width and the logarithmic fit coefficients used for extrapolation. The mean-field benchmark, the random-instance model, and the log ansatz are domain assumptions rather than standard theorems.

free parameters (2)

MF-AOA catalyst standard deviation sigma = Values in Table II, e.g. sigma=0.2 for k=3, r=0.5; sigma=3.0 for k=10, r=1.5
Chosen by hand for each k and r to break Z2 symmetry in the mean-field dynamics. The MF-AOA approximation ratio depends on this choice, so the QAOA-vs-MF-AOA comparison is sensitive to it.
Logistic-fit coefficients for Mp(p) = Slope and offset per k, e.g. c=0.06 shown in the inset of Figure 4
The paper fits the ensemble-averaged approximation ratio to a logarithmic ansatz and uses the fit to extrapolate the required p for 90% and 99% thresholds. These fitted coefficients directly determine the claimed p values.

assumptions (4)

domain assumption The mean-field approximation (product ansatz) faithfully represents a classical benchmark for QAOA.
MF-AOA replaces quantum evolution with classical spin dynamics on Bloch spheres. The paper treats this as the classical counterpart to QAOA, but the approximation has no controlled error bound relative to other classical solvers.
ad hoc to paper The logarithmic ansatz Mp ~ A + c ln(p) holds beyond the simulated range p <= 30.
This is the key assumption used to estimate p=50 and p=770 for 99% approximation ratio. The paper provides no theoretical justification for this functional form at large p.
domain assumption Random Max-kXOR instances generated with clause probability P = rN / C(N,k) represent the intended problem ensemble.
The results depend on this specific random graph model, and the conclusions about QAOA limitations are tied to this ensemble.
domain assumption N=18 findings generalize to larger system sizes.
Section IV.E transfers optimized angles from N=18 to larger N without re-optimization and takes the resulting constant Mp as evidence of universality, but this is only tested up to N=24 for selected settings.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems." pith.science (2026). https://pith.science/paper/UQRFFR72

@misc{pith2026241119388,
  author       = {Pith},
  title        = {Pith review of: Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UQRFFR72}},
  note         = {Machine review of arXiv:2411.19388}
}

abstract

The ability of the Quantum Approximate Optimization Algorithm (QAOA) to deliver a quantum advantage on combinatorial optimization problems is still unclear. Recently, a scaling advantage over a classical solver was postulated to exist for random 8-SAT at the satisfiability threshold. At the same time, the viability of quantum error mitigation for deep circuits on near-term devices has been put in doubt. Here, we analyze the QAOA's performance on random Max-$k$XOR as a function of $k$ and the clause-to-variable ratio. As a classical benchmark, we use the Mean-Field Approximate Optimization Algorithm (MF-AOA) and find that it performs better than or equal to the QAOA on average. Still, for large $k$ and numbers of layers $p$, there may remain a window of opportunity for the QAOA. However, by extrapolating our numerical results, we find that reaching high levels of satisfaction would require extremely large $p$, which must be considered rather difficult both in the variational context and on near-term devices.

Figures

Figures reproduced from arXiv: 2411.19388 by the authors.

**Figure 2.** FIG. 2. Ensemble-averaged approximation ratio of the QAOA [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** FIG. 3. The relative energy deviation ( [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Figures from the paper (5 more)

**Figure 4.** Figure 4: FIG. 4. The ensemble-averaged approximation ratio [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

**Figure 5.** Figure 5: FIG. 5. The ensemble-averade optimal parameters [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]

**Figure 6.** Figure 6: FIG. 6. The required [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]

**Figure 9.** Figure 9: FIG. 9. The distribution of [PITH_FULL_IMAGE:figures/full_fig_p007_9.png]

**Figure 10.** Figure 10: FIG. 10. Ensemble-averaged approximation ratio [PITH_FULL_IMAGE:figures/full_fig_p008_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 23 canonical work pages

[1]

Hogg, Phys

T. Hogg, Phys. Rev. A 61, 052311 (2000)

work page 2000
[2]

Farhi, J

E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph]

arXiv 2014
[3]

Albash and D

T. Albash and D. A. Lidar, Reviews of Modern Physics 90, 015002 (2018)

2018
[4]

Boulebnane and A

S. Boulebnane and A. Montanaro, PRX Quantum 5, 030348 (2024)

work page 2024
[5]

Montanaro and L

A. Montanaro and L. Zhou, Quantum speedups in solv- ing near-symmetric optimization problems by low-depth qaoa (2024), arXiv:2411.04979 [quant-ph]

arXiv 2024
[6]

Y. Quek, D. Stilck Fran¸ ca, S. Khatri, J. J. Meyer, and J. Eisert, Nature Physics 10.1038/s41567-024-02536- 7 (2024)

work page doi:10.1038/s41567-024-02536- 2024
[7]

Abbas, A

A. Abbas, A. Ambainis, B. Augustino, A. B¨ artschi, H. Buhrman, C. Coffrin, G. Cortiana, V. Dunjko, D. J. Egger, B. G. Elmegreen, N. Franco, F. Fratini, B. Fuller, J. Gacon, C. Gonciulea, S. Gribling, S. Gupta, S. Had- field, R. Heese, G. Kircher, T. Kleinert, T. Koch, G. Ko- rpas, S. Lenk, J. Marecek, V. Markov, G. Mazzola, S. Mensa, N. Mohseni, G. Nanni...

2024
[8]

A. A. Mele, A. Angrisani, S. Ghosh, S. Khatri, J. Eisert, D. S. Fran¸ ca, and Y. Quek, Noise-induced shallow circuits and absence of barren plateaus (2024)

work page 2024

Show all 34 references

[9]

Cerezo, M

M. Cerezo, M. Larocca, D. Garc ´ ıa-Mart ´ ın, N. L. Diaz, P. Braccia, E. Fontana, M. S. Rudolph, P. Bermejo, A. Ijaz, S. Thanasilp, E. R. Anschuetz, and Z. Holmes, Does provable absence of barren plateaus imply classi- cal simulability? Or, why we need to rethink variational ...

2024 arXiv
[10]

S. Kazi, M. Larocca, M. Farinati, P. J. Coles, M. Cerezo, and R. Zeier, Analyzing the quantum approximate opti- mization algorithm: Ans¨ atze, symmetries, and Lie alge- bras (2024)

2024
[11]

Marwaha, Quantum 5, 437 (2021)

K. Marwaha, Quantum 5, 437 (2021)

2021
[12]

Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Phys. Rev. A 97, 022304 (2018)

2018
[13]

Farhi, J

E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, Quan- tum 6, 759 (2022)

2022
[14]

H ˚ astad, J

J. H ˚ astad, J. ACM48, 798–859 (2001)

2001
[15]

G. E. Crooks, Performance of the quantum approximate optimization algorithm on the maximum cut problem (2018), arXiv:1811.08419 [quant-ph]

2018 arXiv
[16]

M. X. Goemans and D. P. Williamson, in Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’94 (Association for Computing Ma- chinery, New York, NY, USA, 1994) p. 422–431

1994
[17]

Makarychev and Y

K. Makarychev and Y. Makarychev (Springer Berlin Hei- delberg, Berlin, Heidelberg, 2012) pp. 254–265

2012
[18]

Akshay, H

V. Akshay, H. Philathong, M. E. S. Morales, and J. D. Biamonte, Phys. Rev. Lett. 124, 090504 (2020)

2020
[19]

Marwaha and S

K. Marwaha and S. Hadfield, Quantum 6, 757 (2022)

2022
[20]

Hirvonen, J

J. Hirvonen, J. Rybicki, S. Schmid, and J. Suomela, Large cuts with local algorithms on triangle-free graphs (2014), arXiv:1402.2543 [cs.DC]

2014 arXiv
[21]

C.-N. Chou, P. J. Love, J. S. Sandhu, and J. Shi, Limita- tions of Local Quantum Algorithms on Random Max-k- XOR and Beyond (2021), arXiv:2108.06049 [quant-ph]

2021 arXiv
[22]

W.-K. Chen, D. Gamarnik, D. Panchenko, and M. Rah- man, The Annals of Probability 47, pp. 1587 (2019)

2019
[23]

Basso, D

J. Basso, D. Gamarnik, S. Mei, and L. Zhou (IEEE, 2022). 10

2022
[24]

Gamarnik and A

D. Gamarnik and A. Jagannath, The overlap gap prop- erty and approximate message passing algorithms for p- spin models (2019), arXiv:1911.06943 [math.PR]

2019 arXiv
[25]

Gamarnik, Proceedings of the National Academy of Sciences 118, 10.1073/pnas.2108492118 (2021)

D. Gamarnik, Proceedings of the National Academy of Sciences 118, 10.1073/pnas.2108492118 (2021)

2021 doi
[26]

M¨ uller, A

T. M¨ uller, A. Singh, F. K. Wilhelm, and T. Bode, Data for limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction prob- lems (2024)

2024
[27]

M. H. S. Amin, Phys. Rev. Lett. 102, 220401 (2009)

2009
[28]

Misra-Spieldenner, T

A. Misra-Spieldenner, T. Bode, P. K. Schuhmacher, T. Stollenwerk, D. Bagrets, and F. K. Wilhelm, PRX Quantum 4, 030335 (2023)

2023
[29]

J. A. Smolin and G. Smith, Frontiers in Physics 2, 10.3389/fphy.2014.00052 (2014)

2014
[30]

S. W. Shin, G. Smith, J. A. Smolin, and U. Vazi- rani, How ”Quantum” is the D-Wave Machine? (2014), arXiv:1401.7087 [quant-ph]

2014 arXiv
[31]

Bode and F

T. Bode and F. K. Wilhelm, Phys. Rev. A 110, 012611 (2024)

2024
[32]

Gharibian and O

S. Gharibian and O. Parekh (Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Informatik, 2019)

2019
[33]

Ghosh, L

R. Ghosh, L. A. Nutricati, N. Feinstein, P. A. Warburton, and S. Bose, Exponential speed-up of quantum annealing via n-local catalysts (2024), arXiv:2409.13029 [quant-ph]

2024
[34]

Zhou, S.-T

L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Phys. Rev. X 10, 021067 (2020)

2020

Pith tools

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

[1] [1]

Hogg, Phys

T. Hogg, Phys. Rev. A 61, 052311 (2000)

work page 2000

[2] [2]

Farhi, J

E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph]

arXiv 2014

[3] [3]

Albash and D

T. Albash and D. A. Lidar, Reviews of Modern Physics 90, 015002 (2018)

2018

[4] [4]

Boulebnane and A

S. Boulebnane and A. Montanaro, PRX Quantum 5, 030348 (2024)

work page 2024

[5] [5]

Montanaro and L

A. Montanaro and L. Zhou, Quantum speedups in solv- ing near-symmetric optimization problems by low-depth qaoa (2024), arXiv:2411.04979 [quant-ph]

arXiv 2024

[6] [6]

Y. Quek, D. Stilck Fran¸ ca, S. Khatri, J. J. Meyer, and J. Eisert, Nature Physics 10.1038/s41567-024-02536- 7 (2024)

work page doi:10.1038/s41567-024-02536- 2024

[7] [7]

Abbas, A

A. Abbas, A. Ambainis, B. Augustino, A. B¨ artschi, H. Buhrman, C. Coffrin, G. Cortiana, V. Dunjko, D. J. Egger, B. G. Elmegreen, N. Franco, F. Fratini, B. Fuller, J. Gacon, C. Gonciulea, S. Gribling, S. Gupta, S. Had- field, R. Heese, G. Kircher, T. Kleinert, T. Koch, G. Ko- rpas, S. Lenk, J. Marecek, V. Markov, G. Mazzola, S. Mensa, N. Mohseni, G. Nanni...

2024

[8] [8]

A. A. Mele, A. Angrisani, S. Ghosh, S. Khatri, J. Eisert, D. S. Fran¸ ca, and Y. Quek, Noise-induced shallow circuits and absence of barren plateaus (2024)

work page 2024