Deterministic Grover search with a restricted oracle

Abstract

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 in the original Grover's search enabling the same quadratic speed up. We also provide a visualization using the Bloch sphere for enhanced geometric intuition.

6 pages, 4 figures

References in corpus (5)

• Quantum random access memory
• Architectures for a quantum random access memory
• Fixed-point quantum search with an optimal number of queries
• Multi-phase matching in the Grover algorithm
• Quantum Amplitude Amplification Operators

Cited by in corpus (12)

• Deterministic quantum search with adjustable parameters: implementations and applications
• Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations
• Performance analysis of a hybrid agent for quantum-accessible reinforcement learning
• Characterization, synthesis, and optimization of quantum circuits over multiple-control $\text{Z}$-rotation gates: A systematic study
• Optimization of probabilistic quantum search algorithm with a priori information
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• Near-deterministic quantum search algorithm without phase design
• Derandomization of quantum algorithm for triangle finding
• Grover's search meets Ising models: a quantum algorithm for finding low-energy states
• Deterministic carving of quantum states with Grover's algorithm
• Complex-Phase Extensions of Szegedy Quantum Walk on Graphs
• Quantum algorithm for unstructured search of ranked targets