The MIT Press eBooks
Genetic programming for quantum computers
Lee C. Spector, Howard Barnum, Herbert Joseph Bernstein
Abstract
Genetic programming can be used to automatically discover algorithms for quantum computers that are more efficient than any classical computer algorithms for the same problems. In this paper we exhibit the first evolved betterthan-classical quantum algorithm, for Deutsch’s “early promise ” problem. We also demonstrate a technique for evolving scalable quantum gate arrays and discuss other issues in the application of genetic programming to quantum computation and vice versa. 1. Quantum Computing Quantum computers are computational devices that use atomic-scale objects, for example 2-state particles, to store and manipulate information (Steane, 1997; for an elementary on-line tutorial see Braunstein, 1995; for an introduction for the general reader see Milburn, 1997). The physics of these devices allows them to do things that common digital (henceforth “classical”) computers cannot. Although quantum computers and classical computers appear to be bound by the same limits of Turing computability, physicists argue that quantum computers can solve certain problems using less resources (time and space) than classical computers are thought to require (Jozsa, 1997). For example, Shor’s quantum algorithm finds the prime factors of an n-digit number in time O(n 3), while the best known classical factoring algorithms