Google Groups

When will quantum computers become practical?


Peter Shor Mar 22, 2000 12:00 AM
Posted in group: sci.physics.research
In article <2000032000...@csb.bu.edu>, Leonid Levin <l...@cs.bu.edu> writes:
|> In <FrFuA...@research.att.com>, Peter Shor <sh...@research.att.com> wrote:
|>
|>  > I think I've located the source of our philosophical differences.
|>  > The question is: what is a quantum state? I say it is a vector in
|>  > a high-dimensional Hilbert space (2^n dimensions for n qubits).
|>  > You say that it is a long list of coordinates. What's the difference?
|>
|> This is what I mean by QC folk sweeping too many things under the rug.
|> I am glad I enticed you there to talk dark philosophies in a dark place.
|>
|> In cryptography n may be a thousand bits (and could easily be millions.)
|> By ~n I will mean a reasonable power of n. The number of roughly
|> different vectors in 2^{~n} dimensional space H is 2^{2^{~n}}. Take a
|> random v \in H. The minimal size of a machine which can recognize or
|> generate v (approximately) is 2^{~n} -- far larger than our Universe.
|> (From a cardinality argument: 2^{~K} machines of K atoms.)
|>
|> So, only very special vectors v could be assigned any physical meaning.
|> You cannot take an equal-opportunity stance and reject preferred basis.

But this doesn't say anything about a preferred basis --- it says that
there are some preferred states.  Quantum mechanical machines can quickly
reach some very entangled states which aren't succinctly expressible in
terms of coordinates, and quantum mechanics makes very concrete predictions
about these states.  This is also not purely a quantum mechanical problem.  
There are many 1000-digit numbers that will never be written down (even though,
as opposed to the quantum mechanical situation, they actually could be).  
Are the rules of multiplication for these numbers different?

|>  > In a list of 2^n coordinates, each one is going to be very small.
|>  > There's a preferred basis---of whichever coordinates you choose to
|>  > write down the vector. The question then becomes: does the universe
|>  > treat quantum states as vectors or as lists of coordinates?
|>  > If this question even makes sense,
|>  > the only possible way to answer it is by experiment.
|>
|> As you see from my argument, this question cannot have an experimental
|> answer. This is why I think you can say anything you want about your
|> machine without compelling the physicists to take any stance about it.
|>  If it fails to factor, they would just shrug.
|>  If it, OTOH, succeeds, they would be bewildered.

Well ... only if they consider quantum mechanics to be talking about lists
of coordinates and not vectors.  If there are non-linearities in quantum
mechanics which are detectable by watching quantum computers fail, physicists
will be VERY interested (I would expect a Nobel prize for conclusive evidence
of this).  Of course, quantum computers could also fail for other reasons.  
In some other posts in this thread, John Baez has pointed out a gap in our
theory of quantum fault-tolerant computation having to do with how fast the
multi-term pieces in an error Hamiltonian go to zero.  I expect this will
eventually be resolved satisfactorily eventually, but if quantum computers fail
for this reason it won't be anywhere near as momentous.


Peter Shor