Grover's Quantum Search Algorithm for an Arbitrary Initial Mixed State

Abstract

The Grover quantum search algorithm is generalized to deal with an arbitrary mixed initial state. The probability to measure a marked state as a function of time is calculated, and found to depend strongly on the specific initial state. The form of the function, though, remains as it is in the case of initial pure state. We study the role of the von Neumann entropy of the initial state, and show that the entropy cannot be a measure for the usefulness of the algorithm. We give few examples and show that for some extremely mixed initial states carrying high entropy, the generalized Grover algorithm is considerably faster than any classical algorithm.

4 pages. See http://www.cs.technion.ac.il/~danken/MSc-thesis.pdf for extended discussion

References in corpus (9)

• Quantum Mechanics helps in searching for a needle in a haystack
• Tight bounds on quantum searching
• Quantum computers can search rapidly by using almost any transformation
• On Arbitrary Phases in Quantum Amplitude Amplification
• Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
• Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
• Communication Capacity of Quantum Computation
• Generalized Quantum Search with Parallelism
• General Phase Matching Condition for Quantum Searching

Cited by in corpus (22)

• Theory of Initialization-Free Decoherence-Free Subspaces and Subsystems
• The elusive source of quantum effectiveness
• Coherence number as a discrete quantum resource
• Quantum Searching via Entanglement and Partial Diffusion
• On the role of dealing with quantum coherence in amplitude amplification
• The Degree of Quantum Correlation Required to Speed-Up a Computation
• Strength and Weakness in Grover's Quantum Search Algorithm
• Analysis of Grover's quantum search algorithm as a dynamical system
• Quantum Locker Using a Novel Verification Algorithm and Its Experimental Realization in IBM Quantum Computer
• Complementarity between Success Probability and Coherence in Grover Search Algorithm
• Algebraic analysis of quantum search with pure and mixed states
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
• Fixed Phase Quantum Search Algorithm
• Quantum search degeneration under amplitude noise in queries to the oracle
• A classical limit of Grover's algorithm induced by dephasing: Coherence vs entanglement
• Microstate Distinguishability, Quantum Complexity, and the Eigenstate Thermalization Hypothesis
• Noise resilience and entanglement evolution in two non-equivalent classes of quantum algorithms
• Invariance of success probability in Grover's quantum search under local noise with memory
• Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine
• Constant-Time Quantum Algorithm For The Unstructured Search Problem
• Exact Solvability Of Entanglement For Arbitrary Initial State in an Infinite-Range Floquet System
• Performance of Grover's search algorithm with diagonalizable collective noises