- author = "Lee Spector and Howard Barnum and Herbert J. Bernstein and Nikhil Swamy",
- title = "Quantum Computing Applications of Genetic Programming",
- booktitle = "Advances in Genetic Programming 3",
- publisher = "MIT Press",
- year = "1999",
- editor = "Lee Spector and William B. Langdon and Una-May O'Reilly and Peter J. Angeline",
- chapter = "7",
- pages = "135--160",
- address = "Cambridge, MA, USA",
- month = jun,
- keywords = "genetic algorithms, genetic programming",
- ISBN = "0-262-19423-6",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/aigp3/ch07.pdf",
-
DOI = "
doi:10.7551/mitpress/1110.003.0010",
-
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.",
- notes = "AiGP3 See http://cognet.mit.edu",
