Copyright © 2006 Keio University

Why Quantum?
Two Reasons:Because Moore says
we must.
Will also influenceclassical atomic-levelarchitecture.

Quantum brings newcapabilities:a) Better computationalclass for someproblems (but notuniversal)b) Quantum Key
Distribution (QKD)

AQUA: Advancing Quantum
Architecture

System Co-Design
SoftwareDesignTheoryHardwareDesignProtocolDesignEngineering
Workload(Application)4

What is Quantum Computer
Architecture?
Balance generality
and performance

Extract commonality(e.g., qubit motion)

Copyright © 2006 Keio University ｜5

How Do Architects Contribute?
• Identify critical problems• Improve efficiency of design• Establish targets for fidelity, memory time
• Match applications to systems• Classical control design• Architects understand resource management

6

“If you can get to 1Hz, the engineers can get
another one to two orders of magnitude.”N. Gisin, via C. Monroe...I’m an engineer.

7

Results: Workloads, Devices, Systems• Solidified workload definitions,matched to architecture,significantly improved performance• Proposed quantum multicomputer architectureusing quantum system-area network (QSAN)• Developed semiconductor quantum dot
nanophotonic node architecture using (topological)
surface code error correction

8

Results & Current Work: Networking• Showed that linear network works well for QSAN
• Improved qubus repeater performance 50x
by scheduling purification• Designing quantum repeater protocol stack• Defining Quantum Dijkstra: path selection inheterogeneous repeater networks• Currently examining resource allocation• Integrating quantum networks with the Internet:
attempting to standardize
quantum key distribution with IPsec
9

AQUA: Advancing QuantumArchitecture

Factoring Large Numbers

Copyright © 2006 Keio University ｜11rdv, TDL, KMI, quant-ph/0507023

Factoring Large Numbers

Copyright © 2006 Keio University ｜12Factoring Larger Numbers?

Copyright © 2006 Keio University ｜13Factoring Larger Numbers

Copyright © 2006 Keio University ｜14

Factoring Larger Numbers

Copyright © 2006 Keio University ｜15

Factoring Larger Numbers

Copyright © 2006 Keio University ｜16

Workload Summary• O(.) is not good enough; constant factors matter!
• Interconnect & qubit movement high impact• Some algorithms parallelize well;
can trade space for time
• Arithmetic is key17

AQUA: Advancing QuantumArchitecture

Nanophotonic Device

Copyright © 2006
Keio University｜ 19rdv, T.D. Ladd, A.G. Fowler, Y.
Yamamoto, Int. J. Quantum
Information, 2010

Basic Gate

Copyright © 2006
Keio University｜ 20rdv, T.D. Ladd, A.G. Fowler, Y.
Yamamoto, Int. J. Quantum
Information, 2010

First Fab Tests @Stanford

Copyright © 2006
Keio University｜ 21

First Fab Tests @Stanford

Copyright © 2006
Keio University｜ 22

A Solid-State Quantum Computer
quantum gates(instructions)selected classically,
act on 1-3 qubitsquantumdevice(register)‫‏‬Copyright © 2006 Keio University ｜23

classical program
classical dataclassical control & measurement

Dilutionrefrigerator

System Summary• One chip: 128x770 physical quantum dots
• 64K chips in total system• 6 billion physical qubits in total system!
• Uses (topological) surface code
• 120K logical qubits• In-plane waveguides give fault tolerance• Yield of a few percent will enablelattice-building experiments• 40% yield will give us a functional, large-scale system• Will factor 2048-bit number in a year24

A Solid-State Quantum Computer
quantum gates(instructions)selected classically,
act on 1-3 qubitsquantumdevice(register)‫‏‬Copyright © 2006 Keio University ｜25classical program
classical dataclassical control & measurement
quantum data(create Bell pairs)

Dilutionrefrigerator

The Quantum Multicomputer
coherent
sourcewaveguide
quantum network

nodehomodyne
detector

Laboratory-sized quantum multicomputer ortranscontinental network, either one!
Copyright © 2006 Keio University ｜26

AQUA: Advancing Quantum
Architecture

Two Types of Quantum Networks
Unentangled
Networks

Entangled
Networks
CA

G
B

E
H

28

Variables• Two types of quantum networks• Four network architectures‒ CSAN‒ QLAN, QMAN, QWAN• Applications:‒ QKD: QMAN, QWAN (entangled or not)‒ Shor: QSAN, QLAN (entangled)‒ Generally, connect people, machines, and data
in separate locations, same as classical‒ Other uses for long-distance entanglement?
29

The QMC QSAN
coherent
sourcewaveguide
quantum network

node

Copyright © 2006 Keio University ｜30

homodyne
detector

QMC Network Topologies
Shared bus

Two shared buses

Copyright © 2006 Keio University ｜31

Simple line

Fully connected

Two fully connected

The Quantum Multicomputer
coherent
sourcewaveguide
quantum network

homodyne
detectornodeLinear connection works well for arithmetic
Serial links work surprisingly well with QEC
Copyright © 2006 Keio University ｜32

The Repeater’s Jobs
Entanglement swapping & purification,
which require:• A little bit of quantum communication• Quantum memory• Local quantum operations(gates & measurements)• Lots of decision making(both local and distributed)• Lots of classical communication
33

Repeater Protocol Stack
Application
Purification Control (PC)‫‏‬
Entang. Swapping Ctl (ESC)‫‏‬Purification Control (PC)‫‏‬
Entanglement Control (EC)‫‏‬
Physical Entanglement (PE)‫‏‬
Van Meter et al., IEEE/ACM Trans. on Networking,
34 quant-ph:0705.4128
Jun. 2009,}}}End-to-End
Repeated at
Different
Distances
Distance=1
Only quantum!

