The goal of this work is to understand the application of the evolutionary programming approach to the problem of quantum circuit design. This problem is motivated by the following observations: <ul> <li>In order to keep up with the seemingly insatiable demand for computing power our computing devices will continue to shrink, all the way down to the atomic scale, at which point they become quantum mechanical systems. In fact, this event, known as Moore?s Horizon, is likely to occur in less than 25 years. </li> <li> The recent discovery of several quantum algorithms which can solve some interesting problems more efficiently than any known classical algorithm. </li> <li> While we are not yet certain that quantum computers will ever be practical to build, there do now exist the first few astonishing experimental devices capable of briefly manipulating small quantities of quantum information. The programming of these devices is already a nontrivial problem, and as these devices and their algorithms become more complicated this problem will quickly become a significant challenge. </li> </ul> The Evolutionary Programming (EP) approach to problem solving seeks to mimic the processes of evolutionary biology which have resulted in the awesome complexity of living systems, almost all of which are well beyond our current analysis and engineering capabilities. This approach is motivated by the highly successful application of Koza?s Genetic Programming (GP) approach to a variety of circuit design problems, and specifically the preliminary reports byWilliams and Gray and also Rubinstein who applied GP to quantum circuit design. Accompanying this work is software for evolutionary quantum circuit design which incorporates several advances over previous approaches, including: <ul> <li>A formal language for describing parallel quantum circuits out of an arbitary elementary gate set, including gates with one or more parameters. </li> <li> A fitness assessment procedure that measures both average case fidelity with a respect for global phase equivalences, and implementation cost. </li> <li> A Memetic Programming (MP) based reproductive strategy that uses a combination of global genetic and local memetic searches to effectively search through diverse circuit topologies and optimize the parameterized gates they contain. </li> </ul> Several benchmark experiments are performed on small problems which support the conclusion that Evolutionary Programming is a viable approach to quantum circuit design and that further experiments utilizing more computational resources and more problem insight can be expected to yield many new and interesting quantum circuits.

Chi Wai Ho, Raymond. / Thesis submitted in: December 1999. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2000. / Includes bibliographical references (leaves 93-97). / Abstracts in English and Chinese. / Chapter Chapter 1 --- Introduction --- p.7 / Chapter 1.1 --- Thesis Outline --- p.10 / Chapter 1.2 --- Contribution at a Glance --- p.11 / Chapter Chapter 2 --- Background Concept and Related Work --- p.14 / Chapter 2.1 --- Genetic Algorithms (GAs) --- p.14 / Chapter 2.2 --- The Nature of GAs --- p.16 / Chapter 2.3 --- The Role of Mutation --- p.17 / Chapter 2.4 --- The Role of Crossover --- p.18 / Chapter 2.5 --- The Roles of the Mutation and Crossover Rates --- p.19 / Chapter 2.6 --- Adaptation of the Mutation and Crossover Rates --- p.19 / Chapter 2.7 --- Diversity Control --- p.21 / Chapter 2.8 --- Coarse-grain Parallel Genetic Algorithms --- p.25 / Chapter 2.9 --- Adaptation of Migration Period --- p.26 / Chapter 2.10 --- Serial and Parallel GAs --- p.27 / Chapter 2.11 --- Distributed Java Machine (DJM) --- p.28 / Chapter 2.12 --- Clustering --- p.30 / Chapter Chapter 3 --- Adaptation of the Mutation and Crossover Rates --- p.35 / Chapter 3.1 --- The Probabilistic Rule-based Adaptive Model (PRAM) --- p.35 / Chapter 3.2 --- Time Complexity --- p.37 / Chapter 3.3 --- Storage Complexity --- p.38 / Chapter Chapter 4 --- Diversity Control --- p.39 / Chapter 4.1 --- Repelling --- p.39 / Chapter 4.2 --- Implementation --- p.42 / Chapter 4.3 --- Lazy Repelling --- p.43 / Chapter 4.4 --- Repelling and Lazy Repelling with Deterministic Crowding --- p.43 / Chapter 4.5 --- Comparison of Repelling and Lazy Repelling with Recent Diversity Maintenance Models in Time Complexity --- p.44 / Chapter Chapter 5 --- An Adaptive Parallel Genetic Algorithm --- p.46 / Chapter 5.1 --- A Steady-State Genetic Algorithm --- p.46 / Chapter 5.2 --- An Adaptive Parallel Genetic Algorithm (aPGA) --- p.47 / Chapter 5.3 --- An Adaptive Parallel Genetic Algorithm for Clustering --- p.48 / Chapter 5.4 --- Implementation --- p.48 / Chapter 5.5 --- Time Complexity --- p.51 / Chapter Chapter 6 --- Performance Evaluation of PRAM --- p.52 / Chapter 6.1 --- Solution Quality --- p.58 / Chapter 6.2 --- Efficiency --- p.60 / Chapter 6.3 --- Discussion --- p.62 / Chapter Chapter 7 --- Performance Evaluation of Repelling --- p.66 / Chapter 7.1 --- Performance Comparison of Repelling and Lazy Repelling with Deterministic Crowding --- p.70 / Chapter 7.2 --- Performance Comparison with Recent Diversity Maintenance Models --- p.73 / Chapter 7.3 --- Performance Comparison with Serial and Parallel Gas --- p.75 / Chapter Chapter 8 --- Performance Evaluation of aPGA --- p.78 / Chapter 8.1 --- Scalability of Different Dimensionalities --- p.78 / Chapter 8.2 --- Speedup of Schwefel's function --- p.83 / Chapter 8.3 --- Solution Quality of Clustering Problems --- p.87 / Chapter 8.4 --- Speedup of The Clustering Problem --- p.89 / Chapter Chapter 9 --- Conclusion --- p.91

