Evolution of Quantum Algorithms using Genetic Programming

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

@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.",
  URL =          "https://eldorado.uni-dortmund.de/bitstream/2003/2745/1/Leierunt.pdf",
  URL =          "http://hdl.handle.net/2003/2745",
  address =      "Germany",
  keywords =     "genetic algorithms, genetic programming, Quantum
                 Computing, Quantum Circuits, Evolutionary Circuit
                 Design",
  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