Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations

Abstract

The recursion equation analysis of Grover's quantum search algorithm presented by Biham et al. [PRA 60, 2742 (1999)] is generalized. It is applied to the large class of Grover's type algorithms in which the Hadamard transform is replaced by any other unitary transformation and the phase inversion is replaced by a rotation by an arbitrary angle. The time evolution of the amplitudes of the marked and unmarked states, for any initial complex amplitude distribution is expressed using first order linear difference equations. These equations are solved exactly. The solution provides the number of iterations T after which the probability of finding a marked state upon measurement is the highest, as well as the value of this probability, P_max. Both T and P_max are found to depend on the averages and variances of the initial amplitude distributions of the marked and unmarked states, but not on higher moments.

8 pages, no figures. To appear in Phys. Rev. A

References in corpus (11)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Grover's quantum searching algorithm is optimal
• Quantum computers can search rapidly by using almost any transformation
• Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer
• Grover's search algorithm: An optical approach
• Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
• Nested quantum search and NP-complete problems
• Arbitrary phase rotation of the marked state can not be used for Grover's quantum search algorithm
• Single quantum querying of a database
• Generalized Quantum Search with Parallelism

Cited by in corpus (28)

• Theory of Initialization-Free Decoherence-Free Subspaces and Subsystems
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
• Accuracy vs run time in adiabatic quantum search
• 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
• Coherence number as a discrete quantum resource
• What is a quantum computer, and how do we build one?
• Dynamic Grover Search: Applications in Recommendation systems and Optimization problems
• An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq
• On the role of dealing with quantum coherence in amplitude amplification
• A More General Quantum Searching Algorithm And the Precise Formula of the Amplitude and the Non-symmetric Effects of Different Rotating Angles
• Modularization of multi-qubit controlled phase gate and its NMR implementation
• Quantum heuristic algorithm for traveling salesman problem
• Quantum Discrete Cosine Transform for Image Compression
• Quantum Locker Using a Novel Verification Algorithm and Its Experimental Realization in IBM Quantum Computer
• Synthesizing NMR analogues of Einstein-Podolsky-Rosen states using generalized Grover's algorithm
• Analysis of Grover's quantum search algorithm as a dynamical system
• Fixed-point Quantum Search for Different Phase Shifts
• Algebraic analysis of quantum search with pure and mixed states
• The Precise Formula in a Sine Function Form of the norm of the Amplitude and the Necessary and Sufficient Phase Condition for Any Quantum Algorithm with Arbitrary Phase Rotations
• Amplitude Amplification for Optimization via Subdivided Phase Oracle
• Optimization of probabilistic quantum search algorithm with a priori information
• Quantifiable simulation of quantum computation beyond stochastic ensemble computation
• An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits
• Quantum search processes in the cyclic group state spaces
• Quasi-adiabatic Grover search via the WKB approximation
• Quantum Search Algorithm for Set Operation