April 29, 2004

3:48

Proceedings Trim Size: 9.75in x 6.5in

pay-the-exponential-full-inline

TRADING CLASSICAL FOR QUANTUM COMPUTATIONUSING INDIRECTIONRODNEY VAN METER
Graduate School of Science and Technology, Keio University and CREST-JST
3-14-1 Hiyoushi, Kohoku-ku, Yokohama-shi, Kanagawa 223-8522, Japan
E-mail: rdv@tera.ics.keio.ac.jp
Modular exponentiation is the most expensive portion of Shor’s algorithm. We show that it is possible
to reduce the number of quantum modular multiplications necessary by a factor of , at a cost of
entries, and performing
adding temporary storage space and associated machinery for a table of times as many classical modular multiplications. The storage space may be a quantum-addressableclassical memory, or pure quantum memory. With classical computation as much as  times as fast
as quantum computation, values of from 2 to 30 seem attractive; physically feasible values dependon the implementation of the memory.

1. Introduction
Any software problem can be solved by adding another layer of indirection.
Steven M. Bellovin
To factor the numberusing
Shor’salgorithm , a quantum computing device must ! #"evolve to hold the state    
for a randomly chosen, fixed  , and $&%('*) ,where + is the bit length of . Let ,.-/% 1032 , and 4  4  0565 4  be the binaryexpansion!
))"of 4 , where  4 holds  the superpositionof all values 7 565 $98;: . The value =<can1""
be rewritten >@? A as B )  ,  <@C. Dividing  4 up into words of length D , let  E3F!G 4IH ,"""
the J th word in  4 , be  E F G 4IH %  4LKNM FO  4LKNM FQO  0 5S5 4 K FO 4 K F for 7UTVJXWZYR[3Y\%]
P
RP
""
K
+_^`Dba .  EF!G 4cH , as part of  4 , will hold a superposition of all values 7 to ' .
"We can reduce the + quantum multiplications to Y by using the superposition  E F G 4cHK
as a quantum
index into a memory array holding the ' + -bit entries with values dQe F %!
?
e 0f1g, where h is the index into the array and J is the iteration number. Thesuperpositionofretrieved from theis multipliedwith the current value, valuesj memoryi! #"
1 m"K
\ B#k  djl M giving    <  1<. A total of YnDo'%   %
C < P?
<K+p' classical and Y quantum modular multiplications must be performed, compared with +classical and + quantum modular multiplications using Vedral’s formulation A .
2. Indirection
In a computer, arguments to an instruction (or function) can be passed by value or byreference. By value arguments appear directly in the bits of the instruction. When accessing
1April 29, 2004

3:48

Proceedings Trim Size: 9.75in x 6.5in

pay-the-exponential-full-inline

2

arguments by reference, the address of the argument is held in the instruction; the actual
value must be retrieved from memory before the function can be evaluated. The address iscalled a pointer or an index. Indirection is a generalization of by reference, in which thevalue retrieved from memory may itself be a pointer which must in turn be dereferenced.
In the straightforward quantum implementation of modular exponentiation, the , - values are classical values held in a single quantum register, manipulated during the forward
and reverse parts of the modular addition. In our proposal, the d e F values are held in a?
"table, and a portion of the  4 superposition is used as an index into that table. That is, weare accessing the arguments through a single level of indirection.
3. TheArray

The d array is our bridge from classical computation to quantum. Each entry is + bits.
KWe must compute ' values for the table, requiring D classical modular multiplications
each, before each of the Y quantum multiplications. The de F values must be stored into?
quantum-accessible memory; this may be done all at once before the quantum computation
Kis begun, if the d array can hold Y ' entries, or right before each separate multiplication, ifK
the d can only hold ' entries.
The array can be held using a quantum addressable classical memory (QACM) . In
such a device, memory cells (the modular exponentiation values) are classical, but a quantum superposition is used as an address, and the read out value is a superposition of eachclassical value in proportion to the “amount” of its address present in the address superposition. One such possible device is an optical plate, with photons steered through the various
cells according to the value of specific address bits. Figure 1 shows a 3-bit example. At"
the top, the input (generally  7 ) is steered left or right according to the high-order bit of
the address superposition (carried on a control line not shown in the figure). Subsequentcircles steer left or right according to their address bits, to reach the appropriate classicaldata memory cells. The values retrieved from the memory are combined to give the fulloutput superposition, in weights according to the address superposition.
An equivalent array of qubits can be used in place of the QACM. However, in that case,the cost of filling the table must be accounted for, and our limitation will be the number ofavailable qubits. Figure 2 shows a 3-bit select circuit which will choose from among the 8possible arguments for the modular multiplier. The desired value F % d l F occupies theg ?
location as shown on the right of the figure; it is then used as the argument to the modular
multiplier. This select circuit can be reversed following the multiplication to restore theoriginal locations of the d  F values.
?

4. The Algorithm
In essence, the algorithm involves moving from a bit-oriented breakdown of the multiplications to a word-oriented breakdown.
The algorithm consists of two main parts: classically calculating the d array values, andcalculating their products in the quantum domain. We pay the classical cost in step 1b in
the algorithm below, and the quantum cost in step 3c.

April 29, 2004

3:48Proceedings Trim Size: 9.75in x 6.5in

pay-the-exponential-full-inline3  

 F?



 F?

 Input



 F?

address superposition F?

                     





        





Figure 1.

  steered byClassical

memory cells

Outputsuperposition

Quantum-Addressable Classical Memory (QACM)

The cost of setting up to use the J th iteration of the d array is technology dependent;
K
only one of steps 1c and 3a is necessary. G +p' H gates may be required to set a quantum
memory, or only the change of a single pointer or position if a QACM is large enough tohold the entire d array at once.
(1) Calculate the d array elements:!

KW '(a) Classically calculate d   %  for all *[7iT?
(b) For J from : to YI8 : , classically square (modulo
D times to create d  F?
(c) (Store all d  F into QACM)"#%$) all 'Kelements d  F ?

?

"(2) Initialize , to 1
Y 8 : , do(3) For J from 7 to I(a) (Set up to use d  F values: store into QACM or quantum memory)?
"""
 E F G 4cH as index into d ,  F %  djl M F(b) In quantum domain, use<i! #"?
