Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

AI summary

Overview

Research area: Quantum optimization — specifically constrained combinatorial optimization with near-term (NISQ) variational quantum algorithms, hybrid quantum–classical algorithms, and quantum complexity theory.

Technical level: Advanced. The paper combines QAOA-style circuit analysis (Fejér kernel phase filtering, XY mixers, mixer envelopes) with finite-shot complexity accounting, diamond-norm noise bounds, and oracle-model complexity arguments. Readers need comfort with approximation schemes (FPRAS/PTQAS), total-variation and trace-distance bounds, and one-hot encodings.

Scope (one sentence): This paper converts the instance-dependent sampling guarantee of Constraint-Enhanced QAOA into a complete, noise-aware, polynomial-time hybrid pipeline with explicit shot budgets, classical repair and scoring, a conditional quantum–classical separation, and a hardware demonstration on 127-qubit IBM Eagle-r3 processors.

What This Paper Is About

The authors ask when a noisy quantum sampler can be turned into an end-to-end polynomial-time algorithm with provable performance guarantees, rather than just a heuristic that produces good-looking bitstrings. They build on prior Constraint-Enhanced QAOA (CE–QAOA) results showing that the ideal sampler can place inverse-polynomial probability mass, written p₀ = Ω(n^{−k}), on the set of optimal solutions for structured constrained problems. The paper's goal is to wrap that sampler with independent-shot amplification, deterministic feasibility checking, problem-structured repair, and exact scoring, then track the optimal mass through device noise and convert it into explicit shot and runtime bounds — and finally test the whole pipeline on real superconducting hardware for travelling-salesman instances.

Key Contributions

1. A quantum-powered FPRAS (FPRAS_q). The authors show that, inside the exact-hit regime where the ideal optimal mass is p₀ = Ω(n^{−k}), the full sampling–checking–repair–scoring pipeline recovers an optimum with high probability in polynomial runtime, yielding a fully polynomial randomized approximation scheme they call FPRAS_q.

2. A noise-to-runtime translation (the ε-PTQAS). Using a Lipschitz-type total-variation bound ‖P_ε − P₀‖_TV ≤ ½ G(n,p) ε, they show that an instance-dependent noise window preserves exact-hit recovery with O(p n^{k+1} log(1/δ)) shots when the effective depth is G(n,p) = Θ(pn). Outside that window, deterministic repair still guarantees feasibility and gives an instance-dependent (1+ε)-approximation scheme, termed the ε-Polynomial-Time Quantum Approximation Scheme (ε-PTQAS), whenever repair-induced objective inflation is controlled.

3. A conditional quantum–classical separation. Placing NP-HQ inside the Chen–Cotler–Huang–Li NISQ oracle model, they argue that on any NP-hard kernel-admissible promise family no polynomial-time classical sampler can reproduce NP-HQ's inverse-polynomial optimal overlap unless NP ⊆ BPP — even when given the same classical repair map and perfect access to the constraint structure. The separation is thus located in generating the sampling distribution, not in classical post-processing.

4. Heavy-Hitter QAOA (HH-QAOA) and a hardware demonstration. A geometry-informed filtering refinement retains only bitstrings whose empirical frequencies exceed a threshold, shrinking the retained candidate set from O(n^{k+1}) to O(n^k) and reducing classical post-processing cost by one power of n while preserving the conditional guarantees. The complete NP-HQ pipeline is run on 127-qubit IBM Eagle-r3 processors on QOptlib travelling-salesman instances with up to 100 logical variables, matching or improving the published reference tours in every tested case.

Main Findings

• Exact-hit shot bound is logarithmic in confidence. For the circuit-only PHQC algorithm, the no-hit probability at a good grid point decays as (1 − p*^♯)^S ≤ exp(−p*^♯ S), so S ≥ ⌈ln(1/δ)/p*^♯⌉ suffices for success probability ≥ 1 − δ; if p*^♯ ≥ n^{−k}, this becomes S = O(n^k log(1/δ)), and the full pipeline is polynomial whenever the coarse grid satisfies |𝒢| = poly(n).

