Generalized Quantum Search with Parallelism

Abstract

We generalize Grover's unstructured quantum search algorithm to enable it to use an arbitrary starting superposition and an arbitrary unitary matrix simultaneously. We derive an exact formula for the probability of the generalized Grover's algorithm succeeding after n iterations. We show that the fully generalized formula reduces to the special cases considered by previous authors. We then use the generalized formula to determine the optimal strategy for using the unstructured quantum search algorithm. On average the optimal strategy is about 12% better than the naive use of Grover's algorithm. The speedup obtained is not dramatic but it illustrates that a hybrid use of quantum computing and classical computing techniques can yield a performance that is better than either alone. We extend the analysis to the case of a society of k quantum searches acting in parallel. We derive an analytic formula that connects the degree of parallelism with the optimal strategy for k-parallel quantum search. We then derive the formula for the expected speed of k-parallel quantum search.

14 pages, 2 figures

References in corpus (10)

• Grover's quantum searching algorithm is optimal
• Quantum computers can search rapidly by using almost any transformation
• Experimental realization of a quantum algorithm
• Experimental Quantum Error Correction
• Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer
• Nuclear magnetic resonance spectroscopy: An experimentally accessible paradigm for quantum computing
• Optical Simulation of Quantum Logic
• Quantum Counting
• Nested quantum search and NP-complete problems
• How fast can a quantum computer search?

Cited by in corpus (22)

• Quantum attacks on Bitcoin, and how to protect against them
• Parallel Quantum Computing in a Single Ensemble Quantum Computer
• Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
• Depth optimization of quantum search algorithms beyond Grover's algorithm
• The effect of unitary noise on Grover's quantum search algorithm
• Grover's Quantum Search Algorithm for an Arbitrary Initial Mixed State
• Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure
• Implementation of efficient quantum search algorithms on NISQ computers
• Coherence number as a discrete quantum resource
• Quantum search on noisy intermediate-scale quantum devices
• Analysis of Grover's quantum search algorithm as a dynamical system
• Synthesizing NMR analogues of Einstein-Podolsky-Rosen states using generalized Grover's algorithm
• Algebraic analysis of quantum search with pure and mixed states
• Parallel Quantum Algorithm for Hamiltonian Simulation
• A family of sure-success quantum algorithms for solving a generalized Grover search problem
• Error Avoiding Quantum Codes and Dynamical Stabilization of Grover's Algorithm
• Single-Step Quantum Search Using Problem Structure
• Simulation of static and random errors on Grover's search algorithm implemented in a Ising nuclear spin chain quantum computer with few qubits
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• $\mathcal{P}\mathcal{T}$-symmetric mapping of three states and its implementation on a cloud quantum processor
• Asymptotic bounds on quantum partial search algorithm and its applications to parallel search
• An intrinsic limitation on the size of quantum database