Re: Turing machines, quantum computers, and alephs

From: Thad Smith (ThadSmith_at_acm.org)
Date: 03/20/05 

Date: Sat, 19 Mar 2005 18:15:44 -0700

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.

That reminds me of a computer model that can represent real values with
arbitrary precision and do elemental operations in unit time -- an ideal
analog computer. Physical analog computers have limits based on noise
and the uncertainty principle that prevent realizing more than a few
decimal digits of precision.

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

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?

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?

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

Thad

Relevant Pages

  • 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)
  • 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. ...
    (comp.programming)
  • 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)
  • First programmable quantum computer created
    ... researchers have built the first programmable quantum computer. ... beryllium ions chilled to just above absolute zero. ... Hanneke and colleagues programmed the computer to do operations on a ... Both of the qubits together could be entangled, ...
    (soc.culture.zimbabwe)
  • Re: How long would it take a computer to completely "solve" chess?
    ... |Try calculating how many qubits it would take instead of calculating ... a big speed-up from using some clever algorithm on a classical ... The kind of tree search one needs to do generally requires ... a quantum computer can search N2 items in T time. ...
    (sci.math)