.

/0123



45

3



674



"$#%&

(')

8953



:*+,

*-

cedgfPh

ikjlfTm-d+npoqfsrut!

 ^MX

;=<=>@?BACEDGF=?IH=AKJ AKLML>N=OKJ APLFRQTSVUXWYQ[Z\A]S^<_Q`FURQ\a=bÐ~Ñ ÒKÓ ÔKÕ×Ö]Ø^ÙXÚPÕPÛÓ=ÜÝ@Ò

vxwzy|{

Establish fast quantum modular exponentiation algorithms to run
Shor's algorithm on various quantum computer architectures,using the best available quantum and classical techniques. Thiswill support performance analysis of both architectures andalgorithms, benefiting near-term experimentation and long-term
research planning.
}~FBW]S^U>BA@F

Speed is critical, and subject to:clock speedarchitecturealgorithm
In this work, we have concentrated on the latter two elements, understanding theconstraints of architecture and searching for the best algorithms to match eacharchitecture.

We use a variety of techniques to accelerate the basic computations in modularexponentiation. Parallel multiplication is critical, and improvements in modulo
arithmetic and argument handling help.
Below we show one of the most important optimizations, a faster adder, and compare
it to the standard one.

¹~º~»¼¾½¿½^º~»À¾ÁVÂXÃ©Ä[ÅMÆG¼¼ÇPÈ
a0b0O(log n) latency whenlong-distance gates are free.
O(n) when swap required(NTC architecture) -- witha big constant!

The three most important features of an architecture, in terms of its ability to run
algorithms efficiently, are:s1

carrya2
Cin = 1 {Cin = 0 {b2k100k1’0a3
Cin = 1 { b30Cin = 0 {00Better use of concurrentgates (total still O(n) orlarger).

s20s300a4b4k100(Carry-save and carry-lookahead
are other types that reach O(log n).
See quant-ph/9808061, quant-ph/0406142.)

RL`UG¦SJ AXU@JGL F¦¨§BA@F©JBGL[AWs00a1b1k1’0a5
b50000s40s50k¬©FKLL[CXµ~;¦S¸bXbY^AG>X> APL

number of qubits
the ability to run multiple gates concurrently
the interconnect capability of the system: can gates happen between neighbors only,or any arbitrary pair of qubits?
We use architectural descriptions with important features that help us understandperformance. AC supports long-distance gates, while NTC supports only operations
on nearest neighbors.

IteratingInstead of BitsO(n)latencyByonWords
all architectures
Carry ripples one bit at a time(Can use concurrent gates here, but limited above)(Variants used in both major exponentiation algorithms,VBE (quant-ph/9511018) and BCDP (quant-ph/9602016).)ÉIÊxË+Ì|ÍÏÎeË=¬s­¨±=<G?[Xµ~°S^WKJ\F@?BUA·¶©F~J AXW
Two frames froman animation showing
long-distance gateson an AC architecture.
O(log n) possible, dependingon algorithm.

Algorithms that are up to 700 times faster than basic algorithms,
when 100n qubits of storage are available, for factoring a 128-bit
number. Our algorithms are O(n^2 log n) for nearest-neighborarchitectures, and O(n log^2 n) for long-distance-gatearchitectures.

ª«=¬s­¯®[°E±~FC<©@JG²¯ªA]S^~X³B<KL[W´K?¦VC
Swap Swap gateÞ~ÑXÓ ÔGß\àXázâÚPÕ¯ã~ÚXä·åæ@çéèê\ëìxí¦ÛÓ ÒPîSwap gate Swap gate

Position first, then do action gates
Only 1 new neighbor after each swap
What's the performance penalty?
O(n) performance at best.

JLKNMPOQRSLTVU'KWQYXVKZRN[\^]`_YabKbcb[ï`ðTñóòõô öó÷ùøõöú û üýðTñVòVô ö÷×øþöú ûÿ¸üðTñóòVô öó÷xøþöú û          ¸ð   !   " #   $%%   '&  ()*+   ,-.     /0   1¸ð2&  ()3     4 !   +  $-0   5
67    $ 8 +  9 :     ;<  + "=    >  + ? 
700x faster on AC,@    A- B   - 0  +  C-
100x faster on NTC!
D  - "E+ÿF ïÿ FïGH  + IE ÿF ïÿ Fï

Latency for Quantum Modular Exponentiation
algo Balgo Calgo Dalgo E

Latency (CCNOT Gate Count)

1e+07

The primary use of large amounts of spaceis parallel multiplication.
Graph is execution latency (circuit depth)
for exponentiating 128 bits on an AC architecture,for several different algorithms.

1e+06

50

100

150

200

250

300

Space (multiple of n)

H~<=>~^FKLKbB<~?BAG?=JSFXJS^<@?S?~B<PLKWEs^X<KLSJ\Modular exponentiation is thedominant cost in Shor's algorithm.
2n classical modular multiplications
and n quantum modular multiplications
are used in the standard method.

j ¡ 0

ja mod N ¤x : x n  1 x n  2  x 0Binary expansion ofa x mod N q¢ 1 £1qTo factor the n bit
number N, we must
evolve to hold:jLet d j  a 2 mod N
dj values are computed classically3.

dWeXeLf[hgL\fM

We are currently examining the full impact of clock speed, and have begun
investigations into different physical topologies and performing these algorithms
on fault-tolerant, error-corrected qubits.

1000000Algorithms B, C, D, E, VBE(100n), BCDP(100n) use 100n storage;
others use 5n-7ngates for AC are CCNOT, others are CNOTnj 1xj

 0 d j mod N;=AK¥APL`AG?BUAXW
1) P. Shor, “Polynomial time algorithms for prime factorization and discrete logarithms on aquantum computer”, SIAM J. Comp., 1997.
2) R. Van Meter and K. M. Itoh, “Fast Quantum Modular Exponentiation,” quant-ph/0408006.
3) V. Vedral et al., PRA, 1996 (VBE algo.).
4) D. Beckman et al., PRA, 1996 (BCDP algo.).
5) Fowler et al., QIC, 2004, quant-ph/0402196.
6) Draper et al., EQIS 2004, quant-ph/0406142.