Speaker
Description
While quantum algorithms promise significant speedups for combinatorial optimization, abstract black-box oracles often hide massive compilation overheads that threaten fault-tolerant viability. Drawing on our recent publications [1, 2], this work bridges the gap between algorithmic theory and physical implementation by presenting a fully explicit, gate-level synthesis framework for exact integer optimization.
Targeting Integer Linear Programming (ILP) [1] and bounded non-linear Diophantine equations [2], our architecture relies on purely quantum arithmetic. By coherently encoding integer variables in superposition and evaluating constraints on-the-fly via two's complement logic, we achieve a fully quantum workflow that strictly avoids both quantum-RAM assumptions and classical pre-processing. For ILP, we deploy a coherent random walk over the discrete feasible region. For non-linear Diophantine systems, we introduce a garbage-free evaluation oracle tailored for amplitude amplification.
The core achievement of this work lies in proving that unpacking the black box does not negate the theoretical speedup. Through explicit constructions validated by numerical circuit simulations, we demonstrate that our gate-level arithmetic acts as a strictly bounded overhead. This guarantees that the celebrated oracular advantages of quantum walks and Grover-like search are successfully preserved at the fault-tolerant circuit level, establishing a concrete baseline for practical quantum optimization.
References:
[1] G. Escrig, R. Campos, M. A. Martin-Delgado, Resource-Scalable Fully Quantum Metropolis-Hastings for Integer Linear Programming, arXiv:2602.11285 (2026).
[2] G. Escrig, M. A. Martin-Delgado, From Hilbert's Tenth Problem to Quantum Speedup: Explicit Oracles for Bounded Diophantine Systems, arXiv:2605.13980 (2026).
| Topic | Other |
|---|---|
| Additional Topic | Encoding and processing of data in quantum systems |