Funding
Funding for our work is provided by the National Science Foundation under the Emerging Models and Technologies program, award 0726554.
1. Introduction
A single quantum bit, which can be implemented by the polarization states of a photon or the spin of a single atom, can exist in a superposition of the binary ``0'' and ``1'' states. This is in contrast to classical bits which implemented to exist in either one of two states, but not a superposition of both. An N-qubit quantum computer can be in a superposition of 2N unique states at any given time. These states can be inter-correlated such that a single logic gate can act on all possible 2N states. The exponential speedup offered by quantum computing, based on the ability to process quantum information through gate manipulation [Deutsch85], has led to several quantum algorithms with substantial advantages over known algorithms with traditional computation. The most significant is Shor's algorithm for factoring the product of two large primes in polynomial time [Shor94]. Additional algorithms include Grover's fast database search; adiabatic solution of optimization; precise clock synchronization; quantum key distribution; and recently, Gauss sums and Pell's equation [Grover96, Childs2002, Chuang2000b, BB84, vandam02a, Hallgren02a2].
The tremendous computational potential of quantum computers is closer than we may think. Despite significant practical difficulties, small quantum devices of 5 to 7 bits have been built in the laboratory [Vandersypen00, Laflamme99]. 100-bit devices are on the drawing table and future technologies promise even greater scalability [Lucent, Kane98]. More importantly, improvements in quantum error correction codes have made possible the Threshold Theorem, according to which, as long as the probability of error of each operation on a quantum computer is less than some constant (estimated to be as high as 10-4), scalable quantum computers can be built using faulty components [Knill98, Preskill98, Aharonov97].
The recent intense interest in quantum computers has focused on Shor's algorithm for prime factorization of large numbers. The security of many modern cryptosystems relies on the seeming intractability of factoring the product of two large primes. In particular, it is easy to show that an efficient algorithm for factoring implies that the widely-used RSA public-key system becomes efficiently breakable. While the best-known factoring algorithms for a classical computer run in exponential time, Shor's algorithm can factor an n-bit integer in O(n3) time (O(n3(log(n))log(5)) with error correction). In 1999, researchers using the Number Field Sieve succeeded in factoring a 512-bit product of two primes (RSA-155) in 8400 MIPS years. A 1024-bit product (RSA-309) would take approximately 1.6 billion times more computation!
Unfortunately, practical quantum architectures needed to achieve such gains have not been well-examined, and the overhead of quantum error correction is very significant. Most of the quantum literature assumes fixed quantum circuit models that only work for one algorithm and one data size. Elementary architectural concepts needed to make quantum computers an engineering reality are still lacking: how do we provide quantum storage, data paths, classical control circuits, parallelism, and system integration? We try to answer these questions in the text that follows while providing some introduction to the state of quantum computation.
2. Large-Scale Quantum Architecture Design Limitations [contents]
A relevant large-scale quantum system must be capable of reaching a system size of S = KQ >= 1012, where K denotes the number of computational steps and Q denotes the number of computational units. This kind of scale is very hard to achieve. Quantum data is inherently very unstable, which leads to a lack of reliable operations that can be performed on it. Also if left idle, this quantum data will interact with its environment and lose state, a process called decoherence. Finally, there is the difficulty of transmitting quantum data between computational units without losing state. This implies that the greatest challenge towards a large, practically useful quantum computer, is designing an architecture that incorporates the required amount of fault-tolerance while minimizing overhead.
Previous work in large-scale quantum architecture [Oskin02, Oskin03, Copsey03] has led to the consideration of several main scalability issues that must be taken into account: reliable and realistic implementation technology; robust error correction and fault-tolerant structures; efficient quantum resource distribution.
1. Reliable and realistic implementation technology: There are multiple approaches from very diverse fields of science for the realization of a full-scale quantum information processor. Solid state technologies, trapped ions, and superconducting quantum computation are just a small number of many physical implementations currently being studied. No matter the choice, any technology used to implement a quantum information processor must adhere to four main requirements [DiVincenzo00]: 1) It must allow the initialization of an arbitrary N-qubit quantum system to a known state. 2) A universal set of quantum operations must be available to manipulate the initialized system and bring it to a desired correlated state. 3) The technology must have the ability to reliably measure the quantum system. 4) It must allow much longer qubit lifetimes than the time of a quantum logic gate. The second requirement encompasses multi-qubit operations; thus, it implies that a quantum architecture must also allow for sufficient and reliable communication between physical qubits.
2. Robust error correction and fault tolerant structures: Due to the high volatility of quantum data, actively stabilizing the system's state through error correction will be one of the most vital operations through the course of a quantum algorithm. Fault tolerance and quantum error correction constitute a significant field of research [Shor95, Steane96, Gottesman96, Aharonov97a] that has produced some very powerful quantum error correcting codes analogous, but fundamentally different from their classical counterparts. The most important result, for our purposes, is the Threshold Theorem [Aharonov97a], which says that an arbitrarily reliable quantum gate can be implemented using only imperfect gates, provided the imperfect gates have failure probability below a certain threshold. This remarkable result is achieved through four steps: using quantum error-correction codes; performing all computations on encoded data; using fault tolerant procedures; and recursively encoding until the desired reliability is obtained. A successful architecture must be carefully designed to minimize the overhead of recursive error correction and be able to accommodate some of the most efficient error correcting codes.
3. Efficient quantum resource distribution: The quantum no-cloning theorem [Zurek] (i.e. the inability to copy quantum data) prevents the ability to place quantum information on a wire, duplicate, and transmit it to another location. Each qubit must be physically transported from the source to the destination. This makes each qubit a physical transmitter of quantum information, a restriction which places great constraints on quantum data distribution. Particularly troublesome is moving the qubits over large distances where it must be constantly ensured the data is safe from corruption. One method is to repeatedly error correct along the channel at a cost of additional error correction resources. Another solution is to use a purely quantum concept to implement a long-range wire [Oskin03]: teleportation [Bennett93a], which has been experimentally demonstrated on a very small scale [Bouwmeester97a, Riebe04, Barrett04]. Teleportation transmits a quantum state between two points without actually sending any quantum data, but rather two bits of classical information for each qubit on both ends.
3. Building Quantum Computers: Ion-Traps [contents]
The short flash video to the left shows a single syndrome extraction with the Steane [7,1,3] error correcting code using a very corny simulation of trapped atomic ions. The error correction circuit can be found in quant-ph/9708021 (the "Overhead ..." paper). The resolution will become better upon pressing "play". The ions on the bottom left colored in green are the seven data ions whose syndrome is to be extracted. The ancillary ions are colored red and the ions verifying the ancilla are colored orange and are positioned on the top right. The first step is for all three groups of seven to encoded themselves into an encoded state by applying the corresponding nine CNOT gates. Next, the orange ions verify the red ancillary ions. Finally, the syndrome is extracted by interacting the red (ancilla) ions with the green data ions and measuring the ancilla.
References [contents]
[Deutsch85]. David Deutsch, ``Quantum Computational Networks'', Proc. Soc. R. Lond. A400, pp. 97-117, 1985.
[Shor94]. Peter. W. Shor, ``Polynomial-Time Algorithms For Prime Factorization and Discrete Logarithms on a Quantum Computer'', 35th Annual Symposium on Foundations of Computer Science, pp. 124-134, 1994.
[Grover96]. L. Grover, ``A Fast Quantum Mechanical Algorithm for Database Search'' Symposium on Theory of Computing - STOC-96, pp. 212-219, 1996.
[Childs2002]. A. M. Childs, E. Farhi, and J. Preskill, ``Robustness of adiabatic quantum computation'', Phys. Rev. A65, 2002, quant-ph/0108048.