Quantum computing may improve approximation guarantees for hard problems

Quantum Approximation Complexity of Classical Optimization Problems

Computational Complexity

Summary

This work studies how well quantum computers can find approximate solutions to tough optimization problems compared to classical computers. The authors define new classes that capture how good quantum algorithms can guarantee their results on any input within polynomial time. They show that, assuming some complexity theory assumptions hold, quantum algorithms can sometimes outperform classical ones for certain problems such as factoring and discrete logarithms. However, it remains unknown if this quantum advantage applies to common optimization problems like MaxCut or MaxSAT.

What this means in practice

  • For quantum algorithm developers: Develop algorithms with provable approximation guarantees for problems involving number theory.
  • For cryptography system designers: Assess security and potential quantum vulnerabilities of cryptographic schemes relying on factoring and discrete logarithms under approximation complexity assumptions.

A theory result. No direct application yet.

Authors

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 $\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.