Skip to content
DraconiticResearch
Search Sources API
197,761 studies31 sourcesUpdated 41 min ago
PreprintCC BYHAL

A 0.651-approximation to quantum Max Cut via Rydberg atoms

  • Tomás Crosta
  • Matthieu Saubanere
  • Felix Huber
Open at sourcePDFDOICite

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.

Related

  1. Quantum Walks on Arbitrary Spatial Networks with Rydberg Atoms
    Gabriel Almeida, Raul Santos, Lara Janiurek +1
    QuantumPeer-reviewedCC BY 4.0Quantum physics & quantum informationCrossref
  2. Unconventional quantum spin mixing of two spin-1 atoms beyond the single-mode approximation
    Yanhong Liu, Fulin Deng, Haoxue Qiao +1
    arXivPreprintarXiv licenceFull textAtomic, molecular & optical physicsCondensed matterarXiv
  3. Qudit encoding in Rydberg-blockaded arrays of atoms
    Achille Robert, Tom Bienaimé
    Physical Review APeer-reviewedPublisher termsFull textOptics & photonicsHAL
  4. On the Ising/tricritical-Ising interface: From W3 symmetry to Rydberg atoms
    António Antunes, Junchen Rong
    arXivPreprintCC BY 4.0Full textAtomic, molecular & optical physicsCondensed matterarXiv
  5. Direct tests of conformal symmetry with Rydberg atoms: assessment and proposals
    Junchen Rong, Slava Rychkov
    arXivPreprintCC BY 4.0Full textAtomic, molecular & optical physicsCondensed matterarXiv

Cite

BibTeXRIS
BibTeX
@misc{crosta20260651approximation,
  title = {{A 0.651-approximation to quantum Max Cut via Rydberg atoms}},
  author = {Tomás Crosta and Matthieu Saubanere and Felix Huber},
  howpublished = {HAL},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2606.27224},
  eprint = {2606.27224},
  archivePrefix = {arXiv},
  url = {https://hal.science/hal-05845058v1},
  note = {CC BY},
}
RIS
TY  - UNPB
TI  - A 0.651-approximation to quantum Max Cut via Rydberg atoms
AU  - Tomás Crosta
AU  - Matthieu Saubanere
AU  - Felix Huber
PY  - 2026
DA  - 2026/10/30
PB  - HAL
DO  - 10.48550/arxiv.2606.27224
UR  - https://hal.science/hal-05845058v1
AB  - 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.
ER  -