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

arXiv:2202.08817

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

Xiaopeng Cui, Yu Shi

Published Feb 17, 2022• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2202.08817

Related papers

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

Xiaopeng Cui, Yu Shi

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.

Europhysics Letters (EPL)•Nov 1, 2023•1 citation

Solving Hamiltonian Cycle Problem with Grover’s Algorithm Using Novel Quantum Circuit Designs

Jehn‐Ruey Jiang, Tzu-Hao Kao

The Hamiltonian cycle problem (HCP) is related to the decision of whether there exists a cycle in a graph that visits every vertex exactly once. It is a well-known NP-complete problem, and thus there currently exists no classical algorithm solving it with polynomial time complexity in the worst case. With the emergence of quantum computers, the introduction of Grover’s algorithm has suggested new possibilities for solving the HCP more efficiently. In this article, we propose three novel quantum circuit designs of quantum counters to be embedded in the oracle of Grover’s algorithm to check if the input instance satisfies the HCP constraints to solve the HCP. We executed Grover’s algorithm with the novel quantum circuit designs, through the IBM Quantum Lab service, to solve the HCP to validate the design correctness.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Oct 27, 2023•7 citations

Comparison among Classical, Probabilistic and Quantum Algorithms for Hamiltonian Cycle Problem

Giuseppe Corrente, Carlo Vincenzo Stanzione, Vittoria Stanzione

The Hamiltonian cycle problem (HCP), which is an NP-complete problem, consists of having a graph G with nodes and m edges and finding the path that connects each node exactly once. In this paper we compare some algorithms to solve a Hamiltonian cycle problem, using different models of computations and especially the probabilistic and quantum ones. Starting from the classical probabilistic approach of random walks, we take a step to the quantum direction by involving an ad hoc designed Quantum Turing Machine (QTM), which can be a useful conceptual project tool for quantum algorithms. Introducing several constraints to the graphs, our analysis leads to not-exponential speedup improvements to the best-known algorithms. In particular, the results are based on bounded degree graphs (graphs with nodes having a maximum number of edges) and graphs with the right limited number of nodes and edges to allow them to outperform the other algorithms.

arXiv:2311.10941•Journal of quantum computing•Jan 1, 2023•0 citations

Speedup of high-order unconstrained binary optimization using quantum $${{\mathbb{Z}}}_{2}$$ lattice gauge theory

Bi-Ying Wang, Xiaopeng Cui, Qingguo Zeng +3 more

An important and difficult problem in optimization is the high-order unconstrained binary optimization, which can represent many optimization problems more efficiently than quadratic unconstrained binary optimization, but how to quickly solve it has remained difficult. Here, we present an approach by mapping the high-order unconstrained binary optimization to quantum $${{\mathbb{Z}}}_{2}$$ lattice gauge theory and propose the gauged local quantum annealing, which is the local quantum annealing protected by the gauge symmetry. We present the quantum algorithm and its corresponding quantum-inspired classical algorithm for this problem and achieve algorithmic speedup by using gauge symmetry. By running the quantum-inspired classical algorithm, we demonstrate that the gauged local quantum annealing reduces the computational time by one order of magnitude from that of the local quantum annealing. The authors propose a quantum annealing scheme for solving a higher-order unconstrained binary optimization problem by mapping it to a quantum Z2 lattice gauge theory on a dual graph. This scheme is shown to achieve a speed-up of at least one order of magnitude in finding the ground state compared to other methods.

Communications Physics•Apr 10, 2025•7 citations

Two-dimensional $\mathbb{Z}_2$ lattice gauge theory on a near-term quantum simulator: variational quantum optimization, confinement, and topological order

Luca Lumia, Pietro Torta, Glen Bigan Mbeng +4 more

