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