Re: Quantum algorithm example

On Saturday 24 May 2008 08:39, Daniel Kraft wrote:
I'm looking for a good example algorithm demonstrating the "power"
quantum computers have over classical ones; but it should really be an
example, simple and easy-to-understand, yet showing how something like
"initialize to superposition, find clever transformations to reduce to
state which gives solution with high possibility".

Although its an artificial problem (i.e., not likely to occur in real
life) Deutsch's function characterization problem is simple to explain
and clearly shows the power of computing with qubits. Basically you
can find out if a binary function is a constant with only one
(quantum) evaluation. We use the problem in a introduction called,
"Quantum Computing and Communications," Advances in Computers,
Academic Press, vol. 56, pages 189-244, 2002. It is available on the
web at http://hissa.nist.gov/~black/Papers/quantumCom.html (pages 23
and 24 there).

You might also use the penny flipping game between Q and Captain
Picard suggested by David A. Meyer in "Quantum strategies" (1999):
http://math.ucsd.edu/~dmeyer/research/projects/DQA.html
reference #1
http://physicsworld.com/cws/article/print/9995
(search down to Profiting from a quantum edge)
among other places.

The simplest realistic algorithm is probably Lov K. Grover's search
algorithm.

-paul-
.

Relevant Pages

  • Re: Quantum computer using using artificial atoms.
    ... That betrays a mystical belief about quantum mechanics, ... You can write algorithms for using an abacus, which require, an abacus. ... But you can mathematicize the operations, and a gp device can model an ... >> algorithms that make them behave like quantum computers, ...
    (sci.crypt)
  • Re: Where do the words come from?
    ... and which relies on the quantum effects. ... There are testable differences between classical and quantum computers. ...
    (rec.arts.sf.composition)
  • Re: Advances in science and technology
    ... By the 25th century Colonization of solar system, Intelligent Robots ... Even assuming no vingean singularity, ... Unless our brains are, essentially, quantum computers. ... Speaking as a quantum physicist, ...
    (rec.arts.sf.written)
  • Re: Advances in science and technology
    ... By the 25th century Colonization of solar system, Intelligent Robots ... Even assuming no vingean singularity, ... Unless our brains are, essentially, quantum computers. ... Speaking as a quantum physicist, ...
    (rec.arts.sf.written)