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). (|xrangle) 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 (|xrangle.)
7. Measure the register (|xrangle); 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}

正弦波のような、連続関数ではなく、モジュロ演算のような離散的な関数について見ていきましょう。(bmod 7)で、４を加えていく関数について見ていきましょう。それを表すとこのようになります。(x_{i+1} = x_i + 4 bmod 7)数字の順番としては、

[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))値を返したとき、それがその関数の周期となります。

不運にも、私たちはそれを直接行うことはできません。今まで見てきたように、重ね合わせの状態を観測しようとすると、量子的確率の振幅に依存する、ランダムな値が出てきてしまいます。(x)の値一つだけでは全く役に立ちません。そのかわり、フーリエ変換を量子形式に応用して、(x)の全ての間で干渉を作成することで、曲がりなりにも周期(r)を直接得ることができます。

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

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

ユークリッドのアルゴリズム

最後の古典的段階は、周期(r)を発見し、それを用いて素因数を発見することです。これは古典コンピュータで、2つの数の最大公約数を見つけるための、ユークリッドのアルゴリズムを用いて行われます。ユークリッドのアルゴリズムは数字の大きさによって多項式時間的に計算時間が変化し、実際、古典コンピュータと計算速度は変化しないため、このステップは難しく考える必要はありません。

周期(r)を正しく見つけられたとすると、(N)と(a^{(r/2)}+1)と(a^{(r/2)}-1)の最小公倍数を見つけることで、(N)の素因数を導くことができます。

以上のまとめ

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

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

個々の技術について、より詳しく見ていきましょう。