Near-optimal quantum circuit for Grover's unstructured search using a transverse field
Near-optimal quantum circuit for Grover's unstructured search using a transverse field
复制标题
DOI：
10.1103/physreva.95.062317
复制
发表时间：
2017-06-12
影响因子：
2.9
通讯作者：
Wang, Zhihui
中科院分区：
文献类型：
--
作者：
Jiang, Zhang;Rieffel, Eleanor G.;Wang, Zhihui
受Farhi等人（arXiv：1411.4028）提出的一类量子近似优化算法（QAOA）的启发，提出了一种基于电路的量子算法，用于大海捞针，获得了与Grover原算法相同的二次加速比。在我们的算法中，问题哈密顿量（oracle）和横向场交替施加到系统中的一个并行的方式。我们介绍了一种技术，基于自旋相干态，分析在一个单一的周期的复合幺正。该复合么正驱动分别与初始状态和目标状态具有高度重叠的两个状态之间的闭合转变。在我们的算法中的转移率是Theta（1/root N）的阶，并且重叠是Theta（1）的阶，产生接近最优的查询复杂度T，其类似于或等于root N（pi/2 root 2）。我们的算法是一个QAOA电路，展示了大量的迭代，而不是来自Trotterization的绝热量子优化（AQO）算法的量子优势。它还表明，理解QAOA电路所需的分析涉及到一个非常不同的过程，从估计的能隙的哈密顿在AQO。
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.