WorksPhysics and Astronomy
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.
Introduction
Constrained quantum optimization is often implemented as a hybrid pipeline in which a quantum circuit produces candidate strings followed by classical objective evaluation. However, in highly constrained applications such as routing, assignment, scheduling, matching, and related combinatorial problems with hard structural constraints, the rate of direct feasible samples can remain small even when the sampled strings exhibit strong instance-dependent structure. To exploit this structure, we propose that problem-dependent classical processing of measured samples forms a third layer of the hybrid algorithm, following mixer transport and phase-sensitive interference [1]. This layer can expose constraint information present in the measured distribution, guide feasibility-restoring operations, and separate the contribution of the quantum sampler from that of subsequent classical processing. Such a layer is especially relevant for samples produced on near-term devices, where noise can further reduce the feasible-hit rate while leaving a large population of biased, noisy, or infeasible outcomes [2, 3, 4, 5].
The natural question then is what probability distribution does this three-layer hybrid procedure actually produce? Despite the ubiquity of such workflows, this central probabilistic object is usually left implicit. Hybrid performance is often described informally in terms of the raw quantum sampling distribution together with a repair heuristic, as though repair were merely a secondary implementation detail. We argue that once a suitable deterministic repair map is applied to every sample, however, the operational output is the induced law on the feasible set obtained by transporting raw quantum mass through that map. In other words, the relevant output distribution is the pushforward of the raw quantum sampling law through deterministic repair, as illustrated schematically in Figure 1 and numerically in § 5.1. We show that combining structured quantum dynamics with deterministic feasibility restoration can yield efficiency gains that neither the quantum sampler nor the classical repair procedure produces alone. In benchmark studies, using the same repair rule for quantum and reference samples makes their respective mass on good-solution preimages directly comparable. This permits both set-level comparisons through repaired cost CDFs and solution-level comparisons through the repaired probabilities assigned to individual feasible outputs which we exhibit in detail in § 5.1.

