As the complexity of quantum computers increases, typical architectural issues such as communication, layout, and efficient design need to be addressed. This document addresses some basic architectural ideas for quantum computers.
To be useful in reasonable calculations, quantum states will need constant error correction. This need guides how best to lay out physical components to minimize error-correction overhead. I propose a layout that minimizes communication overhead, and discuss the implementation of error-correction algorithms on that layout. I compare the cost overhead of purely local communication to communication by teleportation, and calculate the break-even point at which teleportation becomes efficient.
Additionally, the overhead of error correction can be reduced by using a memory hierarchy to more efficiently store data not currently being computed on. The main requirement is the same as for a classical computer's cache: temporal locality. I show that an important quantum routine can be rearranged to take advantage of a small quantum memory cache, and compute the achieved savings.
In a quantum system, complex operators are built up from the basic operators allowed by a given technology model. I show that the set of operators required to implement any complex operator in an error-corrected system can be approximated to arbitrary precision, given two elementary operators. I give results for all the operators in the set.
Finally, I examine methods to initialize a quantum system. Quantum operators are reversible, so data cannot simply be written over. Instead, initialization entails compressing the entropy of a set of quantum bits into a small subset of those bits, leaving the rest of the bits in a known, non-random state. I examine three such compression algorithms. The best of these itself requires a pool of known states, and so cannot be used directly. The other two algorithms, however, produce less-than-optimal results. I explore why they produce suboptimal results, and propose that one of the suboptimal algorithms be used to compress the entropy of a subsystem, using the resulting known state to run the optimal algorithm.
As the complexity of quantum computers increases, typical architectural issues such as communication, layout, and efficient design need to be addressed. This document addresses some basic architectural ideas for quantum computers.
To be useful in reasonable calculations, quantum states will need constant error correction. This need guides how best to lay out physical components to minimize error-correction overhead. I propose a layout that minimizes communication overhead, and discuss the implementation of error-correction algorithms on that layout. I compare the cost overhead of purely local communication to communication by teleportation, and calculate the break-even point at which teleportation becomes efficient.
Additionally, the overhead of error correction can be reduced by using a memory hierarchy to more efficiently store data not currently being computed on. The main requirement is the same as for a classical computer's cache: temporal locality. I show that an important quantum routine can be rearranged to take advantage of a small quantum memory cache, and compute the achieved savings.
In a quantum system, complex operators are built up from the basic operators allowed by a given technology model. I show that the set of operators required to implement any complex operator in an error-corrected system can be approximated to arbitrary precision, given two elementary operators. I give results for all the operators in the set.
Finally, I examine methods to initialize a quantum system. Quantum operators are reversible, so data cannot simply be written over. Instead, initialization entails compressing the entropy of a set of quantum bits into a small subset of those bits, leaving the rest of the bits in a known, non-random state. I examine three such compression algorithms. The best of these itself requires a pool of known states, and so cannot be used directly. The other two algorithms, however, produce less-than-optimal results. I explore why they produce suboptimal results, and propose that one of the suboptimal algorithms be used to compress the entropy of a subsystem, using the resulting known state to run the optimal algorithm.
Quantum computing is a new and promising technology with the potential of exponentially powerful computation - if only a large-scale one can be built. There are several challenges in building a large-scale quantum computer - fabrication, verification, and architecture. The power of quantum computing comes from the ability to store a complex state in a single bit. This also what makes quantum systems difficult to build, verify, and design. Quantum states are fragile, so fabrication must be precise, and bits must often operate at very low temperatures. Unfortunately, the complete state may not be measured precisely, so verification is difficult. Imagine verifying an operation that is expected to not always get the same answer, but only an answer with a particular probability! Finally, errors occur much more often than with classical computing, making error correction the dominant task that quantum architectures need to perform well. We provide a basic tutorial of quantum computation for the system designer and examine the fundamental design and verification issues in constructing scalable quantum computers. We find the primary issues to be the verification of precise fabrication constraints, the design of quantum communication mechanisms, and the design of classical control circuitry for quantum operation.
Quantum computation has advanced to the point where system-level solutions can help close the gap between emerging quantum technologies and real-world computing requirements. Empirical studies of practical quantum architectures are just beginning to appear in the literature. Elementary architectural concepts are still lacking: How do we provide quantum storage, data paths, classical control circuits, parallelism, and system integration? And, crucially, how can we design architectures to reduce error-correction overhead? The authors describe a proposed architecture that uses code teleportation, quantum memory refresh units, dynamic compilation of quantum programs, and scalable error correction to achieve system-level efficiencies. They assert that their work indicates the underlying technology's reliability is crucial; practical architectures will require quantum technologies with error rates between 10/sup -6/ and 10/sup -9/.
Advances in quantum devices have brought scalable quantum computation closer to reality. We focus on the system-level issues of how quantum devices can be brought together to form a scalable architecture. In particular, we examine promising silicon-based proposals. We discover that communication of quantum data is a critical resource in such proposals. We find that traditional techniques using quantum SWAP gates are exponentially expensive as distances increase and propose quantum teleportation as a means to communicate data over longer distances on a chip. Furthermore, we find that realistic quantum error-correction circuits use a recursive structure that benefits from using teleportation for long-distance communication. We identify a set of important architectural building blocks necessary for constructing scalable communication and computation. Finally, we explore an actual layout scheme for recursive error correction, and demonstrate the exponential growth in communication costs with levels of recursion, and that teleportation limits those costs.
This thesis addresses the design of a quantum computer (QC) architecture. Quantum error correction is a dominant factor as it is required to protect quantum bits (qubits) from decoherence. However, error correction's costs are substantial and call for a scale-up of 100X more qubits and instruction-level parallelism (ILP) on the order of 10,000 simultaneous operations per cycle. These are daunting challenges for a QC architect, who must balance demands in performance, control efficiency, and scalability of design.
Error modeling is important for designing a QC so that error correction implementations and microarchitecture designs may be evaluated for effectiveness. This thesis presents a new deterministic approach to error modeling that is on the order of 1000X faster than previous Monte Carlo error models. While the deterministic error model is memory limited, it is capable of evaluating useful problems containing on the order of a dozen logical qubits encoded in the [[7,1,3]] quantum error correcting code (QECC).
This dissertation presents a new QC processor architecture that leverages highly mobile qubits found in some QC technologies such as electron-spins on liquid helium (eSHe). The processor architecture presented here is designed to efficiently handle at least an order of magnitude more ILP than previously proposed designs, and it accommodates increasing ILP with size and latency costs scaling only linearly. Compilers are also crucial to a computer's performance and efficiency, and this dissertation describes new compiler optimizations including one that reduces hardware requirements by 25% with no performance loss.
Multiple QC processors may be organized into a tiled configuration to provide sufficient ILP across the entire QC. This dissertation proposes a new distributed block tiling strategy that distributes encoded block qubits across arrays of data tiles and offloads non-critical path error correction routines to separate ancilla tiles. This strategy reduces tile capacity requirements by over 100X with the [[21,3,5]] QECC and achieves a simulated speedup of 2.8X for the eSHe QC when compared to the traditional tiling approach.
In summary, this dissertation presents a novel QC architecture and design tools that improve performance and scalability while making efficient use of both control and qubit resources.
Quantum computation has taken over as one of the largest current research areas in computer architecture and information theory. With the potential to make a large number of factorization-based encryption methods obsolete, companies and governments around the globe are racing to build the first large-scale quantum computer. Currently, most quantum computers are noisy intermediate-scale quantum (NISQ), using a relatively small collection of unreliable qubits. While error correction methods exist, they require a large number of ancilla qubits to protect the data qubits which is not practical for use on current NISQ machines. However, following the Dowling-Neven Law, available qubits on a superconducting chip are growing at an exponential rate similar to Moore's Law. Looking toward larger scale quantum machines, we examine a method to increase usable qubit density of quantum machines implementing error correction by using quantum caches that utilize simpler error correction codes. Alternatively, this also allows for the design of reliable systems while meeting the performance and qubit requirements for quantum algorithms. We modify the Qiskit quantum simulation library to work with caches and investigate the effects of region size and topology on the swap characteristics of algorithm execution. We also present our results and discuss recommended topologies for each algorithm. Lastly, we present mix scale-out simulations to examine the impact of cache on future large-scale machines. The default central cache topology gains a maximum performance increase of 2.15 times compared to the worst topology, which creates a robust cache-aware quantum processor layout.
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.