Does Grover's algorithm actually search N unordered items in time O(N^(1/2)?

[Stephen Parrott]

Does Grover's algorithm actually search N unordered items in time
O(N^(1/2)?

   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
inscribes
the name of every species that he sees together with the date that he
sees
it.  He tells you that he has seen exactly one whooping crane (a very
rare
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
examine
N/2 items.

    [ 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
so,
that would imply that for practical purposes, Grover's quantum speedup
does
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
|1>, |2>, ... , |N>.

THE QUESTION:

    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
experiments),
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.

[Timothy Murphy]

Stephen Parrott wrote:

>
> THE QUESTION:
>
>     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
> experiments),
> 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.

I don't understand the details of Grover's algorithm,
but as far as I can see, if N = 2^r then each light is indexed
by r q-bits or coordinates, whose values correspond
to the state of the lights.
I don't think this setup is supposed to take any time.
There is no suggestion that the circuitry you suggest is needed,
or if it is needed the time to set it up does not count
as part of the algorithm.
I suppose the idea is that once you have set it up
it can be used many times.

An "oracle" is a unitary transformation of this r-dimensional space.
(The choice of unitary transformation is up to the algorithmist.)
The application of this transformation, or any unitary transformation,
counts as 1 step.
(In quantum theory a "measurement" corresponds to a unitary
transformation.)

I guess the same idea applies in the classical case.
Eg if you have n objects and want to split them into m subsets,
this is not supposed to take any time.

But I may have misunderstood the whole thing.

--
Timothy Murphy  
gayleard /at/ eircom.net
School of Mathematics, Trinity College, Dublin

[Daniel S. Riley]

Stephen Parrott <post...@email.toast.net> writes:
> 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".

I don't think that's quite correct... |1>...|N> is the state space
of the problem.  The computational basis comes from the projection
of the state space onto a particular orthonormal basis.  For Grover's
algorithm, the computational basis is the projection of the state
space onto a representation in log2(N) qubits.

>    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.

Just as 255 classical outcomes can be represented with only 8 bits, we
only need log2(N) lights.

> Even if we assume a generic measuring device with N lights (to be used
> for various experiments), wouldn't one expect to spend time O(N) to
> connect it to the Grover experiment? Why is this issue never
> discussed?

The idea is to have a generic quantum computer with the readout
part of the standard setup, so this strikes me as like asking why
classical complexity analysis never discuss how long it takes to
setup a Turing machine.

-dan

[Jeff Barnett]

I think it is a poor analogy. You "setup" a Turing machine once and
forever (in your mind) then bring tapes to it. The machine computes
whatever you expect and you read your answer off the tape. It's
complexity is measured by some function of the input tape length.

On the other hand, the quantum machine can't be setup until you know N
in order to determine log2(N) unless you assume that this machine has
an
unbounded number of qubits. The Turing tape, by definition, is
unbounded
and that assumption hides a bunch of magic. The assumptions about
quantum machines are not so precise today so questions about setup are
surely relevant.
--
Jeff Barnett

[stephenp...@gmail.com]

First of all, I should apologize for the delay in replying.  
The post was intended for sci.physics.research, but my mail program
completed the address for sci.math.research instead, and I didn't
notice.

I think you are right that a measurement with N outcomes only requires
time proportional to log_2 (N) (think of binary search), and so can be
ignored when discussing polynomial-time algorithms.

Thank you for your good answer!

Stephen Parrott