How Fast Can Quantum Annealers Count?
arXiv:1301.4956 · doi:10.1088/1751-8113/47/23/235304
Abstract
We outline an algorithm for the Quantum Counting problem using Adiabatic Quantum Computation (AQC). We show that using local adiabatic evolution, a process in which the adiabatic procedure is performed at a variable rate, the problem is solved with the same complexity as the analogous circuit-based algorithm, i.e., 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.
arXiv comment12 pages. No figures
References in corpus (23)
- Quantum Mechanics helps in searching for a needle in a haystack
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
- Quantum Search by Local Adiabatic Evolution
- Bounds for the adiabatic approximation with applications to quantum computation
- Quantum Counting
- Simple proof of equivalence between adiabatic quantum computation and the circuit model
- Consistency of the Adiabatic Theorem
- First order phase transition in the Quantum Adiabatic Algorithm
- Quantitative conditions do not guarantee the validity of the adiabatic approximation
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- Adiabatic Quantum Computing for Random Satisfiability Problems
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
- General error estimate for adiabatic quantum computing
- Tunneling spectroscopy using a probe qubit
- Computational Difficulty of Computing the Density of States
- Adiabatic quantum search algorithm for structured problems
- Adiabatic quantum optimization fails for random instances of NP-complete problems
- Period Finding with Adiabatic Quantum Computation
- On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm
- Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
- Continuous-Time Quantum Algorithms for Unstructured Problems
Cited by in corpus (6)
- Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
- Quantum Gates with Controlled Adiabatic Evolutions
- Analog Nature of Quantum Adiabatic Unstructured Search
- Period Finding with Adiabatic Quantum Computation
- Fixed-Point Adiabatic Quantum Search
- How Quantum is the Speedup in Adiabatic Unstructured Search?