🧬 biology

Polynomial Time Quantum Approximation Schemes for Constrained Optimization

This paper establishes that a noisy quantum-classical pipeline based on Constraint-Enhanced QAOA, augmented with shot amplification and deterministic repair, constitutes a fully polynomial randomized approximation scheme (FPRAS $_q$ ) and an $\varepsilon$ -Polynomial-Time Quantum Approximation Scheme ( $\varepsilon$ -PTQAS) for constrained optimization, demonstrating a provable quantum advantage over classical samplers and validating the approach on 127-qubit hardware.

Original authors: Chinonso Onah, Kristel Michielsen

Published 2026-10-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Chinonso Onah, Kristel Michielsen

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ⚕️ This is an AI-generated explanation of a preprint that has not been peer-reviewed. It is not medical advice. Do not make health decisions based on this content. Read full disclaimer

In the world of computing, some problems are not just difficult; they are a specific kind of impossible for traditional machines to solve quickly. These are known as constrained optimization problems. Imagine trying to plan a delivery route for a fleet of trucks. You must visit every customer exactly once, stay within weight limits, and finish as fast as possible. The number of possible routes is so vast that even the most powerful supercomputers would take longer than the age of the universe to check them all one by one. For decades, scientists have hoped that quantum computers, which use the strange rules of subatomic particles to process information, could cut through this complexity. However, current quantum machines are noisy and error-prone. They often produce answers that are mathematically impossible, like a route that visits the same city twice or skips a stop entirely. The big question has been whether these imperfect machines can still be part of a reliable system that guarantees a good solution in a reasonable amount of time.

A team of researchers has now answered this question by building a complete pipeline that combines a noisy quantum computer with a classical computer to solve these hard problems. They focused on a specific type of quantum algorithm called the Constraint-Enhanced QAOA, which is designed to respect the rules of the problem while searching for the best answer. Their work shows that even when the quantum machine makes mistakes due to noise, a clever classical computer program can fix those mistakes instantly. By checking the quantum output, repairing any broken routes, and scoring the results, the system can find the optimal solution with high confidence. The researchers proved mathematically that this hybrid approach works in polynomial time, meaning the time it takes to solve the problem grows at a manageable rate as the problem gets bigger, rather than exploding into infinity.

The core of their discovery lies in how the quantum and classical parts work together. The quantum computer acts as a sampler, generating a vast number of potential solutions. Because of the noise in the machine, many of these samples are flawed; they might violate the rules of the problem, such as assigning two trucks to the same road or leaving a city unvisited. In the past, scientists might have simply thrown away these bad samples, but that would waste the quantum computer's effort. Instead, the researchers developed a method where the classical computer acts as a repair shop. It takes every single sample, even the broken ones, and uses a well-known mathematical technique to fix them. If a route is missing a city or has a duplicate, the classical computer rearranges the path to make it valid again, ensuring every city is visited exactly once. This repair process is fast and deterministic, meaning it always produces a valid result.

Once the samples are fixed, the system scores them to see which one is the best. The researchers demonstrated that if the quantum computer is tuned correctly, it naturally produces a higher number of good solutions than bad ones, even in a noisy environment. They showed that by running the quantum circuit enough times, the system is guaranteed to find the perfect solution. They proved that the number of times the machine needs to run to find the answer grows in a predictable way as the problem size increases. This means the method is not just a lucky guess; it is a rigorous algorithm with performance guarantees. The team calls this a fully polynomial randomized approximation scheme, a technical way of saying it is a reliable, fast method for finding near-perfect answers to hard problems.

To test their theory, the researchers took their algorithm to real hardware. They used a 127-qubit quantum processor from IBM, a machine that is currently available but still suffers from significant noise. They applied their system to a set of traveling salesman problems, where the goal is to find the shortest route visiting a specific number of cities. The problems ranged from small instances with 16 logical variables to larger ones with 100. Despite the noisy environment, the system worked. The quantum computer generated a stream of raw data, most of which was invalid. The classical repair step then fixed every single one of these invalid routes. The final results were impressive: for the smaller problems, the system matched the best known solutions perfectly. For the larger, more difficult problems, the system actually found routes that were better than the previously published reference solutions.

