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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)