Evolution of Quantum Algorithms using Genetic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.7917

@PhdThesis{oai:eldorado:0x0007ce5c,

• title = "Evolution of Quantum Algorithms using Genetic Programming",
• author = "Andr{\'e} Leier",
• school = "Dortmund University",
• year = "2004",
• month = jul # "~21",
• annote = "Fachbereich 4; Universit{\"a}t Dortmund",
• contributor = "W. Banzhaf and Fachbereich 4 and D. Sieling",
• language = "ENG",
• oai = "oai:eldorado:0x0007ce5c",
• rights = "These documents can be used freely according to copyright laws. They can be printed freely. It is not allowed to distribute them further on.",
• address = "Germany",
• keywords = "genetic algorithms, genetic programming, Quantum Computing, Quantum Circuits, Evolutionary Circuit Design",
• URL = "https://eldorado.uni-dortmund.de/bitstream/2003/2745/1/Leierunt.pdf",
• URL = "http://hdl.handle.net/2003/2745",
• size = "199 pages",
• abstract = "Automatic quantum circuit design is motivated by the difficulties in manual design, because quantum algorithms are highly non-intuitive and practical quantum computer hardware is not yet available. Thus, quantum computers have to be simulated on classical hardware which naturally entails an exponential growth of computational costs and allows only to simulate small quantum systems, i. e., with only few qubits. Huge search spaces render evolutionary approaches nearly unable to achieve breakthrough solutions in the development of new quantum algorithms. Consequently, at present we must be content to evolve essentially already existing (black-box) quantum algorithms. This thesis presents empirical results on the evolution of quantum circuits using genetic programming. For that purpose, a linear and a linear-tree GP system (allowing intermediate measurements) with integrated quantum computer simulator were implemented. Their practicality in evolving quantum circuits is shown in different experiments for 1-SAT (solutions act like Hogg's algorithm) and the Deutsch-Jozsa problem. These experiments confirm that the evolution of quantum circuits is practically feasible only for sufficiently small problem instances. In this context, scalability and the detection of scalability becomes very important. It is shown that scalable quantum circuits are evolvable to a certain degree: a general quantum circuit can be inferred manually from the evolved solutions for small instances of the given problem. Besides, further experiments indicate that 're-evolution' is effective for the evolution of scalable quantum circuits. With this method the start population of a problem instance is inoculated with evolved solutions for a smaller problem instance. Furthermore, investigations of fitness landscapes and selection strategies are made, with the aim of improving the efficiency of evolutionary search. A notable result is that using the crossover operator damages rather than benefits evolution of quantum circuits.",
• abstract = "Quantenalgorithmen sind hochgradig unintuitiv und einsetzbare Quantenrechner sind (noch) nicht verf{\"{u}}gbar. Dies erschwert den manuellen Entwurf von Quantenalgorithmen und motiviert die Suche nach Techniken zum computerunterst{\"{u}}tzten bzw. automatischen Entwurf. Simulationen von Quantenschaltkreisen (QS) auf konventionellen Rechnern sind aber leider sehr rechenintensiv. Aufgrund der (in der Anzahl der Qubits) exponentiell anwachsenden Kosten ist nur eine Simulation kleiner Quantensysteme (mit wenig Qubits) akzeptabel. Zudem sind die Suchr{\"{a}}ume quasi beliebig gro\ss, worin wohl auch begr{\"{u}}ndet liegt, warum der evolution{\"{a}}re Ansatz bislang nicht zu einem Durchbruch in der Entwicklung neuer Quantenalgorithmen f{\"{u}}hrte. Zum gegenw{\"{a}}rtigen Zeitpunkt muss man sich daher mit der Evolution bekannter (black-box) Quantenalgorithmen begn{\"{u}}gen. Die vorliegende Arbeit pr{\"{a}}sentiert empirische Ergebnisse zur Evolution von QS mit Hilfe des Genetischen Programmierens. F{\"{u}}r die Experimente wurde ein effizienter Quantensimulator entwickelt, der in einem umgebenden GP-System zum Einsatz kommt. Dabei wurden zun{\"{a}}chst linear-tree (erlaubt Zwischenmessungen), sp{\"{a}}ter auch rein lineare Genom-Strukturen f{\"{u}}r die Programmrepr{\"{a}}sentation verwendet. Die Evolvierbarkeit von QS wird an Hand von Experimenten f{\"{u}}r kleine Probleminstanzen des 1-SAT Problems und des Deutsch-Jozsa Problems gezeigt. Die Experimente best{\"{a}}tigen, dass die Evolution von QS nur f{\"{u}}r gen{\"{u}}gend kleine Probleminstanzen praktisch machbar ist. Vor diesem Hintergrund ist gerade die Skalierbarkeit von QS besonders wichtig. Es wird gezeigt, dass skalierbare QS bis zu einem gewissen Grad evolviert werden konnen. Dabei wird ein allgemeiner Schaltkreis von den evolvierten Losungen f{\"{u}}r sehr kleine Probleminstanzen abgeleitet. Die Methode der 'Vorevolution', so belegen weitere Experimente, ist f{\"{u}}r die Evolution skalierbarer QS wirksam einsetzbar. Bei dieser Methode werden der Startpopulation einer Probleminstanz bereits evolvierte Losungen einer kleineren Probleminstanz 'eingeimpft'. Ferner werden Fitnesslandschaften untersucht und ein Vergleich von Selektionsstrategien angestellt, mit dem Ziel, durch diese Erkenntnisse zu einer Effizienzsteigerung der evolution{\"{a}}ren Suche zu gelangen. Dabei ist ein beachtenswertes Resultat, dass die Verwendung eines Crossover Operators der Evolution von QS eher schadet, als ihr n{\"{u}}tzt.",

}

Genetic Programming entries for Andre Leier

Citations