P"g(c) , %  F,"#%$&'"#%$



Note that the algorithm uses, but does not specify, modular multiplication. We canApril 29, 2004

3:48

Proceedings Trim Size: 9.75in x 6.5in4
         

pay-the-exponential-full-inline








Figure 2. 3-bit Quantum Select Circuit (Q-SEL)

choose to use a variant of Vedral’s carry-ripple construction, or Gossett’s carry-save 0 ,which will increase our storage requirements but allow more concurrent execution, reducing wall-clock time (and hence coherence time demands) for the computation.
Figure 3 shows a portion of a modified form of Vedral’s circuit using indirection. The
dashed box indicates where update of the d array takes place, if necessary; only one-qubit
gates are required. Note also that Q-SEL and its reverse are used, but, unlike Vedral’s circuit, we do not need the reverse of multiplication to free up our argument. The degeneratecase of D %Z: is therefore faster than Vedral’s circuit.
5. Evaluating Cost and Selecting Word Length
Barenco’s boundon the probability of success using the approximate quantum Fouriertransform is :7or lower for sizes of a few kilobits . While information can be inferred
even from failures that may reduce the number of iterations required, a large number will
be necessary in the real world. Thus, the cost of the one-time classical computations (whichmay be stored and reused) is further amortized.
The goal of this work is to minimize the cost of executing Shor’s algorithm, for somemetric of cost important to the user. In figure 4 we show the total cost of calculating themodular exponentiation, as a function of word length D . “Cost” in this graph is an arbitrary
metric; it may be wall clock time, total time on parallel machines, price tag, or some othereconomic cost of quantum and classical machines. Perhaps the easiest cost to consider issimply time to perform a modular multiplication. The five curves represent total cost atdifferent ratios of quantum:classical cost, ranging from 1:1 to :7 0 :1. The ’x’ marks oneach curve are the nearest integer value of D to the minimum. This recommended word
length increases by approximately eight bits for each factor of one thousand the relativeApril 29, 2004