Figure 1. Conceptual distributional picture. The target law is shown as the dashed orange dome. At the raw level, neither the classical nor the quantum sampler reproduces the target distribution exactly, but the quantum law is more strongly biased toward it. Applying the same deterministic repair map to both samplers shifts both distributions toward the target. The repaired quantum law moves substantially closer, while the repaired classical law improves but remains farther from the target.
Recent works have established the algorithmic value of classical processing after quantum sampling. Caha, Kliesch, and Koenig incorporated greedy post-processing into the QAOA objective and analyzed approximation and depth tradeoffs for MaxCut [6]. Shirai and Togawa incorporated constraint-restoring post-processing into variational schedules, with simulations and experiments on constrained problems [7]. For the traveling-salesperson problem, Bourreau, Fleury, and Lacomme developed an indirect representation with problem-dependent classical decoding [8, 9]. Bucher et al. combined warm-started mixers, iterative sampling, and greedy repair of noisy hardware outputs [10]. Previous work by two of us incorporated polynomial-time feasibility repair and objective scoring into CE–QAOA, establishing finite-shot and noise-dependent guarantees for hybrid constrained optimization [5]. Sachdeva et al. investigated the distributional effects of greedy classical improvement in large-scale variational quantum optimization, including comparisons with post-processed random sampling [11].
The present work characterizes hybrid quantum–classical optimization through the sampling law induced on the feasible set by systematically constructed, problem-dependent classical repair maps. In the process, we enlarge the optimal-solution sampling event from the feasible optimum set to its complete repair preimage. Analytically, we separate repair-basin geometry from sampler-dependent probability concentration, quantify the role of de terministic tie-breaking, and establish a uniform stochastic-repair reference for permutation constraints. Combining repair-basin aggregation with the amplitude-transfer formalism yields conditional finite-depth and finite-shot success guarantees. We further quantify reductions in sampling requirements and circuit depth thresholds arising from the enlarged success event. Noiseless TSP simulations and superconducting hardware measurements illustrate the resulting concentration of probability on useful repair preimages.
Basic consequences of the pushforward formulation
The pushforward viewpoint is elementary, but it changes what should be counted as algorithmic success. Once every measured configuration is repaired, the raw sample space is partitioned into repair basins
and the probability of obtaining a feasible solution is the total raw probability mass contained in . Thus, deterministic repair replaces the pointwise task of sampling directly by the less restrictive task of sampling any raw configuration that repairs to . A large basin provides a large combinatorial capture region, while the quantum circuit determines how strongly that region is actually populated.
Several basic properties make this interpretation especially attractive for near-term quantum sampling tasks. The pushforward remains a normalized probability law, and the expected cost after repair is obtained simply by repairing each raw sample and then evaluating the cost of the resulting feasible solution. Since the repair map sends every sample into the feasible set and fixes feasible points, it is idempotent. Applying the same deterministic repair map to two raw sampling laws cannot increase their total-variation distance. Repair therefore cannot manufacture a distinction between a quantum sampler and its baseline, while changing the optimization-relevant event from a feasible target set to its larger raw preimage , thereby exposing bias already present in the raw sampling law. Finally, when is polynomial-time computable, samplewise repair adds only classical work for shots and therefore preserves polynomial end-to-end runtime. These structural and computational properties are collected formally in Proposition 9 of Subsection A.1.
At the dynamical level, enlarging the successful event reduces the amount of coherent shell-transfer amplification that must be generated by the quantum circuit at a fixed shot and confidence budget. The resulting reduction in required circuit depth is particularly valuable because phase alignment becomes progressively more demanding as additional layers introduce a larger number of interfering path contributions. The classical repair map supplies combinatorial basin volume, whereas the quantum circuit supplies nonuniform concentration within good basins.
Paper roadmap. The remainder of the paper is organized as follows. § 2 introduces the nested OFM geometry, identifies the multidimensional constraint statistics retained by the penalty Hamiltonian, and develops problem-dependent feasibility repair as a classical OFM primitive. § 3 formulates the repaired output as a pushforward law, derives the exact basin and repaired-success identities, and separates encoded support from leakage under noise. § 4 specializes the framework to the TSP using Hungarian maximum-overlap repair and derives the repaired-success bound and logarithmic-depth threshold. § 5 studies the repaired law in noiseless simulation and on noisy superconducting hardware. § 6.1–§ 6.5 discuss basin amplification, phase-control requirements, the separation between combinatorial volume and quantum concentration, and the implications for hybrid algorithm design. Appendix § 11.§ 1 collects the structural properties of deterministic pushforwards, while App. § 11.§ 3–§ 11.§ 4 address deterministic tie-breaking, full-cube sampling, and problem-dependent repair statistics beyond the permutation setting.
Maximizing Problem Structure via OFM Primitives
Layers of Problem-Algorithm Codesign
Many constrained combinatorial optimization problems possess a nested geometry,
where is the ambient binary space, is a structured encoded configuration space, and is the feasible set. For one-hot product encodings, we write
where is the number of local one-hot choices available in each register, and is the number of registers, even though the same problem may be represented algebraically in an ambient space containing qubits. The local cardinality constraints defining and the residual global constraints defining play different algorithmic roles and should therefore be treated accordingly.
The Onah–Firt–Michielsen (OFM) kernel introduced in Ref. [12] provides a framework for exploiting this nested structure throughout a hybrid quantum–classical workflow. It specifies the encoded subspace, its constraint symmetries, the compatible mixer family, and the structured decomposition of the diagonal Hamiltonian. Crucially, local fixed-cardinality constraints are built into the initial state and preserved by the mixing operator. The remaining global feasibility conditions are retained as diagonal penalty terms and used dynamically to generate problem-dependent phases. In this work, we study how the same constraint geometry can be used classically after measurement to transport the raw sampling law onto the feasible set. We recall the formal definition next.
Definition 1 (Onah–Firt–Michielsen kernel [12]). *An optimization instance belongs to the Onah–Firt–Michielsen kernel if there exist and a one-hot encoder such that
the quantum dynamics is initialized in the fixed-Hamming-weight space
with one excitation in each block. The computational-basis states of are identified with words
We denote this encoded outcome space by
In the encoded basis, the diagonal problem Hamiltonian decomposes as
where encodes the objective, contains the symmetry-preserving global constraint penalties, and contains additional diagonal penalties that need not preserve the full kernel symmetry. The following requirements hold:
(a) Penalty structure. The Hamiltonian is a sum of squared affine residual one-hot, degree, or capacity penalties, optionally together with linear forbids, with integer coefficients bounded by . Consequently,
(b) Pattern symmetry. The symmetry-preserving part is invariant under block permutations and global symbol relabelings . It therefore organizes the encoded space into structured penalty levels
The term collects problem-dependent penalty contributions that break some or all of these symmetries.
(c) Mixer and initial state. The canonical one-hot mixer is the normalized block-local Hamiltonian
which preserves and satisfies
on the one-excitation sector. The corresponding initial state is
Def. 1 extends naturally to product -hot subspaces when the mixer is replaced by a normalized number-conserving block-local Hamiltonian preserving [13, 14], and covers several NP-Hard problems such as the TSP, QAP, CVRP, shared transportation problems, generalized assignment and multiple-knapsack problems, and -dimensional matching for [12, 15, 16, 17, 18].
OFM Primitives
We call an operation an OFM primitive when it is derived from, and compatible with, the encoded subspace, the residual constraint structure, or the geometry of the feasible set fixed by Def. 1. The principal primitives are:
Encoded initialization primitives, which prepare states supported on and hence enforce the local cardinality constraints at initialization.
(ii) Amplitude transport primitives, such as normalized -type mixers, which move probability amplitude within while enforcing the local cardinality constraints.
(iii) Problem-dependent phase operators. Structure-resolving phase primitives, generated by , , and , which imprint global feasibility, objective, and symmetry-breaking information on the encoded amplitudes; and
(iv) CE–QAOA ansatz. CE–QAOA denotes the variational circuit built from a composition of OFM primitives (i)–(iii) above and belongs, conceptually, to the quantum alternating-operator paradigm [19, 20, 21]. A depth- CE–QAOA circuit prepares
(v) Problem-dependent classical maps. Geometry-aware classical primitives, which read the constraint-violation pattern of a measured sample and deterministically map that sample into the feasible set. Because preserves the fixed-weight sector and is diagonal, every layer maps the encoded subspace to itself:
Measurement therefore produces a Born law
The mixer controls transport on , while the diagonal phases control interference among the transported amplitudes. Neither operation, however, requires every measured string to lie in the smaller globally feasible set .
The first three primitives provide the necessary ingredients for generating the structured quantum sampling law. The fifth primitive, the classical map, continues to exploit problem-derived structural information retained in the quantum-generated samples, extending problem–algorithm co-design beyond quantum measurement.
Application classes for problem-dependent classical maps
The hard constraints appearing in constrained optimization problems typically give rise to multidimensional combinatorial data [22, 23, 24, 25]. Assignment constraints generate row and column populations, routing constraints generate degree, visit, load, and connectivity statistics, scheduling constraints generate machine-load and conflict profiles, and coloring constraints generate local conflict patterns. These statistics enter the quantum formulation through the residual terms used to construct the penalty Hamiltonian. The scalar value of aggregates this multidimensional constraint information. Examining its constituent residuals therefore exposes structural statistics associated with each measured sample which can be used by a problem-dependent classical map to restore feasibility while retaining useful bias present in the sampled output. We specify this structure next.
Multidimensional combinatorial data
Let
denote the structural statistic inherited from the constraint formulation underlying the penalty Hamiltonian in Def. 1. Its coordinates may contain marginal counts, degree residuals, collision multiplicities, capacity excesses, visit populations, conflict locations, machine loads, or related combinatorial information. Suppose that the penalty depends on this statistic through
Then every penalty level
is a union of -fibres,
The statistic therefore resolves the combinatorial classes compressed into each scalar penalty level in Def. 1.
A common penalty construction makes this relation explicit. Suppose that
collects the residual statistics associated with the individual constraints, and let the scalar aggregation map be
where the functions penalize deviations from the required values. Then
The scalar energy combines the coordinates of , while the vector retains the information needed to identify the corresponding violation pattern. Evaluating the individual residuals after measurement therefore provides a natural input for a deterministic repair operation.
For the product-space encodings studied here, a useful example is supplied by transition-count statistics. Fix a reference configuration and define
The matrix may itself be regarded as a structural statistic, . Its column marginals recover the symbol populations of ,
For a constraint requiring prescribed symbol multiplicities , define
The corresponding penalty is then
For permutation constraints with , one has for every , giving
Thus the scalar penalty is obtained by applying to the multidimensional transition-count statistic, while retains the finer information specifying how the constraint violation is distributed among the symbols. The row sums of are fixed by the symbol populations of the reference configuration,
and the column sums recover the symbol histogram of ,
The Hamming distance is obtained from the diagonal through
The matrix retains the complete transition-count profile between and . Its diagonal determines the shell index, its column marginals determine the symbol populations of , and its off-diagonal entries identify the types and multiplicities of the local substitutions. Many constraints involving symbol balance, assignment collisions, capacities, visit multiplicities, and permutation conditions can therefore be expressed through the marginal and contingency-table data contained in [23, 25].
The same principle appears throughout classical constrained optimization. Fixed-margin contingency-table fibres are defined through prescribed marginals [23, 24, 25]. Universality results for integer programming are expressed through slim three-way transportation programs [24]. Overlap matrices and local conflict profiles organize random coloring and constraint-satisfaction problems [22, 26]. Routing, assignment, scheduling, allocation, and packing formulations likewise contain multidimensional statistics that identify and characterize their constraint violations [27, 28, 29]. Further examples of these constraint structures are discussed in App. § 11.§ 4. The following subsection formalizes the connection between constraint geometry, structural statistics, and feasibility repair.
Constraint geometry and feasibility repair
As demonstrated in the foregoing, the scalar penalty value aggregates the multidimensional geometry of a constraint violation. We therefore introduce a problem-dependent structural statistic
that resolves the constituent violation pattern. The statistic refines the penalty levels in the sense that
for some function . Thus, two configurations with the same scalar penalty can still be distinguished by the particular violation patterns that produced that penalty.
Let
denote the globally feasible set. A deterministic feasibility-repair primitive is a map
satisfying
In general, the correction can depend on the complete violation signature,
so that identifies the relevant constraint geometry and applies the corresponding correction. A particularly important realization is a metric projection. Given a problem-compatible distance , define
with a fixed deterministic rule for resolving ties. The metric is defined directly on the encoded word space and weighted to reflect the combinatorial meaning of different violations. For permutation constraints with , the encoded space is and the feasible set is identified with . The Hamming-nearest repair is
where is any fixed total ordering used to break ties. Equivalently, minimizes over feasible permutations. The corresponding maximum-overlap assignment is computed by the Hungarian algorithm in time [30].
Pushforward Law and Repair Basins
Pushforward law and repair basins
We now record the basic identities that govern deterministic repair as a pushforward of the raw quantum sampling law. Throughout this section, let be the raw sample space, let be the feasible set, and let be a deterministic repair map. Let be a probability law on , and let denote the repaired feasible law induced by . The additional structural properties of deterministic repair, including normalization, functoriality, idempotency, compositional closure, total-variation contraction, and efficient samplewise realization, are collected in Prop. 9 of App. A.1.
Proposition 2 (Pushforward law and repair basins). For every feasible solution , the repaired law satisfies
Equivalently, if
denotes the repair basin of , then
Proof. By definition, the repaired random variable is , where on . Therefore,
Since is deterministic, the event is exactly the disjoint union of the events over all such that . Hence
which is the desired identity. Rewriting the index set as the repair basin gives the equivalent basin form
Proposition 3 (Repaired expected score). Let be any score or cost function on the feasible set. Then
Equivalently,
Proof. Since on the discrete space , the expectation of the random variable is given by
By definition of composition, , so
This proves the first identity.
For the second form, note that has law on , so
which is the usual expectation formula under the repaired law.
Success probability after repair
Let be any set of good feasible solutions. Depending on the application, may be the set of optimal solutions, the set of solutions below a target cost threshold, or the set of solutions achieving a desired approximation guarantee. The probability of success after repair is then
Since has law , this may be written as
Using again the pushforward structure, we may rewrite this in terms of the raw law :
Equivalently,
where
is the full preimage of the good set under the repair map. The following result holds.
Proposition 4 (Repaired success probability). Let be any target set of feasible solutions, for example the optimal set or an approximation class. Then
Equivalently,
Proof. By definition,
But the event is precisely the preimage . Therefore
Since is discrete, this may also be written as
which gives the second form.
Applying Proposition 4 to two raw sampling laws and gives
so the difference in repaired success probabilities is the excess probability mass that assigns to the repair preimage relative to . That is, the repaired law aggregates the probability of all raw outcomes that are mapped into the target set . This is the mechanism by which deterministic repair can harvest latent instance-specific structure from the raw quantum sampling distribution. The pushforward formulation itself is sampler-independent and applies equally to full-space samplers such as generic QAOA and to structured subspace samplers such as CE–QAOA. The corresponding full-space specialization for generic QAOA is discussed in App. § 11.§ 2.
Noise, leakage, and breakdown of encoded basin compensation
Recall the CE-QAOA sampler defined by the circuit in Eq. (3). In the noiseless CE–QAOA setting, the raw law is supported on the encoded subspace
rather than on the full ambient hypercube . For permutation-constrained problems, the repair basins partition the encoded space , giving
For a fixed optimal permutation , however, the corresponding basin has cardinality
where measures its size relative to the average. The repaired optimum probability is therefore governed by both the optimal-basin volume and the quantum probability concentrated within it. At the average-basin scale , the basin volume compensates the encoded normalization , producing the factorial scale .1
On noisy hardware, however, this mechanism can break down. In particular, coherent or incoherent errors may leak probability mass outside the encoded subspace and into the ambient cube . Once this happens, the average basin factor no longer controls the full repaired law, because part of the repaired output is now inherited from raw samples that never belonged to the encoded subspace in the first place. We formalize this by separating the noisy raw law into its encoded and leaked components.
Definition 5 (Leakage mass and sector decomposition). Let be a noisy raw sampling law on the ambient outcome space , where denotes the noise strength. Define the leakage mass outside the encoded subspace by
Whenever , define the conditional laws
and
Then
where is supported on and is supported on .
The repaired law inherits the same convex decomposition.
Proposition 6 (Pushforward decomposition under leakage). Let be a deterministic repair map into the feasible set . Then the repaired noisy law satisfies
Equivalently, for every feasible ,
Proof. Apply the linearity of pushforward to the decomposition (9):
The pointwise formula is the corresponding statement evaluated on singleton feasible outputs.
Thus repaired success against any target set decomposes into an encoded contribution and a leaked contribution. That is, let be any target set of feasible solutions. Then
where
The decomposition (11) shows precisely that only the fraction of the raw law that remains inside the encoded subspace can still benefit from the encoded-subspace basin geometry. To make this explicit, define the encoded good-preimage size and the leaked good-preimage size by
Equivalently, introducing the average basin scales
we may write the repaired success in the form
where the concentration coefficients are defined by
For the singleton optimum target , this becomes
If , the out-of-sector contribution in Eq. (12) is defined to be zero and need not be introduced. Otherwise, is given by the preceding ratio.
Using the optimal-basin cardinality , , the encoded contribution in Eq. (13) is exactly . At the average-basin scale , this reduces to the factorial normalization , multiplied by the surviving encoded-sector weight and its concentration factor.
Thus the noiseless compensation of the ambient encoded factor survives only on the non-leaked weight . As leakage grows, the encoded-subspace basin-transfer mechanism is linearly suppressed. Equation (13) isolates the two distinct ways in which noise can destroy pushforward advantage, namely, through sector-violating leakage and in-sector concentration loss. Even if leakage is small, noise can reduce the encoded concentration factor by washing out the constructive interference or shell-aligned mass concentration that originally favored the good repair preimage. The first mechanism is geometric and the second mechanism is dynamical. Coherent noise can be especially harmful because it usually generates both at once.
Case study: TSP with deterministic repair
TSP specialization of the OFM kernel
This case study is natural for two reasons. First, the TSP admits a double one-hot permutation encoding compatible with the OFM kernel. Second, deterministic repair from the encoded row-one-hot subspace to the feasible permutation sector is obtained by solving a maximum-overlap assignment problem with the Hungarian algorithm [30].
Let be a complete weighted graph with and distance matrix . A tour is represented by an binary assignment matrix , where denotes the tour position and the visited city. Feasible tours satisfy the double one-hot constraints
This matches the OFM kernel with one-hot blocks, one per tour position, each of local size .
On the computational basis , the objective is
and feasibility is enforced by row- and column-sum penalties,
optionally together with linear forbids. In the OFM kernel, the row one-hot conditions are already enforced dynamically by the encoded subspace and the block-XY mixer, so on the actual sampled space the row penalty is redundant. The remaining column constraints distinguish feasible tours from infeasible encoded outputs.
Accordingly, the raw CE–QAOA outcome space is the encoded row-one-hot subspace
while the feasible set is the permutation sector
Thus, infeasibility within arises through column collisions, omissions, or both. Deterministic repair acts by mapping outputs to a feasible permutation matrix of maximum overlap, thereby inducing the repaired law on . Maximum-overlap repair can admit multiple optimal assignments. A fixed deterministic tie-breaking rule defines the repair map , and the numerical comparisons use the same implementation for every sampler. Appendix A.3 also constructs a symmetry-controlled stochastic repair whose pushforward of the encoded-uniform law is uniform over .
Enhanced Sampling Advantage with Pushforwards
The shell-transfer formalism of Ref. [1] expresses the amplitude at a target configuration as a sum of contributions from paths through the encoded subspace. The corresponding absolute path weight is determined by the mixer, while the phase-aligned bound quantifies its coherent contribution to the target amplitude. We extend this analysis to the complete repair basin of an optimal solution.
Contributor viewpoint on repaired success In the shell-transfer formalism developed in Ref. [1], for a fixed target output , the amplitude is built from many multi-step paths through the encoded subspace. The shell-transfer recursion packages the absolute weighted contribution of those paths according to their distance from , while the phase-alignment hypothesis determines how much of that absolute mass survives in the complex sum. Consequently, the shell-transfer quantities provide a count of potential contributors, and the phase theorem quantifies the survival of quantum amplitude.
To specialize to the TSP setting, let , so , the feasible set is , and
is the deterministic Hungarian maximum-overlap repair map. Fix an optimal permutation , and let
be its repair basin. The accumulated absolute amplitude weight is
where
and, from Ref. [1 Lem. 2],
The repair basins partition the encoded space, giving
Thus, the average repair-basin cardinality is exactly . We define the relative volume of the optimal repair basin by
The average relative basin volume over is exactly one. For the repaired-success analysis, one obtains an adaptation of Theorem 10 in Ref. [1] by extending the pointwise phase-aligned estimate to the complete repair basin.
Corollary 7 (Pushforward enhanced overlap bound). Assume that for every , all depth- path summands ending at lie in a common arc of angular width . Then
Using [19], this becomes
Equivalently, in terms of the relative optimal-basin volume,
Proof. For each , the pointwise phase-aligned bound of Ref. [1 Theorem 8], specialized to , gives
Summing this bound over the repair basin yields
Using [19] gives [22]. Finally,
establishes [23]. □
The basin factor in Corollary 7 aggregates the quantum probability across all configurations repairing to . At the average basin scale , the combinatorial volume compensates the pointwise normalization , producing the factorial scale . The relative basin volume quantifies the corresponding contribution of the optimal repair basin. We now derive the resulting compensation threshold and its finite-shot consequence.
Theorem 8 (Enhanced depth threshold from pushforward compensation). Consider the OFM kernel TSP specialization with and encoded subspace . Let
be the repair basin of a fixed optimal permutation, with relative basin volume
For any depth- mixer-angle schedule satisfying the phase-alignment hypothesis of Corollary 7, suppose that
where and are polynomially bounded functions. Then
Consequently,
independent shots suffice to recover with probability at least .
For , define the maximal absolute transfer factor
attained at . The minimum depth at which the absolute transfer factor can compensate the optimal-basin normalization,
is
Proof. By Corollary 7,
The stated transport and phase conditions give . For independent shots, the probability of failing to recover satisfies
The choice in (26) therefore establishes the finite-shot guarantee. By Ref. [1, Proposition 9], the maximum of is attained at
For any mixer-angle schedule,
with equality at . The compensation condition (28) is reached at the minimum depth satisfying . Taking logarithms gives (29).
Note, however, that at the transport-maximizing schedule , , Corollary 11 of Ref. [1] excludes the common-cone phase condition for and . But this does not exclude useful sampling at other mixing angles or outside the common-cone regime. The depth characterizes compensation of the absolute-transfer normalization and, as already stated, the corresponding repaired-success guarantee additionally requires the phase-alignment hypothesis of Corollary 7. Indeed, since the repaired success probability cannot exceed unity, the lower bound in Corollary 7 implies the consistency condition
This condition quantifies the compatibility between absolute transfer, phase alignment, and probability normalization, consistent with the phase-interference analysis of Ref. [1].
Numerical Study
We compare quantum and classical sampling laws on the same encoded configuration space. For the TSP, this is the row-one-hot space , whose elements are represented by binary assignment matrices with one active entry in each row. The classical reference sampler draws one city label independently and uniformly from for each tour position , and constructs
Consequently, the classical reference law is
It coincides exactly with the computational-basis measurement law of the uniform CE–QAOA initial state . The ideal CE–QAOA circuit starts from this state and generates a quantum sampling law on the same row-one-hot space. The column constraints defining feasible permutations are left to the problem Hamiltonian and the repair map.
We apply the same deterministic Hungarian maximum-overlap repair to both samplers and compare the resulting feasible laws and . Each instance uses equal numbers of quantum and encoded-uniform samples. In particular, for any permutation , the classical reference probability is
We define experimental success through the complete optimal-cost set
Thus, a raw sample is successful precisely when . The same event is used for every sampler.
Noiseless Simulations
We study single-layer CE–QAOA on TSP instances with from Ref. [31], using the selected best angle for each instance. Although the shell-transfer threshold results are developed for exact lattice-normalized spectra in Ref. [1], earlier CE–QAOA analyses [32, 33] extend the phase-averaging treatment beyond exact lattice spectra through Riemann–Lebesgue averaging. Our numerics, obtained without lattice normalization, are consistent with this broader interpretation. We now examine the resulting repaired sampling laws on some known benchmark instances.
For a cost threshold , define the repaired cost cumulative distribution function by
At the known optimal tour cost , this is the probability of recovering a tour of optimal cost, including all optimal permutations. Figure 2 compares the empirical quantum repaired CDF with the shot-matched encoded-uniform pushforward baseline.