• Noise costs exactly one extra power of n in shots. Under the per-layer error condition ε ≤ (2p₀/G(n,p))(1 − 1/G(n,p)), the noisy optimal mass obeys p_min(ε) ≥ p₀/G(n,p) ≥ (c/G(n,p)) n^{−k}, giving S = ⌈(G(n,p)/c) n^k log(1/δ)⌉ and, with G(n,p) = Θ(pn), S = O(p n^{k+1} log(1/δ)). Retaining a G(n,p)^{−1} fraction of the ideal optimal mass is the stated sufficiency condition.

• Noise is bounded, not assumed away. The trace-distance triangle inequality plus channel contractivity gives ‖P_ε − P₀‖TV ≤ ½ G(n,p) ε, where ε bounds the diamond-norm distance of one effective noisy layer from the identity. A primitive two-qubit depolarizing channel with parameter η satisfies ½‖Λ_η − I‖⋄ = (15/16)η ≤ η, which is how local gate error is folded into the per-layer parameter.

• Classical post-processing is cheap. Feasibility checking costs O(n²) per key, polynomial-time repair costs O(n³), and exact scoring costs O(n²), for total classical work O(S n³). With K unique sampled bitstrings (K ≤ min(S, 2^L), L = n²), the loop runs in T(K,n) = O(K n² + K log K), effectively quadratic in n for fixed-shot experiments.

• Pipeline guarantee inherits from the OFM kernel. The Onah–Firt–Michielsen kernel fixes the one-hot encoded manifold (dimension n_loc^m; for assignment/TSP with m = n_loc = n, |X| = n^n using n² physical qubits), the symmetry-preserving penalty structure, the block-local normalized XY mixer, and the uniform product initial state. The favourable sampling mass traces to the Fejér-filter bound q₀ ≥ (p+1)C_β / [(p+1)C_β + M_p(δ)(1 − C_β)], which depends only on filter order p, wrapped-phase gap δ, and the optimal-set mixer-envelope weight C_β.

• Effective depth, not gate count, governs the noise budget. Effective depth is G(n,p) = O((p+1)n) = O(pn) under parallel scheduling, while the dense TSP problem Hamiltonian still contains Θ(n³) two-qubit interaction terms per CE–QAOA layer — the paper distinguishes these explicitly.

• Hardware results. On 127-qubit IBM Eagle-r3 devices with QOptlib TSP instances of up to 100 logical variables, the pipeline matched or improved published reference tours in every tested case.

Methodology in Plain English

The authors start from a structured way of encoding constrained problems — such as assignment and routing problems — into qubits, where each "block" of qubits is constrained to hold exactly one excitation. This encoding is chosen deliberately: the mixing operation used in the quantum circuit cannot leave that set of valid one-hot patterns, so the ideal quantum evolution never wanders into nonsense configurations. The cost of a configuration is turned into a phase, and the circuit's repeated cost-and-mix layers act like a filter that amplifies configurations whose phase sits near the optimal phase and suppresses the rest. The prior work they build on quantified this amplification in closed form, producing a lower bound on the probability of sampling an optimal solution that depends only on the circuit depth, the phase gap, and a geometric quantity describing how much of the mixer's probability spread lands on optimal configurations.

On top of this sampler, the authors layer a classical routine that does three things for every measured bitstring: check whether it satisfies the constraints, repair it if device noise has corrupted the one-hot patterns (using polynomial-time assignment and matching algorithms as repair primitives), and score the repaired candidate exactly, keeping the best. Because the repair and scoring steps are polynomial, the only question is how many shots are needed. They answer it twice: once for an ideal sampler, where the shot count scales as the inverse of the optimal sampling probability, and once for a noisy device, where they bound how much total variation a noisy circuit can introduce per effective layer and show how much of the optimal mass survives. Since total variation is a distance on probability distributions, the loss of optimal mass is at worst linear in the accumulated error times the effective depth — which converts a device-level error number directly into a shot budget. Finally, they argue that no classical polynomial-time sampler could produce the same optimum-biased distribution on NP-hard promise families unless standard complexity assumptions fail, and they add a filtering refinement that discards low-frequency outcomes so that fewer candidates need classical processing.

Why This Matters

