## Want to keep learning?

This content is taken from the Keio University's online course, Understanding Quantum Computers. Join the course to learn more.
3.6

# Structure of Shor's algorithm

Let’s talk about the structure of Peter Shor’s algorithm for factoring large numbers.

As we saw, a “quantum” algorithm is really a hybrid quantum-classical algorithm. It begins with some classical processing, then uses the quantum computer to execute a particular part of the algorithm (a subroutine or function) and measures the result. It then takes those results and does some more classical post-processing. The quantum computer essentially serves as a coprocessor to the classical computer.

In the case of Shor’s algorithm, the quantum subroutine is known as the period finding routine, which uses an important technique known as the quantum Fourier transform, or QFT, to create interference that gives us the period. We then use a classical technique known as Euclid’s algorithm to find the prime factors of the number $$N$$. We will go through each of these steps briefly, then there is an article for each of the parts that goes into more detail.

Fig.1. Block structure of Shor’s algorithm

## Modulo Arithmetic

Recall that modulo arithmetic means that any time our result gets to be greater than or equal to the modulus, we subtract the modulus until we’re back between zero and that number minus one.

Doing arithmetic modulo ten is just like keeping track of only the last digit of any addition or multiplication operation, so for example $$9 \times 9 \bmod 10$$ is just 1, rather than 81.

Consider a function where you add four every step, and do the whole thing modulo seven. If you start with zero, your sequence goes 0, 4, then it should go 8, but since 8 is greater than 7, we subtract 7 and we’re back to 1. Then the next step would be 5. Modulo seven, then, is just like doing math in base seven and keeping only the last digit.

## The Period of a Function

A lot of mathematical functions are periodic. That is, if you start by evaluating the function in some place and move forward, eventually you’ll come back to where you started. In fact, the entire sequence of values repeats itself. The time it takes for that repetition to occur is called the period.

We’ve already talked a lot about waves, so you might suspect that the period of a function is like the period of a wave. In fact, it’s exactly like that!

Fig.2. A simple sine wave

Rather than a continuous function like a sine wave, let’s look at what happens just with discrete steps, like modulo arithmetic. Go back to the function of adding four modulo seven, which we can write like this: $$x_{i+1} = x_i + 4 \bmod 7$$. Our sequence of numbers goes

$0, 4, 1, 5, 2, 6, 3, 0$

After seven steps we are back to zero, where we started. If you keep going, the sequence just repeats itself:

$0, 4, 1, 5, 2, 6, 3, 0, 4, 1, 5, 2, 6, 3, 0, 4, 1, 5, 2, 6, 3, ...$

Every 0 is seven steps apart, and even 4 is seven steps apart in that sequence. We say that the period of our function is seven, and we can say that

$$f(x + 7) = f(x)$$.

## The Quantum Fourier Transform

Select a prime number $$a < N$$. It turns out that, if we can find the period $$r$$ of the function $$f(x) = a^x \bmod N$$ as we increment the variable $$x$$, then we can find the factors of $$N$$. The simplest way to do this, of course, is just to repeat calculating $$f(x)$$ until we find two identical results; the number of steps in between will be the period. While it’s theoretically possible, it’s impractical, because the period grows roughly exponentially as the length of the number grows. For large numbers, that period could be enormous, so big that we could calculate for the lifetime of the universe and never find the period. It’s less efficient than the number field sieve we already have. We need a different approach.

A common classical technique for finding the frequency of a signal, which we can easily invert to find the period, is the Fourier transform. If we could take the Fourier transform of a sequence of these results, we might find the period. Doing so classically, unfortunately, would require data from a sequence of results like the one we just described. Still obviously impractical.

With a quantum computer, though, the finding of the period of a function suddenly becomes practical. We take all of the possible values of $$x$$ in superposition, calculate $$f(x)$$, and now we have a superposition of all of the function results. If we can pick two different values of $$x$$ out of the superposition that produce the same $$f(x)$$, then we can find the period.

Unfortunately, we can’t do that directly. As we have seen, any time you measure a superposition, you get one of the possible values randomly, depending on the quantum probability amplitudes. Finding only one value for $$x$$ doesn’t help us at all. Instead, though, we can apply the quantum form of the Fourier transform (the QFT), and it will create interference among all of values of $$x$$, in a fashion that lets us directly read out the period $$r$$!

Of course, this is still no help if either calculating $$f(x)$$ or doing the QFT is computationally expensive. The modular exponentiation and the QFT both turn out to have a cost that is polynomial in the length of the number in bits, a profound reduction compared to the exponential effort necessary to find the period classically.

This is the core of Shor’s algorithm, and one of the most exciting technical results in any field in the last several decades, in our opinion.

## Euclid’s Algorithm

The final classical step is take $$r$$ and use it to find the factors. This is done on a classical computer, using Euclid’s algorithm for finding the greatest common denominator (gcd) of two numbers. Euclid’s algorithm is polynomial in the size of the numbers, and indeed is fairly fast on a classical computer, so there is no need to be concerned about the difficulty of this step.

Assuming we have correctly found the period $$r$$, calculating the gcd of $$N$$ with the numbers $$a^{(r/2)}+1$$ and $$a^{(r/2)}-1$$ will give us two prime factors of the number $$N$$.

### Putting It All Together

Summarizing, let’s assume we’re trying to factor the number $$N$$, which is written using $$n$$ bits. The algorithm consists of the following steps:

