Re: Quantum Computer Algorithms

From: Patrick Powers (frisbieinstein_at_yahoo.com)
Date: 09/24/04 

Date: Fri, 24 Sep 2004 13:14:09 +0000 (UTC)

David Tweed <dtweed@inf.ed.ac.uk> wrote in message news:<Pine.LNX.4.44.0409221833350.8694-100000@slim.inf.ed.ac.uk>...
> However, David Deutsch (one of the pioneers of QC) has a neat line about
> how when building the Turing machine model "Turing thought he understood
> the physics of marks on tape works".

I don't agree.

Computations proved by Turing to be impossible would still be
impossible on a quantum computer because solution brings
contradiction.

The sort of computations that a quantum computer is meant for are
those believed to be in NP. An informal definition is a puzzle that
is too expensive to solve, but the solution if known can be verified
easily. The classic example is factoring certain composite numbers.

Turing did consider such problems. In his terminology, these can be
solved by a "nondeterministic computation." This confusing term means
that while searching for a solution somehow the correct choice is
always made. If you think about it, you will see that this is very
much the same as the definition of NP.

So now we have uncomputable problems, which cannot be solved, and NP
problems, which a quantum computer could do. There are classes of
problems in between, solvable but not by a quantum computer.
Typically these are competitive games: since there is a competitor
with free will, there is no effective way to verify a purported best
strategy. So, harder than NP.

Relevant Pages

  • Re: Quantum Computer Algorithms
    ... |> how when building the Turing machine model "Turing thought he ... differs between classical and quantum algorithms. ... GIVEN THAT you can do these things in the physical world (physics) ... |The sort of computations that a quantum computer is meant for are ...
    (sci.physics.research)
  • Re: Quantum Computer Algorithms
    ... > impossible on a quantum computer because solution brings ... Turing did not ... than and provably no easier than factoring, which is not NP-complete*. ... These games define the polynomial hierarchy (if the games have a bounded ...
    (sci.physics.research)
  • Re: A unique number for every "person" - can it be done?
    ... >> IRREVELANT to whether it is in the same Turing class as the ... > models the limit of a simplified Von Neumann architecture as the CPU ... The Turing Machine doesn't use ... > The limit of a quantum computer, in theory (no useful one has been ...
    (sci.math)
  • Re: A unique number for every "person" - can it be done?
    ... >> IRREVELANT to whether it is in the same Turing class as the ... > models the limit of a simplified Von Neumann architecture as the CPU ... The Turing Machine doesn't use ... > The limit of a quantum computer, in theory (no useful one has been ...
    (sci.crypt)
  • Re: A unique number for every "person" - can it be done?
    ... >> IRREVELANT to whether it is in the same Turing class as the ... > models the limit of a simplified Von Neumann architecture as the CPU ... The Turing Machine doesn't use ... > The limit of a quantum computer, in theory (no useful one has been ...
    (comp.programming)