How Fast Can Quantum Annealers Count?

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.

12 pages. No figures

References in corpus (10)

• Bounds for the adiabatic approximation with applications to quantum computation
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Tunneling spectroscopy using a probe qubit
• Computational Difficulty of Computing the Density of States
• 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?