Quantum-echo Markov process for combinatorial optimization
Abstract
We introduce a quantum-echo Markov process for combinatorial optimization. Quantum dynamics based on quantum annealing (QA) or the quantum approximate optimization algorithm (QAOA) is used to engineer the transition kernel. Increasing the annealing time in QA or the number of layers in QAOA enables transitions to explore distant configurations while suppressing large energy changes. The Hamming-space delocalization originates from operator spreading, whereas the energy-space localization arises from a dynamically generated correlation. For optimization, we propose quantum-echo local optimization with and without greedy descent. We find that its performance is governed by the interplay between Hamming-space nonlocality and energy-space locality, and that excessive energy-space localization can degrade optimization performance. Incorporating greedy descent substantially improves the performance, highlighting the complementary roles of quantum dynamics for exploration and greedy descent for exploitation. These results establish quantum-echo dynamics as a framework for engineering structured transition kernels and provide a route to using finite-resource quantum many-body dynamics as a computational primitive for iterative optimization.
Related
- Measurement-Efficient Differentiable Quantum Architecture Search for Combinatorial Optimization
- Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization
- Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks
- Beyond QAOA: A Review of AI and Quantum Computing for Adaptive Combinatorial Optimization
- Graph neural networks and the energetic cavity method for combinatorial optimization
BibTeX
@misc{shirai2026quantumecho,
title = {{Quantum-echo Markov process for combinatorial optimization}},
author = {Tatsuhiko Shirai},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38943},
eprint = {2609.38943},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38943},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum-echo Markov process for combinatorial optimization
AU - Tatsuhiko Shirai
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38943
UR - https://arxiv.org/abs/2609.38943
AB - We introduce a quantum-echo Markov process for combinatorial optimization. Quantum dynamics based on quantum annealing (QA) or the quantum approximate optimization algorithm (QAOA) is used to engineer the transition kernel. Increasing the annealing time in QA or the number of layers in QAOA enables transitions to explore distant configurations while suppressing large energy changes. The Hamming-space delocalization originates from operator spreading, whereas the energy-space localization arises from a dynamically generated correlation. For optimization, we propose quantum-echo local optimization with and without greedy descent. We find that its performance is governed by the interplay between Hamming-space nonlocality and energy-space locality, and that excessive energy-space localization can degrade optimization performance. Incorporating greedy descent substantially improves the performance, highlighting the complementary roles of quantum dynamics for exploration and greedy descent for exploitation. These results establish quantum-echo dynamics as a framework for engineering structured transition kernels and provide a route to using finite-resource quantum many-body dynamics as a computational primitive for iterative optimization.
ER -