Extended Abstracts Submitted by the AQUATeam to AQIS 2010
August 4, 2010
1. Takahiko Satoh and Rodney Van Meter, “Path Selection in Heterogeneous Quantum Networks”
2. Luciano Aparicio and Rodney Van Meter, “Multiplexing in Quantum Repeater
Networks”
3. Byung-Soo Choi and Rodney Van Meter, “A Quantum Adder on a Two-Dimensional
Qubit Array Architecture”
4. Clare Horsman, Simon Devitt, and Rodney Van Meter, “Algorithm Optimisation
for Topological Measurement-Based Quantum Computing”
5. Cody Jones, Austin G. Fowler, Jungsang Kim, Thaddeus D. Ladd, Rodney Van
Meter, and Yoshihisa Yamamoto, “A Layered Architecture for Quantum Computing using Optically-Controlled Quantum Dots”
6. Shota Nagayama and Rodney Van Meter, “Defective Qubits in Surface CodeQuantum Computation on a Fixed Lattice”
7. Rodney Van Meter, Thaddeus D. Ladd, Austin G. Fowler, and Yoshihisa Yamamoto, “Heterogeneous Interconnects in a Semiconductor Nanophotonic Surface Code Quantum Computer”

1Path Selection in Heterogeneous Quantum Networks
Takahiko Satoh1 ∗1Rodney Van Meter2 †Department of Computer Science, Graduate School of Information Science and Technology,
the University of Tokyo,
7-3-1, Hongo, Bunkyo-ku, Tokyo, Japan.
2
Faculty of Environment and Information Studies,
Keio University,
5322 Endo, Fujisawa-city, Kanagawa, Japan.

Abstract. To date, research on entangled quantum networks has primarily focused on an abstract model
consisting of a linear chain of repeaters, with a power of two number of hops of identical length and quality.
We are analyzing the behavior of more complex network topologies. In such conﬁgurations, path selectionaﬀects both the performance of individual connections and global network load. We propose a deﬁnition
for link cost and a form of Dijkstra’s algorithm for ranking candidate paths to maximize the throughput of
end-to-end connections. Simulations conﬁrm agreement between the calculated path cost and the expected
throughput.
Keywords: Quantum repeater, quantum network, path selection algorithm

1

Introduction

Networks of quantum repeaters use puriﬁcation andentanglement swapping to create high-ﬁdelity end-to-end
Bell pairs which are then used in distributed quantum
applications [1, 2]. In entanglement swapping, two distributed Bell pairs are spliced together where they meet,creating one longer-distance pair from two shorter ones.
For homogeneous paths of 2n hops, quantum repeaters
operate well using a simple doubling of distance for eachentanglement swap. In real-world networks, candidate
paths will have diﬀering numbers of hops of varying quality, as in Fig. 1. On such heterogeneous paths, we mustreconsider when and where entanglement swapping takes
place, and devise an algorithm for ranking paths. We
use the inverse of single-hop throughput as our link cost.
Path cost, as in Dijkstra’s algorithm [3], is the sum of thelink costs in the path. We have extended our quantum
network simulator to calculate the throughput of end-toend connections for heterogeneous links.

2

Background

2.1

Quantum Repeaters

Quantum repeaters use single-hop quantum links and aseries of classical messages to forge end-to-end entangled
Bell pairs. The responsibility for puriﬁcation and swapping can be divided into layers (shown in Appendix A),
communicating across diﬀerent subsets of the repeaters
in the path. The throughput is known to decline polynomially with distance, though the complexities of limited
systems make it diﬃcult to create an analytic expression
for the throughput.
2.2

Networking

Path selection is important in all networks. In quantum networks, a small diﬀerence in path quality can cause∗satoh@is.s.u-tokyo.ac.jp† rdv@sfc.wide.ad.jp

Figure 1: Real-world quantum networks will oﬀer multiple heterogeneous paths between communication end
points, necessitating a mechanism for path selection.

a large diﬀerence in throughput. Dijkstra’s algorithm isa powerful technique used extensively in the Internet forsolving the path selection problem. In this algorithm,
path cost is Σci , where ci is the cost assigned to linki. The goal of Dijkstra is minimization of global work,
rather than maximization of throughput for any speciﬁc
communication session, but in practice there is a strong
correlation between those two goals.
2.3

Problem Deﬁnition

Naturally, lower path quality will reduce both the ﬁdelity of end-to-end entanglement and the throughput ofa given path, but we do not know the exact relationshipbetween path quality and throughput. We wish to deﬁnea cost for each path, allowing us to order a set of paths
so that low-cost paths better meet our goals for the overall system. Here, we choose maximizing throughput as
our goal, meaning that high-bandwidth paths (measured
in high-ﬁdelity Bell pairs per second) should have a low
cost. To achieve this, we need both a way to establish

50
40
30

(1)

10

As in classical Dijkstra, our quantum Dijkstra (which wecall qDijkstra) deﬁnes path cost as the sum of the linkcosts.

0maximum single-hop throughput
single-hop purif ied throughput

20

Our proposed algorithm is a direct adaptation of Dijkstra’s algorithm to quantum networks. We have examined several possible candidates for link cost, including
link base entanglement ﬁdelity and loss (either linear orin dB). Our calculations suggest that deﬁning link costbased on throughput when used as a single hop repeater
works well. We normalize across the whole network, giving

Linkcost =4

Results

In our simulations, we used four diﬀerent link qualities with the qubus entanglement mechanism, which usesbright pulses and weak non-linear eﬀects [4]. Qubus ishighly sensitive to loss, so we simulate 20 km opticalﬁber links assuming 0.17 dB/km loss, plus an additional
system loss factor.

12

Linkcost

To determine link cost, we simulated a single hop fora variety of loss values. We selected four values to be
our link types, as shown in Table 1. For simplicity, as
described above, we have normalized the link costs relative to the highest-throughput link. Further details arepresented in Appendix B.
Table 1: Linkcost

path quality
Excellent (2)Good (◦)
Fair (4)Poor (×)

4.2

dBloss(dB/20 km)
3.4
3.5
3.6
3.7

throughput(qubits/sec)
176.7
137.9
118.5
95.6

linkcost
1
1.28
1.49
1.84

Veriﬁcation of algorithm

We tested sixteen types of 8-hop paths, with heterogeneous links in the ﬁrst half of the path and homogeneous, excellent links in the second half, and compared
simulated throughput and qDijkstra’s cost. The results,plotted in Fig. 2, conﬁrm a strong relationship between
throughput and path score.

11

10

9

8

7

Path cost
Figure 2: Throughput and the inverse of path cost foreight-hop paths. The symbols °, 4 and × correspondto the weakest link in the path, good, fair, and poor links,
respectively. Further details are presented in Appendix
C.

5
4.1

No Fair or Poor links
Contains Fair link
Contains Poor link60
6Quantum Dijkstra
throughput (qubit/second)

3

70
0

the cost for a single link, and a way to calculate path costfrom a set of link costs.

Discussion

Our simulations show that classical networking techniques can be readily adapted to quantum repeater networks. As in classical networks, the throughput of asingle path will approach the throughput of the lowestquality link, as shown by the grouping of the symbols
in Fig. 2. Dijkstra’s algorithm, in both classical andquantum networks, gives reasonable but not perfect ordering of candidate paths. Using qDijkstra, we can accurately choose the best path without the prohibitive expense of enumerating and simulating all of the possible
paths through large networks. These results give us reason for optimism about the diﬃculty of quantum network
design and a clear direction for achieving that goal.

Acknowledgements
This work was supported by JSPS KAKENHI
21500020. The authors thank François Le Gall for useful
discussions.

References[1] H.-J. Briegel, W. Dür, J.I. Cirac, and P. Zoller. Quantum Repeaters: the Role of Imperfect Local Operations in Quantum Communication Physical Review
Letters, volume 81, pages 5932–5935, 1998.
[2] C. H. Bennett, G. Brassard, C. Crépeau, R. Josza,
and A. Peres, W. Wootters. Teleporting an unknown
quantum state via dual classical and EPR channels

200

Physical Review Letters, volume 70, pages 1895–1899,
1993.

150
0

[5] Rodney Van Meter, Thaddeus D. Ladd, W. J. Munro,
and Kae Nemoto. System Design for a Long-Line
Quantum Repeater. IEEE/ACM Transactions on
Networking, volume 17, number 3, pages 1002–1013,
June 2009. 10.1109/TNET.2008.927260.

3.4

A

3.6

3.8

4.0

4.2

4.4

dBlossQuantum Network

A conceptual diagram of the protocol layers necessary
for a quantum network is shown in Fig. 3 [5].

Fair
Poor

100

[4] T. D. Ladd, P. van Loock, K. Nemoto, and W. J.
Munro, Y. Yamamoto. Hybrid quantum repeater
based on dispersive CQED interaction between matter qubits and bright coherent light New Journal of
Physics, volume 8, pages 184, 2006.

ExcellentGood

50

throughput (qubit/second)[3] Dijkstra, EW. A note on two problems in connexion with graphs. Numerische Mathematik, volume 1,
number 1, pages 269-71. Springer, 1959.

Figure 4: Single-hop simulation, used to deﬁne linkcost.

C

Throughput of 8-hop Paths

The details of our simulated 8-hop paths are shown in
Table 3. The string of symbols indicates the type andorder of links in the path.
Table 3: Details of measurement

Figure 3: Protocol layers for quantum repeaters.

B

Throughput of a Single Hop Path

Table 2 and Fig. 4 are the simulation environmentand results used to establish our link cost for a single
hop. The four link types chosen for more complex paths
are marked in the ﬁgure with the corresponding symbols.
Table 2: Measurement environment of Linkcost
Quantum Repeater
Number of qubits
25 qubits
per repeater link connection
Number of application qubits
200 qubits
teleported (length of simulation)
Optical Fiber
Length20 km
Information losses
3.4∼4.4 dB/20 km

