期刊
PHYSICAL REVIEW A
卷 95, 期 6, 页码 -出版社
AMER PHYSICAL SOC
DOI: 10.1103/PhysRevA.95.062317
关键词
-
资金
- NASA Advanced Exploration Systems program
- NASA Ames Research Center
- AFRL Information Directorate [F4HBKC4162G001]
- Office of the Director of National Intelligence (ODNI)
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据