Speaker
Description
Constrained combinatorial optimization problems (CCOPs) arise in a wide range of practical applications. Quantum optimization methods have attracted considerable attention as heuristic approaches to solving these problems. Because current quantum hardware is limited by short coherence times and gate errors, optimization methods based on relatively short quantum evolutions are desirable.
Multi-stage quantum walks (MSQWs) perform optimization through a sequence of quantum evolutions under Hamiltonians with different parameters. A previous study proposed an efficient heuristic method for determining the MSQW parameters and evaluated it on Ising spin-glass instances [1]. That method targets unconstrained Ising problems, and its applicability to CCOPs has not yet been established.
In this study, we extend the heuristic parameter-setting method to CCOPs. We replace the transverse-field driver with an XY driver that preserves the Hamming-weight constraint, so that dynamics initialized in the feasible subspace remain confined to it. We apply the extended MSQW to CCOPs with equality constraints and evaluate its performance by state-vector simulation for systems of up to 12 qubits. Our results show that the extended heuristic determines effective parameters for CCOPs. Compared with a penalty-based formulation solved within the same MSQW framework, the constraint-preserving MSQW achieves higher success probabilities over the instances considered.
[1] A. Hopkins and V. Kendon. " Heuristics for multi-stage quantum walks to find Ising ground states," arXiv preprint arXiv:2511.01312 (2025).