Editing Shor's algorithm (section)

=== The bottleneck ===
The runtime bottleneck of Shor's algorithm is quantum [[modular exponentiation]], which is by far slower than the [[quantum Fourier transform]] and classical pre-/post-processing. There are several approaches to constructing and optimizing circuits for modular exponentiation. The simplest and (currently) most practical approach is to mimic conventional arithmetic circuits with [[reversible computing|reversible gates]], starting with [[Adder (electronics)#Ripple-carry adder|ripple-carry adders]]. Knowing the base and the modulus of exponentiation facilitates further optimizations.<ref>{{cite journal |first1=Igor L. |last1=Markov |first2=Mehdi |last2=Saeedi |title=Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation |journal=Quantum Information and Computation |volume=12 |issue=5–6 |pages=361–394 |year=2012 |doi=10.26421/QIC12.5-6-1 |arxiv=1202.6614 |bibcode = 2012arXiv1202.6614M |s2cid=16595181 }}</ref><ref>{{cite journal |first1=Igor L. |last1=Markov |first2=Mehdi |last2=Saeedi |title=Faster Quantum Number Factoring via Circuit Synthesis |journal=Phys. Rev. A |volume=87 |issue= 1|pages=012310 |year=2013 |arxiv=1301.3210 |bibcode = 2013PhRvA..87a2310M |doi = 10.1103/PhysRevA.87.012310 |s2cid=2246117 }}</ref> Reversible circuits typically use on the order of <math>n^3</math> gates for <math>n</math> qubits. Alternative techniques asymptotically improve gate counts by using [[quantum Fourier transform]]s, but are not competitive with fewer than 600 qubits owing to high constants.