We propose an implementation of a two-dimensional $\mathbb{Z}_2$ lattice gauge theory model on a shallow quantum circuit, involving a number of single and two-qubits gates comparable to what can be achieved with present-day and near-future technologies. The ground state preparation is numerically analyzed on a small lattice with a variational quantum algorithm, which requires a small number of parameters to reach high fidelities and can be efficiently scaled up on larger systems. Despite the reduced size of the lattice we consider, a transition between confined and deconfined regimes can be detected by measuring expectation values of Wilson loop operators or the topological entropy. Moreover, if periodic boundary conditions are implemented, the same optimal solution is transferable among all four different topological sectors, without any need for further optimization on the variational parameters. Our work shows that variational quantum algorithms provide a useful technique to be added in the growing toolbox for digital simulations of lattice gauge theories.

arXiv:2112.11787•Dec 22, 2021•1 citation

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
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.
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.
The Hamiltonian cycle problem (HCP) is related to the decision of whether there exists a cycle in a graph that visits every vertex exactly once. It is a well-known NP-complete problem, and thus there currently exists no classical algorithm solving it with polynomial time complexity in the worst case. With the emergence of quantum computers, the introduction of Grover’s algorithm has suggested new possibilities for solving the HCP more efficiently. In this article, we propose three novel quantum circuit designs of quantum counters to be embedded in the oracle of Grover’s algorithm to check if the input instance satisfies the HCP constraints to solve the HCP. We executed Grover’s algorithm with the novel quantum circuit designs, through the IBM Quantum Lab service, to solve the HCP to validate the design correctness.
The Hamiltonian cycle problem (HCP), which is an NP-complete problem, consists of having a graph G with nodes and m edges and finding the path that connects each node exactly once. In this paper we compare some algorithms to solve a Hamiltonian cycle problem, using different models of computations and especially the probabilistic and quantum ones. Starting from the classical probabilistic approach of random walks, we take a step to the quantum direction by involving an ad hoc designed Quantum Turing Machine (QTM), which can be a useful conceptual project tool for quantum algorithms. Introducing several constraints to the graphs, our analysis leads to not-exponential speedup improvements to the best-known algorithms. In particular, the results are based on bounded degree graphs (graphs with nodes having a maximum number of edges) and graphs with the right limited number of nodes and edges to allow them to outperform the other algorithms.
Speedup of high-order unconstrained binary optimization using quantum Z2{{\mathbb{Z}}}_{2}Z2​ lattice gauge theory
An important and difficult problem in optimization is the high-order unconstrained binary optimization, which can represent many optimization problems more efficiently than quadratic unconstrained binary optimization, but how to quickly solve it has remained difficult. Here, we present an approach by mapping the high-order unconstrained binary optimization to quantum Z2{{\mathbb{Z}}}_{2}Z2​ lattice gauge theory and propose the gauged local quantum annealing, which is the local quantum annealing protected by the gauge symmetry. We present the quantum algorithm and its corresponding quantum-inspired classical algorithm for this problem and achieve algorithmic speedup by using gauge symmetry. By running the quantum-inspired classical algorithm, we demonstrate that the gauged local quantum annealing reduces the computational time by one order of magnitude from that of the local quantum annealing. The authors propose a quantum annealing scheme for solving a higher-order unconstrained binary optimization problem by mapping it to a quantum Z2 lattice gauge theory on a dual graph. This scheme is shown to achieve a speed-up of at least one order of magnitude in finding the ground state compared to other methods.
Two-dimensional Z2\mathbb{Z}_2Z2​ lattice gauge theory on a near-term quantum simulator: variational quantum optimization, confinement, and topological order
We propose an implementation of a two-dimensional Z2\mathbb{Z}_2Z2​ lattice gauge theory model on a shallow quantum circuit, involving a number of single and two-qubits gates comparable to what can be achieved with present-day and near-future technologies. The ground state preparation is numerically analyzed on a small lattice with a variational quantum algorithm, which requires a small number of parameters to reach high fidelities and can be efficiently scaled up on larger systems. Despite the reduced size of the lattice we consider, a transition between confined and deconfined regimes can be detected by measuring expectation values of Wilson loop operators or the topological entropy. Moreover, if periodic boundary conditions are implemented, the same optimal solution is transferable among all four different topological sectors, without any need for further optimization on the variational parameters. Our work shows that variational quantum algorithms provide a useful technique to be added in the growing toolbox for digital simulations of lattice gauge theories.
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.