The efficiency of compiling high-level quantum algorithms into instruction sets native to quantum computers defines the moment in the future when we will be able to solve interesting and important problems on quantum computers. In my work I focus on the new methods for compiling single qubit operations that appear in many quantum algorithms into single qubit operations natively supported by several popular architectures. In addition, I study several questions related to synthesis and optimization of multiqubit operations. When studying the single qubit case, I consider two native instruction sets. The first one is Clifford+T; it is supported by conventional quantum computers implementing fault tolerance protocols based on concatenated and surface codes, and by topological quantum computers based on Ising anyons. The second instruction set is the one supported by topological quantum computers based on Fibonacci anyons. I show that in both cases one can use the number theoretic structure of the problem and methods of computational algebraic number theory to achieve improvements over the previous state of the art by factors ranging from 10 to 1000 for instances of the problem interesting in practice. This order of improvement might make certain interesting quantum computations possible several years earlier. The work related to multiqubit operations is on exact synthesis and optimization of Clifford+T and Clifford circuits. I show an exact synthesis algorithm for unitaries generated by Clifford+T circuits requiring exponentially less number of gates than previous state of the art. For Clifford circuits two directions are studied: the algorithm for finding optimal circuits acting on a small number of qubits and heuristics for larger circuits optimization. The techniques developed allows one to reduce the size of encoding and decoding circuits for quantum error correcting codes by 40-50\% and also finds their applications in randomized benchmarking protocols.

In this thesis, I describe research results on three topics : (i) a phase transition in the area-law regime of quantum circuits driven by projection measurements; (ii) ultra slow dynamics in two dimensional spin circuits; and (iii) tensor network methods applied to boolean satisfiability problems. (i) Nonuniversal entanglement level statistics in projection-driven quantum circuits; Non-thermalized closed quantum many-body systems have drawn considerable attention, due to their relevance to experimentally controllable quantum systems. In the first part of the thesis, we study the level-spacing statistics in the entanglement spectrum of output states of random universal quantum circuits where, at each time step, qubits are subject to a finite probability of projection onto states of the computational basis. We encounter two phase transitions with increasing projection rate: The first is the volume-to-area law transition observed in quantum circuits with projective measurements; The second separates the pure Poisson level statistics phase at large projective measurement rates from a regime of residual level repulsion in the entanglement spectrum within the area-law phase, characterized by non-universal level spacing statistics that interpolates between the Wigner-Dyson and Poisson distributions. The same behavior is observed in both circuits of random two-qubit unitaries and circuits of universal gates, including the set implemented by Google in its Sycamore circuits. (ii) Ultra-slow dynamics in a translationally invariant spin model for multiplication and factorization; Slow relaxation of glassy systems in the absence of disorder remains one of the most intriguing problems in condensed matter physics. In the second part of the thesis we investigate slow relaxation in a classical model of short-range interacting Ising spins on a translationally invariant two-dimensional lattice that mimics a reversible circuit that, depending on the choice of boundary conditions, either multiplies or factorizes integers. We prove that, for open boundary conditions, the model exhibits no finite-temperature phase transition. Yet we find that it displays glassy dynamics with astronomically slow relaxation times, numerically consistent with a double exponential dependence on the inverse temperature. The slowness of the dynamics arises due to errors that occur during thermal annealing that cost little energy but flip an extensive number of spins. We argue that the energy barrier that needs to be overcome in order to heal such defects scales linearly with the correlation length, which diverges exponentially with inverse temperature, thus yielding the double exponential behavior of the relaxation time. (iii) Reversible circuit embedding on tensor networks for Boolean satisfiability; Finally, in the third part of the thesis we present an embedding of Boolean satisfiability (SAT) problems on a two-dimensional tensor network. The embedding uses reversible circuits encoded into the tensor network whose trace counts the number of solutions of the satisfiability problem. We specifically present the formulation of #2SAT, #3SAT, and #3XORSAT formulas into planar tensor networks. We use a compression-decimation algorithm introduced by us to propagate constraints in the network before coarse-graining the boundary tensors. Iterations of these two steps gradually collapse the network while slowing down the growth of bond dimensions. For the case of #3XORSAT, we show numerically that this procedure recognizes, at least partially, the simplicity of XOR constraints for which it achieves subexponential time to solution. For a #P-complete subset of #2SAT we find that our algorithm scales with size in the same way as state-of-the-art #SAT counters, albeit with a larger prefactor. We find that the compression step performs less efficiently for #3SAT than for #2SAT.

This thesis investigates techniques for the automated optimization of quantum circuits. In the first part we develop an exponential time algorithm for synthesizing minimal depth quantum circuits. We combine this with effective heuristics for reducing the search space, and show how it can be extended to different optimization problems. We then use the algorithm to compute circuits over the Clifford group and T gate for many of the commonly used quantum gates, improving upon the former best known circuits in many cases. In the second part, we present a polynomial time algorithm for the re-synthesis of CNOT and T gate circuits while reducing the number of phase gates and parallelizing them. We then describe different methods for expanding this algorithm to optimize circuits over Clifford and T gates.