The researchers also explored how to make this process even faster. They realized that the quantum computer tends to produce a few very common answers and many rare ones. Instead of checking every single repaired route, they developed a filtering method that focuses only on the most frequent candidates. This "heavy-hitter" approach drastically reduced the amount of work the classical computer had to do, cutting down the time needed to process the results without losing the guarantee of finding the best answer. This refinement makes the entire pipeline much more efficient, suggesting that it could scale to even larger problems in the future.

A crucial part of their work was proving that this advantage comes from the quantum computer itself, not just the classical repair step. They showed that if a purely classical computer tried to do the same job—generating random routes and then fixing them—it would fail to find the optimal solution efficiently. The quantum computer's ability to concentrate its probability on the best solutions is what makes the difference. Without this quantum bias, the classical repair step would be searching for a needle in a haystack. The study establishes that the quantum machine provides the essential head start, while the classical computer ensures the result is usable.

The findings suggest a new way of thinking about quantum computing. Rather than waiting for perfect, error-free machines that may be decades away, this work shows that we can build powerful tools today by combining noisy quantum samplers with robust classical repair. The system does not require the quantum machine to be perfect; it only needs it to be biased toward the right answer. By accepting the noise and building a system that can handle it, the researchers have created a practical path forward for solving some of the most difficult optimization problems in science and engineering. Their work on the IBM Eagle-r3 processor serves as a concrete demonstration that this hybrid approach is not just a theory, but a functioning reality that can already outperform existing benchmarks on real-world problems.

Technical Summary: Polynomial Time Quantum Approximation Schemes for Constrained Optimization

Problem Statement

The paper addresses the challenge of solving constrained combinatorial optimization problems (e.g., Traveling Salesman Problem, Quadratic Assignment Problem) on near-term, noisy quantum devices. The core difficulty lies in bridging the gap between quantum sampling and classical post-processing. While quantum algorithms like QAOA can generate candidate solutions, noise often causes samples to violate hard constraints (e.g., one-hot encoding requirements), rendering them infeasible. Furthermore, existing error mitigation techniques primarily target expectation values rather than the finite-shot recovery of optimal bitstrings. The authors ask: When does a noisy quantum sampler enable an end-to-end polynomial-time algorithm with performance guarantees?

Methodology

The authors propose a complete hybrid quantum-classical pipeline called Noisy Polytime Hybrid Quantum-Classical (NP-HQ). This framework integrates three distinct stages:

Quantum Sampling (CE-QAOA):
The pipeline utilizes the Constraint-Enhanced QAOA (CE-QAOA) sampler based on the Onah–Firt–Michielsen (OFM) kernel. This kernel enforces local cardinality constraints (e.g., one-hot encoding) via the mixer Hamiltonian and initial state, confining the quantum dynamics to a structured subspace. The algorithm employs a block-local XY mixer and a diagonal problem Hamiltonian.
Classical Post-Processing (Checker, Repair, Scoring):
Instead of discarding infeasible samples, the NP-HQ algorithm applies a deterministic post-processor:
- Feasibility Check: Verifies if a sample satisfies constraints.
- Deterministic Repair: If a sample violates constraints due to noise, it is repaired using classical polynomial-time algorithms. For assignment problems, this involves projecting the noisy bit-string onto the nearest permutation matrix using the Hungarian algorithm ( $O(n^3)$ ) or a swap-based heuristic.
- Exact Scoring: The repaired candidate is scored exactly.
Heavy-Hitter Refinement (HH-QAOA):
To reduce classical post-processing costs, the authors introduce a filtering mechanism. It identifies "heavy hitters"—bit-strings with empirical frequencies exceeding a threshold. By leveraging the inverse-polynomial optimal mass guaranteed by the quantum kernel, they refine the threshold to reduce the candidate set size from $O(n^{k+1})$ to $O(n^k)$ , significantly lowering the classical runtime.

