arXiv:2609.30991
Solving Graph Coloring Problems Using Feedback-Based Algorithm for Quantum Optimization
Yuika Kawatomi, Yukina Tatsuta, Kazue Kudo
Abstract
The feedback-based algorithm for quantum optimization (FALQON), which is an extension of the quantum approximate optimization algorithm (QAOA), is a promising approach for finding approximate solutions to combinatorial optimization problems. The FALQON avoids the optimization of variational parameters by using information derived from iterative measurements. To solve a constrained combinatorial optimization problem, it is sometimes more efficient to use an XY mixer rather than the conventional X mixer. We applied the FALQON with the XY mixer to graph coloring and investigated the expectation value of the problem Hamiltonian, success probability of graph coloring, and fair sampling for several small-scale problems. The FALQON with the XY mixer exhibited better performance than that with the X mixer.
AI Summary
The paper studies whether constraint-preserving XY mixers improve feedback-based quantum optimization (FALQON) for graph coloring relative to transverse-X mixers. It uses one-hot color encoding: the X formulation includes a constraint penalty, while the XY mixer preserves feasibility from an initial product of W states and removes that penalty. It explicitly derives the XY feedback observable $H_{\rm f}=i[H_{\rm m},H_{\rm p}]$ and compares energy, coloring success probability, and sampling of degenerate solutions. Evidence comes from noiseless statevector simulations of three graphs with 3–5 vertices and 3–4 colors. At 800 FALQON layers, XY versus X success probabilities are 98.9% versus 72.0%, 69.3% versus 40.7%, and 87.7% versus 39.7%. Ten-layer QAOA comparisons, using medians over 20 optimization runs, give XY success probabilities of 99.6%, 38.2%, and 73.8%. Energy-versus-layer fits favor exponential decay for XY-FALQON and power-law decay for X-FALQON over the simulated range. XY-FALQON also has lower reported root-mean-square relative error from a uniform distribution over valid colorings, although this error can increase while energy decreases. The simulations fix the time step at $\Delta t=0.025$ and the X-mixer penalty at $\lambda=0.5$; both are identified as parameters that could be tuned. FALQON has not converged by 800 layers, and the observed decay forms are not claimed to persist at larger depths. The paper also notes that hardware evaluation of the feedback term incurs additional costs.
Error found: The fair-sampling metric conflates failure probability with nonuniformity among successful outcomes, so its smaller values do not establish the claimed fair-sampling advantage. The conclusion generalizes the observed advantage to one-hot-constrained problems without evidence beyond three tiny noiseless instances and a fixed, untuned X-mixer penalty.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 13 pages, 5 figures