The goal of this work is to understand the application of the evolutionary programming approach to the problem of quantum circuit design. This problem is motivated by the following observations: <ul> <li>In order to keep up with the seemingly insatiable demand for computing power our computing devices will continue to shrink, all the way down to the atomic scale, at which point they become quantum mechanical systems. In fact, this event, known as Moore?s Horizon, is likely to occur in less than 25 years. </li> <li> The recent discovery of several quantum algorithms which can solve some interesting problems more efficiently than any known classical algorithm. </li> <li> While we are not yet certain that quantum computers will ever be practical to build, there do now exist the first few astonishing experimental devices capable of briefly manipulating small quantities of quantum information. The programming of these devices is already a nontrivial problem, and as these devices and their algorithms become more complicated this problem will quickly become a significant challenge. </li> </ul> The Evolutionary Programming (EP) approach to problem solving seeks to mimic the processes of evolutionary biology which have resulted in the awesome complexity of living systems, almost all of which are well beyond our current analysis and engineering capabilities. This approach is motivated by the highly successful application of Koza?s Genetic Programming (GP) approach to a variety of circuit design problems, and specifically the preliminary reports byWilliams and Gray and also Rubinstein who applied GP to quantum circuit design. Accompanying this work is software for evolutionary quantum circuit design which incorporates several advances over previous approaches, including: <ul> <li>A formal language for describing parallel quantum circuits out of an arbitary elementary gate set, including gates with one or more parameters. </li> <li> A fitness assessment procedure that measures both average case fidelity with a respect for global phase equivalences, and implementation cost. </li> <li> A Memetic Programming (MP) based reproductive strategy that uses a combination of global genetic and local memetic searches to effectively search through diverse circuit topologies and optimize the parameterized gates they contain. </li> </ul> Several benchmark experiments are performed on small problems which support the conclusion that Evolutionary Programming is a viable approach to quantum circuit design and that further experiments utilizing more computational resources and more problem insight can be expected to yield many new and interesting quantum circuits.

Many problems within the biological sciences, such as DNA sequencing, protein structure prediction, and molecular docking, are being approached computationally. These problems require sophisticated solution methods that understand the complex natures of biological domains. Traditionally, such solution methods are problem specific, but recent advances in generic problem-solvers furnish hope for a new breed of computational tools. The challenge is to develop methods that can automatically learn or acquire an understanding of a complex problem domain. Estimation of Distribution Algorithms (EDAs) are generic search methods that use statistical models to learn the structure of a problem domain. EDAs have been successfully applied to many difficult search problems, such as circuit design, optimizing Ising spin glasses, and various scheduling tasks. However, current EDAs contain ad hoc limitations that reduce their capacity to solve hard problems. This dissertation presents a new EDA method, the Markovian Learning Estimation of Distribution Algorithm (MARLEDA), that employs a Markov random field model. The model is learned in a novel way that overcomes previous ad hoc limitations. MARLEDA is shown to perform well on standard benchmark search tasks. A multiobjective extension of MARLEDA is developed for use in predicting the secondary structure of RNA molecules. The extension is shown to produce high-quality predictions in comparison with several contemporary methods, laying the groundwork for a new computational tool for RNA researchers.

