Near-optimal quantum circuit for Grover's unstructured search using a transverse field

Zhang Jiang, Eleanor G. Rieffel, and Zhihui Wang
Phys. Rev. A 95, 062317 – Published 12 June 2017

Abstract

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 periodic manner. 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 Θ(1/N), and the overlaps are of order Θ(1), yielding a nearly optimal query complexity of TN(π/22). 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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 7 March 2017

DOI:https://doi.org/10.1103/PhysRevA.95.062317

©2017 American Physical Society

Physics Subject Headings (PhySH)

  1. Research Areas
Quantum Information, Science & Technology

Authors & Affiliations

Zhang Jiang1,2,*, Eleanor G. Rieffel1, and Zhihui Wang1,3

  • 1Quantum Artificial Intelligence Laboratory, NASA Ames Research Center, Moffett Field, California 94035, USA
  • 2Stinger Ghaffarian Technologies Inc., 7701 Greenbelt Road, Suite 400, Greenbelt, Maryland 20770, USA
  • 3Universities Space Research Association, 615 National Avenue, Mountain View, California 94043, USA

  • *zhang.jiang@nasa.gov

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 95, Iss. 6 — June 2017

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×