Re: Quantum Computation

Nick Maclaren wrote:
> charles@xxxxxxxxxxxxxxxxx (Charles) writes:
> |> Can a quantum computer of say, 128 qubits, speed up the computation of
> |> *any* existing (classical) computer algorithm (and if so by what
> |> order), or does it speed up only certain types of algorithms like
> |> those introduced by Shor, Deutsch..etc ?
>
> The latter.

That is true. It is true for *any* two classes of machine whatsoever.
There are problems for which a supercomputer is not faster (in any
meaningful sense) than pencil and paper.

Also, note that complexity is a property of *problems*, not algorithms,
because there is no well defined way to say that two different machines
are running the same algorithm.

> To a very good approximation, there is only one
> practical problem that a quantum computer is known to solve
> significantly faster than a deterministic one: integer
> factorisation a.k.a. the discrete logarithm (Shor). Whether
> there are any other problems that can be is an open question.

That isn't quite true. There is another important class of problems for
which Quantum Computing is better than classical, and it is a more
appropriate topic for this list:

Simulating quantum systems.

Given a description of a quantum system, the problem is to answer
questions about its behavior (Simple questions like "Is the probability
to go from state A to state B in time t more than 0.5").

You might not consider that a "practical" problem, but I would. I view
anything that could be used to design a better transistor, or understand
high temperature superconductivity etc. as practical. Quantum simulation
wouldn't guarantee a solution to either problem, but it sure would help.

> as I understand it, 128 qubits isn't interesting

Perhaps not for factoring, but a quantum system with 128 (binary)
degrees of freedom has a 2^128 dimensional state space, and in general
(classically) you have to evaluate every basis vector. That's *way* too
many.

Physicist are quite good at finding ways to simplify or approximate, but
that only works in special cases.

There are well defined physical theories that cannot be compared to
experiment because no one can calculate any predictions from them.

> Or that was my understanding the last time I looked.

This class of problem was known from the very beginning. It was part of
the original motivation for the idea of Quantum Computing.

Ralph Hartley

.

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
    ... 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: 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)
  • Re: Help support non-crazy scientist?
    ... By receiving such information, you'd ... works if you're using a quantum computer (i.e., ... as a stream of qubits ... human brain isn't a quantum computer, I ...
    (rec.arts.sf.composition)
  • Re: Quantum Computers breaking ciphers
    ... >> quantum computer and used itbto run Shor's Algorithm works and to ... >one qubit that can be chained with other qubits to do a computation. ... but not a quantum computer. ... >investigation of the spin states of some particular molecule. ...
    (sci.crypt)