3:48

Proceedings Trim Size: 9.75in x 6.5in

pay-the-exponential-full-inline5      



Figure 3. Multiplication Using Indirection, Based on Vedral’s Circuit

q:c cost 1e12:1
q:c cost 1e9:1
q:c cost 1,000,000:1
q:c cost 1,000:1
q:c cost 1:1

1e+14

1e+12

1e+10

Total cost update



Q-SELf

MULT-MOD

Q-SEL array      update



Q-SEL





MULT-MOD



Q-SEL



1e+08

1e+06

10000

100

15101520
Word length (w)Figure 4. Total Cost

25303540

April 29, 2004

3:48

Proceedings Trim Size: 9.75in x 6.5inpay-the-exponential-full-inline

6quantum cost increases.
The cost should be normalized to include the differing numbers of times the quantum
and classical calculations must be performed. The classical results can be calculated once,and stored and reused. The quantum algorithm must be rerun until success is achieved.
Using Barenco’s bound, forand ;%.7 , we calculate a probability of success h % :using the AQFT of  5 : 7 A . If it takes one hundred thousand runs, on average, to succeed,then the quantum cost used in the graph should be one hundred thousand times the one-timecost.
This graph is somewhat simplified, in that the cost ratio is treated as fixed. In reality,
the QACM cost will almost certainly depend on the word length.
Commodity microprocessors may be as much as : 7 > times as fast as quantum computing devices. Combined with the success probability, it is clear that the limitation on D
will be the practical size of the d array rather than computational cost.

&6. Conclusions
In this paper, we have shown how the standard computer science technique of indirection
can be used in the quantum domain to accelerate the modular exponentiation that is theprimary cost of Shor’s algorithm. This technique reduces the number of multiplications
necessary, and is independent of the multiplication algorithm chosen. The price we pay
Kfor this is a large classical/quantum tradeoff; we perform ' more multiplications in theclassical domain in exchange for reducing the quantum multiplications by a factor of D .
We expect that this basic technique will apply to other algorithms, as well.
References
1. A. Barenco, A. Ekert, K.-A. Suominen, and P. Törma. Approximate quantum fourier transformand decoherence. Physical Review A, 54:139–146, 1996.
2. P. Gossett. Quantum carry-save arithmetic. http://arXiv.org/quant-ph/9808061, Aug. 1998.
3. N. Kunihiro. Practical running time of factoring by quantum circuits. In Proc. ERATO Conferenceon Quantum Information Science (EQIS2003), Sept. 2003.
4. M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information, pages 266–268. Cambridge University Press, 2000.
5. P. W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proc.
35th Symposium on Foundations of Computer Science, pages 124–134. IEEE Computer SocietyPress, 1994.
6. V. Vedral, A. Barenco, and A. Ekert. Quantum networks for elementary arithmetic operations.
Phys. Rev. A, 54:147–153, 1996. http://arXiv.org/quant-ph/9511018.

Acknowledgments
Thanks to Prof. Kunihiro of the University of Electro-Communications, Drs. Kawano andTakahashi of NTT CRL, Prof. Iwama of Kyoto University, Prof. Yamashita of NAIST, Dr.
Yamaguchi of Stanford, and Prof. Itoh and Eisuke Abe of Keio University. This work wassupported in part by Ken Adelman and Dave Kashtan under the Network Alchemy basic
research funding plan.