Analysis of Grover's quantum search algorithm as a dynamical system

Abstract

Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\varphi >$ of $n$ qubits. It is shown that the optimal time to perform the measurement is independent of $|\varphi >$, namely, it is identical to the optimal time in the original algorithm in which $|\varphi >=|0>$, with the same number of marked states, $r$. The probability of success $P_{\mathrm{s}}$ is obtained, in terms of the amplitudes of the state $|\varphi >$, and is shown to be independent of $r$. A class of states, which includes fixed points and cycles of the Grover iteration operator is identified. The relevance of these results in the context of using the success probability as an entanglement measure is discussed. In particular, the Groverian entanglement measure, previously limited to a single marked state, is generalized to the case of several marked states.

References in corpus (17)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantifying Entanglement
• Strengths and Weaknesses of Quantum Computing
• Tight bounds on quantum searching
• 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
• Quantum computers can search arbitrarily large databases by a single query
• 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
• Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
• An entanglement monotone derived from Grover's algorithm
• Arbitrary phase rotation of the marked state can not be used for Grover's quantum search algorithm
• Single quantum querying of a database
• Grover's Quantum Search Algorithm for an Arbitrary Initial Mixed State
• Generalized Quantum Search with Parallelism

Cited by in corpus (8)

• Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure
• Entangled Quantum States Generated by Shor's Factoring Algorithm
• The Groverian Measure of Entanglement for Mixed States
• Quantum Entanglement involved in Grover's and Shor's algorithms: the four-qubit case
• Formation of Multipartite Entanglement Using Random Quantum Gates
• Algebraic analysis of quantum search with pure and mixed states
• Coherence Fraction in Grover Search Algorithm
• Grover search algorithm