Path combination
22222222
2◦222222◦2222222
24222222
22◦◦2222
2◦2422222◦◦◦2222
2×222222◦2◦42222◦◦◦22222
24×22222◦42×2222
×2×22222
44442222
4××22222
××××2222

Throughput
64.2278
61.5261
53.8885
48.141255.3664
50.634255.579738.157647.3658
52.592338.9788
43.000742.399447.16340.2496
41.5825

Path cost
8
8.28
8.28
8.49
8.56
8.77
8.84
8.84
9.05
9.12
9.33
9.61
9.68
9.96
10.17
11.36

Multiplexing in Quantum Repeater Networks
Luciano Aparicio1 ∗1Rodney Van Meter2 †Graduate School of Information Science and Technology, The University of Tokyo
7-3-1, Hongo, Bunkyo-ku, Tokyo 113-8656, Japan.
2
Faculty of Environment and Information Studies, Keio University5322, Endo, Fujisawa, Kanagawa, 252-0882 Japan

Abstract. Existing research has investigated quantum repeater networks only in abstract, ideal settings.
We are considering a more realistic approach and context, including complex technologies with multiple
connections competing for resources. For these scenarios, we are comparing several different classicalmultiplexing schemes using simulation, measuring the aggregate throughput and fairness for each of them.
Preliminary results suggest that round-robin use of a congested link gives the highest aggregate throughput.
Keywords: quantum networks, quantum repeaters, multiplexing

1

Introduction

Applications that use distributed quantum properties,
such as QKD (Quantum Key Distribution), have the limitation that the fidelity of quantum states and the probability of success decrease with distance, making the usage of these systems for long distances almost impossible. Therefore, researchers have proposed the designof quantum repeater networks [1] which would maintain distributed quantum states across greater distances.
Although some researchers are investigating approaches
that are substantially different from entanglement swapping [2], here we focus on swapping.
In classical networks, stations are usually competingfor shared resources, the service is offered on a best effort basis, and the path selection is a difficult task handled by many different routing algorithms. Quantum networks will not be an exception. Based on analogy withthe classical model, to solve the shared resources issues,
we propose quantum multiplexing and evaluate several
schemes which we are simulating.

2

Background

2.1

Quantum Networks

The process of designing quantum networks is similar
to designing classical networks, as they require detailed
protocol designs, including finite states machines to control physical resources (qubit entanglement, purificationand entanglement swapping in order to maintain adequate fidelity and allow teleportation of qubits from one
station to another). Proposed protocols [3] are composedof layers in analogy to the OSI model. We give a brief
description of each of them and the functions which are
simulated.
The physical layer represents the physical interactionthat creates Bell pairs between two different stations.
Our simulations model the qubus mechanism [4] in whichlaser pulses of many photons generate low-fidelity Bellpairs with high probability.
∗lucho@hongo.wide.ad.jp† rdv@sfc.wide.ad.jp

Figure 1: Multiplexed use of a congested link in a dumbbell network raises aggregate throughput compared topure circuit switching.
The second layer, EC (Entanglement Control), is responsible for managing the single-hop physical entanglement process, utilizing classical messages. Once the entanglement is confirmed, this layer will transfer controlof the Bell pair to a higher protocol layer.
The third layer, PC (Purification Control), is responsible for the purification of the entangled pairs. For single
hops, after the PC layer confirms a good fidelity for the
Bell pairs, control is given to the application layer, which
will start the teleportation of the data qubit that we wish
to send.
For networks which have more than two stations, further steps are required. ESC (Entanglement Swapping
Control) is the layer responsible for choosing two Bellpairs from two different stations and performing the Bellstate measurement that splices the two short Bell pairs
into a longer one. After this is concluded, once again the
PC layer executes purification to improve the fidelity ofthis new Bell pair. ESC and PC are repeated until wehave an end-to-end Bell pair of sufficient fidelity for ourapplication.

2.2

Multiplexing

For a quantum network of more than two end nodes wemay have to consider sharing a channel between different
stations. Therefore, a way to control the resource allocation must be provided. In this work, we want to provethat classical multiplexing strategies can also be applied
to quantum networks. Different multiplexing schemes,such as statistical multiplexing (packet switching), circuit switching, TDM (Time Division Multiplexing) andspatial multiplexing have been studied and compared.
Statistical multiplexing (packet switching) is used in
IP networks, as a best effort service.
Circuit switching, used in standard telephony service,reserves a complete circuit for one connection and noother traffic is allowed to use those resources at the sametime. When the connection is finished, the circuit is released, allowing other stations to transmit.
TDM will assign resources in a time slot round-robinfashion for each station that requests a connection. Everystation will wait its turn to transmit, and if a station is
not ready to use the channel on its turn, the resources gounused.
In spatial multiplexing, some resources (e.g., buffer
space) are assigned to one connection.

3

Quantum Repeater Multiplexing

Each of the multiplexing schemes can be used fairly
directly in repeater networks. The principal operational
difference between classical and quantum is that entanglement swapping is a truly distributed stochastic computation, with state held at each station along the path.
The natural model would therefore be circuit switching,but our analysis suggests that round-robin TDM on thecongested link brings benefits.
Figure 1 shows a sequence of entanglement, purification and entanglement swapping steps, multiplexing useof the central link in the dumbbell network. Straight lines
represent single-hop Bell pairs, and their thickness represents fidelity. In step 1, all the links have one low-fidelity
Bell pair. In step 2, entanglement swapping is done, and
A and B become entangled (spring line). Meanwhile, fidelity is improved for the links EC and FD using new
base pairs and purification. In step 3, new Bell pairs are
obtained for AE, EF and FB, while fidelity keeps increasing for CE and FD as in step 2. In step 4, entanglement
swapping is done for C and D, but in this case with better end-to-end fidelity than in step 2 due to the higher
fidelity on the uncongested links.

4

Simulations

For the case of the dumbbell network studied, one link
is shared. This link has many resources (qubits to be used
for creating Bell pairs), which allows us to implement
different types of multiplexing schemes. In this topology,
station A sends traffic to B, and at the same time station
C sends traffic to D.
For the simulations, we are using Omnet++ 4.0, a
C++-based network simulator. Each station is config-

ured to have 8 qubits for each link connecting to otherstations. Once single-hop Bell pairs are created, entanglement swapping is done in two places, in order to create
an end-to-end Bell pair, which will be immediately usedby the application.
We are simulating a restricted case of the qubus repeater. For 10km links with 0.17dB/km loss, simulations
show that the basic qubus mechanism should producebase entangled pairs of F = 0.769 with probability 36%.
Three rounds of purification will then improve fidelity fora single hop in the following manner: (0.769+0.769)⇒
0.872, (0.872 + 0.872) ⇒ 0.951, (0.951 + 0.951) ⇒ 0.982.
For each hop, three successful rounds of purification
requires eight base-fidelity Bell pairs. Once entanglement
swapping is done, fidelity drops to a value that is roughly
the product of the fidelity of each hop. For two hops it
would be around 0.964 and for three hops 0.947.
The parameters which are measured are the aggregate
throughput (minimum time to complete the workload)
and fairness (how much time one connection makes theothers wait).

5

Discussion

From this research, we can see that classical multiplexing presents us with a possible approach to handle theproblem of shared resources in quantum networks. Multiplexing use of congested links while uncongested links
continue purification gives higher throughput than pure
circuits switching. Our simulations are being extended tolarger networks and more complex traffic patterns, which
we believe will demonstrate more distinct differences between the types of multiplexing. Future work will also
include quantum effects for the determination of the fidelity, instead of the classical aproximation of this work.

6

Acknowledgements

LA acknowledges funding from MEXT. This work was
supported by JSPS KAKENHI 21500020.

References[1] W. Dür, H.-J. Briegel, J. I. Cirac, P. Zoller. Quantum
repeaters based on entanglement purification. Physical Review A, Volume 59, Number 1. 1999.
[2] W. J. Munro, K. A. Harrison, A. Stephens, S. Devitt, and K. Nemoto. From quantum fusiliers tohigh-performance networks. (2009) Arxiv preprint
arXiv:0910.4038.
[3] Rodney Van Meter, Thaddeus D. Ladd, W. J. Munro,
Kae Nemoto. System Design for a Long-Line Quantum Repeater. IEEE/ACM Transactions on Networking, Vol. 17, NO. 3, June 2009.
[4] P. van Loock, T. D. Ladd, K. Sanaka, F. Yamaguchi,
K. Nemoto, W. J. Munro, and Y. Yamamoto. Hybrid
quantum repeater using bright coherent light. Phys.
Rev. Lett., vol. 96, p. 240501, 2006.

A Quantum Adder on a Two-Dimensional Qubit Array Architecture
Byung-Soo Choi1 ∗ †1Rodney Van Meter2 ‡Department of Electronics Engineering, Ewha Womans University, Seoul, Republic of Korea (South Korea)
2
Faculty of Environment and Information Studies, Keio University, Fujisawa, Japan
Abstract. We propose a quantum adder on a two-dimensional
qubit array architecture with nearest√neighbor interaction. The depth of our new adder is O( n) where n is the size of input, which is asymptotically optimal. The size is O(n). When the input size is larger than 58, our new adder can work fasterthan the simple embedding of ripple-carry adders designed for one-dimensional systems.
Keywords: Quantum Architecture, Quantum Adder, Depth Lower Bound, Interaction Distance1

Motivation

