Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm

Abstract

We present a rigorous proof that quantum circuit algorithm can be transformed into quantum adiabatic algorithm with the exact same time complexity. This means that from a quantum circuit algorithm of $L$ gates we can construct a quantum adiabatic algorithm with time complexity of $O(L)$. Additionally, our construction shows that one may exponentially speed up some quantum adiabatic algorithms by properly choosing an evolution path.

8 pages, 4 figures

References in corpus (1)

• How Powerful is Adiabatic Quantum Computation?

Cited by in corpus (7)

• Quantum Adiabatic Algorithm Design using Reinforcement Learning
• Quantum independent set problem and non-abelian adiabatic mixing
• Quantum Computing by Cooling
• Resonant Quantum Search with Monitor Qubits
• Quantum Adiabatic Doping with Incommensurate Optical Lattices
• Quantum algorithm of a set of quantum 2-sat problem
• Q-CHOP: Quantum constrained Hamiltonian optimization