Categories: Algorithms, Cryptography, Quantum information.

Shor’s algorithm

Shor’s algorithm was the first truly useful quantum algorithm. It can solve important problems, most notably integer factorization, much more efficiently than any classical algorithm. It weakens widely-used cryptographic schemes, such as RSA and Diffie-Hellman.

In essence, Shor’s algorithm’s revolutionary achievement is that it can efficiently find the periods s1,...,sAs_1, ..., s_A of a function f(x1,...,xA)f(x_1, ..., x_A) on a discrete finite field, where:

f(x1,...,xA)=f(x1+s1,...,xA+sA)\begin{aligned} f(x_1, ..., x_A) = f(x_1 + s_1, ..., x_A + s_A) \end{aligned}

This is a so-called hidden subgroup problem for a finite Abelian group. With minimal modifications, Shor’s algorithm can solve practically every such problem.

Integer factorization

Originally, Shor’s algorithm was designed to factorize an integer NN. For reasons explained later, this means our goal is to find the period ss of the modular exponentiation function ff:

f(x)=axmodN\begin{aligned} f(x) = a^x \bmod N \end{aligned}

For a given aa and NN. The period ss is the smallest integer satisfying f(x)=f(x+s)f(x) = f(x+s). To do this, the following 2q2q-qubit quantum circuit is used, with qq chosen so that N22q<2N2N^2 \le 2^q < 2 N^2:

Shor's circuit

Here, QFTq\mathrm{QFT}_q refers to the qq-qubit quantum Fourier transform, and the oracle UfU_f calculates f(x)f(x) for predetermined values of aa and NN. It is an XOR oracle, working as follows:

xyUf(a,N)xyf(x)\begin{aligned} \Ket{x} \Ket{y} \quad \to \boxed{U_f(a, N)} \to \quad \Ket{x} \Ket{y \oplus f(x)} \end{aligned}

Execution starts by applying the Hadamard gate HH to the first qq qubits, yielding:

0q0qHq+q0q=1Qx=0Q1x0q\begin{aligned} \Ket{0}^{\otimes q} \Ket{0}^{\otimes q} \quad \to \boxed{H^{\otimes q}} \to \quad \Ket{+}^{\otimes q} \Ket{0}^{\otimes q} = \frac{1}{\sqrt{Q}} \sum_{x = 0}^{Q - 1} \Ket{x} \Ket{0}^{\otimes q} \end{aligned}

Where Q=2qQ = 2^q, and x\Ket{x} is the computational basis state x1xq\Ket{x_1} \cdots \Ket{x_q}. Moving on to UfU_f:

1Qx=0Q1x0qUf(a,N)1Qx=0Q1xf(x)\begin{aligned} \frac{1}{\sqrt{Q}} \sum_{x = 0}^{Q - 1} \Ket{x} \Ket{0}^{\otimes q} \quad \to \boxed{U_f(a, N)} \to \quad \frac{1}{\sqrt{Q}} \sum_{x = 0}^{Q - 1} \Ket{x} \Ket{f(x)} \end{aligned}

Then we measure f(x)f(x), causing it collapse as follows for an unknown arbitrary value of x0x_0:

f(x0)=f(x0+s)=f(x0+2s)==f(x0+(L1)s)\begin{aligned} f(x_0) = f(x_0 + s) = f(x_0 + 2s) = \cdots = f(x_0 + (L-1) s) \end{aligned}

Due to entanglement, the unmeasured (top qq) qubits change state into a superposition:

1L=0L1x0+s\begin{aligned} \frac{1}{\sqrt{L}} \sum_{\ell = 0}^{L - 1} \Ket{x_0 + \ell s} \end{aligned}

Clearly, there is a periodic structure here, but we cannot measure it directly, because we do not know the value of x0x_0, which, to make matters worse, changes every time we run the algorithm. This is where the QFT comes in, which outputs the following state:

1QLk=0Q1(=0L1ωQ(x0+s)k)k\begin{aligned} \frac{1}{\sqrt{QL}} \sum_{k = 0}^{Q - 1} \bigg( \sum_{\ell = 0}^{L - 1} \omega_Q^{(x_0 + \ell s) k} \bigg) \Ket{k} \end{aligned}

Where ωQ\omega_Q is a QQth root of unity. Measuring this state yields a k\Ket{k}, with a probability P(k)P(k):

