Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

72 views

Skip to first unread message

Aug 6, 2016, 10:53:34 AM8/6/16

to

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.

Aug 7, 2016, 8:00:58 AM8/7/16

to

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

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

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

Aug 7, 2016, 9:30:58 PM8/7/16

to

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

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.

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?

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

Aug 9, 2016, 8:09:22 AM8/9/16

to

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

Aug 21, 2016, 3:07:31 PM8/21/16

to

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

0 new messages

Search

Clear search

Close search

Google apps

Main menu