Quantum search by local adiabatic evolution

By Jérémie Roland, Nicolas J. Cerf. 2001

581 citations recorded by the source corpus.

The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the quantum computer evolves slowly enough so that it remains near its instantaneous ground state, which tends to the solution. We apply this time-dependent Hamiltonian approach to Grover’s problem, i.e., searching a marked item in an unstructured database. We find that by adjusting the evolution rate of the Hamiltonian so as to keep the evolution adiabatic on each infinitesimal time interval, the total running time is of order AN, where N is the number of items in the database. We thus recover the advantage of Grover’s standard algorithm as compared to a classical search, scaling as N. This is in contrast with the constant-rate adiabatic approach of Farhi et al. ~e-print quant-ph/0001106!, where the requirement of adiabaticity is expressed only globally, resulting in a time of order N.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/c9e5689e01fda5bfa5556514c632884de56e8265

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Robustness of adiabatic quantum computation (2001, background): “An example of this is seen in [23], where it is shown that optimizing the time-dependent coefficients of HB and HP allows the adiabatic algorithm to achieve a square root speedup for an unordered search problem.”
Shortcuts to adiabaticity: Concepts, methods, and applications (2019, unknown): “(95) The “local adiabatic” approach (Richerme et al., 2013; Roland and Cerf, 2002) gives an equation similar to Eq.”
Adiabatic quantum computation is equivalent to standard quantum computation (2004, background): “In [9,30] it was shown that Grover’s quadratic speed-up for an unsorted search [16] can be realized as an adiabatic computation.”
Ising machines as hardware solvers of combinatorial optimization problems (2022, background): “The sweep time for which the adiabaticity can be achieved is proportional to a negative power of the minimum energy gap between two lowest energy levels during the sweep 149–152 .”
Adiabatic quantum state generation and statistical zero knowledge (2003, methodology): “We take c = 1 / 6 and show how to solve DLP 1 / 6 with CQS.”
Adiabatic Quantum Computing (2016, methodology): “The present results generalize easily to the case where we have M ≥ 1 marked states, for which Grover’s algorithm is known to also give a quadratic speedup in the 16 Note that the scaling conclusion tf ∼ √ N reported in (Roland and Cerf, 2002) is based on the interpretation of Eq.”
High-fidelity quantum driving (2011, methodology): “[21] Roland, J. & Cerf, N.J. Quantum search by local adiabatic evolution Phys.”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, background): “Note, however, that almost all known continuous-time quantum algorithms have HD time-independent (with the notable exception of adiabatic algorithms for search [22, 43], which can nevertheless be simulated efficiently in the quantum circuit model [44]) and satisfy ‖abs(HD)‖ = O(1).”
Quantum computing for finance: Overview and prospects (2018, background): “Furthermore, it is an extremely general model, as it can be modified to add intermediate Hamiltonians [45] and can be made to fulfill local adiabatic conditions [46].”
Fast-forward of adiabatic dynamics in quantum mechanics (2009, background): “…Hamiltonian, it remains so during the process, has been studied in various contexts (Berry 1984; Aharonov & Anandan 1987; Samuel & Bhandari 1988; Shapere & Wilczek 1989; Nakamura & Rice 1994; Bouwmeester et al. 1996; Farhi et al. 2001; Roland & Cerf 2002; Sarandy & Lidar 2005; Du et al. 2008).”