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.

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.

Quantum information processing is of interest as it offers the potential for a new generation of very powerful computers supporting novel computational paradigms. Over the last couple of decades, different aspects of quantum computers ranging from quantum algorithms to quantum physical design have received growing attention. One of the most important research areas is the synthesis and post-synthesis optimization of reversible and quantum circuits. Many synthesis and optimization approaches can be found in the literature, yet, due to the complexity of the problem, finding approaches leading to optimal, or near optimal, results is still an open problem. The synthesized circuits are usually evaluated based on quantum cost models. Therefore, they are often technology mapped to circuits of more primitive gates. To this end, various technology mapping approaches have also been proposed in the past few years. Related work shows an existing gap in optimized technology mapping for reversible and quantum circuits. In this dissertation, an optimized technology mapping design flow is introduced for mapping reversible circuits to quantum circuits. The contributions of this dissertation are classified as follows: - New reversible circuit optimization methods. - Optimized reversible to quantum mapping approaches. - New quantum gate libraries and new cost models for reversible gates based on the new libraries. - Quantum circuit optimization approaches. The steps above, form an optimized flow for mapping reversible circuits to quantum circuits. At each step of the design flow optimized and consistent approaches are suggested with the goal of reducing the quantum cost of the synthesized reversible circuits. The evaluations show that the proposed mapping methodology leads to significant improvement in the quantum cost of the existing benchmark circuits. / Graduate

Thesis (MEng)--Stellenbosch University, 2015. / ENGLISH ABSTRACT: Thorough layout verification of superconductor integrated circuits goes beyond design rule checking and parameter value extraction. The former is used to verify adherence to process design rules, and the latter to determine the element values of components such as inductors and resistors and Josephson junction critical currents. Still, neither gives much warning against subtle layout errors that could result in unintended parasitic elements, or a circuit that does not reflect the original circuit topology. A specialized implementation for Cadence Virtuoso allows layout-versus-schematic verification, but it is limited both to commercial software and in terms of its usefulness. Parameter extraction software such as InductEx is used to extract the component element values of a circuit from its layout if the circuit topology is provided as a netlist, which is mostly created by the designer. However, the element values are extracted for the supplied topology, even if a layout mistake such as creating a connection to the wrong node or a mistake in the netlist results in a model mismatch. After a failed verification, further diagnosis is required to determine whether the error is indeed in the layout or in the input topology - prolonging the verification process significantly. Here we present a free-standing layout-versus-schematic verification toolkit for superconductive integrated circuits, and discuss its implementation after systematically considering the algorithms at its core. We demonstrate results of the layout-versus-schematic verification and how the layout-versus-schematic toolkit is used as a whole in conjunction with InductEx to perform automated parameter extraction for cell-level layout verification. The current version of this toolkit provides the user with three stand-alone tools that are best used in conjunction with InductEx: A GDSII file flattener, a layout-to-schematic netlist extractor (with the option of viewing a pictorial reconstruction of the netlist and schematic) and a netlist comparison tool by which the user can determine whether a layout agrees with an input schematic. We conclude that the netlist comparison and viewing tool provides a valuable method for expediting the layout verification process, making it more efficient and minimizing the chances of mistakes. In its current form the layout-to schematic tool is still limited in that it cannot yet fully support circuits with mutual coupling. Although many improvements can still be made to this toolkit, the implemented version of these tools can already provide great benefit to Rapid Single Flux quantum (RSFQ) cell designers. / AFRIKAANSE OPSOMMING: Deeglike uitleg verifikasie van supergeleier geïntegreerde stroombane strek verder as bloot die nasien van ontwerpreëls en die onttrekking van parameter waardes. Eersgenoemde word gebruik om vas te stel of daar voldoen word aan die proses se ontwerpreëls, en laasgenoemde om die waardes van komponente soos induktors en resistors en die kritiese strome van Josephson aansluitings te bepaal. Nogtans bied nie een van hulle veel waarskuwing teen subtiele uitlegfoute wat onbeplande parasitiese elemente kan veroorsaak nie, of teen ‘n stroombaan wat nie die oorspronklike stroombaan topologie weerspieël nie. ‘n Gespesialiseerde implementasie van Cadence Virtuoso maak LVS (layout-versus-schematic) verifikasie moontlik, maar dit is beperk tot kommersiële sagteware en ook beperk in terme van bruikbaarheid. Parameter onttrekking sagteware soos InductEx word gebruik om waardes van die komponent-elemente van ‘n stroombaan vanuit die uitleg te onttrek wanneeer die stroombaan topologie as ‘n netlist, wat meestal deur die ontwerper geskep is, voorsien word. Die elementwaardes word egter onttrek volgens die topologie wat verskaf is, al is daar uitlegfoute, soos byvoorbeeld wanneer ‘n koppeling met ‘n verkeerde node plaasvind, of wanneer daar netlist foute is wat modelteenstrydighede veroorsaak. Na ‘n mislukte verifikasie poging word verdere diagnostiese stappe gedoen om te bepaal of die fout in die uitleg lê, of in die spesifieke topologie wat verskaf is, wat natuurlik die verifikasieproses aansienlik verleng. Hier stel ons ‘n vrystaande LVS verifikasie sagteware-pakket vir supergeleier geïntegreerde stroombane bekend, en bespreek, deur middel van die algoritmes wat die kern daarvan uitmaak, die implementering van hierdie sagteware-toestel. Ons bied die resultate van die LVS verifikasie aan en wys hoe die LVS sagteware toestel as geheel saam met InductEx gebruik kan word om automatiese parameter uittrekking vir sel-vlak uitleg verifikasie te berwerkstellig. Die huidige weergawe van die pakket bied die verbruiker drie alleenstaande programme wat verkieslik saam met InductEx gebruik moet word: ‘n GDSII “file flattener”, ‘n uitleg-tot-schematiese diagram netlist ekstraktor (met die opsie om ‘n herkonstruktueerde beeld van netlist en skematiese diagram te besigtig) en ‘n netlist vergelyking toestel waarmee die verbruiker kan vasstel of ‘n uitleg met ‘n oorspronklike skematiese diagram ooreenstem. Ons lei af dat die netlist vergelyking toestel ‘n waardevolle metode bied om die uitleg verifikasie proses te bespoedig en vergemaklik en die kanse van foute te minimaliseer. In sy huidige vorm is die uitleg-tot-skematiese diagram toestel beperk omdat dit nog nie stroombane met koppeling kan steun nie.