This Thesis expands the theoretical research done in the area of evolutionary algorithms. The (1+1)EA is a simple algorithm which allows to gain some insight in the behaviour of these randomized search heuristics. This work shows ways to possible improve on existing bounds. The general good runtime of the algorithm on linear functions is also proven for classes of quadratic functions. These classes are defined by the relative size of the quadratic and the linear weights. One proof of the paper looks at a worst case algorithm which always shows a worst case behaviour than many other functions. This algorithm is used as an upper bound for a lot of different classes. / Department of Computer Science

Thesis (Ph. D.)--George Mason University, 2007. / Title from PDF t.p. (viewed Jan. 22, 2008). Thesis director: Kenneth A. De Jong. Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science. Vita: p. 422. Includes bibliographical references (p. 413-421). Also available in print.

Thesis (Ph. D.)--University of Texas at Austin, 2007. / Vita. Includes bibliographical references.

Thesis (M.C.S.) - Carleton University, 2002. / Includes bibliographical references (p. 144-147). Also available in electronic format on the Internet.

Thesis (M.S.)--Missouri University of Science and Technology, 2008. / Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed June 18, 2009) Includes bibliographical references (p. 62-64).

by Wong Man Leung. / Thesis (Ph.D.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 227-236). / List of Figures --- p.iii / List of Tables --- p.vi / Chapter Chapter 1 : --- Introduction --- p.1 / Chapter 1.1. --- Automatic programming and program induction --- p.1 / Chapter 1.2. --- Motivation --- p.6 / Chapter 1.3. --- Contributions of the research --- p.8 / Chapter 1.4. --- Outline of the thesis --- p.11 / Chapter Chapter 2 : --- An Overview of Evolutionary Algorithms --- p.13 / Chapter 2.1. --- Evolutionary algorithms --- p.13 / Chapter 2.2. --- Genetic Algorithms (GAs) --- p.15 / Chapter 2.2.1. --- The canonical genetic algorithm --- p.16 / Chapter 2.2.1.1. --- Selection methods --- p.21 / Chapter 2.2.1.2. --- Recombination methods --- p.24 / Chapter 2.2.1.3. --- Inversion and Reordering --- p.27 / Chapter 2.2.2. --- Implicit parallelism and the building block hypothesis --- p.28 / Chapter 2.2.3. --- Steady state genetic algorithms --- p.32 / Chapter 2.2.4. --- Hybrid algorithms --- p.33 / Chapter 2.3. --- Genetic Programming (GP) --- p.34 / Chapter 2.3.1. --- Introduction to the traditional GP --- p.34 / Chapter 2.3.2. --- Automatic Defined Function (ADF) --- p.41 / Chapter 2.3.3. --- Module Acquisition (MA) --- p.44 / Chapter 2.3.4. --- Strongly Typed Genetic Programming (STGP) --- p.49 / Chapter 2.4. --- Evolution Strategies (ES) --- p.50 / Chapter 2.5. --- Evolutionary Programming (EP) --- p.55 / Chapter Chapter 3 : --- Inductive Logic Programming --- p.59 / Chapter 3.1. --- Inductive concept learning --- p.59 / Chapter 3.2. --- Inductive Logic Programming (ILP) --- p.62 / Chapter 3.2.1. --- Interactive ILP --- p.64 / Chapter 3.2.2. --- Empirical ILP --- p.65 / Chapter 3.3. --- Techniques and methods of ILP --- p.67 / Chapter Chapter 4 : --- Genetic Logic Programming and Applications --- p.74 / Chapter 4.1. --- Introduction --- p.74 / Chapter 4.2. --- Representations of logic programs --- p.76 / Chapter 4.3. --- Crossover of logic programs --- p.81 / Chapter 4.4. --- Genetic Logic Programming System (GLPS) --- p.87 / Chapter 4.5. --- Applications --- p.90 / Chapter 4.5.1. --- The Winston's arch problem --- p.91 / Chapter 4.5.2. --- The modified Quinlan's network reachability problem --- p.92 / Chapter 4.5.3. --- The factorial problem --- p.95 / Chapter Chapter 5 : --- The logic grammars based genetic programming system (LOGENPRO) --- p.100 / Chapter 5.1. --- Logic grammars --- p.101 / Chapter 5.2. --- Representations of programs --- p.103 / Chapter 5.3. --- Crossover of programs --- p.111 / Chapter 5.4. --- Mutation of programs --- p.126 / Chapter 5.5. --- The evolution process of LOGENPRO --- p.130 / Chapter 5.6. --- Discussion --- p.132 / Chapter Chapter 6 : --- Applications of LOGENPRO --- p.134 / Chapter 6.1. --- Learning functional programs --- p.134 / Chapter 6.1.1. --- Learning S-expressions using LOGENPRO --- p.134 / Chapter 6.1.2. --- The DOT PRODUCT problem --- p.137 / Chapter 6.1.2. --- Learning sub-functions using explicit knowledge --- p.143 / Chapter 6.2. --- Learning logic programs --- p.148 / Chapter 6.2.1. --- Learning logic programs using LOGENPRO --- p.148 / Chapter 6.2.2. --- The Winston's arch problem --- p.151 / Chapter 6.2.3. --- The modified Quinlan's network reachability problem --- p.153 / Chapter 6.2.4. --- The factorial problem --- p.154 / Chapter 6.2.5. --- Discussion --- p.155 / Chapter 6.3. --- Learning programs in C --- p.155 / Chapter Chapter 7 : --- Knowledge Discovery in Databases --- p.159 / Chapter 7.1. --- Inducing decision trees using LOGENPRO --- p.160 / Chapter 7.1.1. --- Decision trees --- p.160 / Chapter 7.1.2. --- Representing decision trees as S-expressions --- p.164 / Chapter 7.1.3. --- The credit screening problem --- p.166 / Chapter 7.1.4. --- The experiment --- p.168 / Chapter 7.2. --- Learning logic program from imperfect data --- p.174 / Chapter 7.2.1. --- The chess endgame problem --- p.177 / Chapter 7.2.2. --- The setup of experiments --- p.178 / Chapter 7.2.3. --- Comparison of LOGENPRO with FOIL --- p.180 / Chapter 7.2.4. --- Comparison of LOGENPRO with BEAM-FOIL --- p.182 / Chapter 7.2.5. --- Comparison of LOGENPRO with mFOILl --- p.183 / Chapter 7.2.6. --- Comparison of LOGENPRO with mFOIL2 --- p.184 / Chapter 7.2.7. --- Comparison of LOGENPRO with mFOIL3 --- p.185 / Chapter 7.2.8. --- Comparison of LOGENPRO with mFOIL4 --- p.186 / Chapter 7.2.9. --- Comparison of LOGENPRO with mFOIL5 --- p.187 / Chapter 7.2.10. --- Discussion --- p.188 / Chapter 7.3. --- Learning programs in Fuzzy Prolog --- p.189 / Chapter Chapter 8 : --- An Adaptive Inductive Logic Programming System --- p.192 / Chapter 8.1. --- Adaptive Inductive Logic Programming --- p.192 / Chapter 8.2. --- A generic top-down ILP algorithm --- p.196 / Chapter 8.3. --- Inducing procedural search biases --- p.200 / Chapter 8.3.1. --- The evolution process --- p.201 / Chapter 8.3.2. --- The experimentation setup --- p.202 / Chapter 8.3.3. --- Fitness calculation --- p.203 / Chapter 8.4. --- Experimentation and evaluations --- p.204 / Chapter 8.4.1. --- The member predicate --- p.205 / Chapter 8.4.2. --- The member predicate in a noisy environment --- p.205 / Chapter 8.4.3. --- The multiply predicate --- p.206 / Chapter 8.4.4. --- The uncle predicate --- p.207 / Chapter 8.5. --- Discussion --- p.208 / Chapter Chapter 9 : --- Conclusion and Future Work --- p.210 / Chapter 9.1. --- Conclusion --- p.210 / Chapter 9.2. --- Future work --- p.217 / Chapter 9.2.1. --- Applying LOGENPRO to discover knowledge from databases --- p.217 / Chapter 9.2.2. --- Learning recursive programs --- p.218 / Chapter 9.2.3. --- Applying LOGENPRO in engineering design --- p.220 / Chapter 9.2.4. --- Exploiting parallelism of evolutionary algorithms --- p.222 / Reference --- p.227 / Appendix A --- p.237