Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-26T05:11:19.676Z Has data issue: false hasContentIssue false
  • English
  • Français

Machine invention of quantum computing circuits by means of genetic programming

Published online by Cambridge University Press:  12 June 2008

Lee Spector  and
Jon Klein
Lee Spector
Affiliation:
School of Cognitive Science, Hampshire College, Amherst, Massachusetts, USA
Jon Klein
Affiliation:
School of Cognitive Science, Hampshire College, Amherst, Massachusetts, USA
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Artificial IntelligenceGenetic ProgrammingMachine InventionQuantum Computing
Type
Research Article
Information
AI EDAM , Volume 22 , Issue 3 , August 2008 , pp. 275 - 283
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Angeline, P.J., & Kinnear, K.E. Jr., (1996). Advances in Genetic Programming 2. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Banzhaf, W., Nordin, P., Keller, R.E., & Francone, F.D. (1997). Genetic Programming—An Introduction; On the Automatic Evolution of Computer Programs and its Applications. San Mateo, CA: Morgan Kaufmann.Google Scholar
Barnum, H., Bernstein, H.J., & Spector, L. (2000). Quantum circuits for OR and AND of ORs. Journal of Physics A: Mathematical and General 33(45), 8047–8057.CrossRefGoogle Scholar
Brooks, M. (1999). Quantum Computing and Communications. London: Springer–Verlag.CrossRefGoogle Scholar
Brown, J. (2000). Minds, Machines and the Multiverse: The Quest for the Quantum Computer. New York: Simon & Schuster.Google Scholar
Crawford-Marks, R., & Spector, L. (2002). Size control via size fair genetic operators in the PushGP genetic programming system. Proc. Genetic and Evolutionary Computation Conf., pp. 733–739.Google Scholar
Gruau, F. (1993). Genetic synthesis of modular neural networks. Proc. 5th Int. Conf. Genetic Algorithms, pp. 318–325.Google Scholar
Gruska, J. (1999). Quantum Computing. New York: McGraw–Hill.Google Scholar
Holland, J.H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Hornby, G.S., Kumar, S., & Jacob, C. (2007). Editorial introduction to the special issue on developmental systems. Genetic Programming and Evolvable Machines 8(2), 111–113.CrossRefGoogle Scholar
Kinnear, K.E. Jr. (1994). Advances in Genetic Programming. Cambridge, MA: MIT Press.Google Scholar
Kitano, H. (1990). Designing neural networks using genetic algorithms with graph generation system. Complex Systems 4(4), 461–476.Google Scholar
Koza, J.R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press.Google Scholar
Koza, J.R. (1994). Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge, MA: MIT Press.Google Scholar
Koza, J.R. (2008). Human-competitive machine invention by means of genetic programming. AIEDAM: Artificial Intelligence for Engineering, Design, and Manufacturing 22(3), 185–193.CrossRefGoogle Scholar
Koza, J.R., Andre, D., Bennet, F.H. III, & Kean, M. (1999). Genetic Programming III: Darwinian Invention and Problem Solving. San Mateo, CA: Morgan Kaufman.Google Scholar
Koza, J.R., Bennett, F.H. III, Andre, D., & Keane, M.A. (1996). Automated design of both the topology and sizing of analog electrical circuits using genetic programming. In Artificial Intelligence in Design ’96 (Gero, J.S. & Sudweeks, F., Eds.), pp. 151–170. Dordrecht: Kluwer Academic.CrossRefGoogle Scholar
Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., & Lanza, G. (2003). Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Boston: Kluwer Academic.Google Scholar
Koza, J.R., Keane, M.A., Yu, J., Bennett, F.H. III, & Mydlowec, W. (2000). Automatic creation of human-competitive programs and controllers by means of genetic programming. Genetic Programming and Evolvable Machines 1(1/2), 121–164.CrossRefGoogle Scholar
Massey, P., Clark, J., & Stepney, S. (2004). Human-competitive evolution of quantum computing artefacts by genetic programming. Evolutionary Computation 14(1), 21–40.CrossRefGoogle Scholar
Milburn, G.J. (1997). Schrödinger's Machines: The Quantum Technology Reshaping Everyday Life. New York: Freeman.Google Scholar
Nielsen, M.A., & Chuang, I.L. (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press.Google Scholar
O'Reilly, U.-M., Yu, T., Riolo, R.L., & Worzel, B. (2004). Genetic Programming Theory and Practice II. New York: Springer.Google Scholar
Rieffel, E., & Polak, W. (2000). An Introduction to Quantum Computing for Non-Physicists. Accessed at http://arxiv.org/quant-ph/9809016CrossRefGoogle Scholar
Riolo, R.L., Soule, T., & Worzel, B. (2007). Genetic Programming Theory and Practice IV. New York: Springer.CrossRefGoogle Scholar
Riolo, R.L., & Worzel, B. (2003). Genetic Programming Theory and Practice. Boston: Kluwer.CrossRefGoogle Scholar
Spector, L. (2001). Autoconstructive evolution: Push, Pushgp, and Pushpop. Proc. Genetic and Evolutionary Computation Conf., pp. 137–146.Google Scholar
Spector, L. (2004). Automatic Quantum Computer Programming: A Genetic Programming Approach. Boston: Kluwer Academic.Google Scholar
Spector, L., Barnum, H., & Bernstein, H.J. (1998). Genetic programming for quantum computers. Genetic Programming 1998: Proc. 3rd Annual Conf., pp. 365–373.Google Scholar
Spector, L., Barnum, H., Bernstein, H.J., & Swamy, N. (1999 a). Quantum computing applications of genetic programming. In Advances in Genetic Programming 3 (Spector, L., Langdon, W.B., O'Reilly, U.-M. & Angeline, P.J., Eds.), pp. 135–160. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Spector, L., Barnum, H., Bernstein, H.J., & Swamy, N. (1999 b). Finding a better-than-classical quantum AND/OR algorithm using genetic programming. Proc. Congr. Evolutionary Computation, pp. 2239–2246.Google Scholar
Spector, L., & Bernstein, H.J. (2002). Communication capacities of some quantum gates, discovered in part through genetic programming. Proc. Sixth Int. Conf. Quantum Communication, Measurement, and Computing, pp. 500–503.Google Scholar
Spector, L., & Klein, J. (2005). Trivial geography in genetic programming. In Genetic Programming Theory and Practice III (Yu, T., Riolo, R.L., & Worzel, B., Eds.), pp. 109–123. New York: Springer.Google Scholar
Spector, L., Klein, J., & Keijzer, M. (2005). The Push3 execution stack and the evolution of control. Proc. Genetic and Evolutionary Computation Conf., pp. 1689–1696.CrossRefGoogle Scholar
Spector, L., Langdon, W.B., O'Reilly, U.-M., & Angeline, P.J. (1999c). Advances in Genetic Programming 3. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Spector, L., & Robinson, A. (2002). Genetic programming and autoconstructive evolution with the push programming language. Genetic Programming and Evolvable Machines 3(1), 7–40.CrossRefGoogle Scholar
Spector, L., & Stoffel, K. (1996). Ontogenetic programming. Genetic Programming 1996: Proc. 1st Annual Conf., pp. 394–399.Google Scholar
Steane, A. (1998). Quantum computing. Reports on Progress in Physics 61, 117–173.CrossRefGoogle Scholar
Yu, T., Riolo, R.L., & Worzel, B. (2005). Genetic Programming Theory and Practice III. New York: Springer.Google Scholar
Wilson, S.W. (1987). The genetic algorithm and biological development. Proc. 2nd Int. Conf. Genetic Algorithms, pp. 247–251.Google Scholar