Figure 2. CDFs of repaired tour costs at the selected best angle for . The blue curves represent the repaired quantum laws and the orange curves represent the encoded-uniform pushforward baselines obtained with the same deterministic Hungarian repair map. The quantum laws accumulate greater probability on lower-cost feasible tours over substantial portions of the plotted ranges, with a widening separation across the tested instances.
The repaired quantum CDF lies above the encoded-uniform baseline across substantial portions of the low-cost range in every instance. The separation becomes more pronounced as increases. For , the baseline remains near zero through most of the plotted low-cost region, while the quantum repaired law accumulates substantial probability over low-cost tours. Because both laws are repaired by the same map, these differences are differences in the raw probability assigned to the preimages of the corresponding sets.
A complementary solution-level comparison is shown in Figure 3. For dj8 and dj9, we display the 15 leading feasible solutions ranked by their empirical quantum repaired probabilities and evaluate the encoded-uniform pushforward probabilities of those same solutions. The quantum law assigns greater probability to each displayed solution, with a particularly strong separation for dj9. Thus, the cumulative preference for lower-cost tours seen in the CDFs is accompanied by a solution-by-solution concentration of quantum probability on particular repair preimages.

Figure 3. Solution-level comparison of the repaired feasible sampling laws for the dj8 and dj9 TSP instances at a selected angle. Each panel displays the 15 best feasible solutions ranked by empirical quantum repaired probability. The blue bars show the quantum pushforward , and the orange bars show the encoded-uniform pushforward under the same deterministic Hungarian repair map. The quantum law assigns greater probability to each displayed solution, with the baseline strongly suppressed for dj9 at the displayed resolution. These plots complement the cost-threshold CDFs in Figure 2.
The deterministic tie-breaking convention affects the sizes of the repair basins and hence the encoded-uniform pushforward itself. To quantify this effect, we enumerated all row-one-hot words at . Lexicographically first maximum-overlap repair and the matching solution returned by SciPy 1.17.0 [34], using a zero–one mismatch matrix, assign different permutations to 35.46% of these words. Their respective encoded-uniform repaired laws have total-variation distances 0.395 and 0.208 from the uniform law on permutations. The stochastic symmetry-controlled repair of Appendix § 11.§ 3 has zero total-variation distance. These exact small-size calculations illustrate the role of a fixed tie rule in determining the classical baseline. The quantum and encoded-uniform comparisons above use the same deterministic repair implementation for each instance.
Figure 4 resolves the quantum concentration further into individual raw configurations. It shows infeasible encoded strings that repair to tours of optimal cost 2762 at two CE–QAOA angle pairs. Several individual strings receive more shots than the number expected for an entire average permutation basin under encoded-uniform sampling. These counts identify raw, infeasible contributors to the successful repaired event and show the strength of their quantum weighting.
Figure 4. Raw contributors to the optimal-cost repair preimage at two CE–QAOA angle pairs. Each bar records the number of shots assigned to a raw encoded basis string that repairs to a tour of optimal cost 2762. The dotted line is , the expected shot count of an entire average permutation basin under encoded-uniform sampling. Several individual contributors exceed this reference in both panels.
The combinatorial and dynamical contributions can be distinguished using the basin factors introduced in theorem 8 and § 6.3. For a fixed permutation , the encoded-uniform reference assigns probability , while the quantum law assigns . The CDFs aggregate these probabilities over cost-defined feasible sets, the dj8/dj9 bar plots resolve individual feasible outputs, and the contributor histograms identify tify raw configurations supplying quantum mass to optimal-cost preimages. Together, these comparisons demonstrate the role of both repair-basin volume and instance-dependent quantum concentration in the repaired output law.
Harvesting Quantum Bias on Noisy Superconducting Hardware
We analyze the hardware measurements reported in [5] using the repaired sampling laws considered here. The presentation focuses on the probability assigned to preimages of good tours under the specified repair map. The ideal CE–QAOA evolution produces outcomes in the row-one-hot encoded space . Hardware errors can produce bit strings outside this sector, so the relevant raw measurement space is the ambient cube
Hungarian maximum-overlap repair extends to a deterministic map , taking any measured binary assignment matrix to a maximum-overlap feasible permutation under the fixed tie rule. The noisy hardware law therefore induces
with
For measured samples, Hungarian repair[30] costs in total and produces a feasible permutation from every raw outcome. The empirical repaired law is
The hardware experiment measures how much raw probability is transported into the repair preimages of low-cost feasible tours. As discussed in § 3.3 and in equation (11), in the presence of encoded-subspace leakage, decompose the noisy measurement law as
where and are supported on and , respectively. The repaired hardware law then satisfies
The first term represents repaired contributions from outcomes remaining in the encoded space; the second collects repaired contributions from leaked outcomes. Their sum is the complete repaired output distribution measured in the experiment.
We use single-layer CE–QAOA circuits on the 127-qubit IBM Eagle-r3 processor ibm_brisbane, with QOptlib TSP subset instances containing up to cities, or 100 binary assignment variables [31]. The shallow circuit construction limits coherent depth while the repair operation processes every measured bit string, including outcomes that violate the row-one-hot encoding.
Benchmark instances and transferred single-layer parameters
Seven instances, , require through 100 qubits for their binary assignment encodings. We use the parameter pairs obtained in previous generic-QAOA optimizations and transfer them to CE–QAOA without further hardware parameter optimization [35]. The transferred parameters are reported in Table 1.
| Instance | Best generic-QAOA energy | ||
| wi4 | 0.233 | 2.025 | |
| wi5 | 1.307 | 2.387 | |
| wi6 | 0.748 | 0.741 | |
| wi7 | 2.172 | 0.577 | |
| dj8 | 0.239 | 0.460 | |
| dj9 | 0.002 | 2.507 | |
| dj10 | 1.835 | 2.399 |
Table 1. Generic-QAOA parameters obtained at and transferred to the CE–QAOA hardware circuits. No further parameter optimization was performed on the processor.
All circuits were implemented in Python and transpiled with Qiskit 1.1.2 [36], using device-aware coupling maps and the available native two-qubit gate basis. For each instance, we executed a single CE–QAOA layer with
Measurement-error mitigation and dynamical decoupling were enabled. For each measured outcome , we recorded its repaired image
The empirical raw and repaired feasible fractions are
and
The best repaired tour cost observed in a run is
For a cost threshold , let . The empirical repaired probability of meeting the threshold is
Thus, each observed low-cost repaired tour identifies a raw measurement in a preimage of the corresponding feasible output.
IBM Brisbane: 127-qubit Eagle-r3 processor
Table 2 summarizes the device characteristics recorded for the hardware run. The median two-qubit ECR error was , with a best value of , while the median readout error was . The larger circuits undergo noisy encoded evolution and subsequent measurement on the full binary outcome space. In the language of § 3.3, their repaired law may inherit both probability distorted within and probability leaked into . The experiment therefore probes the complete noisy pushforward .
| Metric | Median value | Best |
| Qubits | 127 | – |
| Two-qubit ECR error | ||
| Readout error |
Table 2. Device characteristics of ibm_brisbane during the reported experiments.
Table 3 compares the best repaired candidates against the reference tour costs distributed with QOptlib [31]. The hardware results reproduce the published optimal costs for the smaller wi instances and improve on the distributed reference costs for the larger dj subsets. The repaired values reported here are known optimal costs, as previously established in Refs. [5, 12]. For the largest instance, the hardware experiment used 10,000 shots, while the noiseless pushforward simulation in § 5.1 recovered an optimum in 1,000 shots. This difference is consistent with the noise-related loss described in § 3.3. The original noiseless CE–QAOA simulations without pushforward in Ref. [12] used shots. However, these figures describe the sampling budgets of the respective experiments under different parameterizations.
| Instance | QOPTLib cost | Repaired hardware cost | Improvement [%] | |
| wi4 | 6 700 | 6 700 | 0 | 0.00 |
| wi5 | 6 786 | 6 786 | 0 | 0.00 |
| wi6 | 9 815 | 9 815 | 0 | 0.00 |
| wi7 | 7 245 | 7 245 | 0 | 0.00 |
| dj8 | 2 794 | 2 762 | 1.15 | |
| dj9 | 2 438 | 2 134 | 12.5 | |
| dj10 | 3 155 | 2 822 | 10.55 |
Table 3. Best repaired tours obtained from ibm_brisbane compared with the reference values distributed by QOptlib [31]. A positive improvement indicates a shorter repaired tour than the reference.
The QOptlib figures in Table 3 are the supplied benchmark reference values. Osaba et al. reported tour costs 2762, 2134, and 2822 on the same dj8, dj9, and dj10 instances in ten independent runs of Quantagonia’s hybrid solver [37]. These match the corresponding repaired hardware costs above. The values were also certified as optimal using mixed-integer programming solvers in earlier work by two of us [12].
Discussion
The pushforward map changes the event counted as success from sampling a particular feasible configuration to sampling any raw configuration in its repair basin. At the combinatorial level, this enlarges the successful event by the volume of the repair preimage. At the dynamical level, the enlarged event reduces the amount of coherent shell-transfer amplification required to reach a fixed success-probability at a fixed depth. The interplay of these two effects leads to further consequences which we now discuss.
From pointwise amplification to basin amplification
The shell-recursion formalism of Ref. [1] characterizes amplitude transport to a target configuration in the encoded product space. For a pointwise successful event, the shell-transfer factor must compensate the normalization associated with a single basis state. The corresponding depth condition scales logarithmically with the local alphabet size, taking the form in the normalization of Ref. [1]. Pushforward repair enlarges the successful event from a fixed optimal permutation to its entire repair basin, , where every configuration in repairs to an optimal solution.
The repair-basin volume enters directly into the amplification requirement. Since the repair basins partition the encoded space , their average cardinality is . Using the relative optimal-basin volume introduced in theorem 8,
the repaired-success bound becomes
At the average basin scale , the combinatorial factor converts the pointwise normalization into the factorial scale . The condition for absolute transfer to compensate the optimal-basin normalization is . Consequently, the compensation depth is
The factorial term determines the average-basin compensation threshold, while in Equation (44) accounts for the volume of the optimal repair basin. For , the larger preimage reduces the required circuit depth. The resulting reduction is especially relevant at finite problem sizes because circuit depth is integer valued. A change in the continuous compensation threshold can remove an entire coherent layer. For the benchmark sizes , the absolute-transfer condition already admits at the average basin scale . Thus, pushforward repair contributes to sampling efficiency through the aggregation of probability over a larger successful event and the corresponding reduction in the absolute-transfer amplification requirement.
Single-layer CE–QAOA and reduced depth as a phase-control resource
The one-layer regime is particularly relevant to the numerical and hardware experiments considered in this work. At shallow depth, the quantum circuit performs fewer coherent operations, while the repair map aggregates the resulting probability over the preimages of feasible solutions. The depth reduction also has a dynamical consequence. Every additional CE–QAOA layer introduces another cost-phase operation and mixer action, enlarging the family of interfering paths contributing to a measured configuration. Reducing the required amplification depth therefore reduces the number of successive operations involved in organizing these contributions. Pushforward repair changes this resource requirement through the size of the successful event. A larger repair basin requires less absolute amplitude transport to reach the same repaired-success threshold. Consequently, repair geometry can reduce both the coherent depth associated with amplification and the complexity of the corresponding phase-control task.
To quantify the finite-size effect, consider a single CE–QAOA layer at the transport-maximizing angle , . Write the optimal repair-basin size as
For a polynomial shot budget , define the depth-one pushforward transport budget
The condition identifies an absolute-transfer budget crossover. For a target failure probability , the finite-shot guarantee instead requires
together with the common-arc hypothesis.
Figure 5 shows how the relative optimal-basin volume and polynomial sampling budgets affect this threshold. Panel (a) identifies the basin enhancement required for single-layer compensation at a fixed unit-shot budget, while panel (b) shows the corresponding increase in the largest problem size satisfying the absolute transfer criterion when the shot budget scales as . The corresponding probability guarantees follow under the phase-alignment conditions in Corollary 7. The derivation and finite-size analysis are given in Appendix § 11.§ 5. The depth-one analysis demonstrates how repair-basin enlargement and classical sampling resources can support shallower coherent circuits. This is relevant to noisy devices, where each additional quantum layer introduces further gate operations, implementation errors, and opportunities for leakage from the encoded subspace.

