Journal
PHYSICAL REVIEW A
Volume 95, Issue 6, Pages -Publisher
AMER PHYSICAL SOC
DOI: 10.1103/PhysRevA.95.062317
Keywords
-
Categories
Funding
- NASA Advanced Exploration Systems program
- NASA Ames Research Center
- AFRL Information Directorate [F4HBKC4162G001]
- Office of the Director of National Intelligence (ODNI)
Ask authors/readers for more resources
Inspired by a class of algorithms proposed by Farhi et al. (arXiv: 1411.4028), namely, the quantum approximate optimization algorithm (QAOA), we present a circuit-based quantum algorithm to search for a needle in a haystack, obtaining the same quadratic speedup achieved by Grover's original algorithm. In our algorithm, the problem Hamiltonian (oracle) and a transverse field are applied alternately to the system in a periodicmanner. We introduce a technique, based on spin-coherent states, to analyze the composite unitary in a single period. This composite unitary drives a closed transition between two states that have high degrees of overlap with the initial state and the target state, respectively. The transition rate in our algorithm is of order Theta(1/root N), and the overlaps are of order Theta(1), yielding a nearly optimal query complexity of T similar or equal to root N(pi/2 root 2). Our algorithm is a QAOA circuit that demonstrates a quantum advantage with a large number of iterations that is not derived from Trotterization of an adiabatic quantum optimization (AQO) algorithm. It also suggests that the analysis required to understand QAOA circuits involves a very different process from estimating the energy gap of a Hamiltonian in AQO.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available