Workloads

So far we have looked at the lower two levels of Figure 2. Before investigating a complete quantum computer architecture, we need to consider the algorithms and programs that will be run on the physical hardware—the workload for the quantum computer. We therefore skip to the top of the stack: quantum programming and quantum algorithms. We are still in the time of Babbage, trying to figure out what Knuth, Lampson, and Torvalds will do with a quantum computer. It has been widely believed that Shor’s factoring algorithm33 and quantum simulation3, 4, 20 will provide the two driving reasons to build machines. There are, however, a number of other useful and interesting quantum algorithms, seven of which are being investigated by teams involved in IARPA’s Quantum Computer Science Program.b Bacon and van Dam1 and Mosca28 have published surveys covering quantum random walks, game theory, linear algebra, group theory, and more. Our understanding of how to design new quantum algorithms that asymptotically outperform classical ones continues to grow, though the number of people who can put the concepts into practice remains small.

Given the applications we have, how large a computer is needed to run them, and how should it be structured? Only a few quantum algorithms have been evaluated for suitability for actual implementation. Shor’s algorithm is commonly used as a benchmark, both for its importance and clarity, and because the arithmetic and quantum Fourier transform on which it is founded are valuable building blocks for other algorithms. 7, 12, 26, 36 Unfortunately, the size and speed of a machine needed to run the algorithm has been widely misunderstood. Architects have suggested a physical machine comprised of high millions to billions of qubits to factor a 2,048-bit number, a size that experimental physicists find staggering. 7, 16, 26, 36

In part because designs for a Shor machine have proven to be intimidatingly large, consensus is building that a Shor machine will not be the first commercially practical system, and interest in designing machines for b http://www.iarpa.gov/solicitations.qcs.html.

The IARP QCS was terminated in April 2013.

quantum chemistry is growing. In a somewhat unexpected result, Brown’s group has shown that certain quantum simulation algorithms expected to be computationally tractable on quantum computers are turning out to have dismayingly large resource requirements. 6 However, the field of quantum simulation is varied, and these simulators remain attractive; they are simply going to take more quantum computational resources (hence, more calendar years to develop and more dollars to deploy) than originally hoped.

A key element of the process of developing applications will be programming tools for quantum computers, and enough language designs were under way by 2005 to warrant a survey with a couple of hundred references. 13 In what are arguably the first examples of true “quantum programming,” as distinct from “quantum algorithm design,” shortly after the publication of Shor’s factoring algorithm, Vedral et al. and Beckman et al. produced detailed descriptions of the circuits (sequences of gate operations) necessary for the modular exponentiation portion of the algorithm, which appeared as a single line in Shor’s original paper. 2, 38 The next step in implementation is to adapt such a description for execution on a particular machine, as in the block marked “Architecture-aware algorithm implementation” in Figure 2. Matching implementation choices to the strengths of the machine, including choosing adder circuits that match the application-level system interconnect, and trading off time and space, will be a collaboration between the programmer and the tools. 37 Maslov and others have studied efficient architecture-aware compilation, 25 an important element in the IARPA program. Compiler backends for specific experimental hardware configurations will soon be important, as will methods for debugging quantum programs in situ.

Quantum system Architectures

Finally we come to the central element
in Figure 2. A complete system design
will specify everything from the “busi-
ness-level” requirements for an algo-
rithm and machine capable of outper-
forming classical computers, through
the details of the algorithm’s imple-
mentation, the strength of error cor-
rection required and type of error man-
agement applied, the corresponding
execution time of logical Toffoli gates
(including the ancilla distillation dis-
cussed earlier), and the microarchitec-
ture of individual areas of the system.

The DiVincenzo criteria are fundamental and necessary, but not sufficient to build a practical large-scale system. Considering instead the issues of quantum computer architecture results in a different focus, highlighting such mundane engineering criteria as being large enough and fast enough to be useful, and small enough and cheap enough to be built. Very loosely, meeting the DiVincenzo criteria can be viewed as the responsibility of experimental physicists, while the latter criteria are the responsibility of computer engineers.

Small-scale quantum architecture can be said to have begun with Lloyd’s 1993 proposal for a molecular chain computer, 23 the first for a potentially buildable device. The word “scalable” attained a permanent position in the lexicon with Kielpinski et al.’s 2002 proposal for an ion trap that can shuffle and manipulate individual atoms, 17 an approach that continues to pay dividends. These ideas and many others for multi-qubit devices, such as the quantum von Neumann approach or scalable ion traps with distinct operation and storage sites, sketch local areas of the system using the technological building blocks, but provide no direct guidance on how to organize large systems that meet the goal of solving one or more problems that are classically intractable.

When considering the macro architecture, certain aspects of the design become clear. Because all of memory is expected to be active, the system will probably not consist of separate CPU and memory banks connected via wide, shared buses. A more uniform array of microarchitecture error correction building blocks is the obvious approach, tempered by issues such as defective devices and the needs of the classical control subsystems. Each of these microarchitecture building blocks may utilize heterogeneous technology with an internal storage/com-putation distinction. 24 Individual chips or ion traps will not be large enough to execute some algorithms (notably Shor) at scale, likely forcing the adoption of a multicomputer structure. 15, 29, 36