Theoretically, quantum information processing systems will show higher performance than classical ones
in some areas [1]. Although this property drives us todesign and implement a scalable quantum computer, thecurrent state of the art is far from achieving a practical quantum computer. Since any information processing system is not a single device, it has to utilize many
components, from high-level software packages to devicelevel libraries. In this study, we focus on one important
subsystem, the arithmetic circuit. To design quantum
arithmetic circuits, many researchers have exploited conventional classical arithmetic circuits such as the ripplecarry adder, the carry-lookahead adder, and the conditional sum adder [2, 3, 4, 5]. The quantum Fourier transform adder, in contrast, is genuinely based on quantum
eﬀects [6].
Unfortunately, most of these adders are based on someideal model of a quantum computer which may not bephysically realizable, such as assuming no limitation oninteraction distance. Although studies with such optimistic assumptions will give us more conﬁdence about
the speedup of a quantum computer, they are still notprecise enough to tell us the exact performance gain, andsometimes to diﬃcult are match to a chosen architecture.
In this work, we focus on addition under more practicalassumptions, such as a two-dimensional layout of qubits
allowing nearest-neighbor interaction only, and supporting only two-qubit gates with concurrent execution, amodel we call 2D NTC. Speciﬁcally, the two-dimensionallayout of qubits can serve as a reasonable model for manytechnologies with fabrication, wiring, and control constraints. Because the input size of quantum gates is limited to one or two qubits, Toﬀoli gates must be broken
down into smaller components. Surprisingly, for this architecture model, no speciﬁc quantum adder has been
proposed. Van√ Meter and Oskin indicated that an adderwould be O( n) in time complexity on the 2D architecture, but no circuit was provided [7].
∗bschoi3@gmail.com† To whom any correspondence should be addressed.
‡ rdv@sfc.wide.ad.jp

2

Summary of Contribution

In this work, we propose a new quantum adder on the
2D NTC architecture. More speciﬁcally, we contributeas follows:• Propose a 2D NTC adder. We propose a 2D
NTC adder, based on a combination of a ripplecarry adder and a carry-lookahead circuit, arrangedin three phases. In the ﬁrst phase, the ﬁrst column executes a simple ripple carry addition andthe other columns do carry lookahead operations
to generate inter-column carry lookahead information. In the second phase, the carry output of theﬁrst column is propagated to the other columns sequentially to generate incoming carry for the corresponding column. In the last step, the incoming
carry value for each column is propagated throughthe rows to generate carry values, and hence ﬁnallyto generate summation values for each bit position.
Once the third phase completes, the sum is copied
out and the addition circuit is reversed to clean all
ancillae.
• Analyze storage requirements. The necessary√
number of qubits for our adder is 5n − n + 1,
inputs, ancillae, and copy out of results, as shownin Table 1. To work as concurrently as possible,
our adder utilizes about twice the number of qubits
compared to 1D NTC adders.
• Analyze depth and compare with otheradders. The depth of other adders is recalculated
based on the same physical constraints. The chosenadders for certain architectures and their depths areshown in Table 2. Based on the coeﬃcients of each
1D NTC adder, our adder works faster when the
input size is larger than 58.
• Compare KQ values. As discussed in Ref. [8],an important measure of the required resources isthe product of the depth and size. Based on thisanalysis, we ﬁnd when the input size is larger than446, our adder is better than 1D NTC adders.
For more details of our adder and its analysis, pleaserefer to the Appendix.

Table 1: Required Number of QubitsNameaibi → pi → si|0⟩ → gi → G[i, j] → ci

Number of qubitsnnn|0⟩ → P [i, j]
Column carryk
Sub Total
For Copy of Sum
Total√
n−2 n+1√n√(2n + 1)+(2n − n)n√5n − n + 1

Explanation
Input A
Input B, Carry propagate for i-th position, and Summation S
Carry generation for i-th position, Carry generation between i and j, and carryfor i-th position
Carry propagation between i and j
Inter column carry. The last Column carry is for the final carry output.
Mandatory + Additional

Table 2: Depth and KQ, in Comparison with Other Adders
Architecture

1D NTC
2D NTCAC

3

Name of Adder(Depth, Number of Qubits)

VBE[9]
VBE-Improved[4]
CDKM[3]Present Adder
QFT-based[6]CLA-based[5]RCA+CLA-based[10](76n − 30, 3n + 1)
(20n − 15, 3n + 1)
(18n + 14, 2n + 2)√√
(152 n − 104, 5n − n + 1)
(3 log n, 2n + 1)
(2 log n + 2, 4n − log n)(10 log n + 6n/log n, n + 4n/log n)Future WorkWhen is the present adder fasterthan the corresponding adder?
n>2
n > 48n > 58
N/A
N/A
N/A

KQ[8]
228n2 + α1
60n2 + α2
36n2 + α3√760n n + α46n log n
8n log n
10n log nmunications and Computer Sciences, E92.A(5):1276–1283,
2009.

Our new adder is the ﬁrst design for a 2D NTC architecture, to the best of our knowledge, but we believe
there is still room for improvement.
First, the number of gates added to the fundamental addition circuit is very large. Most of the gates areused for local shuﬄing of qubits to neighboring positions
so that gates can be executed. This shuﬄing increases
with the distance between qubits which have information
dependency. Therefore, by arranging qubits in a better
way, it may be possible to reduce the necessary numberof operations.
Second, the phase for cleaning ancillae qubits doubles
the number of quantum operations. In our adder, theancillae qubits are re-initialized by applying the inverse
circuit. Perhaps there would be a way to reduce suchdrawback by exploiting overlapping of the clearing phasewith the computation phase.
Third, the number of ancillae qubits is also very large.
Although our design uses additional ancillae in order toexploit parallel execution, this increases the depth as anegative eﬀect and hence has to be minimized as well.
The tradeoﬀ between the depth and qubits may yet yieldadditional gains.

[10] Yoshinori Kawata, Satoshi Yayu, and Shuichi Ueno. An efficient quantum addition circuit : Extended abstract. IEICE Technical Report. Circuits and systems, 107(527):95–96,
March 2008.

Acknowledgements[11] Byung-Soo Choi and Rodney Van Meter. Effects of interaction
distance on quantum addition circuits. http://arxiv.org/
abs/0809.4317, 2008.

This research is supported by the Japan Society for
the Promotion of Science (JSPS) through its “Funding
Program for World-Leading Innovative R&D on Scienceand Technology (FIRST Program).”

References[1] Michele Mosca. Quantum algorithms.
abs/0808.0369, 2008.

http://arxiv.org/[2] Yasuhiro Takahashi. Quantum arithmetic circuits: A survey.
IEICE Transactions on Fundamentals of Electronics, Com-

[3] Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, andDavid Petrie Moulton. A new quantum ripple-carry addition
circuit. http://arxiv.org/abs/quant-ph/0410184, 2004.
[4] Rodney Van Meter and Kohei M. Itoh. Fast quantum modular
exponentiation. Phys. Rev. A, 71(5):052320, May 2005.
[5] Thomas G. Draper, Samuel A. Kutin, Eric M. Rains, andKrysta M. Svore.
A logarithmic-depth quantum carrylookahead adder. http://arxiv.org/abs/quant-ph/0406142,
2004.
[6] Thomas G. Draper. Addition on a quantum computer. http://arxiv.org/abs/quant-ph/0008033, 2000.
[7] Rodney Van Meter and Mark Oskin. Architectural implications of quantum computing technologies. ACM Journal
on Emerging Technologies in Computing Systems, 2(1):31–63,
2006.
[8] Andrew M. Steane.
Overhead and noise threshold offault-tolerant quantum error correction.
Phys. Rev. A,
68(4):042322, Oct 2003.
[9] Vlatko Vedral, Adriano Barenco, and Artur Ekert. Quantum
networks for elementary arithmetic operations. Phys. Rev. A,
54(1):147–153, Jul 1996.

a n +1a ( n − 2 ) n +1

a ( n −1) n +1

b1

b n +1b( n − 2 ) n + 1b( n −1) n +1

a2

a n +2a( n −2) n + 2

a ( n −1) n + 2

a1

a n+1

a n−2 n+1

a n−1 n+1

b2

b n +2b( n − 2 ) n + 2b( n −1) n + 2

b1

b n+1

b n−2 n+1

b n−1 n+1

a2

a n+2

a n−2 n+2

a n−1 n+2

b2

b n+2

b n−2 n+2

b n−1 n+2

a n −1a 2 n −1a ( n −1) n −1

a n n −1b n −1b2 n −1b( n −1) n −1

b n n −1

a n

a2 n

a ( n −1) n

a n n

b n

b2 n

b( n −1) nb n nHigher order qubits

Lower order qubits

RippleCarry
Additiona1

Figure 1: Layout of Input QubitsFirst, generate gi and pi at the same time
Second, generate Gi and Pi sequentiallya n−1a2 n−1

a n−1 n−1

a n n−1b n−1

b2 n−1b n−1 n−1

b n n−1ana2 na n−1 n

an n

b2 n

b n−1 nbn nbnAppendicesA

DesignA.1

Layout of Qubits

The layout of qubits for our new adder on a 2D NTC
architectureis shown in Figure∑n∑n 1. Two input registers
A = i=1 2i−1 ai and B = i=1 2i−1 bi are interleaved in
the square lattice structure. To create√ a compact layout,
the size of rows
andcolumnsisn (for simplicity, we√
assume that n is an integer). Although other qubits arenecessary for addition, which are used for intermediatestorage for information dependency, they are not shownfor simplicity. Since the overall depth heavily depends on
the location of input qubits, the nearest neighbor layoutof input qubits is best.
A.2

Three Phases