P(k)=1QL=0L1ωQ(x0+s)k2=1QLωQx0k=0L1ωQsk2=1QL=0L1ωQsk2\begin{aligned} P(k) = \frac{1}{QL} \bigg| \sum_{\ell = 0}^{L - 1} \omega_Q^{(x_0 + \ell s) k} \bigg|^2 = \frac{1}{QL} \bigg| \omega_Q^{x_0 k} \sum_{\ell = 0}^{L - 1} \omega_Q^{\ell s k} \bigg|^2 = \frac{1}{QL} \bigg| \sum_{\ell = 0}^{L - 1} \omega_Q^{\ell s k} \bigg|^2 \end{aligned}

The last step holds because ωQ=1|\omega_Q| = 1. Surprisingly, this implies that we did not need to perform the measurement of f(x)f(x) earlier! This makes sense: the period ss does not depend on x0x_0, so why would we need an implicit x0x_0 to determine ss?

So, what does the above probability P(k)P(k) work out to? There are two cases:

ifωQsk=1:P(k)=1QLL2=LQifωQsk1:P(k)=1QL1ωQskL1ωQsk2\begin{alignedat}{2} &\mathrm{if} \: \omega_Q^{sk} = 1: \qquad &&P(k) = \frac{1}{QL} |L|^2 = \frac{L}{Q} \\ &\mathrm{if} \: \omega_Q^{sk} \neq 1: \qquad &&P(k) = \frac{1}{QL} \Bigg| \frac{1 - \omega_Q^{sk L}}{1 - \omega_Q^{sk}} \Bigg|^2 \end{alignedat}

Where the latter case was evaluated as a geometric series. The condition ωQsk ⁣= ⁣1\omega_Q^{sk}\!=\!1 is equivalent to asking if sksk is a multiple of QQ, i.e. if sk=cQsk = cQ, for an integer cc.

Recall that LL is the number of times that ss fits in QQ, so L ⁣= ⁣Q/sL\!=\!\lfloor Q / s \rfloor. Assuming Q/sQ/s is an integer, then L ⁣= ⁣Q/sL\!=\!Q/s and Q ⁣= ⁣sLQ\!=\!s L, which tells us that ωQsk ⁣= ⁣ωsLsk ⁣= ⁣ωLk\omega_Q^{sk}\!=\!\omega_{s L}^{s k}\!=\!\omega_L^k. This implies that if kk is a multiple of LL (i.e. k ⁣= ⁣cLk\!=\!c L), then ωLk ⁣= ⁣1\omega_L^k\!=\!1, so P(k)=L/QP(k) = L / Q, which is exactly what we got earlier!

In other words, the condition ωQsk ⁣= ⁣1\omega_Q^{sk}\!=\!1 is equivalent to Q/sQ/s being an integer. In that case, we have that Q ⁣= ⁣sLQ\!=\!sL, which we substitute into P(k)P(k) from earlier:

if(Q/s)N:P(k)=LQ=1s\begin{aligned} \mathrm{if} \: (Q/s) \in \mathbb{N}: \qquad P(k) = \frac{L}{Q} = \frac{1}{s} \end{aligned}

And because kk is a multiple of LL, and LL fits ss times in QQ, there must be exactly ss values of kk that satisfy P(k)=1/sP(k) = 1/s. Therefore the probability of all other kk-values is zero! This becomes clearer when you look at the sum used to calculate P(k)P(k): if Q ⁣= ⁣sLQ\!=\!sL, then it sums ωLk\omega_L^{\ell k} over \ell, leading to perfect destructive interference for the “bad” kk-values, leaving only the “good” ones.

So, to summarize: if Q/sQ/s is an integer, then measuring only yields kk-values that are multiples of L ⁣= ⁣Q/sL\!=\!Q/s. Running Shor’s algorithm several times then gives several kk-values separated by LL. That tells us what LL is, and we already know QQ, so we finally find the period s=Q/Ls = Q/L.

That begs the question: what if Q/sQ/s is not an integer? We cannot check this, since ss is unknown! Instead, we rewrite the probability P(k)P(k) as follows:

if(Q/s)∉N:P(k)=1QL1ωQskL1ωQsk2=1QLsin(πskL/Q)sin(πsk/Q)2\begin{aligned} \mathrm{if} \: (Q/s) \not\in \mathbb{N}: \qquad P(k) = \frac{1}{QL} \Bigg| \frac{1 - \omega_Q^{sk L}}{1 - \omega_Q^{sk}} \Bigg|^2 = \frac{1}{QL} \Bigg| \frac{\sin(\pi s k L / Q)}{\sin(\pi s k / Q)} \Bigg|^2 \end{aligned}

This function peaks if sks k is close to a multiple of QQ, i.e. skcQs k \approx c Q, which we rearrange:

