Geometry-Informed Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

Technical Summary: Geometry-Informed Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

Problem Statement
Constrained combinatorial optimization involves finding optimal configurations subject to hard constraints (e.g., assignment, matching, routing). While classical algorithms exist for specific tractable subclasses, many such problems are NP-hard. Quantum approaches, particularly the Quantum Approximation Optimization Algorithm (QAOA), face challenges in near-term devices:

1. Feasibility: Standard QAOA often samples outside the feasible subspace defined by hard constraints.
2. Noise: Device noise induces constraint violations, degrading the quality of samples.
3. Guarantees: Existing methods often lack rigorous end-to-end performance guarantees (polynomial runtime with high probability of finding an optimum) under realistic noise conditions.

The paper addresses the question: When does a noisy quantum sampler enable an end-to-end polynomial-time algorithm with performance guarantees?

Methodology
The authors propose the Noisy Polytime Hybrid Quantum-Classical (NP-HQ) algorithm, a complete pipeline integrating quantum sampling with deterministic classical post-processing. The methodology rests on three pillars:

1. The OFM Kernel and CE-QAOA:
   The approach utilizes the Onah–Firt–Michielsen (OFM) kernel, which defines a specific encoding for problems like the Travelling Salesman Problem (TSP) and Quadratic Assignment Problem (QAP).

   • Encoding: Uses a one-hot encoding where each logical block has exactly one excitation.
   • Dynamics: Employs Constraint-Enhanced QAOA (CE-QAOA) with a block-local XY mixer that preserves the one-hot subspace.
   • Guarantees: Building on prior work [1], the ideal CE-QAOA sampler is shown to assign an inverse-polynomial probability mass ($p_0 = \Omega(n^{-k})$) to the set of optimal solutions, provided specific geometric conditions (phase separation) are met.

2. Deterministic Repair and Scoring:
   To handle noise and infeasible samples, the pipeline includes a classical post-processor:

   • Feasibility Check: Verifies one-hot constraints.
   • Repair: Uses deterministic polynomial-time algorithms (specifically the Hungarian algorithm for assignment problems or swap-based heuristics) to project noisy, infeasible bit-strings back to the nearest feasible solution (e.g., a valid permutation).
   • Scoring: Evaluates the exact objective function on the repaired candidates.
   • Theoretical Basis: The repair map is shown to be a contraction in total variation distance and does not decrease the probability mass of the optimal set.

3. Noise-Robust Analysis:
   The authors derive a Lipschitz-type bound relating device noise to the degradation of the optimal sampling mass. They establish a "noise window" where, if the effective error per layer is sufficiently low, the noisy optimal mass remains inverse-polynomial. This allows for the calculation of a polynomial shot budget required to recover an optimum with high probability.

Key Contributions

1. FPRAS$_q$ (Exact-Hit):
   In the low-noise regime where the ideal sampler assigns inverse-polynomial mass to the optimum, the NP-HQ pipeline constitutes a Fully Polynomial Randomized Approximation Scheme (FPRAS$_q$). It guarantees finding the global optimum with probability $1-\delta$ in polynomial time (quantum circuit calls + classical post-processing).

2. $\varepsilon$-PTQAS (Approximation):
   Beyond the exact-hit regime, the pipeline provides an $\varepsilon$-Polynomial-Time Quantum Approximation Scheme ($\varepsilon$-PTQAS). If the repair-induced objective inflation is controlled, the algorithm yields a $(1+\varepsilon)$-approximation with polynomial runtime.

3. Quantum-Classical Separation:
   The paper establishes a conditional separation between the NP-HQ pipeline and purely classical strategies. Even if a classical sampler is granted:

   • Access to the same efficient repair maps (Hungarian projection).
   • Perfect access to constraint structures (e.g., sampling uniformly from row-one-hot strings).
   • Polynomial time.
     It cannot reproduce the inverse-polynomial optimal overlap on NP-hard kernel-admissible families unless NP $\subseteq$ BPP. The quantum advantage lies strictly in the generation of the sampling distribution, not the classical processing.

4. Heavy-Hitter QAOA (HH-QAOA):
   A refinement that reduces classical post-processing costs. By leveraging the geometry of the quantum distribution, the algorithm identifies "heavy hitters" (high-frequency samples) and filters the candidate set. This reduces the classical post-processing complexity from $O(n^{k+4})$ to $O(n^{k+3})$ (or lower with further compression) without sacrificing approximation guarantees.

5. Hardware Demonstration:
   The complete pipeline was executed on two distinct 127-qubit IBM Eagle-r3 processors (ibm_brisbane and ibm_sherbrooke) using QOptlib TSP instances with up to 100 logical variables.

   • Results: Despite strong noise (two-qubit error rates $\sim 10^{-3}$ to $10^{-2}$), the deterministic repair restored feasibility for all samples.
   • Performance: The repaired solutions matched or improved upon published reference tours in every tested case, demonstrating the viability of the approach on current hardware.

Significance and Claims
The paper claims to provide the first end-to-end optimization guarantee for a hybrid quantum-classical pipeline under device noise that combines:

• Finite-shot optimal recovery.
• Deterministic feasibility restoration.
• Explicit finite-noise lower bounds on recovered optimal mass.
• Polynomial shot complexity and polynomial post-processing runtime.

The authors argue that constrained quantum optimization should be viewed as a unified pipeline where problem structure is exploited in both the quantum dynamics (via the OFM kernel) and the classical processing (via repair maps). The work demonstrates that even in the NISQ era, shallow constrained circuits combined with rigorous classical post-processing can yield provable approximation schemes and competitive results on real hardware.

Limitations and Scope

• The guarantees are instance-dependent, relying on the existence of a positive phase separation ($\delta > 0$) and sufficient mixer envelope weight.
• The "exact-hit" guarantee holds only within a specific noise window; outside this, the scheme degrades to an approximation scheme.
• The quantum-classical separation is conditional on the assumption that NP $\not\subseteq$ BPP.
• The hardware experiments used fixed, warm-start parameters from generic QAOA optimization rather than hardware-native re-optimization, testing the transferability of parameters to noisy devices.