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.
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".
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?
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.
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
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 113 |
Nodes: | 8 (0 / 8) |
Uptime: | 175:02:52 |
Calls: | 2,506 |
Files: | 8,706 |
Messages: | 1,933,596 |