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]
L. Spector, H. Barnum, H.J. Bernstein, N. Swamy, 1999. "Quantum Computing Applications of Genetic Programming," in Advances in Genetic Programming 3, pp. 135--160, MIT Press.
[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. By Michael A. Nielsen and Isaac L. Chuang. Cambridge University Press. 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]
The Large, the Small and the Human Mind. By Roger Penrose, with Abner Shimony, Nancy Cartwright, and Stephen Hawking. Cambridge University Press. 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
- Quantum computing
Recommendations
Quantum computing
GECCO '07: Proceedings of the 9th annual conference companion on Genetic and evolutionary computationThis tutorial provides an introduction to quantum computing and to the use of evolutionary computation for automatic quantum computer programming. No prior experience with quantum mechanics or with evolutionary computation will be assumed. While the ...
Evolving quantum computer algorithms
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking PapersComputer 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 ...
Evolving quantum computer algorithms
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computationComputer 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2008
1182 pages
Copyright © 2008 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 July 2008
Check for updates
Author Tags
Qualifiers
- Tutorial
Conference
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 1,142Total Downloads
- Downloads (Last 12 months)22
- Downloads (Last 6 weeks)0
Reflects downloads up to 09 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in