Incollection,
Quantum Computing Applications of Genetic Programming
Advances in Genetic Programming 3, chapter 7, MIT Press, Cambridge, MA, USA, (June 1999)
Abstract
Quantum computers are computational devices that use
the dynamics of atomic-scale objects to store and
manipulate information. Only a few, small-scale quantum
computers have been built to date, but quantum
computers can in principle outperform all possible
classical computers in significant ways. Quantum
computation is therefore a subject of considerable
theoretical interest that may also have practical
applications in the future.
Genetic programming can automatically discover new
algorithms for quantum computers spector:1998:GPqc.
We describe how to simulate a quantum computer so that
the fitness of a quantum algorithm can be determined on
classical hardware. We then describe ways in which
three different genetic programming approaches can
drive the simulator to evolve new quantum algorithms.
The approaches are standard tree-based genetic
programming, stack-based linear genome genetic
programming, and stackless linear genome genetic
programming. We demonstrate the techniques on four
different problems: the two-bit early promise problem,
the scaling majority-on problem, the four-item database
search problem, and the two-bit and-or problem. For
three of these problems (all but majority-on) the
automatically discovered algorithms are more efficient
than any possible classical algorithms for the same
problems. One of the better-than-classical algorithms
(for the two-bit and-or problem) is in fact more
efficient than any previously known quantum algorithm
for the same problem, suggesting that genetic
programming may be a valuable tool in the future study
of quantum programming.