Since they were first envisioned, quantum computers have oft been portrayed as devices of limitless power, able to perform calculations in a mere instant that would take current computers years to determine. This is, of course, not the case. A huge amount of effort has been invested in trying to understand the limits of quantum computers---under which circumstances they outperform classical computers, how large a speed-up can be gained, and what draws the distinction between quantum and classical computing. In this Ph.D. thesis, I investigate a few intriguing properties of quantum computers involving quantum oracles and classically-simulatable quantum circuits. In Part I I study the notion of black-box unitary operations, and procedures for effecting the inverse operation. Part II looks at how quantum oracles can be used to test properties of probability distributions, and Part III considers classes of quantum circuits that can be simulated efficiently on a classical computer. In more detail, Part I studies procedures for inverting black-box unitary operations. Known techniques are generally limited in some way, often requiring ancilla systems, working only for restricted sets of operators, or simply being too inefficient. We develop a novel procedure without these limitations, and show how it can be applied to lift a requirement of the Solovay-Kitaev theorem, a landmark theorem of quantum compiling. Part II looks at property testing for probability distributions, and in particular considers a special type of access known as the \textit{conditional oracle}. The classical conditional oracle was developed by Canonne et al. in 2015 and subsequently greatly explored. We develop a quantum version of this oracle, and show that it has advantages over the classical process. We use this oracle to develop an algorithm that decides whether or not a mixed state is fully mixed. In Part III we study classically-simulatable quantum circuits in more depth. Two well-known classes are Clifford circuits and matchgate circuits, which we briefly review. Using these as inspiration, we use the Jordan-Wigner transform to develop new classes of non-trivial quantum circuits that are also classically simulatable.

