John Baez Opinion's about Quantum Cellular Automata:

[spr] Quantum cellular automata
John Baez baez@galaxy.ucr.edu
Fri, 11 Oct 2002 17:42:39 +0000 (UTC)
Previous message: [spr] Re: Bell's theorem and Universe as a CA idea
Next message: [spr] Re: Bell's theorem and Universe as a CA idea
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]


In article ,

Greg Kuperberg wrote:

>>[Moderator's note: the problem is not so much "morals" as that
>>nobody has described how modelling the universe as a CA is supposed
>>to get around the fundamental indeterminacy of QM while still
>>agreeing with experiment. - jb]
>I don't know why people keep overlooking the notion of a quantum
>cellular automaton.

Some people do, but lots of people don't... and certainly not me!

The reason why I made the above remark was that we were talking
about attempts to model the world as an ordinary *classical*
cellular automaton. There are people who really want to do this,
and who scorn the thought of resorting to a *quantum* cellular automaton.
These people are even somewhat influential - though more
among computer scientists and hobbyists than among physicists.
The main two are Ed Fredkin and Stephen Wolfram.
There are two obvious difficulties that any attempt to
model the world as a cellular automaton must overcome:
The first is Bell's theorem. The second is the fact that
a lattice lacks symmetry under rotations and Lorentz boosts.
To get around the first problem one can use a quantum cellular
automaton. However, some people regard this as cheating.

In his book "A New Kind of Science", Wolfram attempts to get
around this problem while still working with classical
cellular automata. I don't really understand this attempt.
To get around the second problem, one can invent cellular automata
that exhibit *approximate* rotation and Lorentz symmetry, at least
when viewed at large length scales. This is another subject,
which I won't talk about here.

So, who invented the idea of a quantum cellular automaton?

Feynman's "quantum checkerboard" model of spinors in 2d spacetime,
dating back at least to 1965, is a nice *example* of a quantum
cellular automaton:

R. Feynman and A. Hibbs, Quantum Mechanics and Path Integrals,
McGraw-Hill, 1965.

In 1980 Benioff showed you could simulate a *classical* Turing
machine using quantum mechanics:

P. Benioff, "The Computer as a Physical System: A Microscopic Quantum
Mechanical Hamiltonian Model of Computers as Represented by Turing
Machines," Journal of Statistical Physics, Vol. 22 (1980), pp. 563-591.
and in 1982 Feynman showed that classical Turing machines can't
simulate quantum systems without an exponential slowdown:
Richard Feynman, "Simulating Physics with Computers," Optics News
Vol. 11 (1982), pp. 467-488.

But when did people first say the words "quantum cellular automaton"?
Deutsch invented "quantum circuits" around 1989:

D. Deutsch, Quantum computational networks, Proc. Roy. Soc. London
Ser. A, 425 (1989), pp. 73-90.
Norm Margolus certainly was speaking about quantum cellular
automata in this 1990 paper:

N. Margolus, Parallel quantum computation, in W. H. Zurek, ed.,
Complexity, Entropy, and the Physics of Information, vol. VIII,
pp. 273-87, Addison-Wesley, 1990, also available as

http://citeseer.nj.nec.com/margolus91parallel.html

But I don't see the actual phrase "quantum cellular
automaton" in here!

Oh well... it doesn't really matter who first uttered the
phrase. The important thing is that people have been studying
quantum cellular automaton for quite a while now. This thesis
is a nice introduction to the subject:
Wim van Dam, Quantum cellular automata, Master's Thesis,
University of Nijmegen, Netherlands, 1996,

http://citeseer.nj.nec.com/vandam96quantum.html

and it also describes a universal quantum cellular automaton,
which simulates any other with only a linear slowdown.
Here's a nice website on quantum cellular automata, with an
emphasis on how you might actually build them with quantum dots:

http://www.nd.edu/~qcahome/

Both these have a bunch of references to other papers.

>If you want to connect physics to CAs, why not also
>connect physics to QCAs?

Indeed! To quote the master:

"I'm not happy with all the analyses that go with just
the classical theory, because nature isn't classical, dammit!"
- Richard Feynman, "Simulating Physics with Computers"