Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Europhysics Letters (EPL)

Correspondence between the Hamiltonian cycle problem and the quantum lattice gauge theory

Xiaopeng Cui, Yu Shi

Published Nov 1, 2023• 1 citation
Publisher

Abstract

Abstract We propose the correspondence between the Hamiltonian cycle (HC) problem in graph theory and the quantum lattice gauge theory (QZ2LGT) defined on the lattice dual to that graph. For the QZ2LGT, when the coupling parameter g is less than the critical value g c , the ground state is a superposition of all configurations with closed strings of same spins, which can be obtained by using an adiabatic quantum algorithm. A subsequent search for a HC among those closed strings solves the original HC problem. The method is demonstrated for random samples of small graphs.

DOI
10.1209/0295-5075/ad130b

Related papers

Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice Gauge Theory

Xiaopeng Cui, Yu Shi

The Hamiltonian cycle (HC) problem in graph theory is a well-known NP-complete problem. We present an approach in terms of $\mathbb{Z}_2$ 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 $g_c$, the ground state is a superposition of all configurations with closed strings of spins in a same single-spin state, which can be obtained by using an adiabatic quantum algorithm with time complexity $O(\frac{1}{g_c^2} \sqrt{ \frac{1}{\varepsilon} N_e^{3/2}(N_v^3 + \frac{N_e}{g_c}}))$, where $N_v$ and $N_e$ are the numbers of vertices and edges of the graph respectively. A subsequent search for a HC among those closed-strings solves the HC problem. For some random samples of small graphs, we demonstrate that the dependence of the average value of $g_c$ on $\sqrt{N_{hc}}$, $N_{hc}$ being the number of HCs, and that of the average value of $\frac{1}{g_c}$ on $N_e$ are both linear. It is thus suggested that for some graphs, the HC problem may be solved in polynomial time. A possible quantum algorithm using $g_c$ to infer $N_{hc}$ is also discussed.

arXiv:2202.08817•Feb 17, 2022•0 citations

An Alternative Adiabatic Quantum Algorithm for the Hamiltonian Cycle Problem

Da-Jian Zhang, D. M. Tong, Yao Lu +1 more

Abstract We put forward an alternative quantum algorithm for finding Hamiltonian cycles in any N-vertex graph based on adiabatic quantum computing. With a von Neumann measurement on the final state, one may determine whether there is a Hamiltonian cycle in the graph and pick out a cycle if there is any. Although the proposed algorithm provides a quadratic speedup, it gives an alternative algorithm based on adiabatic quantum computation, which is of interest because of its inherent robustness.

Communications in Theoretical Physics•May 1, 2015•3 citations

Exact ground-state properties of the SU(2) Hamiltonian lattice gauge theory

Siu A. Chin, O.S. van Roosmalen, E. A. Umland +1 more

The SU(2) Hamiltonian lattice gauge theory is shown explicitly to be equivalent to a nonrelativistic quantum many-body problem in ${S}^{3}$. By exploiting this equivalence, a many-body Monte Carlo algorithm is devised to solve for its ground-state properties. To the extent that a trial wave function consisting of a product of single-plaquette functions is a good approximation to the exact ground state, the present Monte Carlo method is shown to be an efficient means of calculating the ground-state energy with high precision.

Physical review. D. Particles, fields, gravitation, and cosmology/Physical review. D. Particles and fields•Jun 15, 1985•41 citations

Quantum computing Hamiltonian cycles

Terry Rudolph

An algorithm for quantum computing Hamiltonian cycles of simple, cubic, bipartite graphs is discussed. It is shown that it is possible to evolve a quantum computer into an entanglement of states which map onto the set of all possible paths originating from a chosen vertex, and furthermore to subsequently project out all states not corresponding to Hamiltonian cycles.

arXiv:quant-ph/9603001•Mar 3, 1996•1 citation

A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems

Dario Tamascelli, Luca Zanetti

We present a quantum algorithm for solving graph isomorphism problems that is based on an adiabatic protocol. We use a collection of continuous time quantum walks, each one generated by an XY Hamiltonian, to visit the configuration space. In this way we avoid a diffusion over all the possible configurations and significantly reduce the dimensionality of the accessible Hilbert space. Within this restricted space, the graph isomorphism problem can be translated into searching for a satisfying assignment to a 2-SAT (satisfiable) formula and mapped onto a 2-local Hamiltonian without resorting to perturbation gadgets or projective techniques. We present an analysis of the time for execution of the algorithm on small graph isomorphism problem instances and discuss the issue of an implementation of the proposed adiabatic scheme on current quantum computing hardware.

arXiv:1401.1278•Journal of Physics A Mathematical and Theoretical•Jul 24, 2014•32 citations

Simulating lattice gauge theories on a quantum computer

Tim Byrnes, Y. Yamamoto