In this thesis, I present a microscopic theory of quantum circuits based on interacting electron spins in quantum dot molecules. We use the Linear Combination of Harmonic Orbitals-Configuration Interaction (LCHO-CI) formalism for microscopic calculations. We then derive effective Hubbard, t-J, and Heisenberg models. These models are used to predict the electronic, spin and transport properties of a triple quantum dot molecule (TQDM) as a function of topology, gate configuration, bias and magnetic field. With these theoretical tools and fully characterized TQDMs, we propose the following applications: 1. Voltage tunable qubit encoded in the chiral states of a half-filled TQDM. We show how to perform single qubit operations by pulsing voltages. We propose the "chirality-to-charge" conversion as the measurement scheme and demonstrate the robustness of the chirality-encoded qubit due to charge fluctuations. We derive an effective qubit-qubit Hamiltonian and demonstrate the two-qubit gate. This provides all the necessary operations for a quantum computer built with chirality-encoded qubits. 2. Berry's phase. We explore the prospect of geometric quantum computing with chirality-encoded qubit. We construct a Herzberg circuit in the voltage space and show the accumulation of Berry's phase. 3. Macroscopic quantum states on a semiconductor chip. We consider a linear chain of TQDMs, each with 4 electrons, obtained by nanostructuring a metallic gate in a field effect transistor. We theoretically show that the low energy spectrum of the chain maps onto that of a spin-1 chain. Hence, we show that macroscopic quantum states, protected by a Haldane gap from the continuum, emerge. In order to minimize decoherence of electron spin qubits, we consider using electron spins in the p orbitals of the valence band (valence holes) as qubits. We develop a theory of valence hole qubit within the 4-band k.p model. We show that static magnetic fields can be used to perform single qubit operations. We also show that the qubit-qubit interactions are sensitive to the geometry of a quantum dot network. For vertical qubit arrays, we predict that there exists an optimal qubit separation suitable for the voltage control of qubit-qubit interactions.

In this thesis, I present a microscopic theory of quantum circuits based on interacting electron spins in quantum dot molecules. We use the Linear Combination of Harmonic Orbitals-Configuration Interaction (LCHO-CI) formalism for microscopic calculations. We then derive effective Hubbard, t-J, and Heisenberg models. These models are used to predict the electronic, spin and transport properties of a triple quantum dot molecule (TQDM) as a function of topology, gate configuration, bias and magnetic field. With these theoretical tools and fully characterized TQDMs, we propose the following applications: 1. Voltage tunable qubit encoded in the chiral states of a half-filled TQDM. We show how to perform single qubit operations by pulsing voltages. We propose the "chirality-to-charge" conversion as the measurement scheme and demonstrate the robustness of the chirality-encoded qubit due to charge fluctuations. We derive an effective qubit-qubit Hamiltonian and demonstrate the two-qubit gate. This provides all the necessary operations for a quantum computer built with chirality-encoded qubits. 2. Berry's phase. We explore the prospect of geometric quantum computing with chirality-encoded qubit. We construct a Herzberg circuit in the voltage space and show the accumulation of Berry's phase. 3. Macroscopic quantum states on a semiconductor chip. We consider a linear chain of TQDMs, each with 4 electrons, obtained by nanostructuring a metallic gate in a field effect transistor. We theoretically show that the low energy spectrum of the chain maps onto that of a spin-1 chain. Hence, we show that macroscopic quantum states, protected by a Haldane gap from the continuum, emerge. In order to minimize decoherence of electron spin qubits, we consider using electron spins in the p orbitals of the valence band (valence holes) as qubits. We develop a theory of valence hole qubit within the 4-band k.p model. We show that static magnetic fields can be used to perform single qubit operations. We also show that the qubit-qubit interactions are sensitive to the geometry of a quantum dot network. For vertical qubit arrays, we predict that there exists an optimal qubit separation suitable for the voltage control of qubit-qubit interactions.