The adder consists of three phases: ripple carry addition and generation of carry lookahead information; generation of inter-column carry inputs; and generation ofcarry value for each position and summation.
In the ﬁrst phase, as shown in Figure 2, the ﬁrst column
does ripple carry addition, and the other columns generate carry lookahead information for the corresponding
column. Therefore,
in the ﬁrst column, the summation si√
for i = 1 . . . n are generated, and the ﬁnal carry output
Col carry1 = c√n is also generated, which will be used
for the second phase. Meanwhile, carry lookahead information for the corresponding column can be extracted
by generating gi = ai · bi and pi = ai ⊕ bi simultaneously,
and
√ √
√ √
G[⌊i/ n⌋ n + 1, i] = gi ⊕ pi · G[⌊i/ n⌋ n + 1, i − 1],√ √√ √P [⌊i/ n⌋ n + 1, i] = pi · P [⌊i/ n⌋ n + 1, i − 1]√
sequentially, where i > n. Brieﬂy, gi indicates thatthe i-th position inputs generates carry output regardless of incoming carry, since both inputs are set toone. Likewise, pi indicates that the i-th position inputs
cannot generate carry output, but propagate incoming
carry into carrysince only one of inputs sets√
√ output,
to one. G[⌊i/ n⌋ √n +√1, i] indicates that the subset
of inputs from (⌊i/ n⌋ n + 1) to i-th position generates carry output regardless of the incoming carry for

Figure 2: First Phase√ √√ √the (⌊i/ n⌋ n + 1)-th position.
P [⌊i/ n⌋ n + 1, i] in√ √dicates that inputs from (⌊i/ n⌋ n + 1) to i-th position
cannot generate carry√ √output, but propagate the incoming carry for (⌊i/ n⌋ n + 1)-th position. Note
√ that forthe ﬁrst rowofeach
column,
i.e.,
when
i
=
k
n + 1 for√k = 1, . . . , n − 1, G and P are simply√ √√ √G[⌊i/ n⌋ n + 1, ⌊i/ n⌋ n + 1] = gi ,√ √√ √P [⌊i/ n⌋ n + 1, ⌊i/ n⌋ n + 1] = pi .
It is worth emphasizing
last row√ that√ G and P√for the √for eachcolumn,
G[⌊i/
n⌋
n
+
1,
(⌊i/
n⌋
+
1)
n] and√ √√√P [⌊i/ n⌋ n + 1, (⌊i/ n⌋ + 1) n], encompass all carrylookahead information for the corresponding column because of ripples of G and P between rows. Therefore,
when the incoming carry value for the corresponding column is known, the corresponding column can decide theﬁnal carry out, which is the incoming carry value for the
next column.
In the second phase, the ﬁnal carry output of the ﬁrst
column Col carry1 = c√n is propagated to the second
column to generate the carry output Col carry2 . As
shown in Figure 3, the inter-column carry is evaluatedby the following equation:√√
Col carryj = G[(j − 1) n + 1, j n]√√
⊕Col carryj−1 · P [(j − 1) n + 1, j n].
After this phase, all columns have outgoingcarry value√
Col carryj = cj √n , where j = 1, . . . , n, which are used
for incoming carry for the (j +1)-th column, respectively.
In the third phase, the incoming carry value for thecorresponding column is propagated up each column, as
shown in Figure 4, to generate the incoming carry value
ci for each bit position√ √ci = G[⌊i/ n⌋ n + 1, i]√ √⊕Col carry⌊i/√n⌋√n · P [⌊i/ n⌋ n + 1, i],√√where i = k n+2, . . . , (k +1) n. The ﬁnal carry outputof the summation cn is set to Col carry√n . After thisripple, each position generates the summation value, si =ai ⊕ bi ⊕ ci .

a n +1a1a( n−2) n+1a( n−1) n+1

b1

b n+1

b( n−2) n+1b( n−1) n+1

a2

a n+2

a( n−2) n+2a( n−1) n+2

b2

b n +2b( n−2) n+2b( n−1) n+2

a n−1

a2 n−1a( n−1) n−1

a n n−1b n−1

b2 n−1b( n−1) n−1

b n n−1ana2 na( n−1) n

an n

bn

b2 n

b( n−1) n

bn n

col-carrycol-carry

Column-level carry propagation

Figure 3: Second Phase
First, transport Column_carry
Second, generate ci for each position
Third, generate si for each position

a1

a n+1

a( n−2) n+1a( n−1) n+1

b1

b n+1

b( n−2) n+1b( n−1) n+1

a2

a n+2

a( n−2) n+2a( n−1) n+2

b2

b n+2

b( n−2) n+2b( n−1) n+2

a n−1

a2 n−1a( n−1) n−1

a n n−1b n−1

b2 n−1b( n−1) n−1

b n n−1ana2 na( n−1) n

an n

bn

b2 n

b( n−1) n

bn n

Figure 4: Third Phase
To clear the ancillae qubits, the circuit has to copy out
all of the summation values into other qubits, and thenapply the inverse of the addition circuit.

B

Analysis

For fast computation, it is necessary to exploit parallelism as thoroughly as possible. Often, this requires
the use of additional spatial resources. The storage requirements for our new adder are shown√ in Table 1. The
additional number of qubits is 2n − n. For clearing
ancillae, we need to copy the summation output to theadditional qubits, adding √n qubits. Therefore, the total
number of qubits is 5n − n + 1.
When only interactions between neighboring qubits areallowed, the depth of an arithmetic circuit increases. Forthe√2D case, the depth lower bound√ was proved to be
adder
exhibits
O(n) depth since eachΩ( n) [11]. Our√
phase needs O( n) unit time steps. Therefore, our adderis asymptotically optimal for the 2D NTC architecture.
However, it is necessary to compare to other adders designed for the 1D NTC architecture, since they can be
implemented on the 2D NTC architecture without mod-iﬁcation.
In the ﬁrst phase of our adder, there are two ﬂows, one
for the ﬁrst column and the other for other columns. For
calculating the depth we assume only one-input and two
input gates with unit time delay. The depth of the ﬁrst
columnis the sum of the delay of one√ half adder and of√n − 1 full adders, for a total of 26 n − 16. The othercolumns√need a constant delay for generating gi and pi
and O( n√− 1) for generating G[i, j] and P [i, j], for a
total of 36 n − 26. Since the “long pole” determines√ theexecution time, the depth for the ﬁrst phase
is
36
n−26.
√
n
−
1
columnIn the second phase, we have to execute√
carry generation√circuits, needing 18 n − 18 delay. In
the third phase, n − 1 carry generation circuits must be
executed sequentially, followedby the summation circuit.
√
The delay for this√is 21 n − 8. Overall the depth of thethecircuit body is 75 n−52.
√ Next, our adder has to copy √results, using another n swap operations, adding 3 ndelay. Finally, it must undo√the overall computation.
Hence, the whole depth is 152 n − 104.
The overall analysis and the comparison between theadders are shown in Table 2. The ﬁrst column lists the architecture for adders, and the second column some adders
for each architecture. For the 1D NTC architecture, wechose three typical adders. Vedral et al. proposed a plain
adder based on the ripple carry [9], named VBE in thetable. To improve the performance of VBE, Van Meter and Itoh proposed another version, VBE-Improved[4]. Cuccaro et al. proposed a ripple carry adder with
only one ancillae qubit [3], named CDKM. For the 2D
NTC architecture, our adder is shown. For the architecture with arbitrary distance interaction and concurrent execution (AC), several adders have been proposed.
Draper proposed a quantum Fourier transform adder [6],named QFT-based. By exploiting the classical fast addition algorithm, Draper et al. also proposed a carrylookahead adder [5], named CLA-based. Kawata et al.
also proposed an adder based on the combination of ripple carry adder and carry lookahead adder [10], named
RCA+CLA-based.
For comparison, the depth and the size of each adderis shown in the third column. In this work, the depth
is measured in units of one- and two-qubit gates for the
1D and 2D NTC architectures. The depth for AC architecture is based on one-, two-, and CCNOT gates. Notethat numbers for AC architecture are not directly comparable because a Toﬀoli gate is assumed to cost only asingle time step, and long-distance gates are allowed. In
the fourth column, the input size is shown for which ouradder works faster than the corresponding adder.
In the ﬁfth column, we list the depth-storage product KQ, where K and Q are the numbers of computational steps and logical qubits, respectively [8]. KQ isa measure of the resources required for a particular circuit, and is especially useful for estimating the required
strength of error correction. Successful execution of acircuit requires residual logical gate and memory error
rate of pe << (KQ)−1 . Note that the number of qubits
includes input, output, and ancillae.

Algorithm Optimisation for Topological Measurement-Based Quantum
Computing
Clare Horsman1 ∗Simon Devitt2

Rodney Van Meter3

1

Oxford University Computing Laboratory,
Wolfson Building, Parks Road, Oxford, UK
2National Institute of Informatics,
2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, Japan.
3
Faculty of Environment and Information Studies, Keio University
5322 Endo, Fujisawa, Kanagawa, Japan
Abstract. We present methods for optimizing algorithm design in topological cluster state models ofquantum computing. This is a crucial element in the design of large, scalable quantum architectures. We
detail the resources required for defects to be propagated through the cluster to implement specific gatesand subroutines, and give methods by which different types of resources (spatial and temporal) may beinterchanged. We outline constructive methods for generating optimal defect patterns from a given circuit,significantly reducing the quantum resources required to implement key routines for quantum computing.

The development of a large-scale quantum computeris a highly sought-after goal for many groups worldwide. Recent theoretical developments have allowed for
detailed research into an overall architectural structure
for such a computer. The most comprehensive quantum
computing designs are built fundamentally from the ideasof topological cluster states and surface codes [1,2,3].
These models for quantum computing are remarkably
useful. Not only do they exhibit one of the largest faulttolerance thresholds of any model (both for traditional
qubit errors and also more pathological channels suchas loss), but they are also flexible enough to incorporate
into a large-scale architectural design. Such designs allow
scaling to arbitrary size in a conceptually simple manner.
As these topological coding schemes are based on theconcept of measurement-based quantum computation, theprogramming of such a device to perform quantum algorithms is a question of classical software control. The
quantum hardware of such a computer is only responsible
for the creation of a large, entangled cluster state. How
this state is utilized to perform quantum algorithms anderror correction protocols is dictated by measurementson the cluster. The classical control and optimization ofsuch a computer is therefore an important question. This
talk will briefly summarize the basic principles of implementing and optimizing the classical programming of a
topological computer, in order to reduce the overall quantum resources for various subroutines and algorithms.
The concept of algorithm optimization for the topological cluster model can be easily defined. Figure 1a) shows
the standard braiding pattern to perform a CNOT operation between logically encoded defect qubits definedwithin a 3D cluster. Figure 1b) illustrates a sequenceof CNOT gates, performed during a large-scale quantum algorithm. When implementing a standard quantum
subroutine (such as arithmetic gates, quantum Fouriertransforms, oracle queries, etc.) circuit decompositions∗clare.horsman@bristol.ac.uk

