Lean, informalized

Nielsen & Chuang · Chapter 5, The quantum Fourier transform and its applications · p. 244

Problem 5.4 - With fast multiplication, factoring a number of LL bits takes O(L2log⁡Llog⁡log⁡L)O(L^2 \log L \log\log L) operations

Fast multiplication brings quantum factoring below cubic cost.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Exercise

Shor’s algorithm factors a number NN of LL bits. A classical reduction turns factoring into finding the order rr of an element xx modulo NN, the least rr with xr≡1(mod⁡N)x^r \equiv 1 \pmod N, and order finding is phase estimation: a first register of qubits controls a modular exponentiation, an inverse quantum Fourier transform acts on that register, the register is measured, and the continued fraction algorithm extracts rr from the outcome. The modular exponentiation is built from multiplications of numbers of LL bits modulo NN. With schoolbook multiplication, of order L2L^2 operations each, the algorithm takes of order L3L^3 operations.

The exercise is to count again with a fast multiplication and to show that the whole algorithm then takes of order L2log⁡Llog⁡log⁡LL^2 \log L \log\log L operations, fewer than L3L^3 for large LL.

The Operation Count

The first register of order finding for a number of LL bits holds t(c,L)=2L+1+ct(c,L) = 2L + 1 + c(1)✦ qubits, where the number cc of extra qubits sets the probability of success.

The modular exponentiation controlled by a register of tt qubits uses μ(t)=(t−1)+(t−1)\mu(t) = (t-1) + (t-1)(2)✦ multiplications. For factoring the register has the size (1), and the number of multiplications is m(c,L)=μ(t(c,L))=4L+2c.m(c,L) = \mu\bigl(t(c,L)\bigr) = 4L + 2c .(3)✦

The gates outside the exponentiation, among them those of the inverse Fourier transform on the first register, are bounded by the square of its size, g(c,L)=t(c,L)2.g(c,L) = t(c,L)^2 .(4)✦

A fast multiplication of two numbers of LL bits, such as that of Schönhage and Strassen, takes of order F(L)=Llog⁡Llog⁡log⁡LF(L) = L \log L \, \log\log L(5)✦ operations, with log\log the natural logarithm. The improved bound B(L)B(L) for the operation count of factoring a number of LL bits is LL times F(L)F(L): B(L)=L2log⁡Llog⁡log⁡L.B(L) = L^2 \log L \, \log\log L .(6)✦

The Claim

Let M(L)M(L) be the number of operations in one multiplication or division of numbers of LL bits, K(L)K(L) the number of steps of the continued fraction algorithm that recover the order, each step costing M(L)M(L), and R(L)R(L) the cost of the classical reduction from the order to a factor.

Theorem 1. Let cc be a fixed number of extra qubits, and suppose that, as L→∞L \to \infty, M(L)=O(F(L))M(L) = O\bigl(F(L)\bigr), K(L)=O(L)K(L) = O(L) and R(L)=O(L2)R(L) = O(L^2). Then the operation count of the whole algorithm satisfies m(c,L)M(L)+g(c,L)+K(L)M(L)+R(L)=O(B(L))m(c,L)\, M(L) + g(c,L) + K(L)\, M(L) + R(L) = O\bigl(B(L)\bigr)(7)✦ as L→∞L \to \infty, and the improved bound itself satisfies B(L)=o(L3).B(L) = o\bigl(L^3\bigr) .(8)✦

What Is Checked

The claim is stated over the register size (1), the multiplication counts (2) and (3), the gate bound (4), and the growth rates FF and BB of (5) and (6).