Pith. sign in

REVIEW 3 major objections 4 minor 84 references

Quantum-informed surrogate sampling for combinatorial optimization

T0 review · 3 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read QISS turns shallow QAOA correlators into candidate solutions that beat much deeper circuits, classically and with little sensitivity to device noise.

desk verdict A genuinely new post-processing heuristic that turns shallow QAOA correlators into good MaxCut/MIS solutions via a classically sampled factor model; the empirical results look solid, but the headline p=17 baseline comparison needs clarification and the mechanism is explicitly empirical. read the letter →

arxiv 2607.22372 v1 pith:DJSQ3O6U submitted 2026-07-24 quant-ph cond-mat.dis-nn

Elisabeth Wybo , Jernej Rudi Finžgar This is my paper
classification quant-phcond-mat.dis-nn
keywords QuantumApproximateOptimizationAlgorithmsurrogatesamplingMaxCutMaximumIndependentSetfactorgraphMarkovchainMonteCarlolow-weightcorrelatorsnoiseresilience
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

The paper tries to establish that the solution-relevant information in a shallow QAOA circuit can be extracted from O(N) one- and two-point Pauli-Z expectation values and repackaged into a classical factor distribution over spin configurations. Sampling that distribution by MCMC yields MaxCut and MIS solutions that consistently outperform the original QAOA output, with the strongest benchmark claim being that p=3 QAOA correlators beat vanilla QAOA at p=17 on 3-regular MaxCut instances. The reason this matters: if correct, near-term quantum hardware does not need to sample good solutions directly; it only needs to supply low-order statistics, which are easy to measure and error-mitigate, and the classical sampler does the hard work.

What carries the argument

The core object is the factor/surrogate distribution P(z) = Z^{-1} ∏_{S∈S}(1 + μ_S χ_S(z)), where μ_S are measured QAOA expectation values of weight-1 and weight-2 Pauli-Z terms and χ_S are parity functions. It is equivalent to a Gibbs distribution at T=1 with couplings J_S = −arctanh(μ_S). Sampling proceeds by single-site MCMC with conditional probabilities that avoid the partition function; the key input is the augmented graph G' containing every edge within distance 2p of the QAOA light cone, which makes the factor graph non-tree-like and allows samples to escape the QAOA's own distribution.

What would settle it

Construct a 3-regular MaxCut instance or family where the surrogate built from p=3 full light-cone correlators yields no improvement over vanilla QAOA p=3, or where the sampled cut fractions are worse than the input correlators' expected cut. Mechanistically, compute the exact higher-order parity expectations of the QAOA state and the surrogate's implicit higher-order expectations; if they are systematically anti-correlated with cut value, or if the surrogate's modes do not correspond to good cuts, the central claim fails.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the factor model P(z) ∝ ∏_{S∈S}(1 + μ_S χ_S(z)), with couplings J_S = −arctanh(μ_S), acts as a surrogate whose samples improve on the QAOA state it was built from—provided the factor supports include all pairs within the circuit light cone (d_G(i,j) ≤ 2p) rather than only the problem edges. The augmented, non-tree-like factor graph is what lets the surrogate move beyond merely reproducing the input correlations. Across MaxCut and MIS on 3-regular graphs, the surrogate yields cut fractions above vanilla QAOA and close to optimality, and on the hardware experiment the post-processed solutions are essentially identical whether the correlat

Load-bearing premise

The load-bearing premise is that the surrogate's higher-order correlations—those not fixed by the input weight-1 and weight-2 moments—tend to align with the original optimization objective; the paper presents this alignment as an empirical finding (Sec. IV), not a proven property, and notes that it fails in some settings such as MIS with only edge factors.

Editorial extensions

If this is right

  • Fixed shallow-depth QAOA, used only as a correlation source, can outperform much deeper QAOA after classical post-processing; the paper demonstrates p=3 versus p=17 for MaxCut.
  • The entire procedure is training-free: tree-optimal angles and the arctanh coupling rule replace variational optimization.
  • Low-weight correlators are measurable with a system-size-independent sample cost and can be error-mitigated, so QISS inherits noise resilience; device experiments show near-noiseless results from raw correlators.
  • Because sampling is cost-function agnostic, the same surrogate applies to constrained problems such as MIS, with a light pruning post-step to enforce feasibility.
  • QISS is competitive with strong classical heuristics at fixed compute budget, suggesting a practical near-term role for shallow quantum circuits in optimization.