This thesis investigates techniques for the automated optimization of quantum circuits. In the first part we develop an exponential time algorithm for synthesizing minimal depth quantum circuits. We combine this with effective heuristics for reducing the search space, and show how it can be extended to different optimization problems. We then use the algorithm to compute circuits over the Clifford group and T gate for many of the commonly used quantum gates, improving upon the former best known circuits in many cases. In the second part, we present a polynomial time algorithm for the re-synthesis of CNOT and T gate circuits while reducing the number of phase gates and parallelizing them. We then describe different methods for expanding this algorithm to optimize circuits over Clifford and T gates.

Doctor of Philosophy / Electrical and Computer Engineering / Sanjoy Das / Quantum circuit synthesis is one of the major areas of current research in the field of quantum computing. Analogous to its Boolean counterpart, the task involves constructing arbitrary quantum gates using only those available within a small set of universal gates that can be realized physically. However, unlike the latter, there are an infinite number of single qubit quantum gates, all of which constitute the special unitary group SU(2). Realizing any given single qubit gate using a given universal gate family is a complex task. Although gates can be synthesized to arbitrary degree of precision as long as the set of finite strings of the gate family is a dense subset of SU(2), it is desirable to accomplish the highest level of precision using only the minimum number of universal gates within the string approximation. Almost all algorithms that have been proposed for this purpose are based on the Solovay-Kitaev algorithm. The crux of the Solovay-Kitaev algorithm is the use of a procedure to decompose a given quantum gate into a pair of group commutators with the pair being synthesized separately. The Solovay-Kitaev algorithm involves group commutator decomposition in a recursive manner, with a direct approximation of a gate into a string of universal gates being performed only at the last level, i.e. in the leaf nodes of the search tree representing the execution of the Solovay-Kitaev algorithm. The main contribution of this research is in integrating conventional optimization procedures within the Solovay-Kitaev algorithm. Two specific directions of research have been studied. Firstly, optimization is incorporated within the group commutator decomposition, so that a more optimal pair of group commutators are obtained. As the degree of precision of the synthesized gate is explicitly minimized by means of this optimization procedure, the enhanced algorithm allows for more accurate quantum gates to be synthesized than what the original Solovay-Kitaev algorithm achieves. Simulation results with random gates indicate that the obtained accuracy is an order of magnitude better than before. Two versions of the new algorithm are examined, with the optimization in the first version being invoked only at the bottom level of Solovay-Kitaev algorithm and when carried out across all levels of the search tree in the next. Extensive simulations show that the second version yields better results despite equivalent computation times. Theoretical analysis of the proposed algorithm is able to provide a more formal, quantitative explanation underlying the experimentally observed phenomena. The other direction of investigation of this research involves formulating the group commutator decomposition in the form of bi-criteria optimization. This phase of research relaxed the equality constraint in the previous approach and with relaxation, a bi-criteria optimization is proposed. This optimization algorithm is new and has been devised primarily when the objective needs to be relaxed in different stages. This bi-criteria approach is able to provide comparably accurate synthesis as the previous approach.

<p>We demonstrate how quantum machine learning might play a vital role in achieving moderate speedups in machine learning problems and might have scope for providing rich models to describe the distribution underlying the observed data. We work with Restricted Boltzmann Machines to demonstrate the same to supervised learning tasks. We compare the relative performance of contrastive divergence with sampling from Dwave annealer on bars and stripes dataset and then on imabalanced network security data set. Later we do training using Quantum Imaginary Time Evolution, that is well suited for the Noisy Intermediate-Scale Quantum era to perform classification on MNIST data set.  </p>

Submitted by Mario BC (mario@bc.ufrpe.br) on 2017-02-08T13:00:48Z No. of bitstreams: 1 Mouglas Eugenio Nasario Gomes.pdf: 2441879 bytes, checksum: 71064821936a79cf37326006ed006c46 (MD5) / Made available in DSpace on 2017-02-08T13:00:48Z (GMT). No. of bitstreams: 1 Mouglas Eugenio Nasario Gomes.pdf: 2441879 bytes, checksum: 71064821936a79cf37326006ed006c46 (MD5) Previous issue date: 2015-07-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This paper presents the LinDCQ tool — a description language and programming quantum circuits — which enables the creation of quantum circuits with calculus of operations performed in parallel on the GPU, using JOCL. The tool also allows the generation of graphically circuit. Used as a mechanism to generate grammars of languages and automata as language recognizer and the regular expression engine. In this context a discussion of the phases of compilers and on quantum computation is presented as well as an explanation of the main technologies used for the development of quantum circuits. LinDCQ The tool consists of: grammar in BNF form (Backus-Naur-Form), the compiler verifies that the incidence of errors in the code to be executed, a graphical interface to facilitate the programming features that allow the construction of the circuit graphically and parallel algorithms JOCL to perform operations that require greater computational cost in the GPU. At the end of an experiment is performed in order to assess the usability of the tool, to thereby ensure a higher level of user acceptance, facilitating interaction thereof with the tool developed in this work. / Este trabalho apresenta a ferramenta LinDCQ - uma linguagem de descrição e programação de circuitos quânticos — a qual possibilita a criação de circuitos quânticos com cálculo das operações realizados de forma paralela na GPU, utilizando JOCL. A ferramenta também permite a geração do circuito de forma gráfica. Utiliza gramáticas como mecanismo na geração de linguagens e autômatos como mecanismo reconhecedor de linguagens e de expressões regulares. Nesse contexto é apresentada uma discussão sobre as fases dos compiladores e sobre a computação quântica, assim como uma explanação sobre as principais tecnologias utilizadas para o desenvolvimento de circuitos quânticos. A ferramenta LinDCQ é composta de: gramática no formato BNF (Backus-Naur-Form), compilador que verifica a incidência de erros no código a ser executado, de uma interface gráfica com características facilitadoras à programação que permite a construção do circuito de forma gráfica e de algoritmos paralelos em JOCL para executar as operações que requerem maior custo computacional na GPU. Ao final é realizado um experimento com o intuito de aferir a usabilidade da ferramenta, para, deste modo, garantir um maior um nível de aceitação do usuário, facilitando a interação do mesmo com a ferramenta desenvolvida nesta dissertação.

