Quantum Computation vs CA Models of Physics
Ed Fredkin
is clear and easy to understand. The possibility that physics will
allow for the construction of such a computer, so that it out computes
conventional computers is an experimental question where the results
have not yet been established. Finally, many QC problems, such as
factoring, are not known to be exponentially difficult.
The use of the supposed capabilities of a QC as a counter argument
against discrete, spatially simple models of physics does not make a
lot of sense at this time. If the builders of QC are successful, and
1,000 digit numbers are then easily factored and we finally have a
mathematical proof that factoring is exponentially difficult; then and
only then may one declare that QC demonstrates that simple CA's cannot
be good models of fundamental processes in physics.
In some sense, the progress of CA models, in terms of the amount of
physical properties that can be simultaneously represented, has been
amazing. Problems that have to do with the anisotropy of the cellular
space simply evaporate if the CA model can exactly conserve the
quantities of angular and linear momentum; an easy task. In fact every
symmetry of physics can be a gross characteristic of a Cartesian
Lattice based CA, if all of the corresponding conserved quantities
(related by Noether's Theorem) are exactly conserved.
The ace in the hole, for CA models, is computational universality
along with processes that exactly conserve quantities of physics. It's
not that any universal CA should satisfy us; rather it's that
universality implies that all difficulties may be surmountable in ways
that make sense. To date, that promise has been holding true.
The progress of CA models has been a torturous task comparable to the
early progress of QM, but the effort put into developing these models
is microscopic compared to the effort that went into QM during the
last 100 years.
If you look at all the papers published by all the great workers in
QM, there are very, very few that can be seen as entirely correct from
today's perspective. That's the nature of making progress in physics;
100 steps forwards, 99 steps backwards and we keep making progress. Of
course all of the current CA models of physics have fatal flaws, but
there is no doubt that progress keeps being made.
It is unfair to compare the state of CA models with the state of the
Standard Model, rather one ought to take the perspective of comparing
the progress of CA models with the original historical progress of QM.
Finally, CA models give us the possibility of rational answers to
questions that are not dealt with in conventional models of physics.
Physics has had to turn a blind eye to these questions. Examples
include the lack of a process model for Newtonian Mechanics (inertia
and gravitation), the origin of length, the exact nature of time,
where all the constants come from, the fact that we should be able to
understand QM while nobody does; and a very big etc.
Ed F
zirkus
> It is unfair to compare the state of CA models with the state of the
> Standard Model, rather one ought to take the perspective of comparing
> the progress of CA models with the original historical progress of QM.
There is a big difference between the SM and QM vs. CAs. Both the SM
and QM are quasi-elegant theories which have made plenty of physical
predictions which were then confirmed by experiments.
During the 1970s, three different experiments indicated that the SM
was wrong, but the theorists persisted because they felt that they had
an elegant and powerful theory. Later, it was revealed that the
experiments had actually been in error, and thus the SM is an example
of a robust theory. However, CAs have not made any meaningful
predictions about physical reality, whereas QM did almost from the
start and the double-slit experiment is one of the greatest
experiments ever in the history of science. Perhaps CAs will be useful
for helping to elucidate various phenomena, but I am quite skeptical
about the prospects of CAs being some kind of fundamental model.
Peter Shor
> We all recognize that the mathematical concept of a Quantum Computer
> is clear and easy to understand. The possibility that physics will
> allow for the construction of such a computer, so that it out computes
> conventional computers is an experimental question where the results
> have not yet been established. Finally, many QC problems, such as
> factoring, are not known to be exponentially difficult.
I agree that factoring and other QC-solvable problems are not
known to be exponentially difficult. In fact, one prominent number
theorists expects factoring eventually to be shown polynomial-time
computable on a digital computer. However, you can't escape the
weirdness of quantum mechanics quite so easily.
Complexity theorists have looked at the class of languages which
can be probabilistically proved with a constant nomber of rounds
of interaction. In the classical case, this is AM, which is
contained in Pi_2(P), and so in the second level of the polynomial
hierarchy. In the quantum case (where the prover and provee pass
quantum states back and forth), this is QIP(3), which contains
PSPACE. If AM=QIP(3), the polynomial hierarchy collapses. While
it hasn't been proved this doesn't happen, most theoretical
computer scientists think it quite unlikely.
If physics can be simulated by a CA, you either have to explain
why AM isn't QIP(3), or accept the polynomial hierarchy collapsing.
For more complexity classes, see
http://www.cs.berkeley.edu/~aaronson/zoo.html
Peter Shor
Ralph Hartley
> The use of the supposed capabilities of a QC as a counter argument
> against discrete, spatially simple models of physics does not make a
> lot of sense at this time.
Then let me try to describe the argment a little more clearly. It doesn't
depend on the practicality of QC. Nor on the complexity of "practical"
applications of QC, such as factoring.
The point is that if there are *any* problems that are exponential for a
classical computer but polynomial for a quantum one (i.e. if BPP!=BQP),
then there are quantum systems that cannot be efficiently simulated by
*any* classical system.
> If the builders of QC are successful
If BPP!=BQP then it is sufficient that the universe *permits* QC (or any
classically exponential quantum proccess, a slightly weaker requirement),
not that we can implement it. Of course, building one would be pretty final
proof that it is possible. Short of Quantum theory being wrong, it is hard
to see how it could be impossible in principle, though it could remain far
beyond our reach.
> 1,000 digit numbers are then easily factored and we finally have a
> mathematical proof that factoring is exponentially difficult;
You require a proof that P!=NP ?! Factoring is in NP, so prooving it
exponential would prove P!=NP.
Since CAs can only be good models if BPP=BQP, then there isn't much point
in considering them until there is *some* reason to suspect that this is
true. It is considered very unlikely, though a proof either way is not
expected soon. The proof methods of complexity theory don't get much
traction on the problem.
> then and
> only then may one declare that QC demonstrates that simple CA's cannot
> be good models of fundamental processes in physics.
I think you are misplacing the burden of proof a bit here. There are far
more bad models than good ones. You need to show that CA's *can* be good
models. Since I have good reason to doubt that you can prove BPP=BQP, I
doubt you can do that.
> The ace in the hole, for CA models, is computational universality
This might be a good argument if computational universality were rare, but
it is not. You can't swing a |dead>+|alive> cat without hiting something
computationally universal.
At the level at which computatioanl universality is an "ace in the hole"
all universal models are equivalent, since they can all simulate each
other. It's more like "an ace up the sleeve".
Actually, it *is* important that a model be computationally universal.
Since the universe does appear to permit computation, any model that lacks
universality can be pretty much ruled out. Since all reasonable models (and
many unreasonable ones) are at least universal, something more is required.
> it's that
> universality implies that all difficulties may be surmountable in ways
> that make sense. To date, that promise has been holding true.
Has it? Show me a classical CA model in which:
1) Bell's inequalities are always violated, in the way quantum theory predicts.
2) The experimenters are permitted to use computers as part of their
experimental set up. The computers they use may be objects within the model
or not, but the experimenters must be permitted to run arbitrary programs.
3) There is locality, at least to the extent that the experimenters cannot
transmit information instantainiously.
4) There is some kind of correspondance between the locality experienced by
the experimenters and the locality of the CA. This is intended to rule out
a computer in the CA simulating some other model, since that is something
that *any* model can do. Some aspect of the CA must be observable to the
experimenters, at least in principle.
In place of actually exhibiting such a CA, I would accept (or even preffer)
a proof, or even a good argument, that it is possible.
Ralph Hartley
Ed Fredkin
CA models make all kinds of interesting predictions, but there is so
much already known that it is difficult for an infant theory to make
lots of new predictions. Nevertheless, CA models predict that every
continuous symmetry of nature will be violated. I have suggested
experimental tests to detect the violation of rotation symmetry.
These test require no new experiments, one merely needs to look at the
kinds of data one gets from BABAR, jets from LEP, or other similar
data, and do a coordinate transformation on the data, from laboratory
angular information to Right Ascension and Declination (plotting
angles relative to the "fixed stars"). There is reason to believe
that as the energy goes higher the angular resolution needed to
detect violation would be less. The rotation of the Earth and the
complex motion through space of every laboratory, can easily mask such
microscopic violations; a possible reason why no such violations have
been noticed. Of course, another reason is that no one has been
looking for them. And then the final reason, perhaps these violations
don't exist.
CA models also have the power to explain many things that SM and QM
can't deal with, but that only becomes interesting if physics is, in
fact, totally discrete (space and time discrete and the state at a
space-time point having only a few states.) Of course there are other
possible discrete models that are not really CAs.
Ed F
Dave Bacon
> Finally, many QC problems, such as
> factoring, are not known to be exponentially difficult.
>
factoring is not known to lie outside of P, to say that quantum
computers have not been proven to be more efficient at solving certain
problems is a disservice to a lot of good quantum computing research.
For example, consider the setting of communication complexity. In
communication complexity n parties are each given an input x_i to some
function f(x_1,...,x_n). These parties would each like to compute f,
but not knowing the other parties input to f, they have to communicate
to compute f. One can then ask how much one needs to communicate to
compute f. It turns out (in a rather robust form as demonstrated by
Ran Raz) that there are classes of functions f for which you can
provably show that if the parties use classical communication (bits)
they have to communicate exponentially more (in a parameter measuring
the size of the parties inputs) than if the parties had used quantum
communication (qubits) or used preshared quantum entanglement and
classical communication.
Another example, is to consider, so called oracle models. Here one is
given access to a black box to which one can submit queries (about
some problem, say) and recieve answers from this blackbox. Then one
can ask how many times you need to query the black box to solve some
problem. As above, within this model, if one uses quantum queries to
this black box you can rigorously show that you need an exponential
less number of queries (in the natural size of the problem you are
solving) than if you used classical queries. For example, it has been
shown by Richard Cleve that if one queries the black box used in
Shor's factoring algorithm, you will classically need an exponential
number of queries (in Log N , where N is the size of the number you
are factoring.)
So, while it is true that we do not know that factoring is outside of
P, we do know that quantum computers ARE much better at certain tasks
than classical computers.
dabacon