2 views

Skip to first unread message

Dec 16, 2002, 12:23:49 AM12/16/02

to

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.

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

Dec 18, 2002, 9:41:46 PM12/18/02

to

e...@fredkin.com (Ed Fredkin) wrote in message news:

> 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.

Dec 20, 2002, 7:36:10 PM12/20/02

to

e...@fredkin.com (Ed Fredkin) wrote in message news:<386d7a77.02121...@posting.google.com>...

> 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

Dec 21, 2002, 9:34:50 AM12/21/02

to

Ed Fredkin wrote:

> 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

Dec 21, 2002, 9:46:05 AM12/21/02

to

zir...@hotmail.com (zirkus) wrote in message news:<8c7d34cb.02121...@posting.google.com>...

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

Dec 21, 2002, 9:56:28 AM12/21/02

to

e...@fredkin.com (Ed Fredkin) wrote in message news:<386d7a77.02121...@posting.google.com>...

> Finally, many QC problems, such as

> factoring, are not known to be exponentially difficult.

>

This is a bit unfair to quantum computation. While it is true that

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.

> 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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu