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.
6 pages, 4 figures
References in corpus (12)
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Spatial search by quantum walk
- Bounds for the adiabatic approximation with applications to quantum computation
- Thermal and Residual Excited-State Population in a 3D Transmon Qubit
- How Powerful is Adiabatic Quantum Computation?
- Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
- 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
- Inductance of Circuit Structures for MIT LL Superconductor Electronics Fabrication Process with 8 Niobium Layers
- Efficient discrete-time simulations of continuous-time quantum query algorithms
- Analog Nature of Quantum Adiabatic Unstructured Search