【Quantum Challenge2021】ショアのアルゴリズムで35を因数分解する

2021年5月20日から27日にかけて開催されたIBM Quantum Challenge2021の第二問「ショアのアルゴリズム」を解説します。

問題はこちらから入手できます。日本語翻訳もしていただいているのでチャレンジできなかった方も気軽にご覧下さい。

ショアのアルゴリズムとは

ショアのアルゴリズムとは素因数分解を量子コンピューターで効率的に解くためのアルゴリズムで、おそらく社会的には最も注目されているかもしれません。

というのも量子コンピューターが実現すると暗号が破られるとよく言われていますが、実はその主役となっているのがこのショアのアルゴリズムだからです。

現在のRSA暗号は大きな数の素因数分解が古典コンピューターでは計算が困難であるという特性を利用しているため、素因数分解が効率的に解くことが出来るとRSA暗号は破られてしまう可能性があるのです。

問題の前提を理解する

第二問では35を因数分解するアルゴリズムの作成をゴールとしていますが、ショアのアルゴリズムをゼロから作り上げることを目的にはしていないことに注意が必要です。

問題文に「ズル(cheat)」とあるように、今回の問題は位数という素因数分解にあたって最も重要な要素を既に与えられた状態からスタートしています。つまり今回の問題は量子回路を作ってショアのアルゴリズムが正しく動作するか検証することが問題となっています。

では前提として与えられた位数とはそもそも何か説明します。

位数とは整数$N$を法とする共通の因数を持たない整数$x$に対して以下の式を満たす最小の整数$r$を指します。

$x^r \mod N = 1$

素因数分解は一般的に位数発見問題に帰着され、位数を発見することが最重要課題となります。

位数さえ発見さえしてしまえば素因数分解は簡単です。位数$r$が偶数であれば

$(x^r – 1) \mod N = 0 \rightarrow (x^{r/2}+1)(x^{r/2}-1) \mod N = 0$

であるため$(x^{r/2}\pm1) \mod N = 0$であるか、$x^{r/2}\pm1$が$N$の因数を持つかということを表します。つまり$x^{r/2}\pm1$と$N$との公約数を求めることで$N$の因数を得ることができ、これを繰り返すことで最終的に素因数へと分解することが出来ます。

Quantum Challengeの問題ではこの位数$r$が前提として与えられているため「ズル」と表現しているのです。今回は35の位数として$r=4$が与えられていますね。実際に$13^4 \mod 35 = 1$です。

問題では位数を発見するためのサブルーチンとなるユニタリ演算を考えることが求められています。

$U_{x, N}|\alpha\rangle = |\alpha x\mod N\rangle$

このユニタリ演算の固有値は$0 \le s \le r-1$となる整数$s$をラベルとして$\exp(2\pi is/r)$と与えられます。この演算を満たすような量子回路を作成しましょうという話です。

問題を解いていく

では実際に問題に取り組みます。まず最初は次のような位数4の下、35の法として13倍する演算を実現する量子回路を作成します。アウトプットは入力を13倍して35で割った余りとなっています。

$$\begin{aligned}U|1\rangle &= |13\rangle \\ U|13\rangle &= UU|1\rangle &= |29\rangle \\ U|29\rangle &= UUU|1\rangle &= |27\rangle \\ U|27\rangle &= UUUU|1\rangle &= |1\rangle\end{aligned}$$

量子回路で扱いやすいようにそれぞれの数字を量子ビットにエンコード($|1\rangle→|00\rangle, |13\rangle→|01\rangle, |29\rangle→|10\rangle, |27\rangle→|11\rangle$)すると、最終的に満たすべき式は下のようになります。

$$\begin{aligned}U|00\rangle &= |01\rangle \\ U|01\rangle &= |10\rangle \\ U|10\rangle &= |11\rangle \\ U|11\rangle &= |00\rangle\end{aligned}$$

状態変化を見ると、右の量子ビットは必ず反転し、左の量子ビットは右の量子ビットが1だと反転して0だと何もしないです。

以上を踏まえると次のような回路が一例として考えられます。

from qiskit import QuantumCircuit
from qiskit import QuantumRegister, QuantumCircuit
c = QuantumRegister(1, 'control')
t = QuantumRegister(2, 'target')
cu = QuantumCircuit(c, t, name="Controlled 13^x mod 35")


cu.ccx(0,1,2)
cu.cx(0,1)

基本的にはこのような考え方で問題は解き進めることが出来ます。続いてまた量子回路を作っている理由は、位数発見サブルーチンの固有値を求める際に、一定の精度を出すために$n$個の量子ビットを使って固有値を推定しようとした場合、$U^{2^n}$を実行する回路を作る必要があるためです。

詳しくはユニタリ演算の固有値を推定する位相推定アルゴリズムで調べてみてください。問題文中で位相推定という言葉が使われているのはそのためです。

今回使用を想定している量子コンピューター実機は5量子ビット存在していて、2つは状態のエンコーディングに使用しているため、残りの3量子ビットを使用して位数(固有値)を推定しようというわけです。

ということで同様に$U^2$と$U^4$を実行する回路を作ればいいということになります。

次の問題では同じように考えて以下の演算を満たす量子回路を考えます。

$$\begin{aligned}U|00\rangle &= |10\rangle \\ U|01\rangle &= |11\rangle \\ U|10\rangle &= |00\rangle \\ U|11\rangle &= |01\rangle\end{aligned}$$

と言っても求める回路は$U^2$なので先ほどの回路を2つ続ければよいはずですね。

c = QuantumRegister(1, 'control')
t = QuantumRegister(2, 'target')
cu2 = QuantumCircuit(c, t)
cu2.ccx(0,1,2)
cu2.cx(0,1)
cu2.ccx(0,1,2)
cu2.cx(0,1)

最後は$U^4$です。

$$\begin{aligned}U|00\rangle &= |00\rangle \\ U|01\rangle &= |01\rangle \\ U|10\rangle &= |10\rangle \\ U|11\rangle &= |11\rangle\end{aligned}$$

こちらも同じように$U$を4回続けても問題ありませんが、問題文のヒントにあるようによく見ると全てのインプットとアウトプットで状態の変化が起きていません。つまりこれは何もゲート操作をしていないのと同等です。つまりこんな風に書いても正解になるはずですね。

c = QuantumRegister(1, 'control')
t = QuantumRegister(2, 'target')
cu4 = QuantumCircuit(c, t)

以上の回路を組み合わせて位数を発見するサブルーチンの量子回路を組み立てます。一般に量子位相推定の回路は下のように作られます。

従って今回の回路は下のように作ることが出来ます。$U^4$はゲート操作を含まないため回路上では表現されません。

量子回路を実行して位数を求める

では作成したこの回路を実際の実機(santiego)で実行してみましょう。

from qiskit import Aer
qasm_sim = Aer.get_backend('aer_simulator')
counts = qasm_sim.run(tqc).result().get_counts()
plot_histogram(counts)

実行結果はノイズが乗っているものの0,2,4,8の観測確率が大きく、ほぼ等確率で観測されました。この値は何かというと、ユニタリ演算の固有値$\exp(2\pi is/r)$を位相推定アルゴリズムを通して$2^n\cdot\frac{s}{r}$が観測されています。今回は$n=3$です。

$s$は$0\le s \le r-1$を満たす適当な整数であり、これを踏まえると、$s/r$の値として$0, 1/4, 3/4, 1/2$が当てはまるので$r$は4であろうと推定することが出来ます。

このように問題で与えられていた位数$r$が正しいことを確かめることが出来ました。