Metraipolis › archive › dc_dd265d498b2f

Quantum Approximation Complexity of Classical Optimization Problems — arXiv:2610.09584

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.09584
License (as archived)
CC0-1.0
Archived
2026-10-08T12:50:03.080Z
SHA-256 of the archived text
b71f82baca25e0adbe201410b5f6e31655ddf5877164a58d0247122da27a3a77
Stable URL of this page
https://metraipolis.com/documento/dc_dd265d498b2f

How to cite

Quantum Approximation Complexity of Classical Optimization Problems — arXiv:2610.09584 — arXiv (en), https://arxiv.org/abs/2610.09584 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dd265d498b2f (Metraipolis archive dc_dd265d498b2f, sha256 b71f82baca25e0adbe201410b5f6e31655ddf5877164a58d0247122da27a3a77)
BibTeX
@misc{dcdd265d498b2f,
  title = {Quantum Approximation Complexity of Classical Optimization Problems — arXiv:2610.09584},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.09584},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dd265d498b2f; sha256 b71f82baca25e0adbe201410b5f6e31655ddf5877164a58d0247122da27a3a77},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09584. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Classical approximation complexity asks what solution quality can be guaranteed with polynomial-time computation. The classes APX, PTAS, and FPTAS distinguish a fixed approximation ratio, approximation to any fixed accuracy, and approximation schemes whose running time is also polynomial in inverse accuracy. Their randomized counterparts are R-APX, R-PTAS, and R-FPTAS. We define bounded-error quantum counterparts BQ-APX, BQ-PTAS, and BQ-FPTAS. Membership requires a uniform quantum algorithm that, on every input, returns a feasible classical solution achieving at least the claimed approximation ratio with probability at least 2/3. Scores (objective values) must be efficiently classically computable. Running time includes parameter selection, preparation, measurement, decoding, and repetition. Many quantum optimization methods are used heuristically, and high benchmark scores alone do not establish these guarantees. We further establish a conditional hierarchy for logarithmic, polynomial, and exponential approximation factors. Assuming NP $\subsetneq$ BQP, the quantum classes form a strict hierarchy. Problems based on prime factorization and discrete logarithms give conditional quantum-classical separations. Certified Maximum Order has an exact quantum algorithm, while any randomized polynomial-time algorithm guaranteeing at least an inverse-polynomial approximation ratio on every input would yield efficient factoring. Discrete-Logarithm Fitting has an exact quantum algorithm and a deterministic one-half approximation, but any fixed improvement over one half would give a randomized polynomial-time algorithm for the safe-prime discrete logarithm problem. Our results show, under explicit complexity assumptions, that quantum computation can improve worst-case approximation guarantees. A quantum-classical gap for common problems such as MaxCut or MaxSAT remains open.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.09584 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:20:00.319Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).