1) Title: "Evolution of a Human-Competitive Quantum Fourier Transform Algorithm Using Genetic Programming" Authors : Paul Massey, John A Clark, Susan Stepney (2) The name, physical mailing address, e-mail address, and phone number of EACH author of EACH paper, Paul Massey, John A Clark and Susan Stepney Department of Computer Science University of York Heslington York YO10 5DD UK psm111@cs.york.ac.uk (tel - not applicable) jac@cs.york.ac.yk (+44 1904 433379) susan@cs.york.ac.uk (+44 1904 432781) (3) the name of the corresponding author (to whom notices will be sent concerning the competition), Prof SUSAN STEPNEY (Attendee at GECCO 2005 and presenter of the paper) (4) the abstract of the paper, In this paper, we show how genetic programming (GP) can be used to evolve system-size-independent quantum algorithms, and present a human-competitive Quantum Fourier Transform (QFT) algorithm evolved by GP. [The QFT is the basic fundamental building block behind Peter Shor's factorisation algorithms - quabntum computing's killer application.] (5) a list containing one or more of the eight letters (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. (G) The result solves a problem of indisputable difficulty in its field. ************************************************************************************** (6) a statement stating why the result satisfies that criteria (B): We have evolved by genetic programming a system-size-independent algorithm to implement a Quantum Fourier Transform. This is the crucial component of many quantum applications such period finding (with its world famous application to polynomial time factorisation), phase estimation and various other instances of the hidden subgroup problem. A variety of circuit schemes have been suggested to implement the QFT, the first of which was demonstrated by Peter Shor: P.W. Shor. Algorithms for quantum computation: discrete logarithms and factor- ing." quant-ph/9508027, in Proc. 35th Symp. on Foundations of Computer Science (1994). Chapter 5 (The quantum Fourier transform and its applications ) of "Quantum Computing and Quantum Information" by Nielsen and Chuang contains an accessible description of the heart the best-known QFT implementation. Another description of the QFT and its applications can be found at http://beige.ucs.indiana.edu/B679/node104.html Our GP techqniues have successfully evolved the same principal scheme as described in Chuang and Nielsen. (F): As indicated above (G): The result solves a problem of indisputable difficulty in its field. Researchers are still trying to find more efficient implementations. This is a distinctly non-trivial problem. Recent examples of work in this field are: "GENERIC QUANTUM FOURIER TRANSFORMS" Cristopher Moore and Daniel Rockmore http://arxiv.org/PS_cache/quant-ph/pdf/0304/0304064.pdf "Fast parallel circuits for the quantum Fourier transform" R. Cleve, Calgary Univ., Alta., Canada J. Watrous, Calgary Univ., Alta., Canada 41st Annual Symposium on Foundations of Computer Science Although our techniques have found the 'classical' implementation algorithm, this implementation was a highly significant achievement when it was proposed. In addition, it is the highest level quantum-related artifact generated by genetic programming techniques.[The trend to increasing levels of abstraction is absolutely crucial, and recognised from the earliest days of quantum genetic programming by Spector and colleagues.] (7) a full citation of the paper @inproceedings(SS-GECCO05, author = "Paul Massey and John A. Clark and Susan Stepney", title = "Evolution of a Human-Competitive {Q}uantum {F}ourier {T}ransform algorithm using genetic programming", pages = 1657--1664, crossref = "GECCO2005" ) @BOOK{GECCO2005, EDITOR = {Beyer, H.-G. and O'Reilly, U.-M. and Arnold, D.V. and Banzhaf, W. and Blum, C. and Bonabeau, E.W. and Cantu Paz, E. and Dasgupta, D. and Deb, K. and Foste r, J.A. and {de~Jong}, E.D. and Lipson, H. and Llora, X. and Mancoridis, S. and Pelikan, M. and Raidl, G.R. and Soule, T. and Tyrrell, A. and Watson, J.-P. and Zitzler, E.}, TITLE = {{Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2005}}, PUBLISHER = {ACM Press}, ADDRESS = {New York}, YEAR = {2005} } It is to be published as part of GECCO 2005. It will appear in Volume 2 of the above.