1. Pick a prime number $$a < N$$.
2. Use Euclid’s algorithm to check if $$a$$ is a factor of $$N$$; if so, you’re done.
3. Otherwise, prepare your quantum computer and a program for it to execute quantum period finding.
4. The first important quantum step is to calculate the superposition of $$a^x$$ for all values of $$x$$, all done modulo $$N$$. $$|x\rangle$$ and the remainder both appear in our quantum register.
5. Measure the remainder. (Technically, this is unnecessary, but it simplifies the explanation, so we will assume we use it.)
6. Take the quantum Fourier transform (QFT) of $$|x\rangle.$$
7. Measure the register $$|x\rangle$$; call the result $$r$$, which should be a multiple of the period of the modular exponentiation function.
8. If $$r$$ is even and greater than zero, calculate the numbers $$a^{(r/2)}+1$$ and $$a^{(r/2)}-1$$; if not, rerun the quantum portion of the algorithm to find a new $$r$$.
9. Use Euclid’s algorithm to calculate the gcd of each of those numbers and $$N$$, and you should have two factors of $$N$$!

Now, let’s go look at each of the individual techniques, before putting it all together.

# Shorのアルゴリズムの構造

Peter Shorの素因数分解アルゴリズムについて見ていきましょう。

Shorのアルゴリズムにおいては、量子的な繰り返し作業は、繰り返しの単位を見つける上で利用されます。これは、量子フーリエ変換(Quantum Fourier Transform)と呼ばれる手法などにおいて、単位を与える波の干渉を作り出す上で用いられます。私たちはその上で、 N の素因数を見つけるために、ユークリッドのアルゴリズム（ユークリッドの互除法）を用います。これらのステップを簡単に見ていき、一つ一つの細かい記事を見ていきましょう。

Fig.1. Block structure of Shor’s algorithm

## モジュロ演算

モジュロ演算（modなどと呼ばれる)とは、法（基準となる数$$N$$）に対して等しい、またはどれだ け大きい数になっても、その数が0から$$N - 1$$までの間になるまで、$$N$$引き続けるものであったと いうことを思い出してください。

このmodにおいては、どのような加法、乗法においても、最後の桁を見るだけで演算が可能です。例えば、$$9 \times 9 \bmod 10 \equiv 1( \neq 81)$$となります。

$$\bmod 7$$で、毎回４を足していくという関数を考えてみましょう。０から初めたとすると、0, 4そして8というように増えていきますが、8は7より大きいので、7を引いて、1に戻ります。そして再び4を足して5となります。$$\bmod 7$$というのは、7を基準とした数学となり、最終桁だけを追っていけば良いのです。

## 関数の周期

Fig.2. A simple sine wave

$0,4,1,5,2,6,3,0$

というようになります。 7段階踏んだあと、初めと同じ0に戻ります。これを繰り返していくと、下のように、同じ数字の繰り返しが現れます。

$0,4,1,5,2,6,3,0,4,1,5,2,6,3,0,4,1,5,2,6,3,...$

0も4も全ての数字が、7つおきに出てきています。そのため、この関数の周期は7であると言うことができます。そしてこれを表すと、

$f(x+7)=f(x)$

というように書くことができます。

## 量子フーリエ変換

$$a < N$$を満たす素数を一つ選びます。その数について$$f(x) = a^x \bmod N$$という関数$$r$$の周期を発見できた場合、$$N$$素因数を知ることができます。最も単純な方法はもちろん、$$f(x)$$を2つの同じ結果が得られるまで計算し続けることです。確実に周期までの段階で終わらせることが可能です。これは理論的には可能ですが、現実的ではありません。なぜなら、数が大きくなるに連れて、周期は指数関数的に大きくなっていくからです。これは、すでにあるような数のふるいと呼ばれる手法よりも、効率的ではありません。他の手法が必要となります。

しかし量子コンピューターにおいては、関数の周期を見つけることは非常に現実的になってきます。全ての可能な値$$x$$を重ね合わせ状態とし、$$f(x)$$を計算します。そうすることで、関数の結果の全ての重ね合わせ状態を得ることができます。もし2つの異なる値$$x$$が同じ$$f(x)$$値を返したとき、それがその関数の周期となります。

もちろん、これは$$f(x)$$の計算や、量子フーリエ変換が、技術的に厳しいと役には立ちません。冪剰余と量子フーリエ変換は、数の大きさによって、多項式時間での計算コストがかかり、古典的方法で周期を見つける超多項式的な時間に比べると、計算時間を非常に削減できます。

これはShorのアルゴリズムの中心で、今後数十年で最も技術的結果の出そうな分野の一つになると思います。

## 以上のまとめ

$$n$$bitで表される、$$N$$の素因数の求め方をおさらいしてみましょう。アルゴリズムは以下のステップで構成されています。

1. $$N$$より小さい素数$$a$$を選ぶ
2. $$a$$が、$$N$$の素因数であるかを確かめます。もしそうであればそれで終わりです。
3. そうでない場合、量子コンピュータとプログラムを用いて、周期を求めます
4. 量子コンピュータにおける最も重要なステップは、全ての$$x$$に対する$$a^x$$重ね合わせ状態を計算することです。全て$$\bmod N$$ によって行われます。$$\vert x\rangle$$とあまりはどちらも量子レジスタの中に現れます。
5. 余りを計算します。（技術的には必要ありませんが、説明を簡単にするために、この手法を用いていきます。)
6. $$\vert x\rangle$$に対して量子フーリエ変換を行います。
7. レジスタ$$\vert x\rangle$$測定します。この結果は、冪剰余の周期の実数倍となっています。
8. もし$$r$$が0より大きければ$$a^{(r/2)}+1$$と$$a^{(r/2)}-1$$を計算し、0または0より小さいのならば、新しい$$r$$を見つけるために再び量子計算へ戻ります。
9. ユークリッドのアルゴリズムを用いて、各値と$$N$$の最大公約数を求めることで、$$N$$の素因数である2つの数字を得ることができます。