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:1212.6523

Recursive quantum algorithm to find the lowest eigenstate of a general Hamiltonian

Jeongho Bang, Seung-Woo Lee, Chang-Woo Lee, Hyunseok Jeong, Jinhyoung Lee

Published Dec 28, 2012• 1 citation
arXivHTMLPDF

Abstract

We propose a quantum algorithm to obtain the lowest eigenstate of any Hamiltonian simulated by a quantum computer. The proposed algorithm begins with an arbitrary initial state of the simulated system. A finite series of transforms is iteratively applied to the initial state assisted with an ancillary qubit. The fraction of the lowest eigenstate in the initial state is then amplified up to $\simeq 1$. We prove that our algorithm can faithfully work for any arbitrary Hamiltonian in the theoretical analysis. Numerical analyses are also carried out. We firstly provide a numerical proof-of-principle demonstration with a simple Hamiltonian in order to compare our scheme with the so-called Demon-like algorithmic (DLAC), recently proposed in [Nature Photonics 8, 113 (2014)]. The result shows a good agreement with our theoretical analysis, exhibiting the comparable behavior to the best cooling with the DLAC method. We then consider a random Hamiltonian model for further analysis of our algorithm. By numerical simulations, we show that the total number $n_c$ of iterations is proportional to $\simeq {\cal O}(D^{-1}\epsilon^{-0.19})$, where $D$ is the difference between the two lowest eigenvalues, and $\epsilon$ is an error defined as the probability that the finally obtained system state is in an unexpected (i.e. not the lowest) eigenstate.

Related papers

Universal quantum algorithmic cooling on a quantum computer

Pei Zeng, Jinzhao Sun, Xiao Yuan

Quantum cooling, a deterministic process that drives any state to the lowest eigenstate, has been widely used from studying ground state properties of chemistry and condensed matter quantum physics, to general optimization problems. However, the cooling procedure is generally non-unitary, hence its realization on a quantum computer either requires deep circuits or assumes specific input states with variational circuits. Here, we propose universal quantum cooling algorithms that overcome these limitations. By utilizing a dual phase representation of decaying functions, we show how to universally and deterministically realize a general cooling procedure with shallow quantum circuits. We demonstrate its applications in cooling an arbitrary input state with known ground state energy, corresponding to satisfactory, linear algebra tasks, and quantum state compiling tasks, and preparing unknown eigenvalues and eigenstates, corresponding to quantum many-body problems. Compared to quantum phase estimation, our method uses only one ancillary qubit and much shallower circuits, showing exponential improvement of the circuit complexity with respect to the final state infidelity. We numerically benchmark the algorithms for the $8$-qubit Heisenberg model and verify its feasibility for accurately finding eigenenergies and obtaining eigenstate measurements. Our work paves the way for efficient and universal quantum algorithmic cooling with near-term as well as universal fault-tolerant quantum devices.

arXiv:2109.15304•Sep 30, 2021•8 citations

A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems

Qing‐Xing Xie, Zhao Yan

Developing efficient quantum computing algorithms is essential for tackling computationally challenging problems across various fields. This paper presents a novel quantum algorithm, XZ24, for efficiently computing the eigen-energy spectra of arbitrary quantum systems. Given a Hamiltonian $\hat{H}$ and an initial reference state $|ψ_{\text{ref}} \rangle$, the algorithm extracts information about $\langle ψ_{\text{ref}} | \cos(\hat{H} t) | ψ_{\text{ref}} \rangle$ from an auxiliary qubit's state. By applying a Fourier transform, the algorithm resolves the energies of eigenstates of the Hamiltonian with significant overlap with the reference wavefunction. We provide a theoretical analysis and numerical simulations, showing XZ24's superior efficiency and accuracy compared to existing algorithms. XZ24 has three key advantages: 1. It removes the need for eigenstate preparation, requiring only a reference state with non-negligible overlap, improving upon methods like the Variational Quantum Eigensolver. 2. It reduces measurement overhead, measuring only one auxiliary qubit. For a system of size $L$ with precision $ε$, the sampling complexity scales as $O(L \cdot ε^{-1})$. When relative precision $ε$ is sufficient, the complexity scales as $O(ε^{-1})$, making measurements independent of system size. 3. It enables simultaneous computation of multiple eigen-energies, depending on the reference state. We anticipate that XZ24 will advance quantum system simulations and enhance applications in quantum computing.

