T. Reid. University of Waterloo, Waterloo, Ontario, Canada, Master of Mathematics in Combinatorics and
Optimisation, (2005)
Abstract
The goal of this work is to understand the application
of the evolutionary programming approach to the problem
of quantum circuit design. This problem is motivated by
the following observations: In order to keep up with
the seemingly insatiable demand for computing power our
computing devices will continue to shrink, all the way
down to the atomic scale, at which point they become
quantum mechanical systems. In fact, this event, known
as Moore's Horizon, is likely to occur in less than 25
years. The recent discovery of several quantum
algorithms which can solve some interesting problems
more efficiently than any known classical algorithm.
While we are not yet certain that quantum computers
will ever be practical to build, there do now exist the
first few astonishing experimental devices capable of
briefly manipulating small quantities of quantum
information. The programming of these devices is
already a nontrivial problem, and as these devices and
their algorithms become more complicated this problem
will quickly become a significant challenge.
The Evolutionary Programming (EP) approach to problem
solving seeks to mimic the processes of evolutionary
biology which have resulted in the awesome complexity
of living systems, almost all of which are well beyond
our current analysis and engineering capabilities. This
approach is motivated by the highly successful
application of Koza's Genetic Programming (GP) approach
to a variety of circuit design problems, and
specifically the preliminary reports by Williams and
Gray and also Rubinstein who applied GP to quantum
circuit design. Accompanying this work is software for
evolutionary quantum circuit design which incorporates
several advances over previous approaches, including:
A formal language for describing parallel quantum
circuits out of an arbitrary elementary gate set,
including gates with one or more parameters. A fitness
assessment procedure that measures both average case
fidelity with a respect for global phase equivalences,
and implementation cost. A Memetic Programming (MP)
based reproductive strategy that uses a combination of
global genetic and local memetic searches to
effectively search through diverse circuit topologies
and optimise the parameterised gates they contain.
Several benchmark experiments are performed on small
problems which support the conclusion that Evolutionary
Programming is a viable approach to quantum circuit
design and that further experiments using more
computational resources and more problem insight can be
expected to yield many new and interesting quantum
circuits.
%0 Thesis
%1 oai:collectionscanada.ca:OWTU.516
%A Reid, Timothy
%C Waterloo, Ontario, Canada
%D 2005
%K EP, Mathematics, circuits computing, evolutionary programming, quantum wabisabi,
%T On the Evolutionary Design of Quantum Circuits
%U http://etd.uwaterloo.ca/etd/treid2005.pdf
%X The goal of this work is to understand the application
of the evolutionary programming approach to the problem
of quantum circuit design. This problem is motivated by
the following observations: In order to keep up with
the seemingly insatiable demand for computing power our
computing devices will continue to shrink, all the way
down to the atomic scale, at which point they become
quantum mechanical systems. In fact, this event, known
as Moore's Horizon, is likely to occur in less than 25
years. The recent discovery of several quantum
algorithms which can solve some interesting problems
more efficiently than any known classical algorithm.
While we are not yet certain that quantum computers
will ever be practical to build, there do now exist the
first few astonishing experimental devices capable of
briefly manipulating small quantities of quantum
information. The programming of these devices is
already a nontrivial problem, and as these devices and
their algorithms become more complicated this problem
will quickly become a significant challenge.
The Evolutionary Programming (EP) approach to problem
solving seeks to mimic the processes of evolutionary
biology which have resulted in the awesome complexity
of living systems, almost all of which are well beyond
our current analysis and engineering capabilities. This
approach is motivated by the highly successful
application of Koza's Genetic Programming (GP) approach
to a variety of circuit design problems, and
specifically the preliminary reports by Williams and
Gray and also Rubinstein who applied GP to quantum
circuit design. Accompanying this work is software for
evolutionary quantum circuit design which incorporates
several advances over previous approaches, including:
A formal language for describing parallel quantum
circuits out of an arbitrary elementary gate set,
including gates with one or more parameters. A fitness
assessment procedure that measures both average case
fidelity with a respect for global phase equivalences,
and implementation cost. A Memetic Programming (MP)
based reproductive strategy that uses a combination of
global genetic and local memetic searches to
effectively search through diverse circuit topologies
and optimise the parameterised gates they contain.
Several benchmark experiments are performed on small
problems which support the conclusion that Evolutionary
Programming is a viable approach to quantum circuit
design and that further experiments using more
computational resources and more problem insight can be
expected to yield many new and interesting quantum
circuits.
@mastersthesis{oai:collectionscanada.ca:OWTU.516,
abstract = {The goal of this work is to understand the application
of the evolutionary programming approach to the problem
of quantum circuit design. This problem is motivated by
the following observations: In order to keep up with
the seemingly insatiable demand for computing power our
computing devices will continue to shrink, all the way
down to the atomic scale, at which point they become
quantum mechanical systems. In fact, this event, known
as Moore's Horizon, is likely to occur in less than 25
years. The recent discovery of several quantum
algorithms which can solve some interesting problems
more efficiently than any known classical algorithm.
While we are not yet certain that quantum computers
will ever be practical to build, there do now exist the
first few astonishing experimental devices capable of
briefly manipulating small quantities of quantum
information. The programming of these devices is
already a nontrivial problem, and as these devices and
their algorithms become more complicated this problem
will quickly become a significant challenge.
The Evolutionary Programming (EP) approach to problem
solving seeks to mimic the processes of evolutionary
biology which have resulted in the awesome complexity
of living systems, almost all of which are well beyond
our current analysis and engineering capabilities. This
approach is motivated by the highly successful
application of Koza's Genetic Programming (GP) approach
to a variety of circuit design problems, and
specifically the preliminary reports by Williams and
Gray and also Rubinstein who applied GP to quantum
circuit design. Accompanying this work is software for
evolutionary quantum circuit design which incorporates
several advances over previous approaches, including:
A formal language for describing parallel quantum
circuits out of an arbitrary elementary gate set,
including gates with one or more parameters. A fitness
assessment procedure that measures both average case
fidelity with a respect for global phase equivalences,
and implementation cost. A Memetic Programming (MP)
based reproductive strategy that uses a combination of
global genetic and local memetic searches to
effectively search through diverse circuit topologies
and optimise the parameterised gates they contain.
Several benchmark experiments are performed on small
problems which support the conclusion that Evolutionary
Programming is a viable approach to quantum circuit
design and that further experiments using more
computational resources and more problem insight can be
expected to yield many new and interesting quantum
circuits.},
added-at = {2008-06-19T17:46:40.000+0200},
address = {Waterloo, Ontario, Canada},
author = {Reid, Timothy},
bibsource = {OAI-PMH server at oai.collectionscanada.ca},
biburl = {https://www.bibsonomy.org/bibtex/2f65e2413d33d1576183ba487948772ca/brazovayeye},
interhash = {f0db5a4534549444b96621983d14e096},
intrahash = {f65e2413d33d1576183ba487948772ca},
keywords = {EP, Mathematics, circuits computing, evolutionary programming, quantum wabisabi,},
language = {en},
notes = {Experiments 6.1 CNOT, 6.2 CPHASE, 6.3 CPHASE 2, 6.4
SWAP, 6.5 QFT2, 6.6 SQRTSWAP, 6.7 TELEPORTSEND, 6.8
TELEPORTRECEIVE, 6.9 TOFFOLI},
oai = {oai:collectionscanada.ca:OWTU.516},
rights = {Copyright: 2005, Reid, Timothy. All rights reserved.},
school = {University of Waterloo},
size = {93 pages},
timestamp = {2008-06-19T17:50:09.000+0200},
title = {On the Evolutionary Design of Quantum Circuits},
type = {Master of Mathematics in Combinatorics and
Optimisation},
url = {http://etd.uwaterloo.ca/etd/treid2005.pdf},
year = 2005
}