Evolutionary discovery of algorithms as circuits for quantum computers

ABSTRACT

This paper demonstrates an application of an evolutionary approach for solving a class of non-trivial, hardware-design problems. Array processing features of the computer language APL simplify the implementation of an evolutionary solution in which simulation is performed by a genetic algorithm on a population of candidate solutions until one or more are satisfactory quantum algorithms. The objective of the simulation model is the automatic discovery of quantum computer algorithms. The algorithms are expressed in a circuit model that specifies the sequences in which quantum operators are to be applied. The automatically configured circuits operate as quantum computers that for the present have their domains of application limited to evaluation of only a few specific functions. The simulations use a small collection of basic and relatively low-level operators to obtain perfect results for five different target functions. These functions were chosen to demonstrate how, on a personal computer, an evolutionary method is able to discover novel designs of computing hardware. The results establish that it is feasible to use genetic algorithms in an evolutionary method to invent correct hardware designs. The progress of simulated evolution is directed by input/output constraints and a fitness function. Alternative configurations of circuit models can obtain algorithms with promise for future quantum computers. Current simulations yield primitive quantum algorithms with a total of twelve or fewer inputs and outputs. The discovered algorithms produce the correct results for evaluating the five selected logical and arithmetic functions.

REFERENCES

• 1: Barenco, A. et al Elementary Gates for Quantum Computation Phys. Revs A. Vol 52, 1995 pp 3457-3467
• 2: James A. Brown , Sandra Pakin , Raymond P. Polivka, APL2: at a glance, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 3: Goldhaber-Gordon, D.J. et al --- Overview of Nanoelectric Devices, Proceedings of the IEEE, April 1997
• 4: Grover, L.K. Quantum Mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79:325-328 --- see also "A fast Quantum Mechanical Algorithm for Data Base Search" Quantum Physics
• 5: John R. Koza , David Andre , Forrest H. Bennett , Martin A. Keane, Genetic Programming III: Darwinian Invention & Problem Solving, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 6: Monroe, Chris - NIST publication 7415, pages 303-497} --- Two quantum logic gates can be realized in a single trapped beryllium ions
• 7: Moravec, Hans --- "When will the Computer Match the Human Brain" --- Journal of Evolution and Technology 1998. Vol. 1 --- 'http://www.frc.ri.cmu/~hpm'
• 8: NASA/DoD Workshop on Evolvable Hardware --- http://cism.jpl.nasa.gov/ ehw/events/ nasaeh01
• 9: Nielson, M.A. and I. L. Chuang --- "Programmable gate arrays" --- Physical Review Letters 79, 321 (1997)
• 10: Obenland, XXX September 1997 High Performance Computing 1998 also see Ph.D. Dissertation of 1998
• 11: Shor, P.W. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. --- Proceedings of the 25th Annual Symp. on Foundations of Computer Science, pp 124-134, Los Alamitos, CA, 1994 IEEE Press
• 12: Toffoli, T Frontiers in Computation Information Processing 1987 Proceedings of the IFIP 11th World Congress San Francisco, pages 591-597
• 13: Vandersypen, L.M.K. et al, Experimental realization of Shor's quantum factoring algorithm using nuclear magnet resonance --- Nature 20/27 414, pp 883-887, December 2001