Quantum Approximation Complexity of Classical Optimization Problems

Title: Quantum Approximation Complexity of Classical Optimization Problems
Author: Stuart Hadfield

Problem Statement

The paper addresses the lack of rigorous worst-case performance guarantees for quantum optimization algorithms. While many quantum methods (e.g., QAOA, DQI) demonstrate high scores on specific instances or provide bounds on expected values (decoded means), they often lack uniform algorithms that guarantee a specific approximation ratio for every input with bounded error. The work seeks to formally define quantum analogues to classical approximation complexity classes (APX, PTAS, FPTAS) and determine whether quantum computation can strictly improve upon randomized classical algorithms in terms of guaranteed solution quality or the time required to achieve a requested accuracy.

Methodology

The author extends the framework of NP Optimization (NPO) problems to include bounded-error quantum algorithms.

1. Definition of Quantum Classes: The paper defines BQ-APX, BQ-PTAS, and BQ-FPTAS. Membership in these classes requires a uniform quantum algorithm that, on every input, returns a feasible classical solution achieving the claimed approximation ratio with probability at least $2/3$. Crucially, the running time includes all steps: parameter selection, state preparation, measurement, decoding, and repetition. The solution's score must be efficiently computable classically.
2. Decoded-Mean to Output Transfer: A key technical tool is Lemma 6 and Corollary 7, which establish a relationship between the expected score of a decoded solution and a bounded-error classical output guarantee. This allows the translation of expectation-based analyses (common in quantum literature) into the strict output guarantees required for class membership.
3. Conditional Separations: The paper constructs specific problems to demonstrate strict inclusions between quantum and classical classes under standard complexity assumptions (e.g., $NP \not\subseteq BQP$ and $Factor \notin FBPP$). These constructions rely on "search padding" and cryptographic hardness.

Key Contributions and Results

1. Formal Hierarchy of Quantum Approximation Classes
The paper establishes a strict hierarchy for quantum approximation classes under the assumption that $NP \not\subseteq BQP$:
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
This hierarchy is witnessed by classical problems:

• Max-E3SAT: Has a deterministic constant-ratio approximation (in APX) but no quantum PTAS.
• Planar Vertex Cover: Has a deterministic PTAS but no quantum FPTAS.
  These results show that the quantum classes are distinct from one another, though they do not yet separate quantum from randomized classical classes for these specific problems.

2. Certified Maximum Order (CMO): A Strong Quantum–Classical Separation
The paper introduces the Certified Maximum Order (CMO) problem, where the goal is to find the multiplicative order of an element modulo $N$ that is certified by a prime factorization of the order.

• Quantum Result: A bounded-error quantum algorithm can find the exact optimum (the Carmichael function $\lambda(N)$) in polynomial time using factoring and period finding. Thus, $CMO \in BQ\text{-}FPTAS$.
• Classical Barrier: Any randomized polynomial-time algorithm guaranteeing even a polynomial-factor approximation ratio for CMO would imply a randomized polynomial-time factoring algorithm.
• Conclusion: Assuming $Factor \notin FBPP$, $CMO \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$. This establishes a conditional separation where quantum algorithms provide exact solutions while randomized classical algorithms cannot even achieve polynomial-factor approximations.

3. Discrete-Logarithm Fitting (DLog-Fit): A Threshold Separation
The paper defines DLog-Fit, a problem involving predicting labels on a sample based on discrete logarithms.

• Classical Baseline: A deterministic algorithm achieves a $1/2$-approximation (predicting the majority label).
• Quantum Advantage: A quantum algorithm can find a perfect fit (exact optimum).
• Classical Barrier: Any fixed improvement over the $1/2$ ratio by a randomized classical algorithm would solve the discrete logarithm problem in a safe-prime subgroup.
• Conclusion: Under the assumption that safe-prime discrete logarithm is not in $FBPP$, $DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$. This demonstrates a gap at the $1/2$ approximation threshold.

4. General Search Padding (Theorem 8)
The paper provides a generic construction showing that any search problem with efficiently verifiable witnesses can be transformed into an NPO problem with a $1/2$ approximation threshold. If a quantum solver exists for the search but a randomized classical solver does not, the resulting optimization problem lies in $BQ\text{-}FPTAS$ but outside $R\text{-}PTAS$.

5. Analysis of Existing Quantum Methods
The paper applies these definitions to existing algorithms:

• QAOA: For fixed-depth QAOA on 3-regular MaxCut, the paper uses the decoded-mean transfer to show that repetition can yield a bounded-error output guarantee (e.g., exceeding $2/3$ of the optimum), placing this specific graph family in $BQ\text{-}APX$.
• Decoded Quantum Interferometry (DQI): The paper notes that while DQI shows improved expected scores on specific families (like folded OPI), establishing a separation in the explicit-input time model requires proving that randomized classical algorithms cannot achieve the same ratio, which remains an open challenge for unrestricted problems.

Significance and Claims

The paper claims to provide the first rigorous definitions for bounded-error quantum approximation classes and to prove that, under explicit complexity assumptions, quantum computation can strictly improve worst-case approximation guarantees compared to randomized classical computation.

• Modest Scope: The author explicitly states that for common, unrestricted problems like MaxCut or MaxSAT, a quantum–classical gap in worst-case output ratios remains open. The established separations rely on specific, often cryptographic, problem constructions (CMO, DLog-Fit) or restricted graph families.
• Theoretical Framework: The work bridges the gap between heuristic quantum performance (often measured by expectation values) and rigorous complexity theory (bounded-error output guarantees). It clarifies that high benchmark scores alone do not establish approximation class membership without uniformity and runtime bounds.
• Future Direction: The paper identifies the search for a uniform quantum algorithm that guarantees a ratio better than the classical hardness threshold for standard problems (like unrestricted MaxCut) as the central open problem in the field.