In this thesis, I present a microscopic theory of quantum circuits based on interacting electron spins in quantum dot molecules. We use the Linear Combination of Harmonic Orbitals-Configuration Interaction (LCHO-CI) formalism for microscopic calculations. We then derive effective Hubbard, t-J, and Heisenberg models. These models are used to predict the electronic, spin and transport properties of a triple quantum dot molecule (TQDM) as a function of topology, gate configuration, bias and magnetic field. With these theoretical tools and fully characterized TQDMs, we propose the following applications: 1. Voltage tunable qubit encoded in the chiral states of a half-filled TQDM. We show how to perform single qubit operations by pulsing voltages. We propose the "chirality-to-charge" conversion as the measurement scheme and demonstrate the robustness of the chirality-encoded qubit due to charge fluctuations. We derive an effective qubit-qubit Hamiltonian and demonstrate the two-qubit gate. This provides all the necessary operations for a quantum computer built with chirality-encoded qubits. 2. Berry's phase. We explore the prospect of geometric quantum computing with chirality-encoded qubit. We construct a Herzberg circuit in the voltage space and show the accumulation of Berry's phase. 3. Macroscopic quantum states on a semiconductor chip. We consider a linear chain of TQDMs, each with 4 electrons, obtained by nanostructuring a metallic gate in a field effect transistor. We theoretically show that the low energy spectrum of the chain maps onto that of a spin-1 chain. Hence, we show that macroscopic quantum states, protected by a Haldane gap from the continuum, emerge. In order to minimize decoherence of electron spin qubits, we consider using electron spins in the p orbitals of the valence band (valence holes) as qubits. We develop a theory of valence hole qubit within the 4-band k.p model. We show that static magnetic fields can be used to perform single qubit operations. We also show that the qubit-qubit interactions are sensitive to the geometry of a quantum dot network. For vertical qubit arrays, we predict that there exists an optimal qubit separation suitable for the voltage control of qubit-qubit interactions.

This thesis deals with a series of quantum computer implementation issues from the Kane 31P in 28Si architecture to Shor’s integer factoring algorithm and beyond. The discussion begins with simulations of the adiabatic Kane CNOT and readout gates, followed by linear nearest neighbor implementations of 5-qubit quantum error correction with and without fast measurement. A linear nearest neighbor circuit implementing Shor’s algorithm is presented, then modified to remove the need for exponentially small rotation gates. Finally, a method of constructing optimal approximations of arbitrary single-qubit fault-tolerant gates is described and applied to the specific case of the remaining rotation gates required by Shor’s algorithm.

Simuladores quânticos têm tido um importante papel no estudo e desenvolvimento da computação quântica ao longo dos anos. A simulação de algoritmos quânticos em computadores clássicos é computacionalmente difícil, principalmente devido à natureza paralela dos sistemas quânticos. Para acelerar essas simulações, alguns trabalhos propõem usar hardware paralelo programável como FPGAs, o que diminui consideravelmente o tempo de execução. Contudo, essa abordagem tem três problemas principais: pouca escalabilidade, já que apenas transfere a complexidade do domínio do tempo para o domínio do espaço; a necessidade de re-síntese a cada mudança no algoritmo; e o esforço extra ao projetar o código RTL para simulação. Para lidar com esses problemas, uma arquitetura de um co-processador SIMD é proposta, cujas operações das portas quânticas está baseada no modelo Network of Butterflies. Com isso, eliminamos a necessidade de re-síntese com mudanças pequenas no algoritmo quântico simulado, e eliminamos a influência de um dos fatores que levam ao crescimento exponencial do uso de recursos da FPGA. Adicionamente, desenvolvemos uma ferramenta para geração automática do código RTL sintetizável do co-processador, reduzindo assim o esforço extra de projeto. / Quantum simulators have had a important role on the studying and development of quantum computing throughout the years. The simulation of quantum algorithms on classical computers is computationally hard, mainly due to the parallel nature of quantum systems. To speed up these simulations, some works have proposed to use programmable parallel hardware such as FPGAs, which considerably shorten the execution time. However this approach has three main problems: low scalability, since it only transfers the complexity from time domain to space domain; the need of re-synthesis on every change on the algorithm; and the extra effort on designing the RTL code for simulation. To handle these problems, an architecture of a SIMD co-processor is proposed, whose operations of quantum gates are based on Network of Butterflies model. Thus, we eliminate the need of re-synthesis on small changes on the simulated quantum algorithm, and we eliminated the influence of one of the factors that lead to the exponential growth on the consumption of FPGA resources. Aditionally, we developed a tool to automatically generate the synthesizable RTL code of the co-processor, thus reducing the extra design effort.