Figure 5. Depth-one pushforward transport compensation at the maximal absolute-transfer angle . (a) Required relative optimal-basin volume for unit-shot absolute-transfer compensation. Colored markers indicate the largest problem size satisfying the criterion for . (b) Largest problem size for which the depth-one transport budget reaches unity with shots. Both panels quantify absolute-transfer compensation; the finite-shot repaired-success guarantee additionally incorporates the phase-alignment factor.
An important observation is that the average repair-basin size already captures much of the potential resource enhancement. At , increasing the relative basin volume fivefold extends the single-layer threshold only from to . Even increasing the shot budget to extends the threshold only to at the average-basin scale. These diminishing returns highlight the limitations of classical sampling resources and further basin enlargement, motivating additional coherent quantum resources to access larger problem sizes. The persistence of quantum-classical separation in this type of hybrid workflow was briefly discussed in Ref. [5].
Combinatorial basin volume and quantum basin concentration
For a fixed optimal permutation , its basin occupies the fraction and the probability of recovering when the encoded-uniform sampling is followed by Hungarian repair is: . For CE–QAOA, the repaired probability is . The difference between the repaired quantum law and the uniform pushforward is
This quantity measures the excess quantum probability assigned to the optimal repair basin. The distinction can also be expressed through the basin concentration factor
The repaired optimum probability then admits the exact factorization
Here quantifies the combinatorial volume supplied by repair, while quantifies the relative concentration supplied by the quantum sampling law. Values indicate that CE–QAOA assigns greater probability to the optimal repair basin than encoded-uniform sampling. The numerical results exhibit this distinction at two complementary levels. The repaired cost CDFs and the solution-level comparisons in Figure 2 and Figure 3 show how quantum probability is concentrated on low-cost feasible tours and their respective repair preimages. Because both sampling laws are defined on the same row-one-hot encoded space and use the same repair map, these comparisons measure differences in their preimage probabilities.
The contributor histograms in Figure 4 resolve this concentration further at the level of encoded configurations. Several raw strings belonging to an optimum-cost repair preimage receive quantum counts exceeding the average-basin benchmark . These contributors demonstrate how instance-dependent quantum dynamics can populate useful repair preimages far above the uniform reference scale.
Implications for near-term algorithm design
The preceding analysis suggests that the repair map determines the partition of the encoded configuration space into feasible-solution preimages,
while the quantum circuit determines how probability is distributed across this partition. The two operations therefore contribute complementary resources to the hybrid algorithm. For a target set of high-quality feasible solutions, the relevant successful event is the complete preimage . This suggests designing repair maps together with quantum circuits that concentrate probability on those preimages at shallow depth. Such a design objective is naturally expressed through the repaired success probability
or the repaired expected objective
Both quantities incorporate the complete quantum–classical sampling pipeline and can be evaluated directly from repaired measurement outcomes. They also provide natural objectives for selecting circuit parameters and comparing candidate repair strategies.
The separation between basin volume and quantum concentration further clarifies the corresponding algorithmic resources. As established in § 6.3, with the factorization
the factor is determined by the repair geometry, while measures the quantum concentration relative to the encoded-uniform reference. Co-design can therefore investigate both the geometry of useful repair preimages and the dynamics that populate them.
The computational accessibility of favorable sampling distributions is also an important consideration. For MaxCut, Ref. [38] established worst-case complexity barriers to uniformly efficient state preparation achieving a fixed fraction of the optimal gain across all instances. Within the present framework, the corresponding algorithmic question concerns the preparation of quantum distributions with useful concentration on repair preimages and the classical resources needed to transform their samples into high-quality feasible solutions, providing a new avenue for analyzing complete quantum–classical procedures.
Feasibility beyond exact permutation repair
The pushforward construction extends naturally to problems requiring several successive feasibility corrections. In such settings, the raw sampling law is transformed through a composition of problem-dependent classical maps, each resolving a prescribed family of constraint violations. Consider a sequence of repair operations
whose composition maps the raw configuration space into the desired feasible set,
By the functoriality of pushforwards established in Proposition 9,
Thus, the final repaired distribution can be constructed through successive pushforwards of the same underlying sampling law. For any such target set of feasible solutions requiring successive repairs, the complete repair procedure therefore defines a composite successful preimage in the original sampling space.
This formulation applies to constrained problems in which permutation correction, vehicle assignment, capacity restoration, and route-contiguity correction are performed through successive problem-dependent operations. When the individual maps are constructed to preserve previously satisfied constraints, the composition provides a systematic route from encoded samples to globally feasible solutions. Each stage induces a further coarse-graining of the sampling law. This extends the repair-basin viewpoint from a single feasibility map to a compositional architecture for hybrid constrained optimization.
Conclusion
We developed a distributional framework for constrained hybrid quantum optimization in which deterministic repair transports the raw quantum sampling law onto the feasible set. The resulting pushforward distribution provides exact expressions for repaired success probabilities and expected objective values. Within the OFM kernel, we further developed a prescription for constructing problem-dependent repair maps from the constraint structure of the penalty Hamiltonian, with Hungarian maximum-overlap repair providing a concrete realization of the formalism for permutation-constrained optimization problems.
Combining repair-basin aggregation with the shell-transfer formalism from prior work[1], we established finite-shot success guarantees and a basin-dependent coherent-depth threshold. The analysis shows how the optimal-basin volume, characterized by , modifies the amplification requirement and reduces the corresponding absolute-transfer depth threshold through the correction . This establishes a quantitative connection between classical repair geometry, coherent quantum amplification, and the sampling resources required for optimal-solution recovery (theorem 8 and § 6.1).
The distributional mechanism is further characterized by the exact factorization
which separates combinatorial repair-basin volume from quantum probability concentration (§ 6.3). Our numerical experiments provide a striking illustration of the latter using single-layer CE–QAOA and a coarse search over only candidate cost angles . Despite this elementary parameter search, the repaired quantum distributions exhibit systematically enhanced concentration on low-cost tours relative to a shot-matched encoded-uniform baseline subjected to the same repair map. The repaired cost CDFs and solution-level comparisons reveal probability concentration on useful repair preimages. More strikingly, the contributor histograms show individual infeasible configurations whose quantum sampling counts exceed the expected count for an entire average repair basin. These observations demonstrate that pronounced instance-dependent quantum concentration can already emerge from very shallow circuits and inexpensive parameter searches, complementing the modest combinatorial basin enhancements considered in our finite-size analysis (§ 5.1).
For the largest noiseless instance, pushforward repair recovered the optimum using approximately shots, compared with the shots reported in the original CE–QAOA simulations without pushforward repair. Hardware experiments on IBM Brisbane, using encodings of up to 100 logical variables, further recovered known optimal tours from noisy measurement outcomes (§ 5.2) with 10,000 shots. Beyond permutation constraints, the compositional pushforward construction provides a route to successive feasibility corrections for more general OFM-admissible optimization problems (§ 6.5). These theoretical and experimental results establish repair-basin geometry and quantum probability concentration as complementary resources for hybrid constrained optimization, and provide a concrete pathway toward quantum utility and quantum advantage through the joint design of quantum sampling and classical feasibility restoration.
A concrete illustration of the repair-basin contribution is provided by the finite-size absolute-transfer thresholds for single-layer CE–QAOA. At the transport-maximizing mixer angle and with a shot budget , the pointwise absolute-transfer criterion for a fixed optimal encoded bitstring is satisfied through . Deterministic repair extends the corresponding criterion through at the average repair-basin scale (), and through for a fivefold relative basin volume (), as discussed in § 6.2 and A.5. Thus, repair-basin aggregation more than doubles the problem-size threshold for absolute-transfer compensation under the same polynomial shot-budget rule. These thresholds quantify the potential contribution of repair geometry to the transfer budget. The corresponding fixed-confidence sampling guarantees additionally require the phase-alignment hypothesis of Theorem 8, the associated phase factor, and the specified optimal-basin volume. The 30-city case corresponds to a 900-qubit assignment encoding, providing a concrete target for further theoretical, numerical, and hardware investigation.
Data and code availability
A minimal python implementation is available at https://doi.org/10.5281/zenodo.21302533. Additional data available upon request.
Conflict of Interests
All authors declare no competing interests.
Acknowledgements
The authors gratefully acknowledge helpful discussions initiated at the International Workshop on Quantum Optimization held in Oslo, Norway in March 2026. S.H. acknowledges support from AFRL Contract No. FA8750-25-C-B0040.
Pushforward from deterministic repair
Structural properties of deterministic repair
Deterministic feasibility repair acts on sampling laws through a pushforward. Its structural properties follow from the repair map itself and apply to any probability law on the raw sample space. In noisy implementations, the pushforward remains well defined, while the raw distribution may lose encoded-subspace support or concentration on useful repair preimages.
Let be a finite raw sample space, let be the feasible set, and let be a deterministic repair map. For a probability law on , define
In particular,
Proposition 9 (Basic structural and pushforward properties of deterministic repair). Let be finite and let satisfy for every . For any probability law on , write . Then:
Positivity and normalization:
Basin aggregation: with ,
Change of variables: for any and ,
Functoriality: for maps and ,
Retraction and idempotency:
where acts as the identity on in the second expression.
Compositionally closed repair family: let
For every ,
Thus is an idempotent semigroup under composition.
Total-variation contraction: for any probability laws on ,
Efficient samplewise realization: if one repair takes time , then repairing independent samples requires
In particular, polynomial shot budgets and polynomial-time repair give a polynomial-time classical repair stage.
Proof. Since ,
Positivity and the basin formula follow immediately from the definition of . Reordering the finite sums yields
For , functoriality follows from
Because and fixes , one has . The corresponding pushforward identity then follows by functoriality. Likewise, for ,
which proves closure and the stated composition identities. For total variation,
Finally, evaluating on each of samples gives the stated runtime bound.
Full-cube sampling via generic QAOA
The pushforward formulation applies whenever measured configurations are mapped to feasible outputs before objective scoring. The sampled configuration space depends on the quantum ansatz. Generic QAOA samples the full Boolean cube, whereas the OFM-compatible CE–QAOA construction samples a prescribed one-hot product space.
For binary variables, generic QAOA [39] prepares
The transverse-field mixer acts on , and the diagonal cost Hamiltonian generates problem-dependent phases. Techniques for selecting effective parameter schedules include linear or adiabatic ramps [40], parameter transfer across instances [41], recursive variable elimination [42], and warm-start initialization [43, 44].
Let be any deterministic feasibility repair. The resulting law is
All structural pushforward identities apply unchanged. For CE–QAOA in the ideal OFM setting, the initial state and block-XY mixer restrict the raw law to . This encoded structure also determines the basin-volume factors and shell-transfer expressions used in § 4.2. In noisy hardware implementations, the decomposition into encoded and leaked contributions is given in § 3.3.
Tie-breaking and uniqueness issues
The deterministic repair map is single valued. For maximum-overlap assignment, this requires a fixed rule whenever several permutations have the same overlap with a raw word. In the TSP case study, Hungarian repair minimizes Hamming distance to the feasible permutation sector. A lexicographic convention, for example, defines
Any fixed total ordering gives a valid deterministic convention. The same rule must be applied to the quantum and encoded-uniform samples in a distributional comparison. For the encoded-uniform law on , every fixed deterministic rule gives
The repair basins partition , so
The factor appearing in theorem 8 is the value corresponding to the selected permutation. For any sampling law on , define the basin concentration factor by
The repaired probability then factorizes exactly as
For an optimal-cost set , the uniform pushforward probability is similarly .
A symmetry-controlled stochastic repair. Let , define
Consider the stochastic maximum-overlap repair kernel
Proposition 10 (Uniform nearest repair). For each , the kernel selects uniformly among its maximum-overlap permutations and fixes feasible permutations. It can be sampled in time. For the uniform encoded law ,
For any raw law ,
Proof. A permutation can match at most once for each distinct symbol in . Choose one of the occurrences for every such symbol , then assign the missing symbols uniformly to the remaining positions. This produces exactly
maximum-overlap permutations with equal probability. The selection requires operations. If , then and the unique output is .
For any relabeling , the nearest-permutation sets of and are in bijection, so
The uniform word law is invariant under relabeling, and relabeling acts transitively on . Hence is uniform on . Summation over gives the remaining identity.
For the symmetry-controlled stochastic repair of Proposition 10, if the undirected optimum is unique up to rotation and reversal, and all such encodings are retained, then . For a specified good set , the quantity with is an unbiased estimator of . For an explicitly listed , it can be evaluated in time. It is the conditional expectation of the hit indicator obtained from a random tied repair and therefore has no greater variance. If an undirected optimal tour is unique up to rotations and reversal, its permutation encodings have encoded-uniform baseline probability under .
For , no deterministic retraction is equivariant under all city relabelings. A constant word is fixed by a transposition of two unused city labels, whereas no permutation is fixed by that relabeling. Hence the uniformity in (53) is a property of the stochastic kernel and does not imply equal basin cardinalities for a fixed deterministic tie-breaking rule.
Problem-dependent statistics
Contingency-table and transportation constraints
Fixed-margin contingency tables are specified by prescribed row sums, column sums, and higher-order marginals [23, 25, 45]. Related integer-programming constructions arise through multiway transportation formulations [24]. These marginals define the constraint system and enter the penalty Hamiltonian through their residuals. A suitable structural statistic records the observed marginals and their deviations from the required values.
Such residual information identifies entries carrying excess mass and entries with corresponding deficits. Local exchanges, cycle corrections, and flow-balancing operations can then restore prescribed margins. The resulting pushforward law aggregates the probabilities of all measured tables that repair to the same feasible table or transportation plan.
Coloring and constraint-satisfaction problems
Graph-coloring constraints are described through assigned colors, monochromatic edges, vertex conflict degrees, color populations, and overlaps with reference colorings. Related overlap-matrix statistics appear in random coloring and constraint-satisfaction problems [22, 26]. The constituent edge-conflict and assignment residuals identify the vertices and colors associated with each violation.
A problem-dependent repair can recolor high-conflict vertices, preserve valid neighborhoods, and select replacement colors using the local conflict profile. The repaired objective, correction count, and output coloring may then be analyzed as functions of those statistics. The pushforward law aggregates the raw probability of all assignments repairing to the same feasible coloring.
Routing and assignment formulations
Routing and assignment formulations contain multidimensional incidence statistics. In a position-based TSP encoding, the relevant quantities include city-visit populations, repeated and missing cities, and assignment marginals. Arc-based formulations additionally involve incoming and outgoing degree residuals, connectivity conditions, and subtour structure. The Miller–Tucker–Zemlin formulation introduces ordering variables and residuals to eliminate subtours [46], while many-visits TSP imposes prescribed visit multiplicities [29].
The corresponding penalty residuals identify repeated cities, omitted cities, degree violations, disconnected subtours, etc. Repair operations can replace repeated cities, correct degrees, reconnect routes, and insert omitted visits. Assignment and matching problems admit an analogous description through row and column populations, unmatched elements, collisions, and overlap with feasible assignments. Maximum-overlap matching and minimum-distance projection provide natural repair primitives.
Vehicle-routing problems introduce customer coverage, vehicle assignment, route load, capacity, depot incidence, connectivity, and route-count statistics. Their residuals can guide customer transfers, route splitting, component reconnection, insertion of unserved customers, and elimination of duplicate visits. The corresponding pushforward distribution identifies the raw configurations contributing to feasible routes and supports the analysis of objective changes, and concentration on high-quality repaired outputs.
Scheduling, allocation, and packing formulations
Scheduling constraints involve job multiplicities, machine assignments, machine loads, time-slot populations, precedence relations, processing orders, and resource consumption. Configuration and -fold integer-programming formulations organize these through job-type, machine-load, and time-slot aggregates [27, 28]. Penalty residuals record unassigned jobs, duplicate assignments, machine overloads, time conflicts, precedence violations, and resource excesses.
These statistics can guide the assignment of missing jobs, removal of duplicates, transfers between machines, resolution of time conflicts, and restoration of precedence. Allocation, generalized-assignment, multiple-knapsack, and packing formulations admit a similar construction using assignment populations, resource-usage vectors, capacity residuals, and unallocated-item counts. The repair map then transports raw probability to feasible allocations according to the full violation profile.
Basin enhancement, shot complexity, and delayed depth crossover
The finite-depth compensation threshold depends on the volume of the optimal repair preimage and the available sampling budget. Here we evaluate this relation explicitly for a single CE–QAOA layer, as used in the noiseless and hardware experiments. For and , fix an optimal permutation and its basin . Write
Thus is the average-basin reference, while describes an optimal basin larger than that average. The definition uses the same fixed deterministic repair map as the numerical comparisons. Under the phase-alignment hypothesis of Corollary 7, the depth-one repaired-success bound specializes to
The basin factor contributes multiplicatively to the depth-one absolute-transfer term.
The absolute-transfer factor reaches the basin-normalization scale at
Equivalently, the required relative basin volume is
For selected finite sizes,
| 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | |
| 0.681 | 1.430 | 3.161 | 7.341 | 17.870 | 45.495 | 120.898 | 334.756 |
Table 58.
At the average-basin scale , the depth-one absolute-transfer compensation criterion holds through . Increasing to 2, 5, or 10 extends this crossover through , 20, or 21, respectively. These values locate the crossover of the absolute-transfer budget at the maximizing angle.
Polynomial-shot compensation. Consider independent samples. The depth-one absolute-transfer budget, including the sampling allowance, is
The finite-size threshold plotted in Figure 5 is . In terms of the required relative basin volume, this becomes
This criterion separates the effect of repair-basin volume, coherent absolute transport, and polynomial sampling resources.
For completeness, the corresponding phase-aligned probability bound gives an explicit confidence relation. Define . If the common-arc hypothesis holds on , then independent shots fail to recover with probability at most
Consequently, for and target failure probability , a sufficient condition under that hypothesis is
The transport budget records the geometric and mixer contributions; the phase factor and desired confidence enter the corresponding success guarantee through (59).
The largest sizes satisfying for representative relative basin volumes and polynomial shot budgets are
| shot budget | ||||
| 18 | 19 | 20 | 21 | |
| 22 | 23 | 23 | 24 | |
| 25 | 26 | 27 | 27 | |
| 28 | 29 | 30 | 30 | |
| 34 | 35 | 36 | 36 | |
| 48 | 49 | 49 | 50 |
Table 61.
These evaluations establish a finite-size tradeoff between optimal-basin volume and sampling allowance at fixed coherent depth and fixed maximizing mixer angle . Larger basins and larger polynomial shot budgets extend the range satisfying the depth-one absolute-transfer criterion. The corresponding certified repaired-success probability is determined by the full bound (55).
References
- [1]C. Onah, S. Hadfield, and K. Michielsen, Separating geometry from interference in constrained quantum optimization (2026), arXiv:2607.13630 [quant-ph].arxiv.org/abs/2607.13630
- [2]F. B. Maciejewski, J. Biamonte, S. Hadfield, and D. Venturelli, Quantum 9, 1906 (2025).
- [3]S. Hadfield, F. B. Maciejewski, and D. Venturelli, Noise-directed adaptive remapping for integer optimization: from qubits to (encoded) qudits (2026), arXiv:2606.28234 [quant-ph].arxiv.org/abs/2606.28234
- [4]F. Maciejewski, S. Hadfield, O. Wallis, G. Pennington, S. Brandhofer, S. Woerner, D. J. Egger, and D. Venturelli, arXiv preprint arXiv:2607.09368 (2026).arxiv.org/abs/2607.09368
- [5]C. Onah and K. Michielsen, Polynomial Time Quantum Approximation Schemes for Constrained Optimisation (2026), arXiv:2608.01121 [quant-ph].arxiv.org/abs/2608.01121
- [6]L. Caha, A. Kliesch, and R. Koenig, Quantum Science and Technology 7, 045013 (2022).
- [7]T. Shirai and N. Togawa, IEEE Transactions on Quantum Engineering 5, 1 (2024), art. no. 3101114.
- [8]E. Bourreau, G. Fleury, and P. Lacomme, A warm-start qaoa based approach using a swap-based mixer for the tsp: theoretical considerations,implementation and experiments (2025), arXiv:2505.01214 [quant-ph].arxiv.org/abs/2505.01214
- [9]E. Bourreau, G. Fleury, and P. Lacomme, Indirect quantum approximate optimization algorithms: application to the tsp (2023), arXiv:2311.03294 [quant-ph].arxiv.org/abs/2311.03294
- [10]D. Bucher, M. Janetschek, M. Poppel, J. Stein, C. Linnhoff-Popien, and S. Feld, Constrained quantum optimization via iterative warm-start xy-mixers (2026), arXiv:2604.02083 [quant-ph].DOI
- [11]N. Sachdeva, G. S. Hartnett, S. Maity, S. Marsh, Y. Wang, A. Winick, R. Dougherty, D. Canuto, Y. Q. Chong, G. A. Cox, M. Hush, P. S. Mundada, C. D. B. Bentley, M. J. Biercuk, and Y. Baum, New Journal of Physics 28, 064506 (2026).
- [12]C. Onah, R. Firt, and K. Michielsen, Empirical quantum advantage in constrained optimization from encoded unitary designs (2026), arXiv:2511.14296 [cs.ET].arxiv.org/abs/2511.14296
- [13]A. Bärtschi and S. Eidenbenz, Deterministic preparation of dicke states, in Fundamentals of Computation Theory (Springer International Publishing, 2019) p. 126–139.DOI
- [14]J. Yu, S. R. Muleady, Y.-X. Wang, N. Schine, A. V. Gorshkov, and A. M. Childs, Physical Review Letters 136, 030601 (2026).
- [15]C. Onah, N. Misciasci, C. Othmer, and K. Michielsen, in 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 01 (2025) pp. 2149–2160.
- [16]A. Lucas, Frontiers in Physics 2, 5 (2014).
- [17]M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979).
- [18]R. M. Karp, in Complexity of Computer Computations (Plenum, 1972) pp. 85–103.
- [19]S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, Algorithms 12, 34 (2019).
- [20]F. G. Fuchs and R. P. Bassa, Algorithms 15, 202 (2022).
- [21]B. Tsvelikhovskiy, I. Safro, and Y. Alexeev, arXiv preprint arXiv:2309.13787 (2023), arXiv:2309.13787 [quant-ph].arxiv.org/abs/2309.13787
- [22]D. Achlioptas and A. Coja-Oghlan, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (IEEE Computer Society, 2008) pp. 793–802.
- [23]P. Diaconis and B. Sturmfels, The Annals of Statistics 26, 363 (1998).
- [24]J. A. De Loera and S. Onn, SIAM Journal on Optimization 17, 806 (2006).
- [25]A. B. Slavković, X. Zhu, and S. Petrović, Annals of the Institute of Statistical Mathematics 67, 621 (2015).
- [26]A. Coja-Oghlan and D. Vilenchik, International Mathematics Research Notices 2016, 5801 (2016).
- [27]M. Mnich and A. Wiese, Mathematical Programming 154, 533 (2015).
- [28]D. Knop and M. Koutecký, Journal of Scheduling 21, 493 (2018).
- [29]S. S. Cosmadakis and C. H. Papadimitriou, SIAM Journal on Computing 13, 99 (1984).
- [30]H. W. Kuhn, Naval Research Logistics Quarterly 2, 83 (1955).
- [31]E. Osaba and E. Villar-Rodríguez, in Proc. Quantum Tech. 2024 (2024).
- [32]C. Onah and K. Michielsen, Fundamental limitations of qaoa on constrained problems and a route to exponential enhancement (2025), arXiv:2511.17259 [quant-ph] .arxiv.org/abs/2511.17259
- [33]C. Onah and K. Michielsen, Finite-depth, finite-shot guarantees for constrained quantum optimization via fejer filtering (2026), arXiv:2603.01809 [quant-ph] .arxiv.org/abs/2603.01809
- [34]P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, et al., Nature Methods 17, 261 (2020).
- [35]C. Onah and K. Michielsen, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 02, 288 (2025).
- [36]A. Javadi-Abhari, M. Treinish, K. Krulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, Quantum Computing with Qiskit (2024), arXiv:2405.08810 [quant-ph] .
- [37]E. Osaba, E. Villar-Rodriguez, A. Gomez-Tejedor, and I. Oregi, in Intelligent Data Engineering and Automated Learning – IDEAL 2024, Lecture Notes in Computer Science, Vol. 15347 (Springer, 2025) pp. 423–434, arXiv:2401.10302 .
- [38]S. Hadfield, Complexity barriers to state preparation in quantum approximate optimization (2026), arXiv:2609.31520 [quant-ph] .arxiv.org/abs/2609.31520
- [39]E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv:1411.4028 (2014).arxiv.org/abs/1411.4028
- [40]J. A. Montañez-Barrera and K. Michielsen, Towards a universal qaoa protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems, arXiv preprint arXiv:2405.09169 (2024), https://arxiv.org/abs/2405.09169, arXiv:2405.09169 [quant-ph] .
- [41]J. A. Montañez-Barrera, D. Willsch, and K. Michielsen, Quantum Information Processing 24, 10.1007/s11128-025-04743-4 (2025).
- [42]S. Bravyi, A. Kliuch, R. Koenig, and E. Tang, Physical Review Letters 125, 10.1103/physrevlett.125.260505 (2020).
- [43]D. J. Egger, J. Mareček, and S. Woerner, Quantum 5, 479 (2021).
- [44]R. S. do Carmo, M. C. S. Santana, F. F. Fanchini, V. H. C. de Albuquerque, and J. a. P. Papa, Warm-starting qaoa with xy mixers: A novel approach for quantum-enhanced vehicle routing optimization (2025), arXiv:2504.19934 [quant-ph] .arxiv.org/abs/2504.19934
- [45]J. A. De Loera and S. Onn, SIAM Journal on Computing 33, 819 (2004).
- [46]C. E. Miller, A. W. Tucker, and R. A. Zemlin, Journal of the ACM 7, 326 (1960).
