Leaving Quantum Bias on the Table: Pushforwards as a Path to Quantum Advantage in Constrained Optimization
Abstract
Constrained quantum samplers often produce infeasible outputs that retain information about good feasible solutions. We develop a post-measurement framework that constructs problem-dependent classical feasibility maps from constraint-violation statistics and pushes the raw quantum sampling law forward onto the feasible set. The probability of each repaired solution is the total raw mass of its repair preimage, enlarging the successful sampling event from a target feasible set to its full repair preimage. We derive exact identities for repaired success and expected cost, and separate repair-basin geometry from sampler-dependent probability concentration. For noisy implementations, we distinguish leakage from the encoded subspace from concentration loss within it. For permutation constraints, Hungarian maximum-overlap repair provides an O(n^3) implementation, which we study on traveling-salesman problems (TSP). We derive conditional repaired-success bounds and quantify how basin aggregation reduces the absolute-transfer budget required by these bounds. Noiseless simulations show that optimal repair basins contain selectively overweighted infeasible contributors. For an n=10 TSP instance, pushforward repair recovered the optimum using approximately 10^3 shots, compared with 10^6 shots in the original CE-QAOA workflow without repair. On a 127-qubit IBM processor, using encodings of up to 100 qubits, repaired candidates match reference tours on smaller benchmarks and improve them on larger instances. These results establish concentration of quantum probability on useful repair preimages as a design principle for constrained quantum optimization.
Related
- Separating Geometry From Interference in Constrained Quantum Optimization
- Pushforwards of lc pairs under morphisms to abelian varieties
- Optimal Control of State Constrained Systems via Measure Relaxations and Polynomial Optimization
- Quantum Advantage in Multiple Access Wiretap Channels with Entangled Transmitters
- Accelerated Prox-Level Methods for Unknown Piecewise-Smooth Optimization II: Function-constrained Optimization
BibTeX
@misc{onah2026leaving,
title = {{Leaving Quantum Bias on the Table: Pushforwards as a Path to Quantum Advantage in Constrained Optimization}},
author = {Chinonso Onah and Stuart Hadfield and Kristel Michielsen},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00759},
eprint = {2611.00759},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00759},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Leaving Quantum Bias on the Table: Pushforwards as a Path to Quantum Advantage in Constrained Optimization
AU - Chinonso Onah
AU - Stuart Hadfield
AU - Kristel Michielsen
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00759
UR - https://arxiv.org/abs/2611.00759
AB - Constrained quantum samplers often produce infeasible outputs that retain information about good feasible solutions. We develop a post-measurement framework that constructs problem-dependent classical feasibility maps from constraint-violation statistics and pushes the raw quantum sampling law forward onto the feasible set. The probability of each repaired solution is the total raw mass of its repair preimage, enlarging the successful sampling event from a target feasible set to its full repair preimage. We derive exact identities for repaired success and expected cost, and separate repair-basin geometry from sampler-dependent probability concentration. For noisy implementations, we distinguish leakage from the encoded subspace from concentration loss within it. For permutation constraints, Hungarian maximum-overlap repair provides an O(n^3) implementation, which we study on traveling-salesman problems (TSP). We derive conditional repaired-success bounds and quantify how basin aggregation reduces the absolute-transfer budget required by these bounds. Noiseless simulations show that optimal repair basins contain selectively overweighted infeasible contributors. For an n=10 TSP instance, pushforward repair recovered the optimum using approximately 10^3 shots, compared with 10^6 shots in the original CE-QAOA workflow without repair. On a 127-qubit IBM processor, using encodings of up to 100 qubits, repaired candidates match reference tours on smaller benchmarks and improve them on larger instances. These results establish concentration of quantum probability on useful repair preimages as a design principle for constrained quantum optimization.
ER -