This thesis lays down groundwork for researching towards heralding the age of useful quantum computers. It begins with background on quantum graphical calculi, which the work of this PhD has contributed to developing and utilizing. This leads into the first question this PhD research sought to answer: In what ways can quantum graphical calculi facilitate the discovery of new abstractions to close the gaps between algorithms and hardware, and theory and practice? We will focus on what I believe are two of the most promising and fundamental research avenues in this vein. One is quantum error correction, centering on the necessary protocols for quantum algorithms to be realizable on error-prone quantum devices. Building on a fully graphical reformulation of error correcting codes, we introduce a new normal form for Clifford isometries and show its correspondence to stabilizer tableaus. The other is qudit computation, the generalization of qubits (2-level quantum systems) to d-level quantum systems, bringing new possibilities for quantum information processing. To this end, we study the interesting properties of two novel qudit gate sets. One of these gate sets we show is the canonical generalization of the qubit Toffoli+Hadamard gate set to arbitrary prime qudit dimension. We further use these results to solve the multiqutrit exact synthesis problem, advancing the original solution for qubits by Giles and Selinger in 2013. In building upon the foundations in these areas, we seek to uncover paradigm shifts in how we process quantum information.
This thesis lays down groundwork for researching towards heralding the age of useful quantum computers. It begins with background on quantum graphical calculi, which the work of this PhD has contributed to developing and utilizing. This leads into the first question this PhD research sought to answer: In what ways can quantum graphical calculi facilitate the discovery of new abstractions to close the gaps between algorithms and hardware, and theory and practice? We will focus on what I believe are two of the most promising and fundamental research avenues in this vein. One is quantum error correction, centering on the necessary protocols for quantum algorithms to be realizable on error-prone quantum devices. Building on a fully graphical reformulation of error correcting codes, we introduce a new normal form for Clifford isometries and show its correspondence to stabilizer tableaus. The other is qudit computation, the generalization of qubits (2-level quantum systems) to d-level quantum systems, bringing new possibilities for quantum information processing. To this end, we study the interesting properties of two novel qudit gate sets. One of these gate sets we show is the canonical generalization of the qubit Toffoli+Hadamard gate set to arbitrary prime qudit dimension. We further use these results to solve the multiqutrit exact synthesis problem, advancing the original solution for qubits by Giles and Selinger in 2013. In building upon the foundations in these areas, we seek to uncover paradigm shifts in how we process quantum information.
A quantum computer is similar to an ordinary computer, except that instead of bits it uses two-level quantum systems (qubits), and the usual logical operations on bits are replaced with noiseless quantum dynamics in the form of unitary gates or Hamiltonian interactions. Many sets of resources that are universal for quantum computation (that is, capable of implementing any quantum computation) have been found, but general conditions for universality are still only partially understood. Improving our understanding of these conditions contributes to two broad goals. On the one hand, understanding what class of physical systems is suitable for quantum computation allows us choose the systems that are most easily controlled or built in the laboratory. On the other hand, identifying the unifying characteristics of such a class provides insight into the fundamental physics responsible for the much greater computational power of quantum computers. The original results presented in this thesis are a contribution to our understanding of the physical requirements for universal quantum computation. These results lead to the identification of a new, large class of universal dynamics. More specifically, the main problem that is addressed is the following: consider a physical system that is made up of a finite number of qubits that are subject to a natural, fixed interaction described by a two-body Hamiltonian. Suppose we have the ability to control the system only by applying fast one-qubit operations. Under what conditions is this system capable of universal quantum computation? The first original result of the thesis is to prove that universal quantum computation is possible under these conditions given the single extra constraint that the Hamiltonian must entangle, or connect, all of the qubits. In other words, since a two-body Hamiltonian is expressible as a sum of coupling terms each of which acts nontrivially on a pair of qubits, consider the graph whose vertices correspond to qubits and whose edges connect qubits that are coupled by a term in the Hamiltonian. Then this Hamiltonian, together with fast one-qubit unitaries, is universal for quantum computation precisely when the corresponding graph is connected. This result suggests many potential generalizations, three of which are explored in this thesis. The first generalization is to show that the same result holds for a two-body Hamiltonian that acts on D-dimensional quantum systems (qudits), given fast one-qudit unitaries. A second extension is to the case of a many-body Hamiltonian, that is, a Hamiltonian that has coupling terms that act on more than two qubits. Again, we find that under mild restrictions, such Hamiltonians are universal provided they are connected and that arbitrary one-qubit unitaries are available. We also discover and explore some surprising structure in many-body Hamiltonians that is associated with the parity of the couplings. A third related problem that is addressed is the question of what two-qubit unitaries are universal for quantum computation. This problem was originally solved by J.-L. and R. Brylinski [BB02], who gave a technical proof of the universality of any two-qudit gate that is not the swap gate or a product of one-qudit unitaries, given one-qudit unitaries as a free resource. We develop an elementary and constructive proof for the case of qubits, and prove that our construction is very close to optimal in the number of uses of the two-qubit gate. Given a qualitative understanding of what dynamical resources are universal for quantum computation, it is natural to consider developing a quantitative measure of the usefulness of quantum dynamics for quantum information processing. This is done in the final chapter of the thesis, in which the beginnings of a quantitative theory of quantum dynamics are developed.
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. \n \n \nWhen 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. \n \n \nThe 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.
Quantum computation is an exciting and rapidly developing paradigm of computing, which has the potential to improve or accelerate numerous important applications ranging from cryptography to drug discovery. Inspired by these prospects, researchers and engineers across the world have, in recent years, made tremendous advances in building programmable quantum devices. Nevertheless, the size and error rates in state-of-the-art quantum computers are still several orders of magnitude away from those required to achieve computational speedups using existing quantum algorithms. These developments, along with their limitations, motivate us to consider two important questions: First, are there any useful applications in which current or near-term quantum devices can outperform classical computers? Second, can we develop efficient error-correction schemes to suppress the error rates in near-term quantum devices? In this dissertation, we present novel solutions to both of these questions. To address the first question, we identify an important class of problems in condensed-matter physics, namely the identification and characterization of quantum phases of matter, as one promising application of current and near-term quantum information processors. We develop new algorithms for using such quantum devices to solve these problems, and we demonstrate how our methods substantially outperform existing approaches. In addition, we respond to the second question by developing hardware-efficient quantum error correction protocols. By leveraging the distinctive properties and advantages of a given experimental setup to overcome its particular limitations, our proposals significantly reduce the number of quantum bits and operations required for performing quantum error correction and fault-tolerant quantum computation. Together, the works in this dissertation thus pave the way for the near-term realization of quantum computational advantages.
Quantum computing promises to revolutionize several scientific and technological domains through fundamentally new ways of processing information. Among its most compelling applications is digital quantum simulation, where quantum computers are used to replicate the behavior of other quantum systems. This could enable the study of problems that are otherwise intractable on classical computers, transforming fields such as quantum chemistry, condensed matter physics, and materials science. Despite this potential, realizations of practical quantum advantage for relevant problems are hindered by imperfections of current devices. This also affects quantum hardware based on superconducting circuits which is among the most advanced and scalable platforms. The envisaged long-term solution of fault-tolerant quantum computers that correct their own errors remains out of reach mainly due to the associated qubit number overhead. As a result, the field has developed strategies that combine quantum and classical resources, exploit hardware-native operations, and employ error mitigation techniques to extract meaningful results from noisy data. This doctoral thesis contributes to this broader effort by exploring methods for advancing quantum simulation across the full computational stack, including hardware-level innovations, refined techniques for noise modeling and error mitigation, and algorithmic improvements enabled by efficient measurement processing.
Categorical Quantum Mechanics, and graphical calculi in particular, has proven to be an intuitive and powerful way to reason about quantum computing. This work continues the exploration of graphical calculi, inside and outside of the quantum computing setting, by investigating the algebraic structures with which we label diagrams. The initial aim for this was Conjecture Synthesis; the algorithmic process of creating theorems. To this process we introduce a generalisation step, which itself requires the ability to infer and then verify parameterised families of theorems. This thesis introduces such inference and verification frameworks, in doing so forging novel links between graphical calculi and fields such as Algebraic Geometry and Galois Theory. These frameworks inspired further research into the design of graphical calculi, and we introduce two important new calculi here. First is the calculus RING, which is initial among ring-based qubit graphical calculi, and in turn inspired the introduction and classification of phase homomorphism pairs also presented here. The second is the calculus ZQ, an edge-decorated calculus which naturally expresses arbitrary qubit rotations, eliminating the need for non-linear rules such as (EU) of ZX. It is expected that these results will be of use to those creating optimisation schemes and intermediate representations for quantum computing, to those creating new graphical calculi, and for those performing conjecture synthesis.
Quantum computing with qudits, quantum systems with d>2 levels, offers a powerful extension beyond qubits, expanding the computational possibilities of quantum systems, allowing the simplification of the implementation of several algorithms and, possibly, providing a foundation for optimised error correction. In this work, we propose a novel formulation of qudit gates that is universally applicable for any number of levels d, without restrictions on the dimensionality. By extending the mathematical framework of quantum gates to arbitrary dimensions, we derive explicit gate operations that form a universal set for quantum computation on qudits of any size. We demonstrate the validity of our approach through the implementation of the Quantum Fourier Transform (QFT) for arbitrary d, verifying both the correctness and utility of our generalized gates. This novel methodology broadens the design space for quantum algorithms and fault-tolerant architectures, paving the way for advancements in qudit-based quantum computing.