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.