Re: limit speed of computation - Digital vs. Quantum
From: Kent Paul Dolan (xanthian_at_well.com)
Date: 10/13/04
- Next message: Kent Paul Dolan: "Re: limit speed of computation - Digital vs. Quantum"
- Previous message: Mark \(The WannaBe\): "pumping lemma (second try)"
- Maybe in reply to: Kent Paul Dolan: "Re: limit speed of computation - Digital vs. Quantum"
- Next in thread: Kent Paul Dolan: "Re: limit speed of computation - Digital vs. Quantum"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Wed, 13 Oct 2004 20:09:30 +0000 (UTC)
"Tim Tyler" <tim@tt1lock.org> wrote:
> Kent Paul Dolan <xanthian@well.com> wrote or
> quoted:
>> When considering quantum computation, we are
>> talking about a real device in the physical
>> universe, so to compare a CA to it, you must
>> follow the same rules.
> If the universe is a CA, that would not be a
> problem.
But there is no evidence that such is the case,
merely unsubstantiated speculation with no
predictive value or record of accomplishment.
That make "the universe is a CA" an unacceptable
assumption for any discussion about *real world*
limits to *real world* computation, which again is
what we are discussing when we discuss quantum
computing, and what we must also discuss when we
compare quantum computing's potential real world
speed to cellular automata computing's potential
real world speed.
>> You can't just toss in "infinite size" without
>> paying the consequence. [...]
> Infinity was invoked in response to Paul's question:
> ``I would still like to see a design (even in
> principle) of a CA (or some other discrete,
> digital system) which can perform Shor's algorithm
> as efficiently as a QC, and *scales appropriately
> to all magnitudes*.''
> To "scale appropriately to all magnitudes" *any*
> candidate system has *got* to be infinite.
Well, no, you have just fallen into a well-populated
trap, one imported whole from many muddled
discussions in comp.theory. Every attemptable
"magnitude" of computation (for integer factoring,
the original topic of discussion) _is_ "finite"
(there is no such thing as "factoring an infinite
integer", or at least I sincerely hope there isn't),
so every scaling needed to accommodate such a
magnitude is _also_ "finite".
We are merely not able to _bound_ the solution
resources *in advance of choosing the problem*,
a truism for human computation since at least the
invention of the abacus, which is *no reason
whatever* to make the bound "infinity" *in advance*.
We're merely trying to contrast polynomial scaling
with exponential scaling for problems *limited to
the finite integers*, not the infinite limit of such
problems, which fails to be of any interest in this
case.
> With quantum computing, gathering the solutions
> together doesn't take long - because they never
> get very distant from one another in the first
> place. That's because of the huge number of
> dimensions involved in the Hilbert space where the
> wavefunction evolves - e.g.:
> "Also, the number of dimensions needed in this
> abstract space corresponds to the number of
> choices available for the quantum system, and
> this, as we have just seen, can go to infinity."
> - http://www.qedcorp.com/pcr/pcr/hilberts.html
That is a _mathematical_ space, a convenient human
construct in which calculations can be easily
performed, a mere _tool_, much like Fineman's
renormalized infinities in quantum chromodynamics.
Don't confound it with being a description of the
physical universe: you can't get in your car and
go for a drive in Hilbert space, and most likely you
won't find real singularities inside electrons,
merely human comprehension failures.
> If a CA has to exist in a more limited space - and
> the results had to be returned to one spot in that
> space, that *would* be time consuming - but since
> the number of dimensions in the QC case was not so
> constrained, it would not be fair to claim that
> the quantum case does something that a CA can't -
> since a CA can do *exactly* the same thing - if it
> has the same number of dimensions available to
> work in.
But the CA *in the physical universe* does _not_
have access to any such infinitely dimensioned
space. That infinite dimensioned mathematical
conceptual space for quantum mechanics is specific
to QC.
It is not some generally available resource usable
by macrophysical CAs due to human concepts of the
"fairness" of life.
The physical universe, in all accepted theories of
physics, is very much finite dimensional, whether
one accepts the string theory alternatives of 10,
11, or 26 dimensions, or some more obscure
alternative:
http://prola.aps.org/abstract/PRD/v31/i2/p262_1
You need to abandon muddle-minded New Age thinking
when discussing mundane reality, to retain any hope
of being taken seriously. Again, throwing in
"infinity" so casually has _real consequences_, and
in particular, doing so makes your argument in this
case a false one (which, so far as I can see, it was
anyway).
> It should be quite possible to build such CAs [in]
> the real world. That's because quantum physics
> shows that our world is *not* three dimensional -
> instead we live in a quantum universe - which is
> better characterised by Hilbert spaces and quantum
> physics.
Nope.
That universe is available *at the quantum level*,
*as a mathematical construct*, but if you try to
take advantage of it in building your real world
cellular automaton, you've now trapped yourself in a
distinction without a difference: your CA only does
what you claim it does because you have _converted_
it _to_ a QC.
FWIW
xanthian.
-- Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
- Next message: Kent Paul Dolan: "Re: limit speed of computation - Digital vs. Quantum"
- Previous message: Mark \(The WannaBe\): "pumping lemma (second try)"
- Maybe in reply to: Kent Paul Dolan: "Re: limit speed of computation - Digital vs. Quantum"
- Next in thread: Kent Paul Dolan: "Re: limit speed of computation - Digital vs. Quantum"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
|
