Evolving quantum computer algorithms

ABSTRACT

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.

REFERENCES

• 1: A. Steane, 1998. "Quantum Computing," Reports on Progress in Physics, vol. 61, pp. 117--173. http://xxx.lanl.gov/abs/quant-ph/9708022
• 2: P. Shor, 1998. "Quantum Computing," Documenta Mathematica, vol. Extra Volume ICM, pp. 467--486. http://east.camel.math.ca/EMIS/journals/DMJDMV/xvol-icm/00/Shor.MAN.ps.gz
• 3: J. Preskill, 1997. "Quantum Computing: Pro and Con," Tech. Rep. CALT-68-2113, California Institute of Technology. http://xxx.lanl.gov/abs/quant-ph/9705032
• 4: A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, H. Weinfurter, 1995. "Elementary Gates for Quantum Computation," submitted to Physical Review A. http://xxx.lanl.gov/abs/quant-ph/9503016
• 5: N.J. Cerf, C. Adami, P.G. Kwiat, 1998. "Optical Simulation of Quantum Logic," Phys. Rev. A 57, 1477. http://xxx.lanl.gov/abs/quant-ph/9706022
• 6: L. Spector and H.J. Bernstein. 2003. "Communication Capacities of Some Quantum Gates, Discovered in Part through Genetic Programming," in Proc. of the Sixth Intl. Conf. on Quantum Communication, Measurement, and Computing, edited by J.H. Shapiro and O. Hirota. Princeton, NJ: Rinton Press, Inc. pp. 500--503. http://hampshire.edu/lspector/pubs/spector-QCMC-prepress.pdf
• 7: H. Barnum, H.J. Bernstein, and L. Spector. 2000. Quantum circuits for OR and AND of ORs. Journal of Physics A: Mathematical and General, Vol. 33 No. 45 (17 November 2000), pp. 8047--8057. http://hampshire.edu/lspector/pubs/jpa.pdf
• 8: Lee Spector , Howard Barnum , Herbert J. Bernstein , Nikhil Swamy, Quantum computing applications of genetic programming, Advances in genetic programming: volume 3, MIT Press, Cambridge, MA, 1999
• 9: L. Spector, H. Barnum, H.J. Bernstein, N. Swamy, 1999. "Finding a Better-Than-Classical Quantum AND/OR Algorithm Using Genetic Programming," in Proc. 1999 Congress on Evolutionary Computation, IEEE Press.
• 10: L. Spector, H. Barnum, H.J. Bernstein, 1998. "Genetic Programming for Quantum Computers," in Genetic Programming 1998: Proceedings of the Third Annual Conference, pp. 365--374, Morgan Kaufmann.
• 11: Automatic Quantum Computer Programming: A Genetic Programming Approach. By Lee Spector. Kluwer Academic Publishers, 2004, and Springer Science+Business Media, 2007.
• 12: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 13: Schrödinger's Machines: The Quantum Technology Reshaping Everyday Life. By Gerard J. Milburn. W.H. Freeman and Company. 1997.
• 14: Explorations in Quantum Computing. By Colin P. Williams and Scott H. Clearwater. Springer-Verlag/Telos. 1997.
• 15: The Fabric of Reality. By David Deutsch. Penguin Books. 1997.
• 16: Roger Penrose , Malcolm S. Longair, The Large, the Small, and the Human Mind, Cambridge University Press, New York, NY, 1997
• 17: QED: The Strange Theory of Light and Matter. By Richard P. Feynman. Princeton University Press. 1985.
• 18: Oxford's Center for Quantum Computation: http://www.qubit.org/
• 19: Stanford-Berkeley-MIT-IBM NMR Quantum Computation Project: http://squint.stanford.edu/
• 20: Quantum Information and Computation (Caltech - MIT - USC): http://theory.caltech.edu/~quic/index.html
• 21: Quantum Computation at ISI/USC: http://www.isi.edu/acal/quantum/quantum_intro.html
• 22: Los Alamos National Laboratory quantum physics e-print archive: http://xxx.lanl.gov/form/quant-ph
• 23: John Preskill's Physics 229 course web page (many good links): http://www.theory.caltech.edu/people/preskill/ph229/
• 24: Samuel L. Braunstein's on-line tutorial: http://www.sees.bangor.ac.uk/~schmuel/comp/comp.html
• 25: NIST Ion Storage Group: http://www.bldrdoc.gov/timefreq/ion/index.htm
• 26: QGAME, Quantum Gate And Measurement Emulator: http://hampshire.edu/lspector/qgame.html

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

General Terms:
Algorithms, Theory

Keywords:
evolutionary algorithms, genetic programming, interference, quantum computing