On evolutionary algorithms for effective quantum computing

Kruger, Markus Gustav (2012-03)

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].

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/20095
This item appears in the following collections: