pith. sign in

arxiv: 2606.27224 · v1 · pith:W3MEQV2Cnew · submitted 2026-06-25 · 🪐 quant-ph

A 0.651-approximation to quantum Max Cut via Rydberg atoms

Tom\'as Crosta , Matthieu Saubanere , Felix Huber This is my paper

Pith reviewed 2026-06-26 04:19 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum max cutapproximation algorithmsrydberg atomshybrid quantum-classical algorithmssemidefinite programmingquantum optimization
0
0 comments X

The pith

Hybrid algorithm using Rydberg atoms achieves 0.651 approximation ratio for quantum Max Cut

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a hybrid method for approximating quantum Max Cut by combining the dynamics of Rydberg atom systems with semidefinite programming and randomized rounding. This yields a conditional approximation ratio of 0.651, improving on the 0.614 ratio from SDP alone. The improvement holds even if the Rydberg annealing reaches only 89 percent of the true ground state energy. A sympathetic reader would care because it suggests a practical way to leverage near-term quantum hardware for better approximations to hard quantum optimization problems.

Core claim

By using the natural quantum dynamics of Rydberg atom systems in combination with semidefinite programming and randomized rounding, the algorithm achieves a conditional approximation ratio of 0.651 for quantum Max Cut, compared to 0.614 from SDP alone. The advantage persists if the annealing procedure obtains a state with only 89 percent of the true ground state energy.

What carries the argument

The hybrid quantum-classical algorithm that integrates Rydberg atom annealing output with SDP and randomized rounding to produce the improved approximation

If this is right

  • It provides a better approximation than pure classical SDP methods for quantum Max Cut
  • The method is robust to imperfect quantum annealing reaching only 89 percent of ground state energy
  • It opens a route for hybrid algorithms combining quantum dynamics with classical optimization
  • The ratio is conditional on the performance of the Rydberg system

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This approach might generalize to other QMA-complete problems if similar quantum dynamics can be harnessed
  • If Rydberg systems can be scaled, it could lead to practical quantum advantage in approximation tasks
  • The 0.651 ratio might be improved further by better integration or different quantum systems
  • It suggests that physical quantum systems can provide an independent advantage beyond what SDP captures

Load-bearing premise

The specific combination of Rydberg-atom annealing output with SDP and randomized rounding actually produces the stated 0.651 ratio

What would settle it

An experiment or calculation showing that the Rydberg output does not provide any additional information beyond what the SDP already uses, resulting in no improvement over 0.614

Figures

Figures reproduced from arXiv: 2606.27224 by Felix Huber, Matthieu Saubanere, Tom\'as Crosta.

