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

Communications in Theoretical Physics

An Alternative Adiabatic Quantum Algorithm for the Hamiltonian Cycle Problem

Da-Jian Zhang, D. M. Tong, Yao Lu, Gui‐Lu Long

Published May 1, 2015• 3 citations
Publisher

Abstract

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.

DOI
10.1088/0253-6102/63/5/554

Related papers

Solving the Hamiltonian Cycle Problem using a Quantum Computer

Anuradha Mahasinghe, Richard Hua, Michael J. Dinneen +1 more

We review existing quantum computational methods for solving the Hamiltonian cycle problem in different computational frameworks such as quantum circuits, quantum walks and adiabatic quantum computation. Then we present a QUBO (quadratic unconstrained binary optimization) formulation, which is suitable for the adiabatic quantum computation for a D-Wave architecture. Further, we derive a physical Hamiltonian from the QUBO formulation and discuss its adequateness in the adiabatic framework. Finally, we discuss the complexity of running the Hamiltonian cycle QUBO on a D-Wave quantum computer, and compare it with existing quantum computational methods.

Australasian Computer Science Week Multiconference (ACSW)•Jan 14, 2019•23 citations

Adiabatic rotation, quantum search, and preparation of superposition states

M. Stewart Siu

We introduce the idea of using adiabatic rotation to generate superpositions of a large class of quantum states. For quantum computing this is an interesting alternative to the well-studied ``straight line'' adiabatic evolution. In ways that complement recent results, we show how to efficiently prepare three types of states: Kitaev's toric code state, the cluster state of the measurement-based computation model, and the history state used in the adiabatic simulation of a quantum circuit. We also show that the method, when adapted for quantum search, provides quadratic speedup as other optimal methods do with the advantages that the problem Hamiltonian is time independent and that the energy gap above the ground state is strictly nondecreasing with time. Likewise the method can be used for optimization as an alternative to the standard adiabatic algorithm.

arXiv:0704.3630•Physical Review A•Jun 29, 2007•10 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

Theorem on the existence of a nonzero energy gap in adiabatic quantum computation

Da-Jian Zhang, Xiao‐Dong Yu, D. M. Tong

Adiabatic quantum computation, based on the adiabatic theorem, is a promising alternative to conventional quantum computation. The validity of an adiabatic algorithm depends on the existence of a nonzero energy gap between the ground and excited states. However, it is difficult to ascertain the exact value of the energy gap. In this paper, we put forward a theorem on the existence of nonzero energy gap for the Hamiltonians used in adiabatic quantum computation. It can help to effectively identify a large class of the Hamiltonians without energy-level crossing between the ground and excited states.

arXiv:1410.3562•Physical Review A•Oct 16, 2014•15 citations

Alternative adiabatic quantum dynamics with algorithmic applications

Joseph Cunningham, Jérémie Roland

In adiabatic quantum computing the aim is to track an eigenstate as the Hamiltonian changes. In the usual setup this is achieved using the natural time-dependent Hamiltonian evolution of the system and the main technical tool is the adiabatic theorem. We propose several alternative processes that achieve the same goal, but can easily be implemented on a gate-based quantum computer without the overhead of simulating time-dependent Hamiltonian evolution. We give a general framework for deriving `adiabatic' theorems for these processes. As an application, we give various algorithms for solving the Quantum Linear Systems Problem (QLSP) with optimal scaling in the condition number. One of these algorithms was previously developed in [Cunningham, Roland 2024] and another can be seen as a randomised version of the discrete adiabatic algorithm of [Costa et al. 2022]. We also describe versions of Trotterisation in our framework, which allows several results from [An et al. 2025] to be reproduced in a randomised setting. In particular, bounds on the Trotter error in terms of the fidelity are obtained that are asymptotically better than the standard bounds.

quant-pharXiv:2605.30110•May 29, 2026•0 citations

An Alternative Approach to Construct the Initial Hamiltonian of the Adiabatic Quantum Computation

Qian-Heng Duan, Shuo Zhang, Wei Wu +1 more

The adiabatic quantum computation (AQC) has been proven to be equivalent to the standard circuit model. Conventionally, AQC evolves from the initial Hamiltonian which has a uniform equal superposition of the computational basis to the final Hamiltonian whose ground state encodes the solution to a computation problem. We propose an alternative approach to construct the initial Hamiltonian of the AQC which has an unequal superposition of the possible solutions to the problem and show that an educated guess can improve the performance of AQC.

Chinese Physics Letters•Jan 1, 2013•18 citations
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.
We review existing quantum computational methods for solving the Hamiltonian cycle problem in different computational frameworks such as quantum circuits, quantum walks and adiabatic quantum computation. Then we present a QUBO (quadratic unconstrained binary optimization) formulation, which is suitable for the adiabatic quantum computation for a D-Wave architecture. Further, we derive a physical Hamiltonian from the QUBO formulation and discuss its adequateness in the adiabatic framework. Finally, we discuss the complexity of running the Hamiltonian cycle QUBO on a D-Wave quantum computer, and compare it with existing quantum computational methods.
We introduce the idea of using adiabatic rotation to generate superpositions of a large class of quantum states. For quantum computing this is an interesting alternative to the well-studied ``straight line'' adiabatic evolution. In ways that complement recent results, we show how to efficiently prepare three types of states: Kitaev's toric code state, the cluster state of the measurement-based computation model, and the history state used in the adiabatic simulation of a quantum circuit. We also show that the method, when adapted for quantum search, provides quadratic speedup as other optimal methods do with the advantages that the problem Hamiltonian is time independent and that the energy gap above the ground state is strictly nondecreasing with time. Likewise the method can be used for optimization as an alternative to the standard adiabatic algorithm.
Adiabatic quantum computation, based on the adiabatic theorem, is a promising alternative to conventional quantum computation. The validity of an adiabatic algorithm depends on the existence of a nonzero energy gap between the ground and excited states. However, it is difficult to ascertain the exact value of the energy gap. In this paper, we put forward a theorem on the existence of nonzero energy gap for the Hamiltonians used in adiabatic quantum computation. It can help to effectively identify a large class of the Hamiltonians without energy-level crossing between the ground and excited states.
In adiabatic quantum computing the aim is to track an eigenstate as the Hamiltonian changes. In the usual setup this is achieved using the natural time-dependent Hamiltonian evolution of the system and the main technical tool is the adiabatic theorem. We propose several alternative processes that achieve the same goal, but can easily be implemented on a gate-based quantum computer without the overhead of simulating time-dependent Hamiltonian evolution. We give a general framework for deriving `adiabatic' theorems for these processes. As an application, we give various algorithms for solving the Quantum Linear Systems Problem (QLSP) with optimal scaling in the condition number. One of these algorithms was previously developed in [Cunningham, Roland 2024] and another can be seen as a randomised version of the discrete adiabatic algorithm of [Costa et al. 2022]. We also describe versions of Trotterisation in our framework, which allows several results from [An et al. 2025] to be reproduced in a randomised setting. In particular, bounds on the Trotter error in terms of the fidelity are obtained that are asymptotically better than the standard bounds.
The adiabatic quantum computation (AQC) has been proven to be equivalent to the standard circuit model. Conventionally, AQC evolves from the initial Hamiltonian which has a uniform equal superposition of the computational basis to the final Hamiltonian whose ground state encodes the solution to a computation problem. We propose an alternative approach to construct the initial Hamiltonian of the AQC which has an unequal superposition of the possible solutions to the problem and show that an educated guess can improve the performance of AQC.