Bulletin of the American Physical Society
APS March Meeting 2022
Volume 67, Number 3
Monday–Friday, March 14–18, 2022; Chicago
Session K36: Quantum Digital and Analog Algorithms
3:00 PM–6:00 PM,
Tuesday, March 15, 2022
Room: McCormick Place W-194A
Sponsoring Unit: DQI
Chair: Daniel Weiss, Northwestern University
Abstract: K36.00012 : Reflection-based adiabatic ground-state preparation*
5:36 PM–5:48 PM
(Universite de Sherbrooke)
(University of Waterloo)
Grover’s search and adiabatic quantum computation (AQC) are two well-known quantum algorithms for achieving potential quantum speedups over classical algorithms in tackling various hard combinatorial search problems. While Grover’s search is based on the effects of constructive and destructive quantum interference of amplitudes, AQC relies on adiabatic evolution of the ground state of a system to find a solution to an optimization problem. For unstructured search problems, Grover’s algorithm possesses an optimal query complexity. However, many real-world computational problems are endowed with additional structures, and exploiting them can result in more efficient heuristics.
We present a new circuit-model quantum algorithm that is based on a combination of concepts from both Grover's search and AQC. Our algorithm deploys a sequence of reflections determined by the instantaneous eigenspaces of intermediate Hamiltonians along an adiabatic evolution in order to prepare a ground state of a target problem Hamiltonian. Using the NP-hard Max-2-SAT problem, we provide numerical evidence suggesting that, for combinatorial search problems, our algorithm can, on average, find a solution faster than Grover's search.
*We acknowledge support from 1QBit, the University of Waterloo, Mike and Ophelia Lazaridis, and Innovation, Science and Economic Development Canada.
The American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics.
1 Physics Ellipse, College Park, MD 20740-3844
Editorial Office 1 Research Road, Ridge, NY 11961-2701 (631) 591-4000
Office of Public Affairs 529 14th St NW, Suite 1050, Washington, D.C. 20045-2001 (202) 662-8700