are converted into a sequence of braiding operations.
In addition, each basic quantum gate must be decomposed in terms of the primitive operations which arevalid within the topological model. These primitive operations include specific state initialization, measurement
and CNOT operations. More complicated gates require
the introduction of singular states, magic state distillation protocols, and teleported gates; these operations also
require decomposition into a basic braiding pattern.
In order to optimize the braiding sequence for quantum subroutines, we wish to compact a braiding pattern
into the smallest possible cluster volume (given the error
correction requirements of the quantum code). The error
correction strength can be defined by the distance of theunderlying quantum code, d, and is determined by boththe fundamental physical error rates in the computer andthe size of the specific algorithm. Once this distance is
specified, defects are defined in the lattice which have acircumference of d and are separated from each other also
by d. Figure 1a) shows an optimized CNOT gate for a
distance d = 8 topological code. For this braiding operation, the total volume of the cluster is such that all defectregions are separated from each other by the minimum
possible amount (in this case, 8 cluster cells).
When constructing a quantum subroutine, we naively
decompose the circuit into its primitive components(CNOT, Toffoli, Hadamard etc.) and then define a braid
and defect pattern to be implemented in the computer.
As gates such as the Toffoli cannot be implemented directly on the lattice and instead require the preparationof distilled ancilla states and teleportation protocols, directly constructing a braiding sequence for a large subroutine will not in general lead to an optimized pattern.
The purpose of this project is to construct a braiding sequence for a large quantum subroutine (such as aquantum adder or quantum Fourier transform), and thendevelop general techniques to minimize the total cluster
volume needed to implement the braid pattern. The ul-

timate goal is to achieve a optimal braiding sequence ina minimal volume, where all defect separations in thecluster are d, and the cluster prepared by the quantum
hardware contains no wasted space.
When considering the possible patterns of defects andbraids for a gate sequence, we must first take into account the constraints that the code distance puts on how
defects can move. These layout restrictions can be completely characterised for single qubit/braid defects andalso for the interaction between two or more defect pairs
when they intersect. The characterisation includes theresources required to complete a particular layout move;
for some layouts spatial and temporal resources may beinterchanged to a certain extent, but for others a minimum amount of each may be required. One example iswhen a single defect pair is propagated vertically within
a 2-dimensional timeslice (figure 2). In order to preserve
the code distance, the operation requires either an additional parallel row of cells in the cluster state (figure2a), or else a second timeslice surface (figure 2b). So a
choice may be made between spatial or temporal costs inthat case. By contrast, when two defects intersect (figure 3) there is an irreducible temporal cost: one must
propagate over the top of the other temporally, requiring an extra ‘timeslice’ (2-dimensional spatial surface) tocomplete the movement.
One particularly important operation is swapping theposition of two qubits – that is, interchanging two defectpairs. With careful manipulation of the four defects, it
is possible to perform this operation with only one additional cluster cell, although this then requires six different
timeslice surfaces to complete (figure 4). This then enables us to give resource requirements for all algorithms
in the extreme cases where either temporal or spatial resources are required to be minimal, but the other resource
type is unbounded. With no restrictions on temporal resources, the minimum spatial resource for any algorithm
is one additional cell. For an unbounded amount of spatial resource, any sequence of gates with a computational
depth of 1 may be performed with only one additionaltimeslice.
When performing two-qubit gates, in general we have
two options. Either we can propagate long-distancebraids between the qubits, or we can move the qubits andthen perform shorter-range braiding. If we consider the
motion of the braids and the defects together, we obtainthe concept of a path between qubit defects. This pathcan be realised by a combination of qubit defect movement and/or braiding. An algorithm is then defined bya series of paths through the cluster, and optimisation
concerns minimising the cluster volume they require.
If a gate sequence can be laid out on a 2-dimensionaltimeslice such that there exist paths that neither intersect
nor overlap, then the sequence can be performed in a single timestep. However, if no such set of paths exist, thenadditional timeslices are needed. For two paths to cross,at least one extra time surface is required. More surfaces
may be needed depending on whether the path is instantiated as qubit or braid defect movement. If at least oneof the paths is a qubit movement, then the requirementthat qubits must persist through time may mean that
more than one extra surface is needed at an intersection.
However, if two braid defects cross then they always require only a single extra surface. This is furthermore also
the case when any number of paths cross: an intersectionof n paths requires at least n different time surfaces toperform.
We now have a simple way of finding the minimum
time for an algorithm given a certain amount of space.
Laying the qubit defects out on a 2-dimensional surface,
we find the paths between them corresponding to therequired gates such that the maximum number of intersecting paths is minimised. That is then the minimum
time required. Moreover, these paths give the construction of the minimum-time algorithm itself: leaving thequbits static, they are the paths along which long-range
braids are to be propagated. It is then easy to give provably minimum-time constructions by hand of simple algorithms such as a mesh circuit. Once paths have beenfound between the qubits, the next step is to operate on
the path collection to “squeeze” it so that each path thenbecomes contiguous with its neighbours, and there is nospace on the cluster between paths. It is currently ongoing work to prove the conjecture that this squeezing
operation preserves the topology of the defect structure,and that all defect configurations in the same homotopy
class perform the same unitary evolution.
This work has many implications for topologicalmeasurement-based computing. By reducing to a minimum the quantum resources required to implement certain subroutines, it helps decrease the technological barriers to quantum computing. Giving detailed methods
for implementing these optimal routines enables the creation of efficient automated compilers for the topological model, translating logical gate sequences into physical operations on the system. Furthermore, these results
lay the groundwork for large-scale algorithm design thatworks natively in the topological model, allowing the efficient programming of a large-scale multi-task quantum
computer.

References[1] R. Raussendorf, J. Harrington, K. Goyal. Topologicalfault-tolerance in cluster state quantum computation.
New J. Phys. 9, 199 (2007).
[2] S. J. Devitt et al. Architectural design for a topological cluster state quantum computer. New. J. Phys.
11, 083032 (2009).
[3] A. G. Fowler et al. High threshold universal quantum
computation on the surface code. Phys. Rev. A 80,
052312 (2009).
[4] R. Van Meter et al. Distributed quantum computiataion architecture using semiconductor nanophotonics. International Journal of Quantum Information 8,
295–323 (2010)

Acknowledgements
This research is supported by the Japan Society for
the Promotion of Science (JSPS) through its “Funding
Program for World-Leading Innovative R&D on Scienceand Technology (FIRST Program).”Figure 1

Braiding patterns for a) a single CNOT gate and b)
multiple CNOT gates. The dots represent physicalqubits, and the different coloured regions represent
different types of defect, for example the blue regions
are computational qubits. Braiding operations canonly take place between defects of different types. The
introduction of an ancilla (purple) qubit allows us to
braid two qubits of the same (blue) type.

Figure 2

Propagating a defect pair vertically, using a) extra
spatial resources and b) extra temporal resources.

A Layered Architecture for Quantum Computing using
Optically-Controlled Quantum Dots
Cody Jones1,* , Austin G. Fowler2 , Jungsang Kim3 , Thaddeus D. Ladd1,4,† , Rodney Van Meter5 , andYoshihisa Yamamoto1,4
1

2

Edward L. Ginzton Laboratory, Stanford University, Stanford, California, USA
Centre for Quantum Computing Technology, University of Melbourne, Victoria, Australia
3
Fitzpatrick Institute for Photonics, Duke University, Durham, NC, USA
4
National Institute of Informatics, Japan
5
Faculty of Environment and Information Studies, Keio University, Japan*
Corresponding author: ncjones@stanford.edu

Abstract. Designing a quantum computer capable of executing large-scale programs such as Shor’s algorithm is a challenging engineering problem. We develop a complete framework for a quantum computer
based on optical control of quantum dots in a layered architecture, showing how a variety of technologies
must operate synchronously in such a system. Furthermore, we investigate the performance and manufacturability of this system. We find that Shor’s factoring algorithm for a 2048-bit number can be executed inapproximately 14.4 days. Moreover, this architecture can leverage many existing technologies from matureindustries, making the development of a functioning quantum computer a feasible endeavor in the near
future.

1

Introduction

We are designing a quantum computer, with the principal imperative to take advantage of the strong capabilities of device integration afforded by semiconductor
fabrication. Our qubit is defined by the electron spinstates of a charged quantum dot controlled by ultrafast
optical pulses [1, 2]. Optical control makes this systemvery fast, scalable to large problem sizes, and extensible
to quantum communication [3, 4] or distributed architectures [5]. The design of this quantum computer centers on error correction in the form of a topological surface code, which requires only local and nearest-neighbor
gates. The framework of this architecture is flexible, permitting analysis and comparison of other quantum computer designs.

2

Layered Framework

The present architecture is a control stack consistingof four layers, where each layer has a prescribed set ofduties to accomplish. As shown in Figure 1, the interface between two layers is defined by the services a lower
layer provides to the one above it. To execute an operation, a layer must issue commands to the layer below andprocess the results. The various functions in a quantum
computer are organized in a manner which aids understanding for the designer and translates directly into aneffective control structure for the device itself. This approach facilitates isolation of design problems in individual layers, wholesale replacement of an entire layer with adifferent technology, and independent evolution of layers
over time.