We pursue topics in optics that follow three major themes; time averaged dynamics with the associated Effective Hamiltonian theory, quantification and transformation of polarization, and periodicity within quantum circuits. Within the first theme, we develop a technique for finding the dynamical evolution in time of a time averaged density matrix. The result is an equation of evolution that includes an Effective Hamiltonian, as well as decoherence terms that sometimes manifest in a Lindblad-like form. We also apply the theory to examples of the AC Stark Shift and Three-Level Raman Transitions. In the theme of polarization, the most general physical transformation on the polarization state has been represented as an ensemble of Jones matrix transformations, equivalent to a completely positive map on the polarization matrix. This has been directly assumed without proof by most authors. We follow a novel approach to derive this expression from simple physical principles, basic coherence optics and the matrix theory of positive maps. Addressing polarization measurement, we first establish the equivalence of classical polarization and quantum purity, which leads to the identical structure of the Poincar\' and Bloch spheres. We analyze and compare various measures of polarization / purity for general dimensionality proposed in the literature, with a focus on the three dimensional case. % entanglement? In pursuit of the final theme of periodic quantum circuits, we introduce a procedure that synthesizes the circuit for the simplest periodic function that is one-to-one within a single period, of a given period p. Applying this procedure, we synthesize these circuits for p up to five bits. We conjecture that such a circuit will need at most n Toffoli gates, where p is an n-bit number. Moreover, we apply our circuit synthesis to compiled versions of Shor's algorithm, showing that it can create more efficient circuits than ones previously proposed. We provide some new compiled circuits for experimentalists to use in the near future. A layer of "classical compilation" is pointed out as a method to further simplify circuits. Periodic and compiled circuits should be helpful for creating experimental milestones, and for the purposes of validation.

We pursue topics in optics that follow three major themes; time averaged dynamics with the associated Effective Hamiltonian theory, quantification and transformation of polarization, and periodicity within quantum circuits. Within the first theme, we develop a technique for finding the dynamical evolution in time of a time averaged density matrix. The result is an equation of evolution that includes an Effective Hamiltonian, as well as decoherence terms that sometimes manifest in a Lindblad-like form. We also apply the theory to examples of the AC Stark Shift and Three-Level Raman Transitions. In the theme of polarization, the most general physical transformation on the polarization state has been represented as an ensemble of Jones matrix transformations, equivalent to a completely positive map on the polarization matrix. This has been directly assumed without proof by most authors. We follow a novel approach to derive this expression from simple physical principles, basic coherence optics and the matrix theory of positive maps. Addressing polarization measurement, we first establish the equivalence of classical polarization and quantum purity, which leads to the identical structure of the Poincar\' and Bloch spheres. We analyze and compare various measures of polarization / purity for general dimensionality proposed in the literature, with a focus on the three dimensional case. % entanglement? In pursuit of the final theme of periodic quantum circuits, we introduce a procedure that synthesizes the circuit for the simplest periodic function that is one-to-one within a single period, of a given period p. Applying this procedure, we synthesize these circuits for p up to five bits. We conjecture that such a circuit will need at most n Toffoli gates, where p is an n-bit number. Moreover, we apply our circuit synthesis to compiled versions of Shor's algorithm, showing that it can create more efficient circuits than ones previously proposed. We provide some new compiled circuits for experimentalists to use in the near future. A layer of "classical compilation" is pointed out as a method to further simplify circuits. Periodic and compiled circuits should be helpful for creating experimental milestones, and for the purposes of validation.

In this thesis, an evolutionary system for searching quantum operators in the form of unitary matrices is implemented. The aim is to propose several representations of candidate solutions and settings of the evolutionary algorithm. Two evolutionary algorithms were applied: the genetic algorithm and evolutionary strategy. Furthermore, a method of generating a unitary matrix is presented which is used for the first time for this task. This method is in some aspects better than the previous ones. Finally, a comparison of all used techniques is shown in experiments.