Does Grover's algorithm actually search N unordered items in time O(N^(
From Stephen Parrott@21:1/5 to All on Sat Aug 6 08:53:32 2016
Does Grover's algorithm actually search N unordered items in time
This post asks the above question about the famous Grover algorithm.
To establish notation and point of view, I first briefly describe
the problem which this algorithm addresses. Anybody who has a chance
of answering the question will already be familiar with this and may
want to skip to "THE QUESTION" below.
The version of Grover's problem which I shall address goes as
follows. Suppose some birdwatcher keeps a notebook in which he
the name of every species that he sees together with the date that he
it. He tells you that he has seen exactly one whooping crane (a very
bird with a world population in the dozens at one time) in his life.
To verify his claim you ask to inspect his notebook, which contains N
entries. Classically, the time taken to go through the notebook would
be on the order of N, O(N), because in the worst case the whooping crane
might be the last item examined, and on average, one would have to
[ Here for expository simplicity I am employing a common
physicists' abuse of the mathematical O(N) notation;
instead of O(N) I actually mean "theta(N)", meaning that
for some positive constants c and C, the time is lower-bounded
by cN and upper-bounded by CN. ]
Translated into more mathematical notation, the notebook entries
are labeled 1,2, ... , N, and we are given a function f such that
f(k) = 0 if the k'th entry is not "whooping crane" and 1 if it is.
The function f is called an "oracle". We are allowed to consult the
oracle whenever we want, but each oracle consultation entails a certain
cost in time. Thus for a for a "classical" oracle f as just described,
the total cost is O(N).
For a search using quantum mechanics, the labels 1,2, ... , N
for the entries are replaced by an orthonormal basis of
kets |1>, |2>, ... , |N>, known as the "computational basis".
There is a corresponding (somewhat vague) notion of a "quantum oracle"
U (depending on f) which assigns to each ket |k>, a quantum state
(which is not necessarily one of the basis kets). Moreover, the oracle
assigns to an arbitrary state s (not necessarily a basis ket) a state
Us, and the map s ---> Us is assumed unitary.
Grovers algorithm locates the whooping crane with a
preassigned probability arbitrarily close to 1 using
only O(N^(1/2)) quantum oracle calls, which is a substantial improvement
over the classical O(N).
The total time taken by Grover's algorithm depends not just on
the number of oracle calls, but also on several other things. The other
things which are discussed in books and papers which I have seen are all
no faster than O(N^(1/2)).
` However, there is one final step of Grover's algorithm whose speed
I have never seen discussed and which seems to me ought to be O(N). If
that would imply that for practical purposes, Grover's quantum speedup
not improve on the classical O(N).
The last step of Grover's algorithm is to perform a projective
measurement in the computational basis. This measurement has N possible outcomes corresponding to the one-dimensional projectors on the kets
, |2>, ... , |N>.
How can one expect to perform a measurement with N possible outcomes
in time less than O(N)?
To elaborate, in the laboratory such a measurement might be
implemented with N lights connected to appropriate circuitry. It seems
that to set up N lights must require O(N) time. Even if we assume a
generic measuring device with N lights (to be used for various
wouldn't one expect to spend time O(N) to connect it to
the Grover experiment? Why is this issue never discussed?
Grover's algorithm is very clever, and certainly of great
theoretical interest. But I wonder if it is realistic to hope that
an unstructured database like the birds can actually be searched in
time O(N^(1/2)), even using quantum technology.