At the top of the control stack is the logical layer,
where a quantum algorithm is implemented and results
are provided to the user. The bottom hosts the raw physical processes underpinning the quantum computer. The
layers between (virtualization and surface code) are essential for shaping the imperfect quantum processes intoa system of high-accuracy quantum gates at the logicallayer.
2.1

Layer 1: Physical

The lowest layer houses the specific hardware andphysical processes. In simplest terms, this is the storage and manipulation of unprotected quantum information. The physical layer provides the essential physicalprocesses to satisfy the virtualization layer. The system
we propose uses charged quantum dots to store quantum
information in the electron spin state [6, 7, 8, 9, 10, 11].
The quantum dots are embedded in a planar distributed
Bragg reflector (DBR) microcavity [12], and a transverse
magnetic field separates the spin levels [13]. Broadband
optical pulses rotate the spin vector [1, 2]; these opticalpulses are controlled by arrays of MEMS micromirrors[14, 15]. Dispersive readout provides measurement of thespin state [16, 17].
2.2

Layer 2: Virtualization

The virtualization layer is where quantum systems areorganized into information units and operations. Decoherence processes such as environmental noise and control errors mandate that an intermediary processing steptransforms the raw subsystems in the physical layer into
“virtual qubits” and “virtual gates” for the surface code

Layer 4: Logical

Quantum algorithms and interface to classical user

LogicalMeasurement

Logical
Qubit

Qubit
Movement

LogicalToffoli

LogicalCNOT

Layer 3: Surface Code

Closed-loop error correction using the topological surface code

MeasureZ-basisMeasureX-basisVirtualQubit

Virtual1-qubit Gate

2.4
VirtualCNOT

Layer 2: Virtualization

Open-loop error-cancellation such as dynamical decoupling

QND
Readout

QD Spin
SystemLarmorPrecession

Broadband
Pulse

strength is preserved. This feature permits Layer 3 to berobust against the unpredictable error correction stage— the error syndrome must be translated into a mostprobable logical error, a process which can be computationally intensive for a large surface code.

Entangling
Pulse

Layer 1: PhysicalPhysical Apparatus including quantum dots, lasers, and MEMS mirrors

Figure 1: Layered control stack which forms the framework of a quantum computer architecture. Arrows indicate services provided to a higher layer.

3
layer. The virtualization layer is distinct from the surface code layer in that Layer 2 contains only open-loop
control; no readout or active feedback is implemented.
A Virtual Qubit is a quantum two-level system
whose state is protected by dynamical decoupling (DD),decoherence-free subspaces (DFS) [18], or some othermanner of open-loop control. In this particular system,
static decoupling sequences protect the virtual qubit fromdephasing by the nuclear environment [19].
A virtual gate is an operation on a virtual qubit tochange its state, typically with reduced error from theraw processes in the physical layer. This may include
composite physical gate sequences with net suppressed
error. This architecture embeds the BB1 compensation
sequence [20] within the static decoupling sequence sothat the ensemble corrects both dephasing and pulseinduced errors.
2.3

Layer 3: Surface CodeThe surface code layer provides the ability to correct
arbitrary errors with quantum error correction [21, 22].
In contrast to Layer 2, the surface code is a closed-loopsystem used to periodically measure an error syndromeand correcting errors. The probability of an undetected
error decreases exponentially as a function of the “distance” of the code, so that logical qubits and gates with
arbitrarily low error can be produced with a sufficiently
large code. However, the virtual qubits and gates musthave error rates below the threshold of the surface code
(0.75%), so that often Layer 2 techniques are necessary
for Layer 3 to function. The surface code layer uses
closed-loop error correction to provide fault-tolerant logical qubits, logical gates, and logical measurement toLayer 4. The primary control loop of this architectureappears in Figure 2.
In addition to a relatively high threshold, the surface
code also tolerates delayed feedback from measurementof the error syndrome [23, 24]. Logical operation speed(and hence algorithm runtime) may suffer, but the code

Layer 4: Logical

The logical layer hosts the quantum algorithm thata classical user wishes to execute. Operations are performed on the logical qubits provided by the surface code,and the end result is communicated to the classical user.
The system designed here executes Shor’s algorithm [25]to factor a 2048-bit number. As indicated in Figure 3,
the speed of logical operations depends on many performance aspects of Layers 1, 2, and 3, such as optical pulse
repetition rate and bandwidth, fidelity of virtual gates after dynamical decoupling sequences, and the size of thesurface code needed for the chosen algorithm.

Prospects

In this investigation we seek to design a quantum
computer architecture using optically-controlled quantum dots which can be scaled to problems believed to
be intractable for classical computation, such as Shor’salgorithm. We estimate this can factor a 2048-bit numberin 14.4 days by taking advantage of ultrafast optical control. Additionally, this particular architecture attempts
to take advantage of mature technologies from other fields
wherever possible, such as the MEMS mirror arrays. We
implement the surface code for quantum error correction;
this has a strong influence on the physical design of thissystem (such as nearest-neighbor gates for a 2D array ofquantum dots), but in principle other methodologies like
CSS codes [26] are compatible with this framework.
What hardware performance is necessary to build afunctional quantum computer? Common figures of merit
are fidelity, operation time, and qubit coherence time.
Here we go further to show how connectivity and classicalcontrol performance are also crucial. To design a quantum computer requires viewing the system as a whole,such that tradeoffs and compatibility between component
choices may be addressed. We explore how to approachthe complete challenge of designing a quantum computer.
Furthermore, our results present a template for developing quantum architectures based on other technologies, sothat differing approaches to quantum information, suchas ion traps or optical lattices, can be contrasted in ameaningful context. In the future we intend to explore
more rigorously the specific hardware requirements ofthis system, such as developing the integrated circuit required for error syndrome processing in Layer 3, or the
optical projection system for laser pulses in Layer 1.

4

Acknowledgments

This work was supported by the National Science
Foundation CCF-0829694, the Univ. of Tokyo Special
Coordination Funds for Promoting Science and Technology, NICT, and the Japan Society for the Promo-

tion of Science (JSPS) through its “Funding Program forWorld-Leading Innovative R&D on Science and Technology (FIRST Program).” CJ was supported by the National Science Foundation Graduate Fellowship.

References[1] Press D, Ladd T D, Zhang B and Yamamoto Y 2008
Nature 456 218–221[2] Berezovsky J, Mikkelsen M H, Stoltz N G, Coldren
L A and Awschalom D D 2008 Science 320 349–352[3] Briegel H J, Dür W, Cirac J I and Zoller P 1998
Physical Review Letters 81 5932–5935[4] Dür W, Briegel H J, Cirac J I and Zoller P 1999
Physical Review A 59 169–181[5] Van Meter R, Ladd T D, Fowler A G and Yamamoto Y 2010 International Journal of Quantum Information 8 295–323 preprint available asarXiv:0906.2686v2 [quant-ph].
[6] Björk G, Pau S, Jacobson J and Yamamoto Y 1994
Physical Review B 50
[7] Imamoglu A, Awschalom D D, Burkard G, DiVincenzo D P, Loss D, Sherwin M and Small A 1999
Physical Review Letters 83 4204–4207[8] Bonadeo N H, Chen G, Gammon D and Steel D G
2000 Physica Status Solidi B 221 5–18
[9] Guest J R, Stievater T H, Li X, Cheng J, Steel D G,
Gammon D, Katzer D S, Park D, Ell C, Thränhardt
A, Khitrova G and Gibbs H M 2002 Physical Review
B 65[10] Hours J, Senellart P, Peter E, Cavanna A and Bloch
J 2005 Physical Review B 71
[11] Yamamoto Y, Ladd T D, Press D, Clark S, Sanaka
K, Santori C, Fattal D, Fu K M, Höfling S, Reitzenstein S and Forchel A 2009 Physica Scripta T137
[12] Reitzenstein S, Hofmann C, Gorbunov A, Strau M,
Kwon S H, Schneider C, Lffler A, Höfling S, Kamp
M and Forchel A 2007 Applied Physics Letters 90[13] Bayer M, Ortner G, Stern O, Kuther A, Gorbunov
A A, Forchel A, Hawrylak P, Fafard S, Hinzer K,
Reinecke T L, Walck S N, Reithmaier J P, Klopf F
and Schäfer F 2002 Physical Review B 65
[14] Kim C, Knoernschild C, Liu B and Kim J 2007 IEEE
Journal of Selected Topics in Quantum Electronics
13 322–329[15] Knoernschild C, Kim C, Liu B, Lu F P and Kim J
2008 Optics Letters 33 273–275[16] Berezovsky J, Mikkelsen M H, Gywat O, Stoltz N G,
Coldren L A and Awschalom D D 2006 Science 314
1916–1920[17] Atatüre M, Dreiser J, Badolato A and Imamoglu A
2007 Nature Physics 3 101–106[18] Bacon D 2001 Decoherence, control, and symmetry in quantum computers Ph.D. thesis Universityof California, Berkeley[19] Press D, Greve K D, McMahon P L, Ladd T D,
Friess B, Schneider C, Kamp M, Höfling S, Forchel
A and Yamamoto Y 2010 Nature Photonics 4 367–
370[20] Brown K R, Harrow A W and Chuang I L 2004
Physical Review A 70
[21] Raussendorf R, Harrington J and Goyal K 2007 New
Journal of Physics 9[22] Raussendorf R and Harrington J 2007 Physical Review Letters 98[23] Devitt S J, Fowler A G, Stephens A M, Greentree
A D, Hollenberg L C L, Munro W J and Nemoto K
2009 New Journal of Physics 11[24] Fowler A G, Stephens A M and Groszkowski P 2009
Physical Review A 80
[25] Shor P W 1997 SIAM J. Comput. 26 1484–1509[26] Nielsen M A and Chuang I L 2000 Quantum Computation and Quantum Information 1st ed (Cambridge
University Press) ISBN 0521635039†Present address: HRL Laboratories, LLC, 3011 Malibu
Canyon Rd., Malibu, CA 90265