arXiv:2406.00296•Jun 1, 2024•3 citations

Computing the lowest eigenstate of tight-binding Hamiltonians using quantum walks

Georgios D. Varsamis, Ioannis G. Karafyllidis

Finding or estimating the lowest eigenstate of quantum system Hamiltonians is an important problem for quantum computing, quantum physics, quantum chemistry, and material science. Several quantum computing approaches have been developed to address this problem. The most frequently used method is variational quantum eigensolver (VQE). Many quantum systems, and especially nanomaterials, are described using tight-binding Hamiltonians, but until now no quantum computation method has been developed to find the lowest eigenvalue of these specific, but very important, Hamiltonians. We address the problem of finding the lowest eigenstate of tight-binding Hamiltonians using quantum walks. Quantum walks is a universal model of quantum computation equivalent to the quantum gate model. Furthermore, quantum walks can be mapped to quantum circuits comprising qubits, quantum registers, and quantum gates and, consequently, executed on quantum computers. In our approach, probability distributions, derived from wave function probability amplitudes, enter our quantum algorithm as potential distributions in the space where the quantum walk evolves. Our results showed the quantum walker localization in the case of the lowest eigenvalue is distinctive and characteristic of this state. Our approach will be a valuable computation tool for studying quantum systems described by tight-binding Hamiltonians.

International Journal of Quantum Information•Apr 25, 2022•4 citations

Fast quantum algorithms for traversing paths of eigenstates

Sergio Boixo, E. Knill, Rolando D. Somma

Consider a path of non-degenerate eigenstates of unitary operators or Hamiltonians with minimum eigenvalue gap G. The eigenpath traversal problem is to transform one or more copies of the initial to the final eigenstate. Solutions to this problem have applications ranging from quantum physics simulation to optimization. For Hamiltonians, the conventional way of doing this is by applying the adiabatic theorem. We give ``digital'' methods for performing the transformation that require no assumption on path continuity or differentiability other than the absence of large jumps. Given sufficient information about eigenvalues and overlaps between states on the path, the transformation can be accomplished with complexity O(L/G log(L/e)), where L is the angular length of the path and e is a specified bound on the error of the output state. We show that the required information can be obtained in a first set of transformations, whose complexity per state transformed has an additional factor that depends logarithmically on a maximum angular velocity along the path. This velocity is averaged over constant angular distances and does not require continuity. Our methods have substantially better behavior than conventional adiabatic algorithms, with fewer conditions on the path. They also improve on the previously best digital methods and demonstrate that path length and the gap are the primary parameters that determine the complexity of state transformation along a path.

arXiv:1005.3034•May 17, 2010•12 citations

Algorithmic approach to adiabatic quantum optimization

Neil G. Dickson, M. H. S. Amin

It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing nonadiabatically. This information is then used to penalize pathways to the corresponding local minima by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between ${10}^{5}$ and ${10}^{6}$ highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\ensuremath{\sim}$10 iterations.

arXiv:1108.3303•Physical Review A•Mar 5, 2012•40 citations

A Quantum Mechanical Analog of Hamiltonian Monte Carlo

Matthew Hagan

The simulation of quantum systems is the most promising candidate for computational advantagesof large scale, fault-tolerant quantum computers over classical computers. Two fundamental prob- lems that appear when simulating quantum systems on quantum computers are the preparation of good input states to the simulation and the problem of decomposing the time evolution operator ???? into primitive gates that are available on the quantum computer. This thesis presents two new algorithms for solving these problems. The first is a time evolution algorithm that approximates the time evolution operator by combining two previously developed techniques. We bound the error of this composite approach and determine analytic conditions on when this can lead to cost savings of the overall simulation. These savings are then verified through extensive numerics. This simulation algorithm can then be used as a subroutine to prepare thermal states, which are typical input states that have a high overlap with the ground state. Our algorithm is inspired by Hamiltonian Monte Carlo, which is a classical sampling algorithm that utilizes Hamiltonian dynamics to sample from arbitrary probability distributions. We bound the cost of our quantum thermal state preparation algorithm in terms of the total amount of time needed to simulate the Hamiltonian of the system in four scenarios: single qubit systems, truncated harmonic oscillators, non-degenerate systems where one knows the eigenvalues, and non-degenerate systems where no eigenvalue knowledge is present. We numerically demonstrate that this algorithm works as guaranteed and can significantly outperform analytic worst-case bounds.

