Re: Turing machines, quantum computers, and alephs

From: Gerry Quinn (gerryq_at_DELETETHISindigo.ie)
Date: 03/20/05 

Date: Sun, 20 Mar 2005 10:23:08 -0000

In article <XbmdndgHdeQ5LaHfRVn-tw@forethought.net>, ThadSmith@acm.org
says...
> Gerry Quinn wrote:
>
> > The 'qubit-based' quantum computer works with a set of entangled quantum
> > states. Without going into detail, an n-qubit quantum computer can
> > theoretically conduct 2^n computations in parallel. That's a lot of
> > calculations - for a 300-qubit machine it exceeds the number of atoms in
> > the observable universe.
>
> That's an interesting model, but I doubt this it is something that will
> be physically realized. It's beyond my capability to talk of a
> "mechanism" for such a large qubit computer, but suspect that there are
> some fundamental limitations that prevent realization.

I doubt it myself. But right now I'm just interested in the math.

> > However, when we talk about abstract machines with infinite tapes, we
> > need to think about what we mean by 'infinity'. For the Turing machine
> > it is straightforward enough - we can place the positions on the tape in
> > one-to-one correspondence with the natural numbers. Call this infinity
> > Aleph-0. Since the tape head performs any number of sequential
> > operations, the number (if I may use the term) of operations the Turing
> > machine can perform is Aleph-0.
> >
> > For the machine corresponding to the abstract quantum computer, we have
> > Aleph-0 qubits.
>
> The Tuning machine is finite, except for the length of the tape. If you
> allow the number of possible states to grow arbitrarily, effectively
> implementing internal registers and arbitrary parallel processing
> between the internal states and input data, you can increase the
> parallelism of computation to a given factor, such that you are limited
> only by the I/O -- the number of steps required to read the data and
> write the result.

The qubit computer is finite, except for the number of qubits. But let
us grant the standard Turing machine some extra powers. We will allow
it Aleph-0 states, and allow it to choose between Aleph-0 characters on
each tape segment. As far as I can see, there is still no way that it
can perform Aleph-1 calculations. Increasing Aleph-0 by a factor, even
of Aleph-0, still leaves Aleph-0.

> How would the infinite number of internal states, supporting infinite
> parallelism, be different from a infinite number of working qubits?
> Couldn't both compute a finite decideable problem in a small finite
> number of steps?

Just like I've being saying, they are different infinities. It is
theorised that the quantum computer can in fact solve certain problems
with lower time-complexity than a Turing machine. [The reason it isn't
known is, I believe, simply that it tends to be impossible to prove that
there is no unknown algorithm that would reduce it on a Turing machine.]

My point is that the qubit-based quantum computer really does [if it
works!] do more than a Turing machine, and that this has not been
recognised because the difference between the relevant infinities has
not been recognised.
 
> Yes, the number of required states and possible transition equations
> grows (much) faster in the Turing machine than the number of qubits in a
> qubit machine. So what?

2^(Aleph-0) is not equal to Aleph-0. That's what.

> > But the number of calculations it can do in parallel is
> > 2^(Aleph-0), or Aleph-1.
> >
> > Conclusion: the Turing machine is not after all a valid abstract model
> > for the capabilities of a qubit-based quantum computer.
>
> Similarly restrict the qubit model machine to have a finite number of
> active elements (qubits), versus a corresponding, but larger, finite
> number of Turing internal states + rules and I don't see a fundamental
> difference.

The problem here is that you are slipping between 'formal' and
'practical' infinities. If you want to deal with formal infinities,
they are formally different. If you want to deal with practical
infinities, they are practically different. A 300-qubit machine can
perform more calculations than there are atoms in the observable
universe.

You are granting the abstract qubit machine a practical infinity while,
in effect, granting the Turing machine a formal infinity. This is
exactly what is wrong with the standard argument, IMO.

Whether we are talking in terms of practical or formal infinities, the
functions f(x)=x and f(x)=2^x don't rise to the same infinity.

Also, the number of qubits is not limited in theory. Yes, they are
'active' elements as distinct from 'memory' elements, but this is how a
quantum computer, as distinct from a Von Neumann style computer, is
supposed to work. The quantum computer doesn't use a long tape, it uses
lots of qubits.
  
- Gerry Quinn

Relevant Pages

  • Re: Turing machines, quantum computers, and alephs
    ... >> For the machine corresponding to the abstract quantum computer, ... except for the number of qubits. ... us grant the standard Turing machine some extra powers. ... they are different infinities. ...
    (sci.math)
  • Re: Turing machines, quantum computers, and alephs
    ... an n-qubit quantum computer can ... For the Turing machine ... How would the infinite number of internal states, ... be different from a infinite number of working qubits? ...
    (sci.math)
  • Re: Turing machines, quantum computers, and alephs
    ... an n-qubit quantum computer can ... For the Turing machine ... How would the infinite number of internal states, ... be different from a infinite number of working qubits? ...
    (comp.programming)
  • Turing machines, quantum computers, and alephs
    ... The 'qubit-based' quantum computer works with a set of entangled quantum ... Conventional wisdom is that the Turing machine remains an appropriate ... However, when we talk about abstract machines with infinite tapes, we ... need to think about what we mean by 'infinity'. ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... an n-qubit quantum computer can ... > Conventional wisdom is that the Turing machine remains an appropriate ... Since we're talking about abstract machines, ... > need to think about what we mean by 'infinity'. ...
    (comp.programming)