# How many logical qubits are needed to run Shor's algorithm efficiently on large integers ($n > 2^{1024}$)?

First, I know there are differences in logical qubits and physical qubits. It takes more physical qubits for each logical qubit due to quantum error.

Wikipedia states that it takes quantum gates of order $$\mathcal{O}((\log N)^2(\log \log N)(\log \log \log N)$$ using fast multiplication for Shor's Algorithm. That comes out to $$1,510,745$$ gates for $$2^{1024}$$. Further down the article, it says that it usually take $$n^3$$ gates for $$n$$ qubits. This would mean it would take ~$$115$$ qubits.

However, I've run Shor's Algorithm as implemented in Q# samples using Quantum Phase Estimation and it comes out to $$1025$$ qubits.

• Don't get misled by something saying it requires order something. You can't use that to calculate gate counts or numbers of qubits, because (i) there are arbitrary constants that are suppressed by the notation that could change orders of magnitude very easily, and (ii) scaling descriptions like that are only true in the large n limit. For any finite n, behaviour could be a bit different, dominated by a term with a weaker scaling but larger unknown factor. – DaftWullie Dec 26 '18 at 11:24

The question is about how many logical qubits it takes to implement Shor's algorithm for factoring an integer $$N$$ of bit-size $$n$$, i.e., a non-negative integer $$N$$ such that $$1 \leq N \leq 2^n{-}1$$. The question is a poignant one and not easy to answer as there are various tradeoffs possible (e.g., between number of qubits and circuit size).

Executive Summary Answer: $$2n{+}2$$ qubits which leads to a quantum circuit implementation that has less than $$448 n^3 \log_2(n)$$ number of $$T$$-gates. For a bit-size of $$n=1,024$$, this would work out to be $$2050$$ logical qubits and $$4.81 \cdot 10^{12}$$ $$T$$-gates.

As mentioned in the question, one can apply fast methods such as Schoenhage-Strassen's algorithm for fast multiplication to implement the modular arithmetic asymptotically in $$O(n^2 \log(n) \log \log(n))$$ primitive operations (say, over the Clifford$$+T$$ gate set). This has been discussed for instance in Zalka's paper. However, it should be pointed out that this is indeed (i) only a statement about asymptotic cost and (ii) only a statement about the number of operations required and does not imply the number of qubits.

Regarding (i), the constant that is hidden in the "O-notation" can be prohibitively large. To the best of my knowledge, it has not been attempted to construct a quantum circuit to implement Shor's algorithm based on Schoenhage-Strassen, so we do not even know upper bounds on what that constant is. The other catch, (ii), is that it is not straightforward to relate the number of qubits and the gate cost as seems to be suggested in the question. Besides the fact that we do not know the constant, there is another issue, namely that a straightforward implementation of Schoenhage-Strassen via Bennett's method would lead to a very large number of logical qubits required. Therefore, even as there are faster methods available for integer multiplication than the simple method of n additions, these are much more non-trivial to code in quantum programming languages such as LIQUi|> and Q#.

In terms of concrete resource estimates for Shor's algorithm, the paper by Haener et al might be a good entry point which implemented the arithmetic in terms of so-called Toffoli gates which have the advantage of being testable at scale on classical input vectors. It is shown in that paper that $$2n{+}2$$ logical qubits are sufficient to implement Shor's algorithm for factoring integers using a circuit that uses $$64 n^3 \log_2(n)$$ Toffoli gates which yields $$448 n^3 \log_2(n)$$ primitive gates (this latter number refers to the number of $$T$$-gates and ignores that number of Clifford gates as these are significantly more easy to implement fault-tolerantly).

The currently available Q# implementation of Shor's algorithm (see the IntegerFactorization sample at https://github.com/microsoft/quantum) is based on another way of implementing the arithmetic, namely based on Draper's method to implement additions using the Fourier basis, see also here. This implementation follows Beauregard's paper and requires $$2n{+}3$$ logical qubits in total. A recent improvement has been obtained by Gidney who reduced the number of clean qubits to $$2n{+}1$$ (of which only $$n{+}2$$ have to be "clean" qubits, i.e., initialized in a known state. The rest can be "dirty" qubits that can be used and returned in their (unknown) state). Finally, there is an interesting claim by Zalka that the number of qubits can be reduced to $$1.5n{+}2$$ (and perhaps even further), however, his proposed solution comes at a dramatic increase of circuit size as it involves inversions and, to my knowledge, has not been verified nor implemented in a programmatic way.

• I wouldn't call my paper "an improvement of the gate count". It has a gate count orders of magnitude worse to save that one qubit. Fun though. – Craig Gidney Dec 27 '18 at 3:10
• there you go, fixed it. – MartinQuantum Dec 27 '18 at 18:21
• You say $448 n^3 \log_2(n)$ in one place and $448 n^2 \log_2(n)$ in another. – Craig Gidney Jan 12 at 17:13
• According to the paper you cited, the $448n^3 \lg n$ complexity applies to elliptic curves, not to integers. – Craig Gidney Jan 14 at 5:47
• We're slowly getting there. Thanks again and sorry for confusing the numbers. You are absolutely right: $64 n^3 \log_2(n)$ Toffoli gates for factoring, which, using the deterministic circuit identity for Toffoli (=7 T gates per Toffoli), shakes out to be $448 n^3 \log_2(n)$ T-gates after all. Ironically, this $448 n^3 \log_2(n)$ expression also occurs in the estimates for Shor ECC but there is refers to Toffolis, i.e., the cost for same bit size is about a factor 7 higher for Shor ECC than for Shor factoring. Hope it makes sense now. – MartinQuantum Jan 20 at 1:23