← Back to papers
Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice Gauge Theory
Xiaopeng Cui, Yu Shi·February 17, 2022
Physics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
Abstract The Hamiltonian cycle (HC) problem in graph theory is a well-known NP-complete problem. We present an approach in terms of Z2 lattice gauge theory (LGT) defined on the lattice with the graph as its dual. When the coupling parameter g is less than the critical value gc, the ground state is a superposition of all configurations with closed strings of spins in a same singlespin state, which can be obtained by using an adiabatic quantum algorithm with time complexity O( 1 g c √