IEEE Congress on Evolutionary Computation (CEC)

Finding a better-than-classical quantum AND/OR algorithm using genetic programming

Lee C. Spector, Howard Barnum, Herbert Joseph Bernstein, N. Swamy

Published Jan 20, 2003• 118 citations

Abstract

This paper documents the discovery of a new, better-than-classical quantum algorithm for the depth-two AND/OR tree problem. We describe the genetic programming system that was constructed specifically for this work, the quantum computer simulator that is used to evaluate the fitness of evolving quantum algorithms, and the newly discovered algorithm.

DOI: 10.1109/cec.1999.785553

Related papers

Quantum Computing Applications of Genetic Programming

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 et al., 1998].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.

The MIT Press eBooksJan 1, 199972 citations

Evolving blackbox quantum algorithms using genetic programming

Ralf Stadelhofer, Wolfgang Banzhaf, Dieter Suter

Abstract Although it is known that quantum computers can solve certain computational problems exponentially faster than classical computers, only a small number of quantum algorithms have been developed so far. Designing such algorithms is complicated by the rather nonintuitive character of quantum physics. In this paper we present a genetic programming system that uses some new techniques to develop and improve quantum algorithms. We have used this system to develop two formerly unknown quantum algorithms. We also address a potential deficiency of the quantum decision tree model used to prove lower bounds on the query complexity of the parity problem.

Artificial intelligence for engineering design analysis and manufacturingJun 12, 200817 citations

Evolving quantum computer algorithms

Lee C. Spector

Computer science will be radically transformed if ongoing efforts to build large-scale quantum computers eventually succeed and if the properties of these computers meet optimistic expectations. Nevertheless, computer scientists still lack a thorough understanding of the power of quantum computing, and it is not always clear how best to utilize the power that is understood. This dilemma exists because quantum algorithms are difficult to grasp and even more difficult to write. Despite large-scale international efforts, only a few important quantum algorithms are documented, leaving many essential questions about the potential of quantum algorithms unanswered. These unsolved problems are ideal challenges for the application of automatic programming technologies. Genetic programming techniques, in particular, have already produced several new quantum algorithms and it is reasonable to expect further discoveries in the future. These methods will help researchers to discover how additional practical problems can be solved using quantum computers, and they will also help to guide theoretical work on both the power and limits of quantum computing. This tutorial will provide an introduction to quantum computing and an introduction to the use of evolutionary computation for automatic quantum computer programming. No background in physics or in evolutionary computation will be assumed. While the primary focus of the tutorial will be on general concepts, specific results will also be presented, including human-competitive results produced by genetic programming. Follow-up material is available from the presenter's book, Automatic Quantum Computer Programming: A Genetic Programming Approach, published by Springer and Kluwer Academic Publishers.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)Jul 8, 20090 citations

Machine invention of quantum computing circuits by means of genetic programming

Lee C. Spector, Jon Klein

Abstract We demonstrate the use of genetic programming in the automatic invention of quantum computing circuits that solve problems of potential theoretical and practical significance. We outline a developmental genetic programming scheme for such applications; in this scheme the evolved programs, when executed, build quantum circuits and the resulting quantum circuits are then tested for “fitness” using a quantum computer simulator. Using the PushGP genetic programming system and the QGAME quantum computer simulator we demonstrate the invention of a new, better than classical quantum circuit for the two-oracle AND/OR problem.

Artificial intelligence for engineering design analysis and manufacturingJun 12, 200823 citations

Genetic programming for quantum computers

Lee C. Spector, Howard Barnum, Herbert Joseph Bernstein

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

The MIT Press eBooksJan 1, 199855 citations

Evolution of Quantum Algorithms using Genetic Programming

André Leier

Automatic quantum circuit design is motivated by the difficulties in manual design, because quantum algorithms are highly non-intuitive and practical quantum computer hardware is not yet available. Thus, quantum computers have to be simulated on classical hardware which naturally entails an exponential growth of computational costs and allows only to simulate small quantum systems, i. e., with only few qubits. Huge search spaces render evolutionary approaches nearly unable to achieve breakthrough solutions in the development of new quantum algorithms. Consequently, at present we must be content to evolve essentially already existing (black-box) quantum algorithms. This thesis presents empirical results on the evolution of quantum circuits using genetic programming. For that purpose, a linear and a linear-tree GP system (allowing intermediate measurements) with integrated quantum computer simulator were implemented. Their practicality in evolving quantum circuits is shown in different experiments for 1-SAT (solutions act like Hogg's algorithm) and the Deutsch-Jozsa problem. These experiments confirm that the evolution of quantum circuits is practically feasible only for sufficiently small problem instances. In this context, scalability and the detection of scalability becomes very important. It is shown that scalable quantum circuits are evolvable to a certain degree: a general quantum circuit can be inferred manually from the evolved solutions for small instances of the given problem. Besides, further experiments indicate that 're-evolution' is effective for the evolution of scalable quantum circuits. With this method the start population of a problem instance is inoculated with evolved solutions for a smaller problem instance. Furthermore, investigations of fitness landscapes and selection strategies are made, with the aim of improving the efficiency of evolutionary search. A notable result is that using the crossover operator damages rather than benefits evolution of quantum circuits.

Jul 21, 20048 citations