[eng] This thesis can be classified into the research field of quantum algorithms. A typical paper in this field usually focuses on what kind of things we can do with a quantum computer, whether they are useful or advantageous compared to classical computers, and how we can do it more efficiently. Since the ideal fault-tolerant large-scale quantum computer will not be available soon, many papers focus on noisy intermediate-scale quantum (NISQ) devices, how to characterize them through various benchmarking protocols, and how to make them useful through error mitigation or variational algorithms. Most probably, anyone who ends up opening this thesis is already an expert in certain topics, but they can still find some “out of the box" elements in one chapter or another. The results presented in the thesis might not be directly useful, but hopefully, these elements can provide insights and inspiration. The main body of this thesis is organized into six independent chapters. Each chapter is complete and self-consistent. All these chapters share a similarity: They provide some mathematical ideas of quantum computing in one aspect or another. Since part of the research is conducted in collaboration, the pronoun “we" is used throughout the work. In the first chapter, we focus on actions that transform quantum states into quantum states. We begin with a more theoretical approach. These actions naturally process a group structure. And we ask, under what conditions is this group finite? Given an arbitrary finite group, how can we construct these actions? How can these actions be useful to quantum computing? The set of these actions is named "Quantum representation of finite group," and answers to these questions are provided in the main text. Then, in the second chapter, we switch to a more practical scenario. The inspiration came from a problem that appeared in post-quantum cryptography, the dihedral coset problem, which uses quantum algorithms to recover a secret of the group hidden in quantum states. We simplified this problem and designed an interactive protocol for verifying the computational capacity of a quantum device. Holding a small quantum computer, the verifier prepares quantum state samples that encode a secret and sends them one by one to the prover via a one-way quantum channel. The prover then uses his quantum device to recover the secret with a certain probability. The device’s capacity is then reflected in the accuracy of the solution. This interactive protocol can be used locally on a single device as a benchmarking protocol. In the third chapter, we explore quantum entanglement. We present a new method for visualizing entanglement during a quantum evolution, such as the execution of a quantum algorithm. We name this method "Entanglement trajectory" and show that it can provide a "fingerprint" for each quantum process. We determine the boundaries of these trajectories with Random Matrix Theory and use different examples and entanglement measurements to show that this trajectory has an intrinsic quantum meaning and provides more information about the system. In the fourth chapter, we elaborate on the entanglement presented in a succession of numbers. First, we give a numerical and analytical description of the average entropy of succession, which can provide a standard for studying any successions. Then, we simulate the example of k-almost primes and its unions for different system sizes and explore their particular feature. In the fifth chapter, we will show three different methods of using a quantum annealer to solve Multivariate Quadratic (MQ) problems. In the sixth chapter, we present a data encoder in the fixed Hamming weight subspace, which is parameter-optimal and can be extended to a sparse and binary data encoder. We will give a small summary for each chapter. At the end of this thesis, we will provide an overall conclusion for our readers as “take-home messages".
[eng] This thesis can be classified into the research field of quantum algorithms. A typical paper in this field usually focuses on what kind of things we can do with a quantum computer, whether they are useful or advantageous compared to classical computers, and how we can do it more efficiently. Since the ideal fault-tolerant large-scale quantum computer will not be available soon, many papers focus on noisy intermediate-scale quantum (NISQ) devices, how to characterize them through various benchmarking protocols, and how to make them useful through error mitigation or variational algorithms. Most probably, anyone who ends up opening this thesis is already an expert in certain topics, but they can still find some “out of the box" elements in one chapter or another. The results presented in the thesis might not be directly useful, but hopefully, these elements can provide insights and inspiration. The main body of this thesis is organized into six independent chapters. Each chapter is complete and self-consistent. All these chapters share a similarity: They provide some mathematical ideas of quantum computing in one aspect or another. Since part of the research is conducted in collaboration, the pronoun “we" is used throughout the work. In the first chapter, we focus on actions that transform quantum states into quantum states. We begin with a more theoretical approach. These actions naturally process a group structure. And we ask, under what conditions is this group finite? Given an arbitrary finite group, how can we construct these actions? How can these actions be useful to quantum computing? The set of these actions is named "Quantum representation of finite group," and answers to these questions are provided in the main text. Then, in the second chapter, we switch to a more practical scenario. The inspiration came from a problem that appeared in post-quantum cryptography, the dihedral coset problem, which uses quantum algorithms to recover a secret of the group hidden in quantum states. We simplified this problem and designed an interactive protocol for verifying the computational capacity of a quantum device. Holding a small quantum computer, the verifier prepares quantum state samples that encode a secret and sends them one by one to the prover via a one-way quantum channel. The prover then uses his quantum device to recover the secret with a certain probability. The device’s capacity is then reflected in the accuracy of the solution. This interactive protocol can be used locally on a single device as a benchmarking protocol. In the third chapter, we explore quantum entanglement. We present a new method for visualizing entanglement during a quantum evolution, such as the execution of a quantum algorithm. We name this method "Entanglement trajectory" and show that it can provide a "fingerprint" for each quantum process. We determine the boundaries of these trajectories with Random Matrix Theory and use different examples and entanglement measurements to show that this trajectory has an intrinsic quantum meaning and provides more information about the system. In the fourth chapter, we elaborate on the entanglement presented in a succession of numbers. First, we give a numerical and analytical description of the average entropy of succession, which can provide a standard for studying any successions. Then, we simulate the example of k-almost primes and its unions for different system sizes and explore their particular feature. In the fifth chapter, we will show three different methods of using a quantum annealer to solve Multivariate Quadratic (MQ) problems. In the sixth chapter, we present a data encoder in the fixed Hamming weight subspace, which is parameter-optimal and can be extended to a sparse and binary data encoder. We will give a small summary for each chapter. At the end of this thesis, we will provide an overall conclusion for our readers as “take-home messages".
Quantum computing exists at the intersection of mathematics, physics, chemistry, and engineering; the main goal of quantum computing is the creation of devices and algorithms which use the properties of quantum mechanics to store, manipulate and measure information. There exist many families of algorithms, which, using non-classical logical operations, can outperform traditional, classical algorithms in terms of memory and processing requirements. In addition, quantum computing devices are fundamentally smaller than classical processors and memory elements; since the physical models governing their performance are applicable on all scales, as opposed to classical logic elements, whose underlying principles rely on the macroscopic nature of the device in question. \n \nQuantum algorithms, for the most part, are predicated on a theory of resources. It is often assumed that quantum computers can be placed in a precise fiducial state prior to computation, and that logical operations are perfect, inducing no error on the system which they affect. These assumptions greatly simplify algorithmic design, but are fundamentally unrealistic. In order to justify their use, it is necessary to develop a framework for using a large number of imperfect devices to simulate the action of a perfect device, with some acceptable probability of failure. This is the study of fault-tolerant quantum computing. In order to pursue this study effectively, it is necessary to understand the fundamental nature of generic quantum states and operations, as well as the means by which one can correct quantum errors. Additionally, it is important to attempt to minimize the use of computational resources in achieving error reduction and fault-tolerant computing. \n \nThis thesis is concerned with three projects related to the use of error-prone quantum systems to transmit and manipulate information. The first of these is concerned with the use of imperfectly-prepared states in error-correction routines. Using optimal quantum error correction, we are able to deduce a method of partially protecting encoded quantum information against preparation errors prior to encoding, using no additional qubits. The second of these projects details the search for entangled states which can be used to transmit classical information over quantum channels at a rate superior to classical states. The third of these projects concerns the transcoding of data from one quantum code into another using few ancillary resources. The descriptions of these projects are preceded by a brief introduction to representations of quantum states and channels, for completeness. \n \nThree techniques of general interest are presented in appendices. The first is an introduction to, and a minor advance in the development of optimal error correction codes. The second is a more efficient means of calculating the action of a quantum channel on a given state, given that the channel acts non-trivially only on a subsystem, rather than the entire system. Finally, we include documentation on a software package developed to aid the search for quantum transcoding operations.
It was back in spring 2014 when the author of this doctoral dissertation was finishing its master thesis, whose main objective was the understanding of Peter W. Shor’s most praised result, a quantum algorithm capable of factoring integers in polynomial time. During the development of this master thesis, me and my yet-tobe doctoral advisor studied the main aspects of quantum computing from a purely algebraic perspective. This research eventually evolved into a sufficiently thorough canvas capable of explaining the main aspects and features of the mentioned algorithm from within an undergraduate context. Just after its conclusion, we seated down and elaborated a research plan for a future Ph.D. thesis, which would expectantly involve quantum computing but also a branch of algebra whose apparently innocent definitions hide some really hard problems from a computational perspective: the theory of numerical semigroups. As will be seen later, the definition of numerical semigroup does not involve sophisticated knowledge from any somewhat obscure and distant branch of the tree of mathematics. Nonetheless, a number of combinatorial problems associated with these numerical semigroups are extremely hard to solve, even when the size of the input is relatively small. Some examples of these problems are the calculations of the Frobenius number, the Apéry set, and the Sylvester denumerant, all of them bearing the name of legendary mathematicians. This thesis is the result of our multiple attempts to tackle those combinatorial problems with the help of a hypothetical quantum computer. First, Chapter 2 is devoted to numerical semigroups and computational complexity theory, and is divided into three sections. In Section 2.1, we give the formal definition of a numerical semigroup, along with a description of the main problems involved with them. In Section 2.2, we sketch the fundamental concepts of complexity theory, in order to understand the true significance within the inherent hardness concealed in the resolution of those problems. Finally, in Section 2.3 we prove the computational complexity of the problems we aim to solve. Chapter 3 is the result of our outline of the theory of quantum computing. We give the basic definitions and concepts needed for understanding the particular place that quantum computers occupy in the world of Turing machines, and also the main elements that compose this particular model of computation: quantum bits and quantum entanglement. We also explain the two most common models of quantum computation, namely quantum circuits and adiabatic quantum computers. For all of them we give mathematical definitions, but always having in mind the physical experiments from which they stemmed. Chapter 4 is also about quantum computing, but from an algorithmical perspective. We present the most important quantum algorithms to date in a standardized way, explaining their context, their impact and consequences, while giving a mathematical proof of their correctness and worked-out examples. We begin with the early algorithms of Deutsch, Deutsch-Jozsa, and Simon, and then proceed to explain their importance in the dawn of quantum computation. Then, we describe the major landmarks: Shor’s factoring, Grover’s search, and quantum counting. Chapter 5 is the culmination of all previously explained concepts, as it includes the description of various quantum algorithms capable of solving the main problems inside the branch of numerical semigrops. We present quantum circuit algorithms for the Sylvester denumerant and the numerical semigroup membership, and adiabatic quantum algorithms for the Ap´ery Set and the Frobenius problem. We also describe a C++ library called numsem, specially developed within the context of this doctoral thesis and which helps us to study the computational hardness of all previously explained problems from a classical perspective. This thesis is intended to be autoconclusive at least in the main branches of mathematics in which it is supported; that is to say numerical semigroups, computational complexity theory, and quantum computation. Nevertheless, for the majority of concepts explained here we give references for the interested reader that wants to delve more into them.
The framework of this thesis is fault-tolerant quantum algorithms. Grover's algorithm and quantum walks are described in Chapter 2. We start by highlighting the central role that rotations play in quantum algorithms, explaining Grover's, why it is optimal, and how it may be extended. Key subroutines explained in this area are amplitude amplification and quantum walks, which will constitute useful parts of other algorithms. In the third chapter, in contrast, we turn to the exponential advantages promised by the Fourier transform in the context of the hidden subgroup problem. However, since this application is restricted to cryptography, we later explore its use in quantum linear algebra problems. Here we explain the development of the original quantum linear solver algorithm, its improvements, and finally the dequantization techniques that would often restrict the quantum advantage to polynomial. Chapter 4 is concerned with quantum simulation. We will review classical quantum chemistry techniques, and then focus on Hamiltonian simulation and ground state preparation as the key problems to be solved. Hamiltonian simulation, in particular, will enable the use of quantum phase estimation which computes the eigenvalues or energies of a given quantum state. Given the tradition of our group with error correction, we could not end this thesis without dedicating a final chapter to this topic. Here we explain the most important quantum error correction codes, the surface and color codes, and one extension of the latter, gauge color codes. They will show the complexity of implementing non-Clifford quantum gates, therefore validating their consideration as the bottleneck metric.
In this article, we propose an interactive protocol for one party (the verifier) holding a quantum computer to verify the quantum computation power of another party's (the prover) device via a one-way quantum channel. This protocol is referred to as the dihedral coset problem (DCP) challenge. The verifier needs to prepare quantum states encoding secrets (DCP samples) and send them to the prover. The prover is then tasked with recovering those secrets with a certain accuracy. Numerical simulation demonstrates that this accuracy is sensitive to errors in quantum hardware. Additionally, the DCP challenge serves as a benchmarking protocol for locally fully connected quantum architecture and aims to be performed on current and near-future quantum resources. We conduct a 4-qubit experiment on one of the IBM Q devices.
Quantum computers promise to be a revolutionary new technology. However, in order to realise this promise many hurdles must first be overcome. In this thesis we investigate two such hurdles: the presence of noise in quantum computers and limitations on the connectivity and control in large scale quantum computing architectures.In order to combat noise in quantum devices we must first characterize this noise. To do this several diagnostic tools have been developed over the last two decades. The current industry standard for such a diagnostic tool is called randomized benchmarking. Randomized benchmarking doesn't give a full characterization of the noise afflicting the quantum device but rather attempts to give some indication of of the device's average behavior, captured in a quantity called the average fidelity. Because it does not endeavor to characterize every small detail of the noise it can be efficiently applied even to very large quantum devices. However, with this power also comes increased complexity. Randomized benchmarking has a lot of moving parts, and some fairly strong assumptions must be made in order to guarantee its correctness. In this thesis we attempt to justify these assumptions and if possible remove or weaken them, making randomized benchmarking a more robust and general tool. In chapter 6 of this thesis we investigate the finite statistics of randomized benchmarking. We prove strong bounds on the number of samples needed to perform rigorous randomized benchmarking. To do this we make use tools from representation theory. In particular we use a characterization of certain representations of the Clifford group, which we develop in chapter 5. In chapter 7 we re-use these tools to also bound the number of samples needed to perform rigorous unitarity randomized benchmarking, a newer variant of randomized benchmarking quickly gaining in popularity. These results retroactively justify the use of randomized benchmarking in an experimental setting and also provide guidance on optimal statistical practices in the context of randomized benchmarking. In chapter 8 we expand upon the standard randomized benchmarking protocol and formulate a new class of protocols which we call character randomized benchmarking. This new class of protocols removes a critical assumption made in standard randomized benchmarking, making character randomized benchmarking vastly more generally applicable. To show the advantages of character randomized benchmarking we implement it in an experiment characterizing the noise in a Si/SiGe quantum dot device. This experiment is detailed in chapter 9. Finally we deal with the second main topic of this thesis in chapter 10. Large scale quantum computer will, like classical computers, face limitations in the connectivity between different parts of the computer. This is due to a fundamental law in computer design called Rent's rule, which states that the number of wires connecting a (quantum) computer chip to the outside world is much smaller than the number of components in that chip. This means the individual components of the chip can not be controlled individually in parallel. Given that parallelism is absolutely critical for the functioning of quantum computers this is a serious problem for the development of large scale quantum computers. Luckily it is possible to organize quantum computing devices in such a way that they can be controlled using a relatively small amount of input wires. One example of such an organization is called a crossbar architecture. Recently a proposal was made for a crossbar architecture quantum computer in quantum dots, and in chapter 10 of this thesis we investigate in detail the advantages and disadvantages of such an architecture. We focus in particular on its effect on standard quantum error correction procedures, a key part of a functioning quantum computer, and one where parallel control of all parts of the quantum device is essential.
Algorithms are mathematical procedures developed to solve a problem. When encoded on a computer, algorithms must be "translated" to a series of simple steps, each of which the computer knows how to do. This task is relatively easy to do on a classical computer and we witness the benefits of this success in our everyday life. Quantum mechanics, the physical theory of the very small, promises to enable completely novel architectures of our machines, which will provide specific tasks with higher computing power. Translating and implementing algorithms on quantum computers is hard. However, we will show that solutions to this problem can be found and yield surprising applications to number theory.