Quantum Interference as a Proposal Mechanism for Combinatorial Optimization

How can quantum circuits be utilized as structured proposal generators to improve the efficiency of solving combinatorial optimization problems, such as QUBO (Quadratic Unconstrained Binary Optimization) and Ising models? The authors investigate whether localized quantum interference can provide a resource-efficient alternative to traditional variational quantum algorithms.

The authors introduce Quantum Interference Proposal Search (QIPS), a non-variational framework that uses seed-conditioned quantum circuits to generate finite-shot proposal distributions. Unlike variational approaches that train a single circuit, QIPS uses feedback-controlled, randomized circuit deviations to maintain localized interference patterns. These patterns generate candidate bitstrings that are evaluated classically to update an elite frontier of low-energy solutions. The performance of QIPS is benchmarked against a matched classical control that uses the same search loop, frontier update rules, and total proposal budget across six different problem families with 18 to 29 variables.

QIPS successfully accesses low-energy states by leveraging emergent structure in seed-conditioned quantum proposals. While the classical control often achieves higher top-K recovery, QIPS remains competitive under the same proposal budget. The study demonstrates that QIPS does not rely on a single, perfectly reproducible interference pattern; instead, it harvests useful low-energy bitstrings from an ensemble of circuits where interference peaks vary across realizations. This suggests that localized quantum interference is a viable resource for guiding search dynamics toward the low-energy tail of the solution space.