Technical Report MSC-2001-01

Title: Grover's Quantum Search Algorithm and Mixed States
Authors: Dan Kenigsberg (Eli Biham)
Abstract: Quantum computation is a field of computation theory that tries to find what can be computed, while taking into account the quantum nature of the physical world. The most celebrated achievement of quantum computation is Shor's algorithm, which factors large integers in polynomial time. Another achievement is Grover's unordered search algorithm, which finds a single ``marked'' element of a database in time which is in the order of the square root of the size of that database.

We commence the thesis with a brief introduction to that field of science. Then we present Grover's search algorithm, and a proof that it is the optimal search algorithm---it is better than any other algorithm, be it classical or quantum. The algorithm includes an initialization step and $O(\sqrt N)$ iterations of selective phase inversions and Hadamard transforms.

The parameters of the algorithm have been generalized by various authors. Some have generalized the Grover Iterate, and some have generalized the initial state of the algorithm. We present these generalizations and provide an analysis of each of them in a uniform method. Then we show and discuss the most general extension to the Grover Iterate.

We present a new generalization of the initial state of the algorithm, in which it is allowed to be an arbitrary mixed quantum state. We show that even when the initial state is extremely mixed, there are cases where Grover's algorithm performs very well. We provide an approximation to the von Neumann entropy of pseudo-pure states, and we find that it grows smoothly with the level of mixedness of the pseudo-pure state. Combined with the previous result about the good performance of Grover's algorithm, our finding is in disagreement with Bose et al. We give a simple counter-example to their claim that for states with entropy larger than $\frac12\log N$, Grover's algorithm is as bad as classical algorithms, and show where their mistake comes from.

We examine the usefulness of Grover's algorithm when initialized in a pseudo-pure state, and provide a measure for its effectiveness, including a threshold under which the algorithm is ineffective. We find that this threshold coincides with Braunstein et al.'s inseparability bound. This result may be considered as an evidence that entanglement is necessary for nontrivial quantum computation.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2001
To the main CS technical reports page

Computer science department, Technion