Reading between the lines

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

  • Editorial extension: The result reframes near-term quantum optimization as a statistics-generation task; the achievable approximation ratio may be limited more by the information content of weight-2 correlators than by circuit depth.
  • Editorial extension: The thermal-input saturation seen in Appendix B hints that the benefit depends on the input state encoding coherent assignments; QAOA's structured local correlations appear more informative than thermal correlations at matching energy densities.
  • Editorial extension: A testable implication is that including weight-3 or weight-4 correlators, or structured encodings such as Pauli-correlation encodings, could push the surrogate further; the paper notes this but does not test it.
  • Editorial extension: The success of the non-tree-like augmented graph suggests the mechanism is not moment matching but the introduction of cycles and frustration; understanding when these cycles help versus hurt could yield a criterion for choosing factor supports.
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.

Referee Report

3 major / 4 minor

Summary. The paper introduces Quantum-Informed Surrogate Sampling (QISS), a post-processing method that constructs a classical factor distribution from low-weight (weight-1 and weight-2) QAOA correlators and draws candidate solutions from it by MCMC. The surrogate is the Gibbs form P(z) ∝ ∏_{Sα∈S}(1+μ_{Sα}χ_{Sα}(z)), equivalently H′ with couplings J_{Sα}=-arctanh(μ_{Sα}) at temperature T=1, and it does not use the cost function explicitly. The authors benchmark QISS on MaxCut and MIS on random 3-regular graphs, using the original edge set S=E∪V and the augmented set S′=E′∪V with E′={(i,j): d_G(i,j)≤2p}. They report that, for MaxCut, QISS from p=3-4 QAOA correlators beats vanilla tree QAOA at p=17 on average, and that QISS also improves regularized warm-start QAOA (RWS-QAOA), including on the 54-qubit IQM Emerald QPU, with QISS output nearly insensitive to device noise. The main conceptual claim is that shallow QAOA circuits can serve as generators of informative low-order statistics rather than as direct samplers.

Significance. If the reported empirical results hold, QISS is a simple, modular, and potentially useful post-processing layer: it requires only O(N) one- and two-body correlators, avoids recursive outer loops, and does not need further quantum device access. The paper has several genuine strengths: the surrogate construction is transparent; the distinction between the edge-only and augmented correlator sets is clearly demonstrated; the authors are explicit that the surrogate does not in general reproduce its input moments (Sec. III B, Eq. (25)); and Appendix B directly addresses the question of whether the improvement is specific to QAOA correlations. The QPU demonstration of noise robustness is valuable, and the detailed-balance/ergodicity proofs in Appendix A are correct as far as they go. The paper does not claim a quantum advantage, and its classical comparisons are reasonable in spirit. However, the central 'beats p=17 vanilla QAOA' claim is weakened by the ambiguous status of the external p=17 baseline, and the 'quantum-informed' attribution needs a stronger control experiment than the thermal-state comparison.

major comments (3)
  1. [Abstract; Sec. IV A 1; Fig. 4; Ref. [35]] The headline claim that 'QISS from p=3 QAOA correlators outperforms vanilla QAOA at p=17 on average' rests on the dotted baseline labelled 'Tree QAOA p=17', taken from Ref. [35]. The title of Ref. [35] is 'Lower bounding the maxcut of high girth 3-regular graphs using the qaoa', which suggests the plotted value may be a rigorous lower bound on the p=17 QAOA expectation, not the achieved mean. These are not the same quantity: a lower bound can be substantially below the actual QAOA performance. Please state explicitly what the dotted line represents. If it is a lower bound, the abstract and Sec. IV A 1 overstate the result; the comparison should be re-run against actual p=17 QAOA estimates (or the claim should be reworded as 'exceeds the best known lower bound for p=17'). The same ambiguity affects the sentence in Sec. IV A 2 that QISS at p=1 'exceeds the vanilla tree-QAOA value at p=17'.
  2. [Sec. III D; Eq. (12); Appendix B] The core conceptual premise is that the specific values and placement of QAOA correlators drive the improvement. However, the surrogate does not reproduce its input moments (Sec. III B), and the good-solution property is explicitly labelled 'the empirical finding of Sec. IV' in Sec. III D. Appendix B then shows that thermal two-point correlations, when fed into the same factor model, also produce large improvements on MaxCut. This raises the real possibility that the gains are a generic property of the dense pairwise factor model on the augmented graph G′, rather than of QAOA correlations specifically. The paper needs a randomization control: for example, permute the measured μ_{ij} among the edges of G′, or replace them with magnitude-matched random/thermal correlators, and check whether QISS performance is unchanged. If it is unchanged, the 'quantum-informed' part of the central claim
  3. [Sec. III A; Sec. III D; Eq. (11)] The method has several free choices that are not tested for sensitivity: the temperature T=1 in Eq. (11), the 300 burn-in sweeps and 5000 sampling sweeps in Sec. III A, and the support-set choice S′. The paper states in Sec. III D that the model incorporates quantum information 'without introducing additional tunable parameters', but T, the MCMC schedule, and the support-set geometry are all tunable and are fixed by convention. Since the model is not moment-matching, T directly controls the concentration of the surrogate and hence the cut quality; a different T could strengthen or erase the reported gains. Please add a sensitivity analysis (e.g., average cut fraction vs T for representative p,N, plus mixing diagnostics such as the integrated autocorrelation time from Eq. (28)-(30) for the actual chains). Without this, the reader cannot judge whether the reported improvements are robust o