Key Contributions

1. Theoretical Guarantees: FPRASq and $\epsilon$ -PTQAS

The paper establishes that the NP-HQ pipeline constitutes a Fully Polynomial Randomized Approximation Scheme with quantum resources (FPRASq) under specific conditions:

Exact-Hit Regime: If the ideal CE-QAOA sampler assigns an inverse-polynomial probability mass ( $p_0 = \Omega(n^{-k})$ ) to the set of optimal solutions, and the device noise is within a specific window, the pipeline recovers the global optimum with high probability in polynomial time.
Noise Robustness: Using a Lipschitz-type total-variation bound, the authors translate device noise levels into a lower bound on the post-noise optimal mass. They prove that as long as the effective error per layer $\epsilon$ satisfies $\epsilon \leq p_0 / G(n, p)$ , the optimal mass remains inverse-polynomial, preserving the polynomial shot complexity $S = O(p n^{k+1} \log(1/\delta))$ .
Approximation Regime: Outside the exact-hit window, the deterministic repair ensures feasibility. If the repair-induced objective inflation is controlled, the algorithm yields an instance-dependent $(1+\epsilon)$ -approximation scheme, termed $\epsilon$ -PTQAS.

2. Quantum-Classical Separation

The authors place the algorithm within the Chen–Cotler–Huang–Li oracle model. They demonstrate a conditional separation between the hybrid NP-HQ pipeline and purely classical strategies:

Even if a classical algorithm is granted the same polynomial-time repair (Hungarian projection) and access to constraint structures (e.g., row-one-hot strings or uniform permutations), it cannot reproduce the inverse-polynomial optimal overlap uniformly over NP-hard kernel-admissible families unless NP $\subseteq$ BPP.
The separation lies in the generation of the sampling distribution, not in the classical processing of the samples.

3. Heavy-Hitter QAOA (HH-QAOA)

The paper introduces a geometry-informed filtering refinement. By utilizing the specific structure of the CE-QAOA output distribution, the threshold for heavy hitters can be raised, reducing the candidate set size and classical post-processing complexity by a factor of $n$ without sacrificing approximation guarantees.

Experimental Results

The authors validated the complete pipeline on 127-qubit IBM Eagle-r3 processors (specifically ibm_brisbane and ibm_sherbrooke) using QOptlib traveling-salesman instances with up to 100 logical variables ( $n^2$ qubits).

Noise Environment: The experiments operated in a strongly noisy regime (two-qubit gate errors $\sim 10^{-3}$ to $10^{-2}$ ), where raw feasibility was extremely low.
Performance: Despite the noise, the deterministic Hungarian repair successfully mapped all sampled outcomes to valid permutations.
Quality: The best repaired tours matched or improved upon published reference tours in every tested case. For smaller instances (e.g., wi4–wi7), the algorithm matched the reference solutions exactly, while for harder instances (e.g., dj9, dj10), it achieved improvements of 7.8% to 12.5% over the reference solutions.
Efficiency: The classical post-processing cost was negligible compared to the hardware execution overhead, even with full repair applied to all samples.

Significance and Claims

The paper claims to provide the first end-to-end optimization guarantee for a noisy quantum pipeline that combines:

Finite-shot optimal recovery.
Deterministic feasibility restoration.
An explicit finite-noise lower bound 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 quantum-classical pipeline where problem structure is exploited at both stages. They assert that the quantum advantage is not merely in constraint handling (which can be done classically) but in the structured sampling distribution that biases the quantum kernel toward the global optimum, a feat unattainable by efficient classical samplers under standard complexity assumptions. The work demonstrates that shallow, constrained circuits on current hardware, when paired with robust classical repair, can produce high-quality solutions for NP-hard problems.