Published April 21, 2022 | Version v1
Journal article Open

Deterministic Grover search with a restricted oracle

  • 1. University of Chicago

Description

Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms across a broad class of unstructured search problems. The original protocol is probabilistic, returning the desired result with significant probability on each query but, in general, requiring several iterations of the algorithm. We present a modified version to return the correct result with certainty without having user control over the quantum search oracle. Our deterministic, two-parameter "D2p" protocol utilizes generalized phase rotations replacing the phase inversions after a standard oracle query. The D2p protocol achieves a 100% success rate in no more than one additional iteration compared to the optimal number of steps as in the original Grover's search enabling the same quadratic speedup. We also provide a visualization using the Bloch sphere for enhanced geometric intuition.

Files

PhysRevResearch.4.L022013.pdf

Files (1.1 MB)

Name Size Download all
md5:40526bebdb27a5bf31268dcc3558623c
1.1 MB Preview Download

Additional details

Identifiers

DOI
10.1103/physrevresearch.4.l022013
Other
oai:uchicago.tind.io:11642

Funding

National Science Foundation
CCF-1730449
National Science Foundation
PHY-1653820
Air Force Office of Scientific Research
FA9550-21-1-0209
Army Research Office
W911NF-18-1-0125

UChicago Information

Division(s)
Physical Sciences Division, Pritzker School of Molecular Engineering
Department(s)
Physics
Center(s) or Institute(s)
James Franck Institute