Evolution of Quantum Algorithms using Genetic Programming

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.

Quantenalgorithmen sind hochgradig unintuitiv und einsetzbare Quantenrechner sind (noch) nicht verfügbar. Dies erschwert den manuellen Entwurf von Quantenalgorithmen und motiviert die Suche nach Techniken zum computerunterstü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äume quasi beliebig groß,worin wohl auch begründet liegt, warum der evolutionäre Ansatz bislang nicht zu einem Durchbruch in der Entwicklung neuer Quantenalgorithmen führte. Zum gegenwärtigen Zeitpunkt muss man sich daher mit der Evolution bekannter (black-box) Quantenalgorithmen begnügen. Die vorliegende Arbeit präsentiert empirische Ergebnisse zur Evolution von QS mit Hilfe des Genetischen Programmierens. Für die Experimente wurde ein effizienter Quantensimulator entwickelt, der in einem umgebenden GP-System zum Einsatz kommt. Dabei wurden zunächst linear-tree (erlaubt Zwischenmessungen), später auch rein lineare Genom-Strukturen für die Programmrepräsentation verwendet. Die Evolvierbarkeit von QS wird an Hand von Experimenten für kleine Probleminstanzen des 1-SAT Problems und des Deutsch-Jozsa Problems gezeigt. Die Experimente bestätigen, dass die Evolution von QS nur für genü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 können. Dabei wird ein allgemeiner Schaltkreis von den evolvierten Lösungen für sehr kleine Probleminstanzen abgeleitet.Die Methode der 'Vorevolution', so belegen weitere Experimente, ist für die Evolution skalierbarer QS wirksam einsetzbar. Bei dieser Methode werden der Startpopulation einer Probleminstanz bereits evolvierte Lösungen 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ären Suche zu gelangen. Dabei ist ein beachtenswertes Resultat, dass die Verwendung eines Crossover Operators der Evolution von QS eher schadet, als ihr nützt.