Analog Nature of Quantum Adiabatic Unstructured Search
arXiv:1904.04420 · doi:10.1088/1367-2630/ab51f9
Abstract
The quantum adiabatic unstructured search algorithm is one of only a handful of quantum adiabatic optimization algorithms to exhibit provable speedups over their classical counterparts. With no fault tolerance theorems to guarantee the resilience of such algorithms against errors, understanding the impact of imperfections on their performance is of both scientific and practical significance. We study the robustness of the algorithm against various types of imperfections: limited control over the interpolating schedule, Hamiltonian misspecification, and interactions with a thermal environment. We find that the unstructured search algorithm's quadratic speedup is generally not robust to the presence of any one of the above non-idealities, and in some cases we find that it imposes unrealistic conditions on how the strength of these noise sources must scale to maintain the quadratic speedup.
arXiv comment7 pages, 3 figures. v2. Updated to published version
References in corpus (47)
- 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
- 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
- Quantum Adiabatic Markovian Master Equations
- Fault-tolerant quantum computation with long-range correlated noise
- Adiabatic Quantum Simulation of Quantum Chemistry
- Thermal and Residual Excited-State Population in a 3D Transmon Qubit
- Quantum Speedup by Quantum Annealing
- How Powerful is Adiabatic Quantum Computation?
- Fabrication Process and Properties of Fully-Planarized Deep-Submicron Nb/Al-AlOx/Nb Josephson Junctions for VLSI Circuits
- First order phase transition in the Quantum Adiabatic Algorithm
- Probing for quantum speedup in spin glass problems with planted solutions
- Decoherence in 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
- Noise resistance of adiabatic quantum computation using random matrix theory
- Experimental determination of Ramsey numbers
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Decoherence in adiabatic quantum computation
- Adiabatic quantum algorithms as quantum phase transitions: first versus second order
- Inductance of Circuit Structures for MIT LL Superconductor Electronics Fabrication Process with 8 Niobium Layers
- Exponential complexity of an adiabatic algorithm for an NP-complete problem
- Robustness of the adiabatic quantum search
- Non-Markovian decoherence in the adiabatic quantum search algorithm
- Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
- The quantum adiabatic search with decoherence in the instantaneous energy eigenbasis
- Efficient discrete-time simulations of continuous-time quantum query algorithms
- Adiabatic quantum search algorithm for structured problems
- Adiabatic Quantum Search in Open Systems
- Period Finding with Adiabatic Quantum Computation
- Effects of dissipation in an adiabatic quantum search algorithm
- Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
- Continuous-Time Quantum Algorithms for Unstructured Problems
- Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
- How Fast Can Quantum Annealers Count?
- Decoherence in a dynamical quantum phase transition
- Realizable Quantum Adiabatic Search
Cited by in corpus (7)
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Quantum Adiabatic Algorithm Design using Reinforcement Learning
- Lower Bounds on Quantum Annealing Times
- Disorder-assisted graph coloring on quantum annealers
- How Quantum is the Speedup in Adiabatic Unstructured Search?
- Why adiabatic quantum annealing is unlikely to yield speed-up
- Assessing the performance of quantum annealing with nonlinear driving