Turing machines, quantum computers, and alephs

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

Date: Sat, 19 Mar 2005 11:32:53 -0000

This is something that came up on a related thread, but I think it is
interesting enough to have a thread to itself.

The Church-Turing thesis, i.e. "Every 'function which would naturally be
regarded as computable' can be computed by a Turing machine." is
generally regarded as defining the limits of computation. And a Turing
machine consists of an infinite linear tape on which a read-write head,
capable of a finite number of states, moves step by step, reading one of
a finite number of symbols, writing one of them, changing to a
particular state based on what it read and it's current state, and
moving in one of two directions or stopping. It is an abstract machine
that is a good model for electronic computers.

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.

Conventional wisdom is that the Turing machine remains an appropriate
model for the abstract limit of what a quantum computer is capable of.
The reasoning is that, no matter how many computations it can do, it is
still a finite number, and an ordinary machine could do that many if it
took enough time. Since we're talking about abstract machines, we don't
care about physical limits such as the size of the universe.

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

The two functions f(x)=x and f(x)=2^x both reach any finite value of
f(x). But they don't rise towards the same infinity.

Comments?

- Gerry Quinn

Relevant Pages

  • 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)
  • 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'. ...
    (sci.math)
  • 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'. ...
    (sci.math)
  • Re: Turing machines, quantum computers, and alephs
    ... > machine consists of an infinite linear tape on which a read-write head, ... an n-qubit quantum computer can ... > Conventional wisdom is that the Turing machine remains an appropriate ... Since we're talking about abstract machines, ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... > machine consists of an infinite linear tape on which a read-write head, ... an n-qubit quantum computer can ... > Conventional wisdom is that the Turing machine remains an appropriate ... Since we're talking about abstract machines, ...
    (sci.math)