•Oct 1, 2025•0 citations
We propose a quantum algorithm to obtain the lowest eigenstate of any Hamiltonian simulated by a quantum computer. The proposed algorithm begins with an arbitrary initial state of the simulated system. A finite series of transforms is iteratively applied to the initial state assisted with an ancillary qubit. The fraction of the lowest eigenstate in the initial state is then amplified up to ≃1\simeq 1≃1. We prove that our algorithm can faithfully work for any arbitrary Hamiltonian in the theoretical analysis. Numerical analyses are also carried out. We firstly provide a numerical proof-of-principle demonstration with a simple Hamiltonian in order to compare our scheme with the so-called Demon-like algorithmic (DLAC), recently proposed in [Nature Photonics 8, 113 (2014)]. The result shows a good agreement with our theoretical analysis, exhibiting the comparable behavior to the best cooling with the DLAC method. We then consider a random Hamiltonian model for further analysis of our algorithm. By numerical simulations, we show that the total number ncn_cnc​ of iterations is proportional to ≃O(D−1ϵ−0.19)\simeq {\cal O}(D^{-1}\epsilon^{-0.19})≃O(D−1ϵ−0.19), where DDD is the difference between the two lowest eigenvalues, and ϵ\epsilonϵ is an error defined as the probability that the finally obtained system state is in an unexpected (i.e. not the lowest) eigenstate.
Quantum cooling, a deterministic process that drives any state to the lowest eigenstate, has been widely used from studying ground state properties of chemistry and condensed matter quantum physics, to general optimization problems. However, the cooling procedure is generally non-unitary, hence its realization on a quantum computer either requires deep circuits or assumes specific input states with variational circuits. Here, we propose universal quantum cooling algorithms that overcome these limitations. By utilizing a dual phase representation of decaying functions, we show how to universally and deterministically realize a general cooling procedure with shallow quantum circuits. We demonstrate its applications in cooling an arbitrary input state with known ground state energy, corresponding to satisfactory, linear algebra tasks, and quantum state compiling tasks, and preparing unknown eigenvalues and eigenstates, corresponding to quantum many-body problems. Compared to quantum phase estimation, our method uses only one ancillary qubit and much shallower circuits, showing exponential improvement of the circuit complexity with respect to the final state infidelity. We numerically benchmark the algorithms for the 888-qubit Heisenberg model and verify its feasibility for accurately finding eigenenergies and obtaining eigenstate measurements. Our work paves the way for efficient and universal quantum algorithmic cooling with near-term as well as universal fault-tolerant quantum devices.
Developing efficient quantum computing algorithms is essential for tackling computationally challenging problems across various fields. This paper presents a novel quantum algorithm, XZ24, for efficiently computing the eigen-energy spectra of arbitrary quantum systems. Given a Hamiltonian H^\hat{H}H^ and an initial reference state ∣ψref⟩|ψ_{\text{ref}} \rangle∣ψref​⟩, the algorithm extracts information about ⟨ψref∣cos⁡(H^t)∣ψref⟩\langle ψ_{\text{ref}} | \cos(\hat{H} t) | ψ_{\text{ref}} \rangle⟨ψref​∣cos(H^t)∣ψref​⟩ from an auxiliary qubit's state. By applying a Fourier transform, the algorithm resolves the energies of eigenstates of the Hamiltonian with significant overlap with the reference wavefunction. We provide a theoretical analysis and numerical simulations, showing XZ24's superior efficiency and accuracy compared to existing algorithms. XZ24 has three key advantages: 1. It removes the need for eigenstate preparation, requiring only a reference state with non-negligible overlap, improving upon methods like the Variational Quantum Eigensolver. 2. It reduces measurement overhead, measuring only one auxiliary qubit. For a system of size LLL with precision εεε, the sampling complexity scales as O(L⋅ε−1)O(L \cdot ε^{-1})O(L⋅ε−1). When relative precision εεε is sufficient, the complexity scales as O(ε−1)O(ε^{-1})O(ε−1), making measurements independent of system size. 3. It enables simultaneous computation of multiple eigen-energies, depending on the reference state. We anticipate that XZ24 will advance quantum system simulations and enhance applications in quantum computing.
Finding or estimating the lowest eigenstate of quantum system Hamiltonians is an important problem for quantum computing, quantum physics, quantum chemistry, and material science. Several quantum computing approaches have been developed to address this problem. The most frequently used method is variational quantum eigensolver (VQE). Many quantum systems, and especially nanomaterials, are described using tight-binding Hamiltonians, but until now no quantum computation method has been developed to find the lowest eigenvalue of these specific, but very important, Hamiltonians. We address the problem of finding the lowest eigenstate of tight-binding Hamiltonians using quantum walks. Quantum walks is a universal model of quantum computation equivalent to the quantum gate model. Furthermore, quantum walks can be mapped to quantum circuits comprising qubits, quantum registers, and quantum gates and, consequently, executed on quantum computers. In our approach, probability distributions, derived from wave function probability amplitudes, enter our quantum algorithm as potential distributions in the space where the quantum walk evolves. Our results showed the quantum walker localization in the case of the lowest eigenvalue is distinctive and characteristic of this state. Our approach will be a valuable computation tool for studying quantum systems described by tight-binding Hamiltonians.
Consider a path of non-degenerate eigenstates of unitary operators or Hamiltonians with minimum eigenvalue gap G. The eigenpath traversal problem is to transform one or more copies of the initial to the final eigenstate. Solutions to this problem have applications ranging from quantum physics simulation to optimization. For Hamiltonians, the conventional way of doing this is by applying the adiabatic theorem. We give ``digital'' methods for performing the transformation that require no assumption on path continuity or differentiability other than the absence of large jumps. Given sufficient information about eigenvalues and overlaps between states on the path, the transformation can be accomplished with complexity O(L/G log(L/e)), where L is the angular length of the path and e is a specified bound on the error of the output state. We show that the required information can be obtained in a first set of transformations, whose complexity per state transformed has an additional factor that depends logarithmically on a maximum angular velocity along the path. This velocity is averaged over constant angular distances and does not require continuity. Our methods have substantially better behavior than conventional adiabatic algorithms, with fewer conditions on the path. They also improve on the previously best digital methods and demonstrate that path length and the gap are the primary parameters that determine the complexity of state transformation along a path.
It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing nonadiabatically. This information is then used to penalize pathways to the corresponding local minima by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between 105{10}^{5}105 and 106{10}^{6}106 highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\ensuremath{\sim}$10 iterations.
The simulation of quantum systems is the most promising candidate for computational advantagesof large scale, fault-tolerant quantum computers over classical computers. Two fundamental prob- lems that appear when simulating quantum systems on quantum computers are the preparation of good input states to the simulation and the problem of decomposing the time evolution operator ???? into primitive gates that are available on the quantum computer. This thesis presents two new algorithms for solving these problems. The first is a time evolution algorithm that approximates the time evolution operator by combining two previously developed techniques. We bound the error of this composite approach and determine analytic conditions on when this can lead to cost savings of the overall simulation. These savings are then verified through extensive numerics. This simulation algorithm can then be used as a subroutine to prepare thermal states, which are typical input states that have a high overlap with the ground state. Our algorithm is inspired by Hamiltonian Monte Carlo, which is a classical sampling algorithm that utilizes Hamiltonian dynamics to sample from arbitrary probability distributions. We bound the cost of our quantum thermal state preparation algorithm in terms of the total amount of time needed to simulate the Hamiltonian of the system in four scenarios: single qubit systems, truncated harmonic oscillators, non-degenerate systems where one knows the eigenvalues, and non-degenerate systems where no eigenvalue knowledge is present. We numerically demonstrate that this algorithm works as guaranteed and can significantly outperform analytic worst-case bounds.