{"id":"arxiv/2610.09584","url":"https://arxiv.org/abs/2610.09584","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum Approximation Complexity of Classical Optimization Problems","domain":"quant-ph","source":"arxiv","authors":["Stuart Hadfield"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}