Thesis (MSc)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: The goal of this thesis is to present evolutionary algorithms, and demonstrate their applicability
in quantum computing. As an introduction to evolutionary algorithms, it is applied to the simple
but still challenging (from a computational viewpoint) Travelling Salesman Problem (TSP).
This example is used to illustrate the e ect of various parameters like selection method, and
maximum population size on the accuracy and e ciency of the evolutionary algorithms.
For the sample problem, the 48 continental state capitals of the USA, solutions are evolved
and compared to the known optimal solution. From this investigation tournament selection
was shown to be the most e ective selection method, and that a population of 200 individuals
per generation gave the most e ective convergence rates.
In the next part of the thesis, evolutionary algorithms are applied to the generation of optimal
quantum circuits for the following cases:
The identity transformation : Picked for its simplicity as a test of the correct implementation
of the evolutionary algorithm. The results of this investigation showed that the
solver program functions correctly and that evolutionary algorithms can indeed nd valid
solutions for this kind of problem.
The work by Ding et al. [16] on optimal circuits for the two-qubit entanglement gate,
controlled-S gate as well as the three qubit entanglement gate are solved by means of EA
and the results compared. In all cases similar circuits are produced in fewer generations
than the application of Ding et al. [16]. The three qubit quantum Fourier transform gate
was also attempted, but no convergence was attained.
The quantum teleportation algorithm is also investigated. Firstly the nature of the
transformation that leads to quantum teleportation is considered. Next an e ective
circuit is sought using evolutionary algorithms. The best result is one gate longer than
Brassard [11], and seven gates longer than Yabuki [61]. / AFRIKAANSE OPSOMMING: Die doel van hierdie tesis is om evolusionêre algoritmes te ondersoek en hulle toepaslikheid
op kwantumkomputasie te demonstreer. As 'n inleiding tot evolusionêre algoritmes is die
eenvoudige, maar steeds komputasioneel uitdagende handelsreisigerprobleem ondersoek. Die
invloed van die keuse van 'n seleksie metode, sowel as die invloed van die maksimum aantal
individue in 'n generasie op die akkuraatheid en e ektiwiteit van die algoritmes is ondersoek.
As voorbeeld is die 48 kontinentale hoofstede van die state van die VSA gekies. Die oplossings
wat met evolusionêre algoritmes verkry is, is met die bekende beste oplossings vergelyk. Die
resultate van hierdie ondersoek was dat toernooi seleksie die mees e ektiewe seleksie metode
is, en dat 200 individue per generasie die mees e ektiewe konvergensie tempo lewer.
Evolusionêre algoritmes word vervolgens toegepas om optimale oplossings vir die volgende
kwantumalgoritmes te genereer:
Die identiteitstransformasie: Hierdie geval is gekies as 'n eenvoudige toepassing met 'n
bekende oplossing. Die resultaat van hierdie toepassing van die program was dat dit
korrek funksioneer, en vinnig by die korrekte oplossings uitkom.
Vervolgens is daar ondersoek ingestel na vier van die gevalle wat in Ding et al. [16]
bespreek word. Die spesi eke transformasies waarna gekyk is, is 'n optimale stroombaan
vir twee kwabis verstrengeling, 'n beheerde-S hek, 'n drie kwabis verstrengelings hek,
en 'n drie kwabis kwantum Fourier transform hek. In die eerste drie gevalle stem die
oplossings ooreen met die van Ding et al. [16], en is die konvergensie tempo vinniger.
Daar is geen oplossing vir die kwantum Fourier transform verkry nie.
Laastens is daar na die kwantumteleportasiealgoritme gekyk. Die eerste stap was om te
kyk na die transformasie wat in hierdie geval benodig word, en daarna is gepoog om 'n
e ektiewe stroombaan te evolueer. Die beste resultaat was een hek langer as Brassard
[11], en sewe hekke langer as Yabuki [61].
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/20095 |
| Date | 03 1900 |
| Creators | Kruger, Markus Gustav |
| Contributors | Geyer, Hendrik B., Visagie, Stephan E., Stellenbosch University. Faculty of Science. Dept. of Physics. |
| Publisher | Stellenbosch : Stellenbosch University |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | English |
| Type | Thesis |
| Format | 108 p. : ill. |
| Rights | Stellenbosch University |
Page generated in 0.0021 seconds