Four-Hop Protocol Interactions
App
PC
ESC
PC
ESC
PC
EC
PE
35ESC
PC
EC
PE

ESC
PC
ESC
PC
EC
PE

Van Meter et al., IEEE/ACM Trans. on Networking,Aug. 2009 (to appear)

ESC
PC
EC
PE

App
PC
ESC
PC
ESC
PC
EC
PE

Network Link Technology (Qubus)
millimeters to kilometers

coherent
optical source(laser)‫‏‬waveguidetransceiver
qubit innode 1transceiver
qubit innode 2

Munro, Nemoto, Spiller, New J. Phys. 7, 137 (2005)‫‏‬36 Ladd et al., NJP 8, 184 (2006)‫‏‬homodyne
detector

Entanglement Pumping
0.6380.638

0.72
0.638

0.75
0.638

0.77
0.638

0.79

Ineffective w/ large fidelity difference37Symmetric Purification
0.638
0.638

0.72
0.797

0.638

0.72

0.638 X

38

Problems:
Exact matching canrequire long waits.
Not realistic whenmemory effects(decoherence)‫‏‬considered.
Can deadlock if
resources are limited.

Greedy Purification
0.638
0.638

0.72
0.757

0.638
0.638 X

39

Doesn’t wait foranything, uses
whatever’s available.
Works well w/ large
number of qubits
per repeater.

Banded Purification
0.638
0.6380.72
0.797

0.638
0.72

0.638 X

Large gains in throughput.
Moderate # qubits (5-50).
Avoids deadlock.
Realistic memory model.
Simple to implement inreal time (even in HW).
Probably not optimal,
but probably close.

Divide fidelity space
into multiple bandse.g., above & below 0.70
40Banded Purification Performance

41

Van Meter et al., IEEE/ACM Trans. on Networking,Aug. 2009 (to appear), quant-ph:0705.4128

Banded Purification Latency

42

Van Meter et al., IEEE/ACM Trans. on Networking,Aug. 2009 (to appear), quant-ph:0705.4128

RoutingCAGB

E
DH

F
Simple: use Dijkstra’s Shortest Path First.
...but we don’t yet know the cost metric.
43

Different “Which Path”?
CA

44

GE
DH
F

3 hops: ACGB
4 hops: ACGHB
ACEHB
B
ADEHB
ADFHB
5 hops: ACEHGBADEHGBADECGB
ADFHGB
6 hops: ACECGHB
7 hops: ADFHECGBACEDCHGBBut What is Distance?
CAG What if hops are not homogeneous?

E
DH
F

B

Are 2n-1 hops,
2n hops,and 2n+1 hops
significantly different?

45

How Do We Order These?
• How does number oflinks matter?
• Does number of weaklinks matter?
• Does position of weaklink matter?
• Is cost additive?
• At this logical level,is this technologyindependent?
46

Other Problems• Defining swap points• Static or dynamic?
• Avoiding leapfrog• Avoiding deadlock• Minimizing waits forclassical messages

47

Defining Cost in a Quantum Network
○

×△

○

Cost =f(○,×,△,○)

Classical Dijkstra:
Cost＝○＋×＋△＋○IC2009-WIP

Quantum: Dijkstra?
Cost＝○?×?△?○What functions arepossible?
2009年10月27日

Quantum Dijkstra’s Algorithm

49Resource Management (QoS?)‫‏‬
A<->B & C<->D
want to talk.

CARemember, it’s adistributed computation.

DWorse, fragile quantum memory means there
is a hard real time component.

==>requires circuit switching???
(bottleneck likely is memory per node)‫‏‬50

B

Open Repeater Problems• Well, repeater HW doesn’t work yet...
‒ Establishing swapping points‒ Non-power-of-two hops
‒ Finish & publish protocol state machine‒ Resource management models‒ Optimizing classical communication‒ Other error correction mechanisms besidespurification
51

IPsec with QKD

key

52

Secure, Local
Connection

Secure, Local
Connection

keyIPsec with QKD
Dark Fiber
IPsec Gateway
Quantum Path for
Key ExchangeInternetIPsec Tunnel
Classical internet pathusing Quantum-made key

53

IPsec Gateway

The Message• Architecture and architects matter• Interconnects and networks matter• Distributed systems are the only way
to achieve scalability• Classical architecture techniques are viablein the quantum domain• ...and our group is having fun and solving
important problems, so come hang out with us!
54Collaborators on Four Continents• Kohei Itoh & Agung Trisetyarso, Keio Yagami• Takahiko Satoh & Shota Nagayama, Keio SFC• Thaddeus Ladd & Yoshi Yamamoto, Stanford• Bill Munro, HP Labs, Bristol, UK• Kae Nemoto, NII, Tokyo• Austin Fowler, Melbourne, Australia• Byung-Soo Choi, Ewha Woman’s U., Korea• Thanks to NSF and JSPS for current funding,and MICT, MEXT, QAP, and Keio’s Mori Fundfor past funding• ...and thanks to NEC for the loan of the QKD devices
Copyright © 2006 Keio University ｜55

Papers• “Distributed Quantum Computation Architecture Using
Semiconductor Nanophotonics,” IJQI, 2010
• “System Design for a Long-Line Quantum Repeater,”IEEE/ACM Trans. On Networking, Jun. 2009
• I-D: “IKE for IPsec with QKD,” Oct. 2009draft-nagayama-ipsecme-ike-with-qkd-00.txt• These & others available on my web page

Copyright © 2006 Keio University ｜56

Food for Thought• When will first Science or Nature paper
appear using a quantum computer, but notabout the quantum computer?
• That is, when will a quantum computer doscience, rather than be science?
• Answers from quantum researchers range
from “less than five years” to “more than fortyyears”
57

AQUA: Advancing Quantum
Architecture