Separating Geometry From Interference in Constrained Quantum Optimization

Technical Summary: Separating Geometry from Interference in Constrained Quantum Optimization

Problem Statement
Constrained optimization problems (e.g., routing, scheduling, assignment) are often encoded as product spaces of local variables subject to global feasibility penalties. A central challenge in quantum algorithms for these problems, such as the Quantum Alternating Operator Ansatz (QAOA) and Constraint-Enhanced QAOA (CE-QAOA), is understanding how constraint-preserving mixing operators transport quantum amplitude across an exponentially large search space. While the mixer redistributes amplitude, it is unclear whether this transport inherently seeks a target configuration or merely diffuses, and how local and global constraints interact with quantum interference to produce a sampling advantage.

Methodology
The authors develop a framework that decouples three typically intermixed effects:

1. Transport Geometry: The movement of probability mass across the search space defined by the mixer.
2. Coherent Interference: The phase alignment of computational paths reaching a target.
3. Classical Post-processing: Problem-specific decoding or repair maps.

The core of the methodology involves a shell reduction on the encoded product space $X = [n]^m$. By defining the Hamming distance $d(x, y)$ from a target configuration $y$, the authors project the high-dimensional Hilbert space dynamics onto a set of "Hamming shells" $S_r(y)$ (configurations differing from $y$ in exactly $r$ local registers).

For the complete-graph block-XY mixer, the authors prove that the transition amplitude between any two configurations depends only on whether local symbols agree or differ. This symmetry allows the derivation of exact shell-transfer coefficients ($T_{r,t}$) that describe the flow of absolute path mass between shells, independent of specific configuration labels. This reduces the transport problem to a finite-dimensional recursion.

To address interference, the paper introduces a lattice-normalized phase control regime. By ensuring the cost Hamiltonian's eigenvalues are integer-bounded and the phase angles are chosen such that all path summands lie within a common arc of angular width $\Theta < \pi$, the authors apply a geometric bound (Lemma 7) to convert the sum of absolute path masses into a lower bound on the complex amplitude of the target state.

Key Contributions and Results

1. Separation of Transport and Interference:
   The analysis demonstrates that the mixing operator alone does not possess target-seeking ability. When normalized, the shell-transfer process relaxes toward the "bulk" of the search space (corresponding to a uniformly random configuration) rather than concentrating on the target. Quantum sampling advantage arises only when the phases of the many paths reaching the target are sufficiently aligned to reinforce the amplitude.

2. Exact Shell-Transfer Recursion:
   For the complete-graph block-XY mixer, the authors derive an exact generating function for shell-transfer coefficients (Proposition 4) and a finite radial recursion (Theorem 5). This allows the calculation of the total weighted contribution of all paths of depth $p$ ending in a specific shell without simulating the full exponential Hilbert space.

3. Dimension-Free Success Probability:
   Under the lattice-normalized phase alignment condition (Theorem 8), the authors show that the absolute path mass $v^{(p)}_0$ (calculated via the shell recursion) provides a certified lower bound on the target amplitude. Specifically, if the mixer angles are chosen constructively (Proposition 9) and the circuit depth $p$ grows only logarithmically with the problem size ($p \ge \frac{1}{2} \log_2 n$), the success probability of sampling the target configuration becomes independent of the ambient Hilbert-space dimension, the search-space size ($n^m$), or the feasible-set cardinality.

4. Diagnostic Framework:
   The shell formalism is applied to develop practical diagnostics:

   • Mixer Geometry Analysis: Different mixer topologies (complete, path, cycle, star) yield different "lumpability defects" when projected onto Hamming shells. The complete graph is the only geometry that closes exactly on Hamming shells; others require refined distance statistics (e.g., path or cyclic distance).
   • Transpilation Diagnostics: The framework provides a method to certify how Trotterization and gate synthesis distort the ideal shell-transfer law, offering scalable certificates for compiled mixers.
   • Attribution of Quality: It allows for the separation of solution quality contributions between the quantum distribution and classical post-processing (e.g., feasibility repair).

Significance and Claims
The paper claims to provide a rigorous analytical mechanism explaining how constrained quantum optimization can overcome the "curse of dimensionality" inherent in uniform sampling. By explicitly separating the geometric transport (which is phase-blind) from the coherent phase control, the authors identify a specific engineering criterion: the mixer must generate sufficient transport mass across the product space, while the phase operator must be designed to align these paths constructively.

The resulting formalism connects constrained quantum optimization to classical concepts such as lumped Markov chains, Krawtchouk polynomials, and association schemes from coding theory. The authors assert that this separation clarifies the source of quantum sampling advantages and enables independent analysis and engineering of the mixer and phase components for a broad class of constrained problems, moving beyond numerical optimization to provide certified performance guarantees.