minor comments (4)
  1. [Sec. III C, Eq. (32)] The symbol S is used both for the selected factor collection and for the full power set, with the confusing line '2^N=|S|'. Please introduce a separate symbol (e.g., 2^[N]) for the full set of subsets.
  2. [Appendix A] There is a typo, 'probablilities', in the proof of Proposition A.1. Also, it is worth stating explicitly that the positivity assumption P(z)>0 for all z is satisfied because each factor 1+μ_{Sα}χ_{Sα}(z) is positive for |μ|<1 and does not vanish identically when |μ|=1.
  3. [Fig. 4 caption and Sec. IV A 1] The text says QISS 'substantially outperforms vanilla QAOA', but Fig. 4(A) shows no improvement for the edge-only set. Please make the distinction between the two panels explicit in the caption: the improvement occurs only for the augmented correlator set S′.
  4. [Fig. 5 and Sec. IV A 2] For p=0, the QISS and RWS-QAOA markers overlap by construction. This is stated in the text but could be made more prominent, since otherwise it appears as a null result that contradicts the later improvements.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: QISS's improvement is an empirical benchmark, and the surrogate construction is not equivalent to its inputs.

full rationale

The derivation chain is self-contained. The surrogate P(z) in Eq. (9) is constructed from measured QAOA correlators mu_{S_alpha} (Eq. 8), and the couplings J_{S_alpha} = -arctanh(mu_{S_alpha}) (Eq. 12) are fixed analytically with no parameter fitted to the final cut/independence objective. The paper does not claim to derive the good-solution property: Sec. III D explicitly calls it "the empirical finding of Sec. IV". The central comparison (QISS p=3 vs vanilla QAOA p=17) is an average over simulated/QPU instances, not a constructed identity. The maximum-entropy discussion is not used as a derivation; the paper explicitly says the surrogate forgoes moment matching (langle chi_{S_alpha} rangle_P != mu_{S_alpha}), so any benefit is an empirical property of the induced interaction structure. The self-citations ([61] for tree-optimal angles, [31] for the QGreedy baseline) are not load-bearing: [61] is published independent work and only supplies input parameters; [31] is a baseline, not the central claim. Appendix B's thermal-correlation experiments act as a control and are honestly reported as showing QAOA correlations lead to better results than thermal ones. The only weakness is the unproven MCMC mixing time (Appendix A proves ergodicity only), but that is a correctness/rigor limitation, not circularity. Hence no circular step can be exhibited by the paper's own equations.

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

The central claim rests on imported QAOA angles, hand-chosen surrogate temperature, and an empirically assumed alignment between the surrogate and the optimization objective; no new physical entities are introduced.

free parameters (3)
  • Surrogate temperature T = 1
    Eq. (11) fixes T=1 by hand; no tuning or sensitivity analysis. Sampling behavior and solution quality depend on this choice.
  • RWS regularization strength eta = 0.6
    Eq. (37) uses eta=0.6, imported from Ref. [33]; controls warm-start angles theta* and hence all correlations and QISS outputs.
  • MCMC sampling schedule = 300 burn-in, 5000 sweeps, lag 10
    Sec. III A; chosen to balance cost and autocorrelation; not justified by convergence diagnostics, and no formal mixing time.