Research impact. Most variational quantum optimization papers report empirical approximation ratios or expectation values; this one closes the loop from a sampling guarantee to an end-to-end, finite-shot, noise-aware runtime bound, including the classical post-processing cost. It also reframes the quantum–classical separation question: instead of asking whether the quantum device can process constraints better, it argues the advantage, if any, lives in generating the distribution. That gives the field a concrete, falsifiable target and a formal home (the Chen–Cotler–Huang–Li oracle model) for the claim.

Real-world applications (drawn from the problem classes the authors state are covered by the kernel):

• Logistics and routing: travelling salesman (TSP/ATSP) and capacitated vehicle routing.
• Scheduling: job-shop and flow-shop scheduling problems.
• Resource allocation: quadratic assignment, generalized assignment, and multiple-knapsack problems.
• Matching and sharing: k-dimensional matching for k ≥ 3, and shared-transportation problems.

Industry relevance. One author is affiliated with Volkswagen AG, and the hardware experiments use production superconducting processors rather than simulators, on instances up to 100 logical variables. The results suggest a practical recipe for industry: a shallow constraint-preserving quantum sampler, a cheap polynomial classical repair-and-score layer, and a heavy-hitter filter to keep post-processing fast — with an explicit error threshold that tells an operator when the exact-hit guarantee is still in force.

Future Directions

• Extending the exact-hit window. The noise tolerance condition ε ≤ (2p₀/G(n,p))(1 − 1/G(n,p)) shrinks as the effective depth G(n,p) = Θ(pn) grows and as p₀ shrinks. Finding circuit constructions or error-mitigation schemes that enlarge this instance-dependent window, or that avoid paying the full extra power of n in shots, is the obvious next theoretical step.

• Controlling repair-induced objective inflation. The (1+ε) guarantee outside the exact-hit window is conditional on the repair map's objective inflation staying bounded. Characterizing which problem families admit repair maps with provable inflation bounds — beyond the Hungarian- and Blossom-based primitives used here — is an open problem the paper leaves instance-dependent.

• Scaling and thresholding HH-QAOA empirically. HH-QAOA reduces the candidate set from O(n^{k+1}) to O(n^k) and lowers post-processing cost by one power of n, with the flow diagram attributing an O(n^{k+3}) cost to that stage (Theorem 30). How to set the frequency threshold in practice, and how the reduction behaves beyond the 127-qubit / 100-variable demonstrations, is not settled.

• Testing the separation claim. The quantum–classical separation is conditional (it would imply NP ⊆ BPP otherwise). Constructing small kernel-admissible promise families where the classical sampler's overlap can be measured against NP-HQ's would give empirical traction on a fundamentally complexity-theoretic statement.

Target Audience

Quantum algorithm researchers working on variational and sampling-based optimization; complexity theorists interested in NISQ-era oracle models and hybrid quantum–classical separations; and industrial practitioners in logistics, scheduling, or operations research who want to know what guarantees — and what qubit counts, depths, and error rates — a near-term quantum optimization pipeline actually delivers. Readers should have graduate-level familiarity with QAOA, approximation schemes, and quantum channel distance measures; the hardware results and pipeline description are accessible to a broader technical audience.

Authors’ abstract

When does a noisy quantum sampler yield an end-to-end polynomial-time optimization algorithm with performance guarantees? Building on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA, we show that inverse-polynomial ideal probability on the optimal set, together with independent sampling, polynomial-time feasibility repair, and scoring, produces an exact-hit fully polynomial randomized approximation scheme, which we call an FPRASq. This guarantee survives device noise within an instance-dependent window. For effective circuit depth linear in the product of layer count and problem size, preserving an inverse-depth fraction of the ideal optimal mass increases the required shot complexity by one power of the problem size. Beyond this window, deterministic repair guarantees feasibility and provides an instance-dependent approximation guarantee whenever the induced objective inflation is controlled. The resulting NP-HQ algorithm fits the Chen-Cotler-Huang-Li oracle model. On any NP-hard kernel-admissible promise family, reproducing its inverse-polynomial optimal overlap with a polynomial-time classical sampler would imply that NP is contained in BPP, even with identical repair and perfect access to the constraint structure. Thus, the separation lies in generating the sampling distribution. We further introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical post-processing cost by one power of the problem size. Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables and match or improve every tested QOptlib reference tour.