Figure 1
Figure 1. Figure 1: FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. A lower bound of the solution is rounded into a [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: shows the ratio µ for 1000 coefficients in 6-, 12- and 18-qubit systems. The ratio is always above 0.95, but the mean value of µ decreases with the number of qubits. This indicates that µ can exceed the approximation ratio by a large margin. FIG. 4. Ratio µ associated with ϱr for 1000 random graphs on 6-, 12- and 18-qubit systems. Noise Robustness In practice, current quantum platforms can obtain only appr… view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Lower bound on the approximation ratio versus the [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. Ground state approximation of 1000 Gibbs states [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
read the original abstract

Quantum Max Cut, also known as the anti-ferromagnetic Heisenberg Hamiltonian, is a QMA-complete problem which serves as a benchmark for approximation algorithms in quantum physics. Here we develop a hybrid approximation algorithm to quantum Max Cut, which uses the natural quantum dynamics of Rydberg atom systems in combination with semidefinite programming and randomized rounding. It achieves a conditional approximation ratio of $0.651$, compared to the best-known ratio of $0.614$ that relies on semidefinite programming alone. The algorithm is robust in the sense that the advantage persists even if the annealing procedure of the Rydberg atom system obtains a state whose energy is only $89\%$ of its true ground state energy. Our approach opens a new route for hybrid quantum-classical algorithms that combine quantum with classical optimization methods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript develops a hybrid approximation algorithm for Quantum Max Cut (the anti-ferromagnetic Heisenberg model) that combines Rydberg-atom annealing dynamics with semidefinite programming and randomized rounding. It claims a conditional approximation ratio of 0.651 (versus the prior 0.614 SDP-only bound) that remains valid even when the Rydberg procedure reaches only 89% of the true ground-state energy.

Significance. If the hybrid ratio derivation is correct, the result would constitute a concrete improvement in approximation algorithms for a QMA-complete problem by integrating physical quantum dynamics with classical post-processing, and would supply an explicit robustness threshold (89%) that could guide future hybrid quantum-classical schemes.

major comments (1)
  1. [Abstract (paragraph 2)] The central claim that the Rydberg output, when inserted into the SDP and rounding pipeline, produces a 0.651 ratio (even at 89% ground-state energy) is load-bearing but is stated without an explicit calculation or bound in the provided text. The abstract asserts the numerical improvement but supplies no equations relating the Rydberg expectation values or overlap to the final ratio, so it is impossible to verify that the advantage is not already subsumed by the classical 0.614 analysis.
minor comments (1)
  1. The term 'conditional approximation ratio' is used without a precise statement of the conditioning assumptions (e.g., on the Rydberg state fidelity or the SDP feasible set).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater transparency in the abstract. We address the comment below and will make the requested revision to the manuscript.

read point-by-point responses

  1. Referee: [Abstract (paragraph 2)] The central claim that the Rydberg output, when inserted into the SDP and rounding pipeline, produces a 0.651 ratio (even at 89% ground-state energy) is load-bearing but is stated without an explicit calculation or bound in the provided text. The abstract asserts the numerical improvement but supplies no equations relating the Rydberg expectation values or overlap to the final ratio, so it is impossible to verify that the advantage is not already subsumed by the classical 0.614 analysis.

    Authors: We agree that the abstract, as currently written, does not contain the explicit relation or bound and therefore does not allow immediate verification of the improvement. The full derivation appears in Section 4, where we show how the Rydberg expectation value ρ is substituted into the SDP objective and how the resulting vector is rounded to obtain the 0.651 guarantee; the same section also derives the 89 % robustness threshold by bounding the degradation in the SDP value as a function of the energy deficit. To make this traceable from the abstract, we will add one sentence that states the key relation between the Rydberg overlap and the improved ratio and points to the relevant theorem. This change will be made in the revised version. revision: yes

Circularity Check

0 steps flagged

No circularity: 0.651 ratio presented as algorithmic output, not self-defined or fitted

full rationale

The abstract states the hybrid algorithm (Rydberg annealing + SDP + randomized rounding) achieves a conditional 0.651 ratio, robust to 89% ground-state energy. No equations or text in the provided material define the ratio in terms of itself, rename a fitted parameter as a prediction, or rely on self-citation chains for the central claim. The improvement over the 0.614 SDP baseline is asserted as a consequence of the described pipeline without reduction to tautology. This matches the default expectation of a non-circular paper; the derivation chain is treated as self-contained pending explicit equations in the full manuscript.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no equations or sections from which free parameters, axioms, or invented entities can be extracted.

pith-pipeline@v0.9.1-grok · 5667 in / 1169 out tokens · 49302 ms · 2026-06-26T04:19:45.317015+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

47 extracted references · 1 canonical work pages

  1. [1]

    HybQuant

    For each qubiti, concatenate the 3 columns ofLcor- responding toX i, Yi, Zi, to construct a set of unit vectors xi ∈R 9n [7]. Now sample a random matrixR∈R 3×9n with mean zero and standard deviation one. Then set, vi = Rxi ∥Rxi∥ =   aX i aY i aZ i   .(7) It is known that substituting these coefficients into Eq.(6) returns at least 0.498 of the true ...

    2024

  2. [2]

    M. X. Goemans and D. P. Williamson, J. ACM42, 1115–1145 (1995)

    1995

  3. [3]

    Cubitt and A

    T. Cubitt and A. Montanaro, SIAM Journal on Comput- ing45, 268 (2016)

    2016

  4. [4]

    J. W. Helton, Annals of Mathematics156, 675 (2002)

    2002

  5. [5]

    Navascu´ es, S

    M. Navascu´ es, S. Pironio, and A. Ac´ ın, New Journal of Physics10, 073013 (2008)

    2008

  6. [6]

    Pironio, M

    S. Pironio, M. Navascu´ es, and A. Ac´ ın, SIAM Journal on Optimization20, 2157–2180 (2010)

    2010

  7. [7]

    Baumgratz and M

    T. Baumgratz and M. B. Plenio, New Journal of Physics 14, 023027 (2012)

    2012

  8. [8]

    Gharibian and O

    S. Gharibian and O. Parekh, Leibniz International Pro- ceedings in Informatics (LIPIcs)145, 31:1 (2019)

    2019

  9. [9]

    Anshu, D

    A. Anshu, D. Gosset, and K. Morenz, Beyond product state approximations for a quantum analogue of Max Cut (2020). 6

    2020

  10. [10]

    Parekh and K

    O. Parekh and K. Thompson, Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Informatik Leibniz International Proceed- ings in Informatics (LIPIcs),198, 102:1 (2021)

    2021

  11. [11]

    Lee, Optimizing quantum circuit parameters via SDP (2022), arXiv:2209.00789

    E. Lee, Optimizing quantum circuit parameters via SDP (2022), arXiv:2209.00789

    arXiv 2022

  12. [12]

    King, Quantum7, 1180 (2023)

    R. King, Quantum7, 1180 (2023)

    2023

  13. [13]

    Lee and O

    E. Lee and O. Parekh, Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Informatik297, 105:1 (2024)

    2024

  14. [14]

    Gribling, L

    S. Gribling, L. Sinjorgo, and R. Sotirov, Improved ap- proximation ratios for the quantum max-cut problem on general, triangle-free and bipartite graphs (2025), arXiv:2504.11120

    arXiv 2025

  15. [15]

    A. Apte, E. Lee, K. Marwaha, O. Parekh, and J. Sud, chloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik351, 101:1 (2025)

    2025

  16. [16]

    Bakshi, A

    A. Bakshi, A. Basu, P. Kothari, and A. Li, Sharp bounds on the eigenvalues of Kikuchi graphs and applications to quantum max cut (2026), arXiv:2605.14994

    Pith/arXiv arXiv 2026

  17. [17]

    A. Apte, O. Parekh, and J. Sud, Conjectured bounds for 2-local Hamiltonians via token graphs (2025), arXiv:2506.03441

    Pith/arXiv arXiv 2025

  18. [18]

    Huber, K

    F. Huber, K. Thompson, O. Parekh, and S. Gharib- ian, Second order cone relaxations for quantum max cut (2024), arXiv:2411.04120

    arXiv 2024

  19. [19]

    Lubinski, C

    T. Lubinski, C. Granade, A. Anderson, A. Geller, M. Roetteler, A. Petrenko, and B. Heim, Frontiers in Physics10, 940293 (2022)

    2022

  20. [20]

    Cerezo, A

    M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio,et al., Nature Reviews Physics3, 625 (2021)

    2021

  21. [21]

    Kucera, C

    S. Kim, S.-W. Ahn, I.-S. Suh, A. W. Dowling, E. Lee, and T. Luo, npj Quantum Information11, 10.1038/s41534- 025-01020-1 (2025)

    work page doi:10.1038/s41534- 2025

  22. [22]

    Schmid, N

    M. Schmid, N. Mohseni, and M. J. Hartmann, Hierar- chical divide and conquer quantum approach to combi- natorial optimization problems with tunable reduction (2025), arXiv:2512.18464

    arXiv 2025

  23. [23]

    Zhou, S.-T

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Physical Review X10, 021067 (2020)

    2020

  24. [24]

    Tene-Cohen, T

    Y. Tene-Cohen, T. Kelman, O. Lev, and A. Makmal, npj Quantum Information12, 50 (2026)

    2026

  25. [25]

    Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Physical Review A97, 022304 (2018)

    2018

  26. [26]

    R. J. Banks, D. E. Browne, and P. Warburton, Quantum 8, 1253 (2024)

    2024

  27. [27]

    Gao and et.al, Phys

    D. Gao and et.al, Phys. Rev. Lett.134, 090601 (2025)

    2025

  28. [28]

    Deng and et.al, Phys

    Y.-H. Deng and et.al, Phys. Rev. Lett.131, 150601 (2023)

    2023

  29. [29]

    Google Quantum AI and Collaborators., Observation of constructive interference at the edge of quantum ergod- icity (2025)

    2025

  30. [30]

    Proctor, K

    T. Proctor, K. Young, A. Baczewski, and et al, Nature Reviews Physics7, 105–118 (2025)

    2025

  31. [31]

    Abbas, A

    A. Abbas, A. Ambainis, B. Augustino, and et al., Nature Reviews Physics6, 718–735 (2024)

    2024

  32. [32]

    Kshetrimayum, S

    A. Kshetrimayum, S. S. Jahromi, S. Singh, and R. Or´ us, Quantum advantage: a tensor network perspective (2026), arXiv:2603.18825

    arXiv 2026

  33. [33]

    Hangleiter, Has quantum advantage been achieved? (2026), arXiv:2603.09901

    D. Hangleiter, Has quantum advantage been achieved? (2026), arXiv:2603.09901

    arXiv 2026

  34. [34]

    Boyd and L

    S. Boyd and L. Vandenberghe,Convex Optimization (Cambridge University Press, Cambridge, UK, 2004)

    2004

  35. [35]

    Henriet, L

    L. Henriet, L. Beguin, A. Signoles, T. Lahaye, A. Browaeys, G.-O. Reymond, and C. Jurczak, Quantum 4, 327 (2020)

    2020

  36. [36]

    C. Chen, G. Bornet, M. Bintz, G. Emperauger, L. Leclerc, V. S. Liu, P. Scholl, D. Barredo, J. Hauschild, S. Chatterjee,et al., Nature616, 691 (2023)

    2023

  37. [37]

    Bornet, G

    G. Bornet, G. Emperauger, C. Chen, B. Ye, M. Block, M. Bintz, J. A. Boyd, D. Barredo, T. Comparin, F. Mez- zacapo,et al., Nature621, 728 (2023)

    2023

  38. [38]

    Geier, N

    S. Geier, N. Thaicharoen, C. Hainaut, T. Franz, A. Salzinger, A. Tebben, D. Grimshandl, G. Z¨ urn, and M. Weidem¨ uller, Science374, 1149 (2021)

    2021

  39. [39]

    A. W. Glaetzle, M. Dalmonte, R. Nath, C. Gross, I. Bloch, and P. Zoller, Physical Review Letters114, 173002 (2015)

    2015

  40. [40]

    Bluvstein, H

    D. Bluvstein, H. Levine, G. Semeghini, T. T. Wang, S. Ebadi, M. Kalinowski, A. Keesling, N. Maskara, H. Pichler, M. Greiner,et al., Nature604, 451 (2022)

    2022

  41. [41]

    Whitlock, A

    S. Whitlock, A. W. Glaetzle, and P. Hannaford, Journal of Physics B: Atomic, Molecular and Optical Physics50, 074001 (2017)

    2017

  42. [42]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. (MIT Press, 2009)

    2009

  43. [43]

    Silv´ erio, S

    H. Silv´ erio, S. Grijalva, C. Dalyac, L. Leclerc, P. J. Kar- alekas, N. Shammah, M. Beji, L.-P. Henry, and L. Hen- riet, Quantum6, 629 (2022)

    2022

  44. [44]

    J. Wang, D. Jansen, I. Frerot, M.-O. Renou, V. Magron, and A. Ac´ ın, Scalable ground-state certification of quan- tum spin systems via structured noncommutative poly- nomial optimization (2026), arXiv:2604.01555

    arXiv 2026

  45. [45]

    Briet, F

    J. Briet, F. M. de Oliveira Filho, and F. Vallentin, Theory of Computing10, 77–105 (2014)

    2014

  46. [46]

    Gatermann and P

    K. Gatermann and P. A. Parrilo, Journal of Pure and Applied Algebra192, 95–128 (2004). 7 Appendix A: Numerical results Approximation for random graphs The main text introduced Algorithm 1 to approximate the ground state energy of the QMC Hamiltonian, Hqmc =− 1 4 X (ij)∈E ωij(I−X iXj −Y iYj −Z iZj).(A1) We compared the upper bound from Eqs. (20), (23) with...

    2004

  47. [47]

    To construct Bloch vectorsv i ∈R 3, we use the following result

    By construction, these satisfy: xixj = 1 2 tr((XiXj +Y iYj)ϱr).(C7) Now note that these are unit vectorsx i have with dimen- sion 4ninstead of 3. To construct Bloch vectorsv i ∈R 3, we use the following result. Lemma 5(Bri¨ et-de Oliveira Filho-Vallentin [44], Lemma 2.1).Letx i,x j be unit vectors inR n and let R∈R r×n be a random matrix whose entries are...