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.

Knowledge compilation improves search-intensive problem-solvers that are easily specified but inefficient. One promising approach improves efficiency by constructing a database of problem-instance/best-action pairs that replace problem-solving search with efficient lookup. The database is constructed by reverse enumeration- expanding the complete search space backwards, from the terminal problem instances. This approach has been used successfully in counter-planning to construct perfect problem-solvers for sub domains of chess and checkers. However, the approach is limited to small problems because both the space needed to store the database and the time needed to generate the database grow exponentially with problem size. This thesis addresses these problems through two mechanisms. First, the space needed is reduced through an abstraction mechanism that is especially suited to counter-planning domains. The search space is abstracted by representing problem states as equivalence classes with respect to the goal achieved and the operators as equivalence classes with respect to how they influence the goals. Second, the time needed is reduced through a hueristic best-first control of the reverse enumeration. Since with larger problems it may be impractical to run the compiler to completion, the search is organized to optimize the tradeoff between the time spent compiling a domain and the coverage achieved over that domain. These two mechanisms are implemented in a system that has been applied to problems in chess and checkers. Empirical results demonstrate both the strengths and weaknesses of the approach. In most problems and 80/20 rule was demonstrated, where a small number of patterns were identified early that covered most of the domain, justifying the use of best-first search. In addition, the method was able to automatically generate a set of abstract rules that had previously required two person-months to hand engineer. / Graduation date: 1992

Thesis (M.S.)--Rochester Institute of Technology, 1983. / Typescript. Includes bibliographical references (leaves 74-78).

Thesis (M.S.)--Ohio University, March, 2004. / Includes bibliographical references (p. 115-122).

Thesis (Ph. D.)--University of Washington, 1996. / Vita. Includes bibliographical references (p. [138]-146).

Thesis (Ph. D.)--University of Wisconsin--Madison, 1970. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references.

Thesis (M.S.)--Ohio University, March, 2004. / Title from PDF t.p. Includes bibliographical references (p. 115-122)

One of the basic requirements of communication protocols in a heterogeneous computer network is a standard external data-transfer representation. Abstract Syntax Notation One (ASN.1) has been widely used in international standard specifications. Its transfer-syntax of Basic Encoding Rules (BER) is applied as the standard external data representation. This thesis presents an efficient BER implementation, called the ED library. The ED library includes a number of encoding and decoding routines that may be used as primitive functions to compose encoders and decoders for arbitrarily complicated ASN.1 data-types. The Performance of the ED library is measured and discussed. Based on the ED library, an ASN.1-C compiler, called CASN1, is designed and implemented to release communication software programmers from the arduous work of translating protocol-defined data-types and constructing their encoders and decoders. Given an ASN.1 protocol specification, CASN1 automatically translates the input ASN.1 modules into C and generates the BER encoders and decoders for the protocol denned data-types. This thesis discusses the design principles, user interface, internal structures, and the implementation and of CASN1. Example applications are given. Both the ED library and CASN1 are implemented in C on UNIX 4.2 BSD using the YACC and LEX tools. / Science, Faculty of / Computer Science, Department of / Graduate

https://dc.etsu.edu/digital-animation-videos-oer/1033/thumbnail.jpg

No description available.