Fan-out

Surface CodeController

MEMS Local
Controller

Virtualization
Controller

2

3

4

5

6

7

Surface Code
Processing

Virtualization
Processing

Signal
Propagation

MEMS Processing

Register
Loading

MEMS
Micromirror
Switching

LogicalController

Quantum Dots
in DBR Cavity

81

Pipelined Control Cycle

LogicalProcessing

Global EC
Processing

13

Signal
Propagation

Light
Propagation

Local EC
Processing

12

Store
Result11

Global EC
Processor

Photodetector

10

9Local EC
Processor

Fan-inLayer 4: Logical
Layer 3: Surface CodeLayer 2: Virtualization
Layer 1: PhysicalError correction processors
handle local errors, so they
are distributed across thedetector array.

Figure 2: Primary control cycle of the quantum computer. Though presented as a sequence of steps, each layer issues
multiple commands to the layer below, and operations are pipelined. The true quantum behavior exists in step 8,
where ultrafast laser pulses interact with charged quantum dots, and in step 9, where the qubit state is measured bydetecting the polarization of light reflected from the DBR cavity containing the quantum dots.

LogicalCNOT

Lattice
RefreshVirtual1-qubit
Gate

LogicalToffoli Gate

DefectBraiding

Layer 3: Surface Code

Virtual 2-qubit
Gate

T2(Dephasing)Entangling
Operation}

Optical Pulses}

Optical Control Hardware

Layer 2: Virtualization

VirtualMeasurement
Spin State
Rotation

Larmor period
TL = 40 ps

Measurement
Pulse

Layer 4: Logical

EOM/AOM
SwitchingMicromirror
Deflectionns(10 -9)µs(10 -6)Layer 1: Physicalms(10 -3)Figure 3: Relative timescales for critical operations within each layer. The arrows indicate dependence of higher
operations on lower layers. The red arrow signifies that the surface code lattice refresh must be much faster than thedephasing time in order for error correction to function.

Defective Qubits in Surface Code Quantum Computation on a Fixed
Lattice
Shota Nagayama1 ∗Rodney Van Meter2 †1

Graduate School of Media and Governance, Keio University5322, Endo, Fujisawa City, Kanagawa, Japan.
2
Faculty of Environment and Information Studies, Keio University5322, Endo, Fujisawa City, Kanagawa, Japan.
Abstract. Surface code quantum computation is a feasible architecture for fault-tolerant quantum computation. However, there are some physical problems that must be overcome to implement it. Withsolid-state systems, physically non-functional devices may exist, aﬀecting our ability to correct errors. We
describe the relationship between the yield and physical and logical error rates, using realistic models forthe error rate for both plaquette and superplaquette operations.
Keywords: Surface code quantum computing, yield, error rate

1

Introduction

Surface code quantum computation[1] is a feasible architecture for fault-tolerant quantum computation, but
it has several problems to be solved. One such problem is how to deal with physical defects. If the numberof defects is large, we need a large lattice, losing eﬃciency of the use of physical resources. Stace, Barrett
and Doherty[2] addressed the loss problem in an idealized environment. They assumed the ability to measure“superplaquette” operators perfectly, an assumption thatraises the threshold by an order of magnitude. They do
not consider hole movement, which is critical. Operationsin the surface code are done by moving two holes in thelattice. Physical error chains which connect holes resultin logical errors, so the distance between holes determines
the tolerance property. Hole movements will change thisdistance. Our in-progress simulations describe the tolerance properties of a defective lattice. Our goal is to determine the minimum lattice hole size and spacing, given
the yield and physical gate error rate, for non-idealized
conditions.

2

Surface code quantum computing

In surface code quantum computing, a lattice consisting of physical qubits represents one or more logicalqubits. The correlation between a pair of lattice boundaries represents a logical qubit. We concentrate here on
surface code quantum computing based on solid statephysics, for example quantum dots with unpaired electron spins as the qubits, and cavity QED for control.
We use the term “hole” where Raussendorf et al.[3]and Fowler et al. use “defect”. A hole is a region of thelattice that is not used. The boundary of a hole givesa degree of freedom that can be used as a logical qubit.
We use the term “defect” to refer to physical qubit errors
such as non-functional quantum dots. Note that a defectmay act as an immobile hole, which may either disturb
the computation or be used in computation.
The yield is the ratio of quantum dots of suﬃcientquality to the total number of dots produced. Yield is∗kurosagi@sfc.wide.ad.jp† rdv@sfc.wide.ad.jp

aﬀected by spectral inhomogeneity, poor cavity quality,
and other factors, depending on quantum dot type. The
lower the yield, the bigger the lattice size should be toachieve the same error correction strength.
The physical error rate (Pphy ) is the probability that aphysical gate or other physical error occurs. Physical errors are detected with stabilizer measurements. We call aset of qubits which consist of a syndrome qubit and 4 data
qubits a “plaquette”. Measurements on this unit give thestabilizer measurements of the plaquette. A “superplaquette” is a over-sized plaquette, formed around one ormore defects. A defect connects two plaquettes aroundit into a superplaquette. Two defects may connect threeplaquettes. We need diﬀerent sequences of measurements
to measure the stabilizers of diﬀerent superplaquettes.
The adjusted error rate (Padj ) is the probability of an error chain crossing a plaquette or superplaquette, adjusted
for the probable errors on measuring the stabilizer. The
logical error rate depends on the distance between twoholes or between a boundary of the lattice and a hole.
The shortest distance determines the logical error rate
Plog = (Padj )distance .

3

Superplaquettes

As noted above, there may be various types of superplaquettes, consisting of various numbers of single plaquettes, chained in various shapes. Each type of superplaquette has a speciﬁc equation to calculate its Padj ,see Table 1 and Figure 1, based on the number of gatesneeded to implement the superplaquette operator. The
relationship between Padj and the number of gates is
Padj = 1 − (1 − Pphy )#gates . Optimizing the stabilizer
circuit for arbitrary superplaquettes is an open problem
that we think can be solved using graph theory, see Appendix A.2.

4

The inﬂuence of yield on logical error
rate

Figure 2 shows the eﬀect of low yield on the surface
code. The presence of defects treated as superplaquettes shortens error chains between holes. The blue error
chain requires ﬁfteen lattice qubit bit ﬂips, while the redjkstra’s algorithm is used to ﬁnd the shortest path.

5

Summary

We have shown that the presence of defects signiﬁcantly reduces the error correction capability of the surface code. Not only are defects in themselves computationally useless, but they also reduce other qubits’ eﬃciency. We suggest the following as open problems:Figure 1: Plaquettes and superplaquettes. “×” denotes a defect. (a) Defect-free plaquette. (b) A 2superplaquette formed by a single defect. (c)-(e) Some
3- to 5-superplaquettes formed by multiple defects.
case
(a)
(b)
(c)
(d)
(e)

#gates
5
12
15
15
19

Padj
Padj:(a) = 1 − (1 − Pphy )5
Padj:(b) = 1 − (1 − Pphy )12
Padj:(c) = 1 − (1 − Pphy )15
Padj:(d) = 1 − (1 − Pphy )15
Padj:(e) = 1 − (1 − Pphy )19

Table 1: The number of physical gates needed to implement the stabilizer operation of each superplaquette in
Figure 1, and the corresponding Padj .

1. Superplaquette overhead Superplaquettes needstabilizer circuits speciﬁc to their individual shape.
The memory error rate of non-defective qubits may
increase if they have to wait longer for superplaquette operations to complete.
2. Full path simulation Our initial simulations do
not enumerate all patterns of paths. While the logical error rate increases exponentially with the path
length, errors on non-shortest paths may aﬀect theoverall logical error rate. If there are many paths
whose error rate is not small enough to be ignored,
the result of our simulation may be unduly optimistic.
3. Defective syndrome qubit We did not assume
that syndrome qubits can be defects. Defective syndrome qubits will aﬀect the stabilizer operation signiﬁcantly.
Once we have Padj for every plaquette and superplaquette, we can build a weighted graph. Using the logarithm of every Padj as the edge weight then allows us toapply Dijkstra’s algorithm to determine the single mostprobable error path. For high defect rates, we expect thispath to dominate the overall error probability. For nearlyhomogeneous lattices with few defects, large numbers ofpaths with similar probabilities will exist, requiring more
careful counting and/or simulation to determine Plog .

Figure 2: Examples of error chains. This blue line represents the ideal situation. No defects, or superplaquettes
reduces the tolerance property. However, the situation
around the red line is more realistic with superplaquettes
and error chains that can run over them. Superplaquettes reduce the tolerance property, so the logical error
rate will increase.

chain requires only eleven. The logical error rate of theblue error chain is Plog = (Padj:(a) )14 . This equation describes only the probability of a logical error occuring,
not the probability of measuring the -1 eigenstate either
correctly or incorrectly. In this situation there are defects in the lattice, so the shortest error chain will be thered line. It passes across only eleven qubits, so the error
equation will be Plog = (Padj:(a) )7 ×(Padj:(b) )3 ×(Padj:(c) ).
Superplaquettes act like a “bypass” around two or moreplaquettes, reducing the tolerance property directly.
The logical error rate depends mainly on the shortest
path of the error chains. We are developing computer
simulations to reveal the relationship between yield andthe shortest path in the channel between two holes. Di-

Acknowledgements
This research is supported by the Japan Society for
the Promotion of Science (JSPS) through its “Funding
Program for World-Leading Innovative R&D on Scienceand Technology (FIRST Program).” We would also liketo thank Austin G. Fowler, Nathan Cody Jones, Simon
Devitt, Byung-Soo Choi and especially Clare Horsman.