We examine the problem of simulating lattice gauge theories on a universal quantum computer. The basic strategy of our approach is to transcribe lattice gauge theories in the Hamiltonian formulation into a Hamiltonian involving only Pauli spin operators such that the simulation can be performed on a quantum computer using only one- and two-qubit manipulations. We examine three models, the U(1), SU(2), and SU(3) lattice gauge theories, which are transcribed into a spin Hamiltonian up to a cutoff in the Hilbert space of the gauge fields on the lattice. The number of qubits required for storing a particular state is found to have a linear dependence on the total number of lattice sites. The number of qubit operations required for performing the time evolution corresponding to the Hamiltonian is found to be between a linear to quadratic function of the number of lattice sites, depending on the arrangement of qubits in the quantum computer. We remark that our results may also be easily generalized to higher $\mathrm{SU}(N)$ gauge theories.

arXiv:quant-ph/0510027•Physical Review A•Feb 17, 2006•221 citations
Abstract We propose the correspondence between the Hamiltonian cycle (HC) problem in graph theory and the quantum lattice gauge theory (QZ2LGT) defined on the lattice dual to that graph. For the QZ2LGT, when the coupling parameter g is less than the critical value g c , the ground state is a superposition of all configurations with closed strings of same spins, which can be obtained by using an adiabatic quantum algorithm. A subsequent search for a HC among those closed strings solves the original HC problem. The method is demonstrated for random samples of small graphs.
Solving Hamiltonian Cycle Problem using Quantum Z2\mathbb{Z}_2Z2​ Lattice Gauge Theory
The Hamiltonian cycle (HC) problem in graph theory is a well-known NP-complete problem. We present an approach in terms of Z2\mathbb{Z}_2Z2​ lattice gauge theory (LGT) defined on the lattice with the graph as its dual. When the coupling parameter ggg is less than the critical value gcg_cgc​, the ground state is a superposition of all configurations with closed strings of spins in a same single-spin state, which can be obtained by using an adiabatic quantum algorithm with time complexity O(1gc21εNe3/2(Nv3+Negc))O(\frac{1}{g_c^2} \sqrt{ \frac{1}{\varepsilon} N_e^{3/2}(N_v^3 + \frac{N_e}{g_c}}))O(gc2​1​ε1​Ne3/2​(Nv3​+gc​Ne​​​)), where NvN_vNv​ and NeN_eNe​ are the numbers of vertices and edges of the graph respectively. A subsequent search for a HC among those closed-strings solves the HC problem. For some random samples of small graphs, we demonstrate that the dependence of the average value of gcg_cgc​ on Nhc\sqrt{N_{hc}}Nhc​​, NhcN_{hc}Nhc​ being the number of HCs, and that of the average value of 1gc\frac{1}{g_c}gc​1​ on NeN_eNe​ are both linear. It is thus suggested that for some graphs, the HC problem may be solved in polynomial time. A possible quantum algorithm using gcg_cgc​ to infer NhcN_{hc}Nhc​ is also discussed.
The SU(2) Hamiltonian lattice gauge theory is shown explicitly to be equivalent to a nonrelativistic quantum many-body problem in S3{S}^{3}S3. By exploiting this equivalence, a many-body Monte Carlo algorithm is devised to solve for its ground-state properties. To the extent that a trial wave function consisting of a product of single-plaquette functions is a good approximation to the exact ground state, the present Monte Carlo method is shown to be an efficient means of calculating the ground-state energy with high precision.
We present a quantum algorithm for solving graph isomorphism problems that is based on an adiabatic protocol. We use a collection of continuous time quantum walks, each one generated by an XY Hamiltonian, to visit the configuration space. In this way we avoid a diffusion over all the possible configurations and significantly reduce the dimensionality of the accessible Hilbert space. Within this restricted space, the graph isomorphism problem can be translated into searching for a satisfying assignment to a 2-SAT (satisfiable) formula and mapped onto a 2-local Hamiltonian without resorting to perturbation gadgets or projective techniques. We present an analysis of the time for execution of the algorithm on small graph isomorphism problem instances and discuss the issue of an implementation of the proposed adiabatic scheme on current quantum computing hardware.
We examine the problem of simulating lattice gauge theories on a universal quantum computer. The basic strategy of our approach is to transcribe lattice gauge theories in the Hamiltonian formulation into a Hamiltonian involving only Pauli spin operators such that the simulation can be performed on a quantum computer using only one- and two-qubit manipulations. We examine three models, the U(1), SU(2), and SU(3) lattice gauge theories, which are transcribed into a spin Hamiltonian up to a cutoff in the Hilbert space of the gauge fields on the lattice. The number of qubits required for storing a particular state is found to have a linear dependence on the total number of lattice sites. The number of qubit operations required for performing the time evolution corresponding to the Hamiltonian is found to be between a linear to quadratic function of the number of lattice sites, depending on the arrangement of qubits in the quantum computer. We remark that our results may also be easily generalized to higher SU(N)\mathrm{SU}(N)SU(N) gauge theories.