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:0806.0385 · Physical Review A

Adiabatic quantum computation with a one-dimensional projector Hamiltonian

Avatar Tulsi

Published Nov 23, 2009• 27 citations
arXivHTMLPDF

Abstract

Adiabatic quantum computation is based on the adiabatic evolution of quantum systems. We analyze a particular class of quantum adiabatic evolutions where either the initial or final Hamiltonian is a one-dimensional projector Hamiltonian on the corresponding ground state. The minimum-energy gap, which governs the time required for a successful evolution, is shown to be proportional to the overlap of the ground states of the initial and final Hamiltonians. We show that such evolutions exhibit a rapid crossover as the ground state changes abruptly near the transition point where the energy gap is minimum. Furthermore, a faster evolution can be obtained by performing a partial adiabatic evolution within a narrow interval around the transition point. These results generalize and quantify earlier works.

DOI
10.1103/physreva.80.052328

Related papers

ON THE ADIABATIC EVOLUTION OF ONE-DIMENSIONAL PROJECTOR HAMILTONIANS

Jie Sun, Songfeng Lu

In this paper, we discuss the adiabatic evolution of one-dimensional projector Hamiltonians. Three kinds of adiabatic algorithms for this problem are shown, in which two of them provide a quadratic speedup over the other one. But when the ground state of the initial Hamiltonian and that of the final Hamiltonian have a zero overlap, the algorithms above all fail, in the sense of infinite time complexity. A corresponding revised method for this phenomenon through adding a driving Hamiltonian is also shown, from which a constant time complexity can be gained. But by a simple analysis, we find that the original time complexity for the adiabatic evolution is shifted to implement the driving Hamiltonian, which is supported by several early works in the literature.

International Journal of Quantum Information•Jun 1, 2012•9 citations

On Models of Nonlinear Evolution Paths in Adiabatic Quantum Algorithms4

孙杰, 路松峰

In this paper,we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state.If the overlap between the initial state and final state of the quantum system is not equal to zero,both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding complexity.But when the initial state has a zero overlap with the solution state in the problem,the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time.However,inspired by a related reference,a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the intrinsic fault of the second model - an increase in energy.Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above.These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.

理论物理通讯：英文版•Jan 1, 2013•0 citations

On Models of Nonlinear Evolution Paths in Adiabatic Quantum Algorithms

Jie Sun, Songfeng Lu, Samuel L. Braunstein

In this paper, we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state. If the overlap between the initial state and final state of the quantum system is not equal to zero, both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding "complexity". But when the initial state has a zero overlap with the solution state in the problem, the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time. However, inspired by a related reference, a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the "intrinsic" fault of the second model — an increase in energy. Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above. These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.

arXiv:1301.1115•Communications in Theoretical Physics•Jan 1, 2013•8 citations

How the High-energy Part of the Spectrum Affects the Adiabatic Computation Gap

Yosi Atia, Dorit Aharonov

Towards better understanding of how to design efficient adiabatic quantum algorithms, we study how the adiabatic gap depends on the spectra of the initial and final Hamiltonians in a natural family of test-bed examples. We show that perhaps counter-intuitively, changing the energy in the initial and final Hamiltonians of only highly excited states (we do this by assigning all eigenstates above a certain cutoff the same value), can turn the adiabatic algorithm from being successful to failing. Interestingly, our system exhibits a phase transition; when the cutoff in the spectrum becomes smaller than roughly $n/2$, $n$ being the number of qubits, the behavior transitions from a successful adiabatic process to a failed one. To analyze this behavior, and provide an upper bound on both the minimal gap as well as the success of the adiabatic algorithm, we introduce the notion of "escape rate", which quantifies the rate by which the system escapes the initial ground state (a related notion was also used by Ilin and Lychkovskiy in arXiv:1805.04083). Our results indicate a phenomenon that is interesting on its own right: an adiabatic evolution may be robust to bounded-rank perturbations, even when the latter closes the gap or makes it exponentially small.

arXiv:1906.02581•Jun 6, 2019•0 citations

A quantum search algorithm based on partial adiabatic evolution

Yingyu Zhang, Heping Hu, Songfeng Lu

This paper presents and implements a specified partial adiabatic search algorithm on a quantum circuit. It studies the minimum energy gap between the first excited state and the ground state of the system Hamiltonian and it finds that, in the case of M = 1, the algorithm has the same performance as the local adiabatic algorithm. However, the algorithm evolves globally only within a small interval, which implies that it keeps the advantages of global adiabatic algorithms without losing the speedup of the local adiabatic search algorithm.

Chinese Physics B•Apr 1, 2011•13 citations

Schedule path optimization for adiabatic quantum computing and optimization

Lishan Zeng, Jun Zhang, Mohan Sarovar

