Re: Quantum Computer Algorithms

From: Ralph Hartley (hartley_at_aic.nrl.navy.mil)
Date: 09/24/04 

Date: Fri, 24 Sep 2004 13:10:53 +0000 (UTC)

dar7yl wrote:

> My experience with computers has mostly been with the classic "von Neumann"
> architecture, a variant of the other-classical "Turing Machine" universal
> calculator. I will refer to this as "Classic Computing".

A quantum computer is similar, except that it can do a couple of extra
operations. A "nondeterministic Turing machine" and a "quantum computer"
are very similar concepts (they are both members a class of concepts, the
"counting classes"). They all compute the same functions, but the
complexity may be different.

It is not known if they are actually the same (complexity wise), or if
either is the same as an ordinary Turing machine, but it is presumed that
they are not.

The difference is that while a nondeterministic Turing machine is a totally
abstract notion, a quantum computer is something you might be able to
actually build.

> Within Classic Computing, there has evolved the concept of Algorithms, which
> are codified representations of operations which may be performed using the
> architecture.
>
> I have seen a few references to QC algorithms

Just as nondeterministic algorithms are sequences of operations that can be
performed on a nondeterministic machine, quantum algorithms can be
performed on a quantum computer.

> How does QC relate to CC?
> Can you translate CC algorithms into the QC realm?

CC algorithms are a subset of QC algorithms, so that translation is trivial.

> And vice-versa?

Yes. Some people seem to think that because quantum computers involve
"amplitudes" from the continuous set of complex numbers, quantum computers
have an uncountable number of states. But that is generally not so. The
total number of reachable states is countable (just as for a classical
computer), and at ant fixed time after starting the number of possible
states is finite (just as for a classical computer).

For any quantum algorithm there is a classical algorithm that computes a
representation of its state as a function of time.

Fine print that doesn't really matter: the classical computer needs access
to a random number generator, and the simulation is only statistically the
same (i.e. the probability of producing a representation is the same as the
probability that the QC will be in the represented state), which is all
that can be required, since different runs of the same QC are only
statistically the same as each other.

Anticipating your next question:

> Can you develop a Turing Machine that mimics a QC? (ie, a simulator)

Yes. But it is generally believed that no simulator can work in polynomial
time. The status of this belief is similar to the belief that P!=NP, fairly
"obviously" true, but no real prospect of a proof.

The obvious way to simulate a quantum computation is exponential.

> What problem domains can be solved using QC? What can't?

There are some problems for which there are quantum algorithms faster than
the best known classical algorithm.

Simulating a physical quantum system is the most obvious and diverse class,
but there are also problems of general interest.

Factoring is the best known example. Actually, such problems seem to be
surprisingly rare, all fit into a few classes.

They would, however, have a substantial economic impact (both positive and
negative). Especially in cryptography.

> How practical are QC's? ie, how far away from actual computations being
> performed?

Still a ways. You noted a report of five particles being entangled. When we
can reliably do a thousand or so, error correction starts to make headway,
and you should be able to do lots.

That we don't know for sure that my last statement is true, reflects the
difficulties of the theoretical side of quantum computation. Which even
though it has received lots of attention, in my opinion needs much more.

> If a simulator is possible (see above), does it not follow that the
> simulator can be used to solve NP-complete problems?.

No. So far as we know, BQP (the quantum equivalent of P) is neither a
superset nor a subset of NP.

In other words, NP-complete problems are *not* among those that are known
to be polynomial on a quantum computer.

There are fewer problems (like "what is the output of a given quantum
computer") believed to be in BQP but not in NP, but I *would* have heard of
any proof that none exist.

Both quantum and nondeterministic computers "do many computations in
parallel" in a sense, but in two *different* senses (and neither in the
obvious sense).

Also,

> assuming that the simulator can work in polynomial time.

This is quite likely false (it is true iff BQP=P).

If you are at all interested, get the book _Quantum Computation and Quantum
Information_ by Nielsen and Chuang. It is well written, complete (as of
2000 which is good enough to start with), and does not assume knowledge of
either computation or quantum mechanics.

Ralph Hartley

Relevant Pages

  • Re: Quantum computer using using artificial atoms.
    ... "Surrogate Factoring" is Snake Fur. ... > If quantum computers can work, then there are algorithms that can do ... There have been other mechanical factoring ideas. ... > What a quantum computer can do, a gp computer with the appropriate ...
    (sci.crypt)
  • Re: Quantum Computer Algorithms
    ... A quantum computer is similar, except that it can do a couple of extra ... A "nondeterministic Turing machine" and a "quantum computer" ... The difference is that while a nondeterministic Turing machine is a totally ... Just as nondeterministic algorithms are sequences of operations that can be ...
    (sci.physics.research)
  • Re: How long IF IT IS A DRAW?
    ... You're reasoning as though your quantum computer was able to search an ... and there's no reason to think ... #algorithms altogether, ... chess algorithms had emerged in the past few years. ...
    (sci.math)
  • Quantum algorithms and complexity of computation
    ... Keith Ramsay wrote: ... > | Let's guess that it will take our quantum computer one second to ... > exponentially growing number of nodes, and there's no reason to think ... > #algorithms altogether, ...
    (sci.math)
  • 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)