Separating Geometry From Interference in Constrained Quantum Optimization

arXiv (Cornell University)

Abstract

We study the separation of geometric effects from quantum interference in quantum optimization algorithms. Constrained optimization problems such as routing, assignment, and scheduling are often encoded as product spaces of local variables, together with global feasibility penalties. The central algorithmic question we address is how a constraint-preserving mixing operator transports quantum amplitude across an exponential search space in the presence of local and global constraints. We develop a framework that separates three effects that are usually intermixed: amplitude transport, coherent interference among transported amplitudes, and problem-dependent classical postprocessing. We show that the mixing operator alone does not have a target-seeking ability. Concretely, the normalized distribution induced by its amplitude transport moves toward the distance profile of a uniformly random configuration. Thus, quantum sampling advantage may only arise when the phases of the many computational paths reaching a target configuration are sufficiently aligned for their amplitudes to reinforce. We show that, when the cost phases are engineered so that these paths add coherently, a number of circuit alternations growing only logarithmically with problem size suffices to convert the sum of their absolute contributions into a lower bound on the target amplitude, yielding a certified success probability independent of the ambient Hilbert-space dimension, the search-space size, or the feasible-set cardinality. We develop applications to problem-specific transpilation diagnostics, scalable hardware probes, constraint-induced classical maps of quantum-generated samples, the attribution of solution quality between the quantum distribution and classical post-processing in hybrid quantum-classical workflows and connections to distance-partitioned product spaces from classical coding theory.

Authors 3

1. Chinonso Onah Aachen Department of Physics

   RWTH Aachen University · Volkswagen Group (Germany)

   Affiliation as printed

   Department of Physics , RWTH Aachen University , 52056 Aachen , Germany

   Volkswagen AG , Berliner Ring 2 , 38440 Wolfsburg , Germany

2. Stuart Hadfield

   Research Institute for Advanced Computer Science

   Affiliation as printed

   USRA Research Institute for Advanced Computer Science (RIACS) , CA , USA

3. Kristel F. L. Michielsen

   Forschungszentrum Jülich · University of Cologne

   Affiliation as printed

   Forschungszentrum Jülich , Germany

   Universität zu Köln , 50923 Köln , Germany