arXiv:2610.09584
Quantum Approximation Complexity of Classical Optimization Problems
Stuart Hadfield
Abstract
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 $\nsubseteq$ 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.
AI Summary
The paper asks how to classify worst-case quantum approximation guarantees for classical optimization problems with efficiently checkable solutions and objective values. It defines $\mathsf{BQ\text{-}APX}$, $\mathsf{BQ\text{-}PTAS}$, and $\mathsf{BQ\text{-}FPTAS}$ using uniform quantum algorithms that return a feasible classical solution meeting the promised ratio with probability at least $2/3$. Runtime includes parameter selection, preparation, measurement, decoding, and repetition. Assuming $\mathsf{NP}\nsubseteq\mathsf{BQP}$, standard approximation gaps and integrality arguments establish strict inclusions between the three quantum classes, with further distinctions for logarithmic, polynomial, and exponential approximation factors. The main quantum–classical separation uses Certified Maximum Order: maximize a certified multiplicative order modulo $N$, whose optimum is the Carmichael function $\lambda(N)$. Factoring and component-group constructions give an exact quantum optimizer. Conversely, any randomized polynomial-time approximation within a polynomial factor yields efficient factoring: a certified order $r$ divides $\lambda(N)$, allowing enumeration of the polynomially many possible missing multipliers before exponent-based factoring. A second construction, Discrete-Logarithm Fitting, has a deterministic $1/2$ approximation and an exact quantum optimizer; any fixed improvement over $1/2$ would solve safe-prime discrete logarithm, by sample concentration over competing hypotheses. The paper also converts decoded expected-score guarantees into bounded-error outputs through an elementary tail bound and repetition. The separations are conditional and arise from exact quantum search on constructed arithmetic problems; the hierarchy witnesses adapt classical results. No quantum ratio advantage is established for unrestricted MaxCut or MaxSAT. Surrogate energies require a separate connection to decoded scores, and oracle-query or streaming-space advantages do not establish explicit-input polynomial-time separations.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.