How Quantum is the Speedup in Adiabatic Unstructured Search?
arXiv:1811.08302 · doi:10.1007/s11128-019-2281-y
Abstract
In classical computing, analog approaches have sometimes appeared to be more powerful than they really are. This occurs when resources, particularly precision, are not appropriately taken into account. While the same should also hold for analog quantum computing, precision issues are often neglected from the analysis. In this work we present a classical analog algorithm for unstructured search that can be viewed as analogous to the quantum adiabatic unstructured search algorithm devised by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)]. We show that similarly to its quantum counterpart, the classical construction may also provide a quadratic speedup over standard digital unstructured search. We discuss the meaning and the possible implications of this result in the context of adiabatic quantum computing.
arXiv comment6 pages, 4 figures
References in corpus (35)
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum Annealing in the Transverse Ising Model
- 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
- Adiabatic Quantum Computing
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Spatial search by quantum walk
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Quantum Search by Local Adiabatic Evolution
- Defining and detecting quantum speedup
- Bounds for the adiabatic approximation with applications to quantum computation
- Experimental signature of programmable quantum annealing
- Exponential improvement in precision for simulating sparse Hamiltonians
- Thermal and Residual Excited-State Population in a 3D Transmon Qubit
- First order phase transition in the Quantum Adiabatic Algorithm
- How Powerful is Adiabatic Quantum Computation?
- Fabrication Process and Properties of Fully-Planarized Deep-Submicron Nb/Al-AlOx/Nb Josephson Junctions for VLSI Circuits
- Probing for quantum speedup in spin glass problems with planted solutions
- Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Inductance of Circuit Structures for MIT LL Superconductor Electronics Fabrication Process with 8 Niobium Layers
- Analog Errors in Ising Machines
- Efficient discrete-time simulations of continuous-time quantum query algorithms
- Adiabatic quantum search algorithm for structured problems
- Analog Nature of Quantum Adiabatic Unstructured Search
- Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
- Continuous-Time Quantum Algorithms for Unstructured Problems
- An Analog Analogue of a Digital Quantum Computation
- How Fast Can Quantum Annealers Count?
- Realizable Quantum Adiabatic Search
Cited by in corpus (5)
- Lower Bounds on Quantum Annealing Times
- Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
- Why adiabatic quantum annealing is unlikely to yield speed-up
- Noise-tolerant quantum speedups in quantum annealing without fine tuning
- Quantum-inspired memory-enhanced stochastic algorithms