A necessary condition for quantum adiabaticity applied to the adiabatic Grover search
arXiv:1802.06011 · doi:10.1007/s10946-018-9751-z
Abstract
Numerous sufficient conditions for adiabaticity of the evolution of a driven quantum system have been known for quite a long time. In contrast, necessary adiabatic conditions are scarce. A practicable necessary condition well-suited for many-body systems has been proven recently in [Phys. Rev. Lett. 119, 200401 (2017)]. Here we tailor this condition for estimating run times of quantum adiabatic algorithms. As an illustration, the condition is applied to the adiabatic algorithm for searching in an unstructured database (adiabatic Grover search algorithm). We find that thus obtained lower bound on the run time of this algorithm reproduces scaling ( being the number of database entries) of the explicitly known optimal run time. This observation highlights the merits of the new adiabatic condition and its potential relevance to adiabatic quantum computing.
References in corpus (17)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Adiabatic Quantum Computing
- Quantum Search by Local Adiabatic Evolution
- Quantum speed limits: from Heisenberg's uncertainty principle to optimal quantum control
- Quantum Speedup by Quantum Annealing
- The quantitative condition is necessary in guaranteeing the validity of the adiabatic approximation
- Bloch oscillations in one-dimensional spinor gas
- Necessary Condition for the Quantum Adiabatic Approximation
- Kinetic theory for a mobile impurity in a degenerate Tonks-Girardeau gas
- Time scale for adiabaticity breakdown in driven many-body systems and orthogonality catastrophe
- The Adiabatic Theorem for Quantum Systems with Spectral Degeneracy
- Necessary and sufficient condition for quantum adiabatic evolution by unitary control fields
- The Travelling Salesman Problem and Adiabatic Quantum Computation: An Algorithm
- Comment on "Quantitative Condition is Necessary in Guaranteeing the Validity of the Adiabatic Approximation" [arXiv:1004.3100]
- Reply to "Comment on 'Kinetic theory for a mobile impurity in a degenerate Tonks-Girardeau gas'"
- Why the Quantitative Condition Fails to Reveal Quantum Adiabaticity
- Quantum Many-Body Adiabaticity, Topological Thouless Pump and Driven Impurity in a One-Dimensional Quantum Fluid
Cited by in corpus (4)
- Quantum speed limit for thermal states
- Bounds on quantum adiabaticity in driven many-body systems from generalized orthogonality catastrophe and quantum speed limit
- Lower bounds for adiabatic quantum algorithms by quantum speed limits
- Quantum speed limits for an open system in contact with a thermal bath