assumptions (5)
  • domain assumption Shallow QAOA local observables are determined by the radius-p light cone
    Sec. II B; justifies using only pairs with d_G(i,j)<=2p and tree-optimal angles.
  • domain assumption Random 3-regular graphs are locally tree-like
    Sec. II B; permits using fixed tree-optimal angles from Ref [61] and comparing to tree QAOA baselines.
  • standard math The factor weights 1+mu chi are strictly positive
    Assumed in Appendix A for ergodicity; requires |mu|<1 for all factors; violated near saturating correlators.
  • ad hoc to paper The surrogate's higher-order correlations align with the original cost function
    Sec. III D explicitly calls this an empirical finding; it is the load-bearing premise for QISS's improvement.
  • ad hoc to paper MCMC reaches stationarity within the chosen burn-in
    Appendix proves ergodicity, not mixing time; no diagnostic in main text for cut-fraction convergence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum-informed surrogate sampling for combinatorial optimization." pith.science (2026). https://pith.science/paper/DJSQ3O6U

@misc{pith2026260722372,
  author       = {Pith},
  title        = {Pith review of: Quantum-informed surrogate sampling for combinatorial optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DJSQ3O6U}},
  note         = {Machine review of arXiv:2607.22372}
}
abstract

We introduce Quantum-Informed Surrogate Sampling (QISS), a post-processing framework that generates candidate solutions to combinatorial optimization problems from low-weight correlations of shallow quantum circuits. The quantum device estimates local observables, which are directly accessible by repeated measurements and for which a wide range of error-mitigation tools are available, while candidate solutions are generated classically without explicit dependence on the combinatorial optimization problem itself. We evaluate QISS on Maximum Cut and Maximum Independent Set problems on $N$ variables and show that only $O(N)$ low-order correlators from shallow circuits suffice to produce competitive solutions that surpass vanilla QAOA. For MaxCut on 3-regular graphs, QISS from $p=3$ QAOA correlators outperforms vanilla QAOA at $p=17$ on average, with further improvements possible by warm-starting QAOA. We validate the procedure on the 54-qubit IQM Emerald quantum device and demonstrate its noise resilience. Our results support a regime for near-term optimization in which shallow circuits serve not as direct samplers but as generators of informative statistics for scalable classical sampling.

Figures

Figures reproduced from arXiv: 2607.22372 by the authors.