kQcs\begin{aligned} \frac{k}{Q} \approx \frac{c}{s} \end{aligned}

We know the left-hand side, and, from the definition of f(x)f(x), clearly sNs \le N. We chose QN2Q \sim N^2, so ss is quite small, and consequently cc is too, since k<Qk < Q.

In other words, c/sc/s is a “simple” fraction, so our goal is to find a “simple” fraction that is close to the “complicated” fraction k/Qk/Q. For example, if k/Q ⁣= ⁣0.332k/Q\!=\!0.332, then probably c/s ⁣= ⁣1/3c/s\!=\!1/3.

This can be done rigorously using the continued fractions algorithm: write k/Qk/Q as a continued fraction, until the non-integer part of the denominator becomes small enough. This part is then neglected, and we calculate whatever is left, to get an estimate of c/sc/s.

Of course, P(k)P(k) is a probability distribution, so even though the odds are in our favour, we might occasionally measure a misleading kk-value. Running Shor’s algorithm several times “fixes” this.

So, to summarize: if Q/sQ/s is not an integer, the measured kk-values are generally close to cQ/sc Q / s for an integer cc. By approximating k/Qk/Q using the continued fraction algorithm, we estimate c/sc/s. Repeating this procedure gives several values of c/sc/s, such that ss is easy to deduce by taking the least common multiple of the denominators.

In any case, once we think we have ss, we can easily verify that f(x) ⁣= ⁣f(x ⁣+ ⁣s)f(x)\!=\!f(x\!+\!s). Whether ss is the smallest such integer depends on how lucky we are, but fortunately, for most applications of this algorithm, that does not actually matter, and usually we find the smallest ss anyway.

You typically need to repeat the algorithm O(logq)\mathcal{O}(\log{q}) times, and the QFT is O(q2)\mathcal{O}(q^2). The bottleneck is modular exponentiation ff, which is O(q2(logq)loglogq)\mathcal{O}(q^2 (\log{q}) \log{\log{q}}) and therefore worse than the QFT, yielding a total complexity of O(q2(logq)2loglogq)\mathcal{O}(q^2 (\log{q})^2 \log{\log{q}}).

OK, but what does ss have to do with factorizing integers? Well, recall that ff is given by:

f(x)=axmodN\begin{aligned} f(x) = a^x \bmod N \end{aligned}

NN is the number to factorize, and aa is a random integer coprime to NN, meaning gcd(a,N)=1\gcd(a, N) = 1. The fact that ss is the period of ff for a certain aa-value, implies that:

ax=ax+smodN    1=asmodN\begin{aligned} a^x = a^{x + s} \bmod N \quad \implies \quad 1 = a^s \bmod N \end{aligned}

Suppose that ss is even. In that case, we can rewrite the above equation as follows:

(as/2)21=0modN\begin{aligned} (a^{s/2})^2 - 1 = 0 \bmod N \end{aligned}

In other words, (as/2)2 ⁣ ⁣1(a^{s/2})^2 \!-\! 1 is a multiple of NN. We then use that (a ⁣ ⁣b)(a ⁣+ ⁣b)=a2 ⁣ ⁣b2(a\!-\!b) (a\!+\!b) = a^2\!-\!b^2:

(as/21)(as/2+1)=0modN\begin{aligned} \big( a^{s/2} - 1 \big) \big( a^{s/2} + 1 \big) = 0 \bmod N \end{aligned}

Because ss is even by assumption, the two factors on the left are integers, and as just mentioned, their product is a multiple of NN. Then we only need to calculate:

gcd ⁣(as/2 ⁣ ⁣1,N)>1andgcd ⁣(as/2 ⁣+ ⁣1,N)>1\begin{aligned} \gcd\!\big( a^{s/2}\!-\!1, N \big) > 1 \quad\:\: \mathrm{and} \quad\:\: \gcd\!\big( a^{s/2}\!+\!1, N \big) > 1 \end{aligned}

And there we have the factors of NN! The gcd\gcd can be calculated efficiently in O(q2)\mathcal{O}(q^2) time.

But what if ss is odd? No problem, then we just choose a new aa coprime to NN, and keep repeating Shor’s algorithm until we do find an even ss. We do the same if as/2 ⁣± ⁣1a^{s/2}\!\pm\!1 is itself a multiple of NN.

References

  1. J.S. Neergaard-Nielsen, Quantum information: lectures notes, 2021, unpublished.
  2. S. Aaronson, Introduction to quantum information science: lecture notes, 2018, unpublished.