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

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

Stephen Parrott <postnews@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

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

Daniel S. Riley <dsr@mail.lns.cornell.edu> wrote:

Stephen Parrott <postnews@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.

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

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

On Sunday, August 7, 2016 at 6:30:58 PM UTC-7, Daniel S. Riley wrote:

Stephen Parrott <postnews@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

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

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