Figure 1
Figure 1. (A), µSα = ⟨ψp(γ, β)| Y i∈Sα Zi |ψp(γ, β)⟩. (1) In practice we only use weights |Sα| = 1, 2 for all Sα considered. These µSα can be estimated on a quantum device by repeated state preparation and measurement and provide accessible partial information about the QAOA state. We then initialize a classical factor model as a surrogate distribution over the solution space {−1, +1} N , see [PITH_FULL_IMAGE:figures/full_fi… view at source ↗
Figure 2
Figure 2. FIG. 2. Starting from an original graph [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5 [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6 [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7 [PITH_FULL_IMAGE:figures/full_fig_p013_7.png]
Figure 8
Figure 8. Figure 8: FIG. 8 [PITH_FULL_IMAGE:figures/full_fig_p014_8.png]
Figure 9
Figure 9. Figure 9: FIG. 9 [PITH_FULL_IMAGE:figures/full_fig_p015_9.png]
Figure 10
Figure 10. Figure 10: FIG. 10 [PITH_FULL_IMAGE:figures/full_fig_p016_10.png]
Figure 11
Figure 11. Figure 11: FIG. 11 [PITH_FULL_IMAGE:figures/full_fig_p018_11.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

84 extracted references · 6 canonical work pages

  1. [35]

    De Palma, M

    G. De Palma, M. Marvian, C. Rouz´ e, and D. S. Fran¸ ca, PRX Quantum 4 (1), 010309, 20234, 010309 (2022), arXiv:2204.03455 [quant-ph]

    arXiv 2022

  2. [1]

    QAOA correlations We first apply QISS to correlators from vanilla QAOA. Since the MaxCut Hamiltonian isZ 2-symmetric, all one- body expectation values vanish, so it suffices to compute the two-body correlators⟨γ ⋆,β ⋆|ZiZj|γ⋆,β ⋆⟩for pairs with dG(i, j)≤2p. Based on these, we apply QISS (see Sec. III A) to each instance, using either the edge setS=Eor the...

  3. [2]

    [33], we can useregularized warm-start QAOA(R WS-QAOA) to generate correlations that can be supplied to QISS

    R WS-QAOA correlations Following Ref. [33], we can useregularized warm-start QAOA(R WS-QAOA) to generate correlations that can be supplied to QISS. In R WS-QAOA, a linear-time classical preprocessing step is performed that introduces biases into the initial QAOA state. Instead of initializing each qubit as|+⟩, the stateR y(θi)|+⟩is prepared on each qubit,...

  4. [3]

    R WS-QAOA QPU correlations In this section we describe the implementation of R WS-QAOA on the 54-qubit IQM Emerald QPU with a square- grid connectivity (see Fig. 1(A)). We leveraged the fact that, upon solving the relaxed objective to determine the warm-start anglesθ i, many of them take the extremal valuesθ i ∈ {0, π}. Forθi = 0 (θ i =π) qubitiis initial...

    2000

  5. [4]

    8: (i) Simulated Annealing (SA) and (ii) a low-rank Burer–Monteiro (BM) implementation of the Goemans–Williamson SDP relaxation for MaxCut

    Comparison to classical algorithms We compare the results of QISS based on mean values from QAOA and from R WS-QAOA to two classical algorithms in Fig. 8: (i) Simulated Annealing (SA) and (ii) a low-rank Burer–Monteiro (BM) implementation of the Goemans–Williamson SDP relaxation for MaxCut. As a simulated-annealing baseline [71], we use the classical Simu...

  6. [5]

    We therefore supply QISS with the one-body expectations⟨Z i⟩for all i∈Vtogether with the two-body correlators⟨Z iZj⟩that do not factorize, i.e

    QAOA correlations The absence ofZ 2 symmetry means that for pairs with non-overlapping light cones,d G(i, j)>2p, the two-body correlators factorize as⟨Z iZj⟩=⟨Z i⟩ ⟨Zj⟩. We therefore supply QISS with the one-body expectations⟨Z i⟩for all i∈Vtogether with the two-body correlators⟨Z iZj⟩that do not factorize, i.e. those withd G(i, j)≤2p. We use the same ins...

  7. [6]

    10, we compare the independence ratios averaged over 40 instances at each system sizeN

    Algorithm comparison In Fig. 10, we compare the independence ratios averaged over 40 instances at each system sizeN. For each instance, we took the best of the generated candidate solutions. We compare to classical baselines such as minimal greedy [76] and the linear-prioritized search algorithm of Ref. [75]. In addition, we compare to the quantum-enhance...

  8. [7]

    Hogg and D

    T. Hogg and D. Portnov, Information Sciences128, 181 (2000)

    2000

Show all 84 references
  1. [8]

    Hogg, Phys

    T. Hogg, Phys. Rev. A61, 052311 (2000)

    2000

  2. [9]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, (2014), 10.48550/ARXIV.1411.4028, arXiv:1411.4028 [quant-ph]

    2014 doi arXiv

  3. [10]

    Montanaro, Physical Review Research2(2020), 10.1103/physrevresearch.2.013056

    A. Montanaro, Physical Review Research2(2020), 10.1103/physrevresearch.2.013056

    2020 doi

  4. [11]

    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. Hadfield, R. Heese, G. Kircher, T. Kleinert, T. Koch, G. Korpas...

    2023 doi arXiv

  5. [12]

    A. M. Dalzell, N. Pancotti, E. T. Campbell, and F. G. Brand˜ ao, inProceedings of the 55th Annual ACM Symposium on Theory of Computing(ACM, 2023) p. 1131–1144

    2023

  6. [13]

    S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V. Isakov, T. Khattar, and R. Babbush, Nature646, 831–836 (2025)

    2025

  7. [14]

    Mechanisms for quantum advantage in global optimization of nonconvex functions,

    D. Herman, G. Ozgul, A. Apte, J. L. Kim, A. Prakash, J. Shen, and S. Chakrabarti, “Mechanisms for quantum advantage in global optimization of nonconvex functions,” (2025), arXiv:2510.03385 [quant-ph]

    2025

  8. [15]

    Pagano andet al., Proc

    G. Pagano andet al., Proc. Natl. Acad. Sci. U.S.A. (2020), trapped-ion experimental implementation of QAOA on long-range Ising models

    2020

  9. [16]

    M. P. Harrigan, K. J. Sung, and M. N.et al., Nature Phys.17, 332 (2021)

    2021

  10. [17]

    Ebadi, A

    S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuleti´ c, and M. D. Lukin, Sci...

    2022

  11. [18]

    Pelofske, A

    E. Pelofske, A. B¨ artschi, L. Cincio, J. Golden, and S. Eidenbenz, npj Quantum Information10(2024), 10.1038/s41534- 024-00906-w

    2024 doi

  12. [19]

    Shaydulin, C

    R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y. Sun, Y. Alexeev, J. M. Dreiling, J. P. Gaebler, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. V. Horst, S. Hu, J. Johansen, M. Matheny, T. Mengle, M. ...

    2024 doi

  13. [20]

    Z. He, D. Amaro, R. Shaydulin, and M. Pistoia, Communications Physics8(2025), 10.1038/s42005-025-02136-8

    2025 doi

  14. [21]

    Boulebnane and A

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

    2024

  15. [22]

    Applying the quantum approximate optimization algorithm to general constraint satisfaction problems,

    S. Boulebnane, M. Ciudad-Ala˜ n´ on, L. Mineh, A. Montanaro, and N. Vaishnav, “Applying the quantum approximate optimization algorithm to general constraint satisfaction problems,” (2024), arXiv:2411.17442 [quant-ph]

    2024 arXiv

  16. [23]

    Quantum speedups in solving near-symmetric optimization problems by low-depth qaoa,

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

    2025 arXiv

  17. [24]

    Akshay, D

    V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, Phys. Rev. A104, L010401 (2021)

    2021

  18. [25]

    Farhi, D

    E. Farhi, D. Gamarnik, and S. Gutmann, (2020), 10.48550/ARXIV.2004.09002, arXiv:2004.09002 [quant-ph]

    2020 doi arXiv

  19. [26]

    C.-N. Chou, P. J. Love, J. S. Sandhu, and J. Shi, (2021), 10.48550/ARXIV.2108.06049, arXiv:2108.06049 [quant-ph]

    2021 doi arXiv

  20. [27]

    Basso, D

    J. Basso, D. Gamarnik, S. Mei, and L. Zhou,2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), , 335–343 (2022)

    2022

  21. [28]

    Anshu and T

    A. Anshu and T. Metger, Quantum 7, 999 (2023)7, 999 (2022), arXiv:2209.02715 [quant-ph]

    2023 arXiv

  22. [29]

    Farhi, D

    E. Farhi, D. Gamarnik, and S. Gutmann, (2020), 10.48550/ARXIV.2005.08747, arXiv:2005.08747 [quant-ph]

    2020 doi arXiv

  23. [30]

    A. Chen, N. Huang, and K. Marwaha, (2023), 10.48550/ARXIV.2310.01563, arXiv:2310.01563 [quant-ph]

    2023 doi arXiv

  24. [31]

    Gamarnik and M

    D. Gamarnik and M. Sudan, (2013), 10.48550/ARXIV.1304.1831, arXiv:1304.1831 [math.PR]

    2013 doi arXiv

  25. [32]

    Gamarnik and A

    D. Gamarnik and A. Jagannath, (2019), 10.48550/ARXIV.1911.06943, arXiv:1911.06943 [math.PR]

    2019 doi arXiv

  26. [33]

    Gamarnik, Proceedings of the National Academy of Sciences118(2021), 10.1073/pnas.2108492118, arXiv:2109.14409 [cs.CC]

    D. Gamarnik, Proceedings of the National Academy of Sciences118(2021), 10.1073/pnas.2108492118, arXiv:2109.14409 [cs.CC]

    2021 arXiv

  27. [34]

    D. S. Franca and R. Garcia-Patron, Nature Physics17, 1221 (2020), arXiv:2009.05532 [quant-ph]

    2020 arXiv

  28. [36]

    Dupont, B

    M. Dupont, B. Sundar, B. Evert, D. E. B. Neira, Z. Peng, S. Jeffrey, and M. J. Hodson, Physical Review Applied23 (2025), 10.1103/physrevapplied.23.014045

    2025 doi

  29. [37]

    A scalable quantum-enhanced greedy algorithm for maximum independent set problems,

    E. Wybo, J. R¨ onkk¨ o, O. Hirviniemi, J. R. Finˇ zgar, and M. Leib, “A scalable quantum-enhanced greedy algorithm for maximum independent set problems,” (2026), arXiv:2601.21923 [quant-ph]

    2026

  30. [38]

    I. L. Markov and Y. Shi, SIAM Journal on Computing38, 963 (2008), https://doi.org/10.1137/050644756

    2008 doi

  31. [39]

    Regularized warm-started quantum approximate optimization and conditions for surpassing classical solvers on the max-cut problem,

    Z. He, A. Apte, B. Augustino, A. Babakhani, A. Khan, S. Omanakuttan, and R. Shaydulin, “Regularized warm-started quantum approximate optimization and conditions for surpassing classical solvers on the max-cut problem,” (2026), arXiv:2603.10191 [quant-ph]

    2026

  32. [40]

    Farhi and A

    E. Farhi and A. W. Harrow, (2016), 10.48550/ARXIV.1602.07674, arXiv:1602.07674 [quant-ph]

    2016 doi arXiv

  33. [41]

    Lower bounding the maxcut of high girth 3-regular graphs using the qaoa,

    E. Farhi, S. Gutmann, D. Ranard, and B. Villalonga, “Lower bounding the maxcut of high girth 3-regular graphs using the qaoa,” (2025), arXiv:2503.12789 [quant-ph]

    2025

  34. [42]

    P. K. Barkoutsos, G. Nannicini, A. Robert, I. Tavernelli, and S. Woerner, Quantum4, 256 (2020)

    2020

  35. [43]

    Layden, G

    D. Layden, G. Mazzola, R. V. Mishmash, M. Motta, P. Wocjan, J.-S. Kim, and S. Sheldon, Nature619, 282 (2023)

    2023

  36. [44]

    Nakano, H

    Y. Nakano, H. Hakoshima, K. Mitarai, and K. Fujii, Physical Review Research6, 033105 (2024), preprint: arXiv:2305.08789 (QAOA-MC)

    2024 arXiv

  37. [45]

    Quantum-enhanced markov chain monte carlo for combinatorial optimization,

    K. V. Marshall, D. J. Egger, M. Garn, F. Schiavello, S. Brandhofer, C. Zoufal, and S. Woerner, “Quantum-enhanced markov chain monte carlo for combinatorial optimization,” (2026), arXiv:2602.06171 [quant-ph]

    2026

  38. [46]

    Divide-and-conquer neural network surrogates for quantum sampling: Accelerating markov chain monte carlo in large-scale constrained optimization problems,

    Y. Kawamata, Y. Nakano, and K. Fujii, “Divide-and-conquer neural network surrogates for quantum sampling: Accelerating markov chain monte carlo in large-scale constrained optimization problems,” (2026), arXiv:2604.20701 [quant- ph]

    2026 arXiv

  39. [47]

    Quantum-enhanced optimization by warm starts,

    I. ˇCepait˙ e, N. Vaishnav, L. Zhou, and A. Montanaro, “Quantum-enhanced optimization by warm starts,” (2025), arXiv:2508.16309 [quant-ph]

    2025 arXiv

  40. [48]

    Bravyi, A

    S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Phys. Rev. Lett. 125, 260505 (2020)125, 260505 (2019), arXiv:1910.08980 [quant-ph]

    2020 arXiv

  41. [49]

    Dupont and B

    M. Dupont and B. Sundar, (2023), 10.48550/ARXIV.2307.05821, arXiv:2307.05821 [quant-ph]

    2023 doi arXiv

  42. [50]

    L. T. Brady and S. Hadfield, Physical Review A110(2024), 10.1103/physreva.110.052435

    2024 doi

  43. [51]

    J. R. Finˇ zgar, A. Kerschbaumer, M. J. Schuetz, C. B. Mendl, and H. G. Katzgraber, PRX Quantum5(2024), 10.1103/prxquantum.5.020327

    2024 doi

  44. [52]

    Martinez, O

    V. Martinez, O. Fawzi, and D. S. Fran¸ ca, Quantum10, 2068 (2026)

  45. [53]

    D. J. Egger, J. Mareˇ cek, and S. Woerner, Quantum5, 479 (2021)

    2021

  46. [54]

    R. Tate, M. Farhadi, C. Herold, G. Mohler, and S. Gupta, ACM Transactions on Quantum Computing4(2023), 10.1145/3549554

    2023 doi

  47. [55]

    R. Tate, J. Moondra, B. Gard, G. Mohler, and S. Gupta, Quantum7, 1121 (2023)

    2023

  48. [56]

    Z. He, R. Shaydulin, S. Chakrabarti, D. Herman, C. Li, Y. Sun, and M. Pistoia, npj Quantum Information9, 121 (2023)

    2023

  49. [57]

    K. N. Okada, H. Nishi, T. Kosugi, and Y.-i. Matsushita, Scientific Reports14, 1167 (2024)

    2024

  50. [58]

    Chancellor, Quantum Science and Technology4, 045004 (2019)

    N. Chancellor, Quantum Science and Technology4, 045004 (2019)

    2019

  51. [59]

    N. P. Sawaya, A. T. Schmitz, and S. Hadfield, Quantum7, 1111 (2023)

    2023

  52. [60]

    Bak´ o, A

    B. Bak´ o, A. Glos,¨O. Salehi, and Z. Zimbor´ as, Quantum9, 1663 (2025)

    2025

  53. [61]

    Sciorilli, L

    M. Sciorilli, L. Borges, T. L. Patti, D. Garc ´ ıa-Mart ´ ın, G. Camilo, A. Anandkumar, and L. Aolita, Nature Communications 16(2025), 10.1038/s41467-024-55346-z

    2025 doi

  54. [62]

    An information-minimal geometry for qubit-efficient optimization,

    G. Ma and D. G. Angelakis, “An information-minimal geometry for qubit-efficient optimization,” (2026), arXiv:2511.08362 [quant-ph]. 21

    2026

  55. [63]

    Preskill, Quantum 2, 79 (2018)2, 79 (2018), arXiv:1801.00862 [quant-ph]

    J. Preskill, Quantum 2, 79 (2018)2, 79 (2018), arXiv:1801.00862 [quant-ph]

    2018 arXiv

  56. [64]

    Lucas, Frontiers in PhysicsV olume 2 - 2014(2014), 10.3389/fphy.2014.00005

    A. Lucas, Frontiers in PhysicsV olume 2 - 2014(2014), 10.3389/fphy.2014.00005

    2014

  57. [65]

    Basso, E

    J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou, In Proceedings of the 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC ’22), 7:1–7:21, (2022) (2021), 10.4230/LIPICS.TQC.2022.7, arXiv:2110.14206 [quant-ph]

    2022 arXiv

  58. [66]

    Regular trees in random regular graphs,

    E. Makover and J. McGowan, “Regular trees in random regular graphs,” (2006)

    2006

  59. [67]

    Wybo and M

    E. Wybo and M. Leib, Quantum9, 1892 (2025)

    2025

  60. [68]

    Gray, Journal of Open Source Software3, 819 (2018)

    J. Gray, Journal of Open Source Software3, 819 (2018)

    2018

  61. [69]

    Pearl,Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference(Morgan Kaufmann, 1988)

    J. Pearl,Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference(Morgan Kaufmann, 1988)

    1988

  62. [70]

    C. J. Geyer, Statistical Science7(1992), 10.1214/ss/1177011137

    1992

  63. [71]

    D. C. Liu and J. Nocedal, Mathematical Programming45, 503–528 (1989)

    1989

  64. [72]

    J. J. Wallman and J. Emerson, Physical Review A94, 052325 (2016)

    2016

  65. [73]

    Hashim, R

    A. Hashim, R. K. Naik, A. Morvan, J.-L. Ville, B. Mitchell, J. M. Kreikebaum, M. Davis, E. Smith, C. Iancu, K. P. O’Brien,et al., arXiv preprint arXiv:2010.00215 (2020)

    2010 arXiv

  66. [74]

    Temme, S

    K. Temme, S. Bravyi, and J. M. Gambetta, Physical Review Letters119, 180509 (2017)

    2017

  67. [75]

    Li and S

    Y. Li and S. C. Benjamin, Physical Review X7, 021050 (2017)

    2017

  68. [76]

    Halperin, D

    E. Halperin, D. Livnat, and U. Zwick, Journal of Algorithms53, 169 (2004)

    2004

  69. [77]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science220, 671 (1983)

    1983

  70. [78]

    dwave-samplers: Ocean-compatible classical samplers,

    D-Wave Systems Inc., “dwave-samplers: Ocean-compatible classical samplers,”https://docs.dwavequantum.com/en/ latest/ocean/api_ref_samplers/index.html(2026)

    2026

  71. [79]

    Burer, R

    S. Burer, R. D. Monteiro, and Y. Zhang, SIAM Journal on Optimization12, 503 (2002)

    2002

  72. [80]

    Dunning, S

    I. Dunning, S. Gupta, and J. Silberholz, INFORMS Journal on Computing30(2018)

    2018

  73. [81]

    Marino and S

    R. Marino and S. Kirkpatrick, (2020), 10.48550/ARXIV.2003.12293, arXiv:2003.12293 [cs.DS]

    2020 doi arXiv

  74. [82]

    N. C. Wormald, Annals of Applied Probability5, 1217 (1995)

    1995

  75. [83]

    Hukushima and K

    K. Hukushima and K. Nemoto, Journal of the Physical Society of Japan65, 1604–1608 (1996)

    1996

  76. [84]

    Parisi, Phys

    G. Parisi, Phys. Rev. Lett.43, 1754 (1979)

    1979

Pith tools

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