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:1301.4956 · Journal of Physics A Mathematical and Theoretical

How fast can quantum annealers count?

Itay Hen

Published May 27, 2014• 11 citations
arXivHTMLPDF

Abstract

We outline an algorithm for the quantum counting problem using adiabatic quantum computation (AQC). We show that the mechanism of quantum-adiabatic evolution may be utilized toward estimating the number of solutions to a problem, and not only to find them. Using local adiabatic evolution, a process in which the adiabatic procedure is performed at a variable rate, the problem of counting the number of marked items in an unstructured database is solved quadratically faster than the corresponding classical algorithm. The above algorithm provides further evidence for the potentially powerful capabilities of AQC as a paradigm for more efficient problem solving on a quantum computer, and may be used as the basis for solving more sophisticated problems.

DOI
10.1088/1751-8113/47/23/235304

Related papers

Quantum search by local adiabatic evolution

Jérémie Roland, Nicolas J. Cerf

The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the quantum computer evolves slowly enough so that it remains near its instantaneous ground state, which tends to the solution. We apply this time-dependent Hamiltonian approach to Grover's problem, i.e., searching a marked item in an unstructured database. We find that by adjusting the evolution rate of the Hamiltonian so as to keep the evolution adiabatic on each infinitesimal time interval, the total running time is of order $\sqrt{N},$ where N is the number of items in the database. We thus recover the advantage of Grover's standard algorithm as compared to a classical search, scaling as N. This is in contrast with the constant-rate adiabatic approach of Farhi et al. (e-print quant-ph/0001106), where the requirement of adiabaticity is expressed only globally, resulting in a time of order N.

arXiv:quant-ph/0107015•Physical Review A•Mar 26, 2002•629 citations

How powerful is adiabatic quantum computation?

W. van Dam, M. Mosca, U. Vazirani

The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.

arXiv:quant-ph/0206003•Annual Symposium on Foundations of Computer Science•Jan 1, 2001•175 citations

Adiabatic Quantum Counting by Geometric Phase Estimation

Chi Zhang, Zhaohui Wei, Anargyros Papageorgiou

We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion, $α$, of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase $2πα$. By estimating the Berry phase, we can approximate $α$, and solve the problem. For an error bound $ε$, the algorithm can solve the problem with cost of order $(\frac{1}ε)^{3/2}$, which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.

arXiv:0805.1387•May 9, 2008•0 citations

On the efficiency of Hamiltonian-based quantum computation for low-rank matrices

Zhenwei Cao, Alexander Elgart

We present an extension of adiabatic quantum computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.

arXiv:1004.4911•Journal of Mathematical Physics•Mar 1, 2012•6 citations

On the efficiency of Hamiltonian–based quantum computation for low–rank matrices

Zhenwei Cao, Alexander Elgart

We present an extension of Adiabatic Quantum Computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.

•Jan 1, 2012•6 citations

Adiabatic quantum search algorithm for structured problems

Jérémie Roland, Nicolas J. Cerf

The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.

arXiv:quant-ph/0304039•Physical Review A•Dec 15, 2003•29 citations
We outline an algorithm for the quantum counting problem using adiabatic quantum computation (AQC). We show that the mechanism of quantum-adiabatic evolution may be utilized toward estimating the number of solutions to a problem, and not only to find them. Using local adiabatic evolution, a process in which the adiabatic procedure is performed at a variable rate, the problem of counting the number of marked items in an unstructured database is solved quadratically faster than the corresponding classical algorithm. The above algorithm provides further evidence for the potentially powerful capabilities of AQC as a paradigm for more efficient problem solving on a quantum computer, and may be used as the basis for solving more sophisticated problems.
The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the quantum computer evolves slowly enough so that it remains near its instantaneous ground state, which tends to the solution. We apply this time-dependent Hamiltonian approach to Grover's problem, i.e., searching a marked item in an unstructured database. We find that by adjusting the evolution rate of the Hamiltonian so as to keep the evolution adiabatic on each infinitesimal time interval, the total running time is of order N,\sqrt{N},N​, where N is the number of items in the database. We thus recover the advantage of Grover's standard algorithm as compared to a classical search, scaling as N. This is in contrast with the constant-rate adiabatic approach of Farhi et al. (e-print quant-ph/0001106), where the requirement of adiabaticity is expressed only globally, resulting in a time of order N.
The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.
We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion, ααα, of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase 2πα2πα2πα. By estimating the Berry phase, we can approximate ααα, and solve the problem. For an error bound εεε, the algorithm can solve the problem with cost of order (1ε)3/2(\frac{1}ε)^{3/2}(ε1​)3/2, which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.
We present an extension of adiabatic quantum computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.
We present an extension of Adiabatic Quantum Computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.
The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.