References[1] Austin G. Fowler, Ashley M. Stephens, and Peter Groszkowski. High-threshold universal quantum
computation on the surface code. Phys. Rev. A,
80(5):052312, Nov 2009.
[2] Thomas M. Stace, Sean D. Barrett, and Andrew C.
Doherty. Thresholds for topological codes in the presence of loss. Physical Review Letters, 102(20):200501,
2009.
[3] Robert Raussendorf, Jim Harrington, and Kovid
Goyal. Topological fault-tolerance in cluster state
quantum computation. New Journal of Physics,
9:199, 2007.

A

Appendix

A.1

Lattice design

Figure 3 shows the design of a lattice. Each hole ismade to be (d × d), so it has 4d circumference. The distances between holes and between each hole and boundaries of the lattice are at least 4d. Thus, when the yield
is 1, which is the ideal situation, we can take the power“distance” as 4d.

A.2

Plog = (Padj )4d(1)

d = f (yield, Padj )(2)Graph problem in superplaquette operation

Superplaquette operations are shaped as chains of
CNOT gates. Figure 4 shows an example of a 3superplaquette in a straight chain. Data/syndrome
qubits are nodes, and edges are between adjacent qubits
in the graph determining the number of gates. We ﬁndthat the diameter of the graph determines the number ofgates.

Figure 3: Lattice model.

Figure 4: Circuit of an operation for a 3-superplaquette.
This operation needs 22 gates and 1 measurement, 12
time steps.

Heterogeneous Interconnects in a Semiconductor Nanophotonic Surface CodeQuantum Computer
Rodney Van Meter1 , Thaddeus D. Ladd2,4,† , Austin G. Fowler3 , and Yoshihisa Yamamoto2,4
1

Faculty of Environment and Information Studies, Keio University, 5322 Endo, Fujisawa, Kanagawa,
252-0882, Japan
2
Edward L. Ginzton Laboratory, Stanford University, Stanford, CA, 94305-4088, USA
3
Center for Quantum Computing Technology, University of Melbourne, Victoria 3010, Australia
4
National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan

Abstract. The problem of communication will dominate both architectural choices and application performancein large-scale quantum computers. We propose a system based on semiconductor nanophotonics and electron spinsin quantum dots that utilizes different communication protocols depending on the expected fidelity of connection.
Although the surface code requires, at minimum, only two-dimensional nearest-neighbor coupling, our multi-levelapproach solves problems with heterogeneous coupling created by device layout limitations and by defective qubits,
and supports inter-chip communication in the same framework.
Keywords: nanophotonics, surface code, quantum computer architecture

1

Introduction

Few of the many proposals for quantum computer architectures take an explicitly heterogeneous approach to designingsystems, but the limitations of device size, classical control
hardware, and quantum interconnects make perfectly uniform,
large-scale systems impossible. As quantum architectures mature, they will adopt multi-level interconnect systems. The
most visible distinction is between coupling within one chipor device, and coupling between chips, though intra-chip connections may also come in different flavors. Connectivity requirements strongly depend on the means chosen for quantum
error correction.
Surface code quantum computation has one of the highest
error thresholds for systems with constrained interconnects,
at around 0.75% for gate and memory errors [4]. The logical error rate improves rapidly as the distance of the code isincreased, and the resources required can be scaled incrementally. Moreover, movement of logical qubits or execution ofgates between distant logical qubits can be done in nearly constant time, at the expense of space, allowing time performanceof some algorithms (such as arithmetic) to be asymptotically
optimal.
The surface code requires qubits arranged in a twodimensional lattice. With the prospect of a low yield ofqubits that meet our quality criteria, and a system architecture that does not support direct physical coupling to neighbors in all four cardinal directions, our proposed system couples qubits through heterogeneous communication channels
that pass through different numbers, types and sizes of optical components. This requires the use of purification [1, 2] aswell as different physical gate mechanisms.
In this paper, we present a nanophotonic architecture using
the surface code. First, we describe the core components witha focus on the heterogeneity of the interconnect, followed bya discussion of the expected performance of very large-scale

Figure 1: Scanning electron micrograph of a non-functional
GaAs demonstration device with (unshown) InAs quantum
dot layer, created to explore fabrication issues.
systems, some of the lessons learned, and the resulting demands on the evolution of the underlying technology.

2 Architecture
We are developing an architecture that utilizes unpaired
electron spins held in quantum dots in optical cavities [5].
Coupling is performed using different physical gates, dependent on the loss between the qubits to be entangled, using laser
pulses routed in-plane through waveguides that thread among
the cavities. Individual qubits can be coupled to the waveguides via optically-controlled tuning of resonant frequencies,
accomplished using MEMS micromirror arrays and out-ofplane lasers.
Figure 1 shows our basic layout. The smallest circular cavities include the quantum dots used for qubits, and are assigned
three low-level roles in the system: lattice qubits (wedged between larger circular waveguides), ancillae for teleported gatecircuits (between large circles and racetrack-shaped waveguides), and transceivers (between racetrack-shaped waveguides and linear waveguides). The large, circular waveguides
are used for high-fidelity gates between ancillae and latticequbits, requiring no additional purification.
The linear waveguides are arranged in alternating columns
for logic gates and long-distance communication via teleportation and purification. The teleportation waveguides,
flanked by many transceiver qubits, initially create lowfidelity Bell pairs over large vertical distances, between neighboring columns, or between chips, depending on the settingof optical switches (not shown in the figure; see the complete
architecture in Ref. [5]). Assuming 0.1dB optical loss for incolumn connections and 0.4dB between neighboring columns,
our calculations show that the respective connections requireapproximately 100 and 1,000 pulses in the teleporation waveguides, including purification.
The master architecture is a quantum multicomputer, consisting of thousands of chips arranged in an H × 1 array witheach chip coupled to left and right neighbors through switchedextensions of the teleportation waveguides. Previous studies
have shown that this wide, shallow multicomputer arrangement works well for systems using CSS codes [6]; in thisarchitecture, sections of lattice are stitched together in a distributed fashion across device boundaries, likewise avoiding
the need for topologically complex inter-node switching fabrics [3].

3Discussion

The architecture presented here has numerous strengths,
including the explicit planning for heterogeneous communication and low yield. The lattice maintenance process isresource-efficient and highly flexible, minimizing the number of ancillae required for plaquette syndrome measurement.
The rich interconnect supports software-defined lattice arrangements, allowing defective qubits to be mapped out of
the system easily.
Our architecture has two principal weaknesses. First, despite the high-speed repetition rate of signals (specified as
10GHz) in the logic and teleportation waveguides, the large
number of pulses required in each vertical column still results in a complete lattice refresh time of ∼50µsec. This inturn demands ∼50msec memory coherence time and resultsin Toffoli gate times that are also ∼50msec, slow but tolerable for our purposes. Second, although the basic structuresof cavities and waveguides are large by modern VLSI standards, the spacing between cavities and waveguides and thesurface roughness of optical components require very exacting fabrication. Adequate fabrication is currently achievable
only with e-beam lithography, which is fast enough for small
test devices but too slow (hence, expensive) for the productionlevels required for large-scale systems.
Our investigations produced a clear imperative that was unexpected, but logical in hindsight: pursue quality of components at the expense of yield. Within our system, a yield of
only a few percent of qubits declared “functional” will allow
lattice-building experiments, and a yield of 40% will allow
the construction of supercomputer-scale systems capable ofusing Shor’s algorithm to factor kilobit or larger numbers in atimescale of months, many times faster than classical systems.
We believe that this minimum yield is the lowest yet reported.
Finally, this work has helped to establish targets for various
experimental values: the 50msec memory lifetime mentioned

above, a teleported gate error rate of 0.2%, and the demanding
nature of optical communication. With our architecture andchoice of gate mechanism, changes in switch loss of less thanhalf a decibel result in an order of magnitude increase in thenumber of required pulses and corresponding negative effects
on performance.
Our overall architecture bears out the intuitive idea thatricher interconnectivity among components will improve therobustness of the system. By using a multi-level strategy
incorporating purification and appropriate choices of physical gate sequences, heterogeneity and physical defects can be
managed in an integrated fashion.

Acknowledgements
This research is supported in part by the Japan Society
for the Promotion of Science (JSPS) through its “Funding
Program for World-Leading Innovative R&D on Science andTechnology (FIRST Program).” This work was supported
in part by National Science Foundation CCF0829694, withpartial support by MEXT and NICT. We acknowledge thesupport of the Australian Research Council, the AustralianGovernment, and the US National Security Agency (NSA)
and the Army Research Office (ARO) under contract number
W911NF-08-1-0527. The authors thank Shinichi Koseki forfabricating and photographing the test structure.

References[1] J. Cirac, A. Ekert, S. Huelga, and C. Macchiavello. Distributed quantum computation over noisy channels. Physical Review A, 59:4249, 1999.
[2] J. Dehaene, M. Van den Nest, B. De Moor, and
F. Verstraete. Local permutations of products of Bellstates and entanglement distillation. Physical Review A,
67(2):22310, 2003.
[3] A. Fowler, A. Stephens, and P. Groszkowski. High threshold universal quantum computation on the surface code.
Physical Review A, 80:052312, 2009.
[4] R. Raussendorf, J. Harrington, and K. Goyal. Topologicalfault-tolerance in cluster state quantum computation. New
Journal of Physics, 9:199, 2007.
[5] R. Van Meter, T. D. Ladd, A. G. Fowler, and Y. Yamamoto. Distributed quantum computation architectureusing semiconductor nanophotonics. International Journal of Quantum Information, 8:295–323, 2010. preprint
available as arXiv:0906.2686v2 [quant-ph].
[6] R. Van Meter, W. J. Munro, K. Nemoto, and K. M. Itoh.
Arithmetic on a distributed-memory quantum multicomputer. ACM Journal of Emerging Technologies in Computing Systems, 3(4):17, Jan. 2008.
†Present address: HRL Laboratories, LLC, 3011 Malibu
Canyon Rd., Malibu, CA 90265