Abstract Adiabatic quantum computing and optimization have garnered much attention recently as possible models for achieving a quantum advantage over classical approaches to optimization and other special purpose computations. Both techniques are probabilistic in nature and the minimum gap between the ground state and first excited state of the system during evolution is a major factor in determining the success probability. In this work we investigate a strategy for increasing the minimum gap and success probability by introducing intermediate Hamiltonians that modify the evolution path between initial and final Hamiltonians. We focus on an optimization problem relevant to recent hardware implementations and present numerical evidence for the existence of a purely local intermediate Hamiltonian that achieve the optimum performance in terms of pushing the minimum gap to one of the end points of the evolution. As a part of this study we develop a convex optimization formulation of the search for optimal adiabatic schedules that makes this computation more tractable, and which may be of independent interest. We further study the effectiveness of random intermediate Hamiltonians on the minimum gap and success probability, and empirically find that random Hamiltonians have a significant probability of increasing the success probability, but only by a modest amount.

arXiv:1505.00209•Journal of Physics A Mathematical and Theoretical•Mar 14, 2016•31 citations
Adiabatic quantum computation is based on the adiabatic evolution of quantum systems. We analyze a particular class of quantum adiabatic evolutions where either the initial or final Hamiltonian is a one-dimensional projector Hamiltonian on the corresponding ground state. The minimum-energy gap, which governs the time required for a successful evolution, is shown to be proportional to the overlap of the ground states of the initial and final Hamiltonians. We show that such evolutions exhibit a rapid crossover as the ground state changes abruptly near the transition point where the energy gap is minimum. Furthermore, a faster evolution can be obtained by performing a partial adiabatic evolution within a narrow interval around the transition point. These results generalize and quantify earlier works.
In this paper, we discuss the adiabatic evolution of one-dimensional projector Hamiltonians. Three kinds of adiabatic algorithms for this problem are shown, in which two of them provide a quadratic speedup over the other one. But when the ground state of the initial Hamiltonian and that of the final Hamiltonian have a zero overlap, the algorithms above all fail, in the sense of infinite time complexity. A corresponding revised method for this phenomenon through adding a driving Hamiltonian is also shown, from which a constant time complexity can be gained. But by a simple analysis, we find that the original time complexity for the adiabatic evolution is shifted to implement the driving Hamiltonian, which is supported by several early works in the literature.
In this paper,we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state.If the overlap between the initial state and final state of the quantum system is not equal to zero,both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding complexity.But when the initial state has a zero overlap with the solution state in the problem,the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time.However,inspired by a related reference,a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the intrinsic fault of the second model - an increase in energy.Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above.These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.
In this paper, we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state. If the overlap between the initial state and final state of the quantum system is not equal to zero, both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding "complexity". But when the initial state has a zero overlap with the solution state in the problem, the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time. However, inspired by a related reference, a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the "intrinsic" fault of the second model — an increase in energy. Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above. These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.
Towards better understanding of how to design efficient adiabatic quantum algorithms, we study how the adiabatic gap depends on the spectra of the initial and final Hamiltonians in a natural family of test-bed examples. We show that perhaps counter-intuitively, changing the energy in the initial and final Hamiltonians of only highly excited states (we do this by assigning all eigenstates above a certain cutoff the same value), can turn the adiabatic algorithm from being successful to failing. Interestingly, our system exhibits a phase transition; when the cutoff in the spectrum becomes smaller than roughly n/2n/2n/2, nnn being the number of qubits, the behavior transitions from a successful adiabatic process to a failed one. To analyze this behavior, and provide an upper bound on both the minimal gap as well as the success of the adiabatic algorithm, we introduce the notion of "escape rate", which quantifies the rate by which the system escapes the initial ground state (a related notion was also used by Ilin and Lychkovskiy in arXiv:1805.04083). Our results indicate a phenomenon that is interesting on its own right: an adiabatic evolution may be robust to bounded-rank perturbations, even when the latter closes the gap or makes it exponentially small.
This paper presents and implements a specified partial adiabatic search algorithm on a quantum circuit. It studies the minimum energy gap between the first excited state and the ground state of the system Hamiltonian and it finds that, in the case of M = 1, the algorithm has the same performance as the local adiabatic algorithm. However, the algorithm evolves globally only within a small interval, which implies that it keeps the advantages of global adiabatic algorithms without losing the speedup of the local adiabatic search algorithm.
Abstract Adiabatic quantum computing and optimization have garnered much attention recently as possible models for achieving a quantum advantage over classical approaches to optimization and other special purpose computations. Both techniques are probabilistic in nature and the minimum gap between the ground state and first excited state of the system during evolution is a major factor in determining the success probability. In this work we investigate a strategy for increasing the minimum gap and success probability by introducing intermediate Hamiltonians that modify the evolution path between initial and final Hamiltonians. We focus on an optimization problem relevant to recent hardware implementations and present numerical evidence for the existence of a purely local intermediate Hamiltonian that achieve the optimum performance in terms of pushing the minimum gap to one of the end points of the evolution. As a part of this study we develop a convex optimization formulation of the search for optimal adiabatic schedules that makes this computation more tractable, and which may be of independent interest. We further study the effectiveness of random intermediate Hamiltonians on the minimum gap and success probability, and empirically find that random Hamiltonians have a significant probability of increasing the success probability, but only by a modest amount.