;

IJ

 !#"KSpeed 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.

d^e+4/^ - g\ 4&'FzOXO O(log n) latency whenlong-distance gates are free.
O(n) when swap required(NTC architecture) -- witha big constant!

s00
a1
b1s1

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

0s20

s30
a4b4k100k1’0
a5
b50000s40

s50kdO#"IteratingInstead of BitsO(n)latencyBy
onWords
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¬¶'·¸

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.

 (¡£¤¥§¦£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.

,Y

Swap Swap gate=FEHGa0¢

3+.e`&a"2/BDCUVV Wb0O!/Two frames froman animation showing
long-distance gateson an AC architecture.
O(log n) possible, dependingon algorithm.

<Below we show one of the most important optimizations, a faster adder, and compare
it to the standard one.

""z+c::{Y.

We use architectural descriptions with important features that help us understandperformance. AC supports long-distance gates, while NTC supports only operations
on nearest neighbors.

=,AWe 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.

The three most important features of an architecture, in terms of its ability to run
algorithms efficiently, are: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?

@®R¯4°±a­f²g«³2´Oª(Carry-save and carry-lookahead
are other types that reach O(log n).
See quant-ph/9808061, quant-ph/0406142.)dx"z-^`{+g'&-,X"|ZY~}OX^"z/?

PQRMTS¨©ª^«'¬(­MNO

=#>"!$&%#'("'*),+.-/0)213+45)67-8)29&:

Establish fast quantum modular exponentiation algorithms to run
Shor's algorithm on various quantum computer architectures,using the best available quantum and classical techniques. This
will support performance analysis of both architectures andalgorithms, benefiting near-term experimentation and long-term
research planning.
L/F+.-< "!#¹z±,­º»±¼½ ¾^¿ÀÁzÂ Ã

ÄÅ²g«'ªaÆÇ È#ÉÊËÍÌÏÎyÙiÚÜÛ ÝßÞÓà]áÛãâNäåÚgÈ'ìyí æcÞîçïéÛãâNäNðÙ2ÚÜÛñòÝóä4äcôTõöðÞ÷áTïéÛãâNäï
ÚãÈ'ìyí^ñûÝóä4äcôTõDàÏÞ÷á4êÏÛãâNäïü àÏÞîïéáÛãâNäNð
ý ê4ÞÖðcÝÛãâNäéá
700x faster on AC,þ ÝßÞÓàà]ÛãâNäï
100x faster on NTC!
 àÏÞ ÝóçéÛãâNäéá ÝßÞÖðcÝÛãâNäéáÐTÌ]ÑÓÒ
ÝàNÞëá
Ýóïæ]ç
æ_ÞÓð
ê4êï
ÝÿäNà
áðä
ð.àÏð

ÕÔ È#ÉÊËÍÌNÎæcÞèçÏçéÛãâNäåÝßÞÖê4à]ÛãâNäå
ê4ÞøäcêÏÛãâNäNð
ïNÞÓð_ÝÛãâNäïÝßÞøäéðNÛãâNäåÝßÞÖê.åéÛãâNäïæcÞèåÏçéÛãâNäï× ÍÇ
× ÍÇ
ÐTÌ]ÑÖÒ
ÝêÞÓð
Ýùï
ðúæ
æ_ÞÓð
êï.ä
ÝùäÏà

×gÔØÈ#É4Ê.ËÍÌNÎ ÐTÌ]ÑÖÒ
åNÞëê.à]ÛãâNäåÝæcÞîïæãÛãâNäåÝTÞèåá.ÞèäcáÛãâNäNðÝúð
àÏÞëêïéÛãâNäNðêáÝßÞÖððNÛãâNäå æ_ÞÓðÝßÞÖðcÝÛãâNäNðæNçåNÞ ÝÝÛãâNäï Ýùä]ê
× ÍÇ
× ÍÇ

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)XZYN"P [:\+]O8+.^

Modular exponentiation is thedominant cost in Shor's algorithm.
2n classical modular multiplications
and n quantum modular multiplications
are used in the standard method.
2+_S^`7a"(bc/a mod N monqt 1

u

js 0

ja mod N v

x : x n j 1 x n j 2 kckck x 0

Binary expansion ofxdY.ea"f+g`ih1
qr

To factor the n bit
number N, we must
evolve to hold:jLet d j l a mod N
dj values are computed classically3.

$#%

%'&

( &

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 CNOTnjpq 1xjd j mod N0 xw#"y^-/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.