ショアのアルゴリズム

次に、整数因数分解問題に注目し、位相推定を用いて量子コンピューター上でどのように効率的に解くことができるかを見てみよう。 私たちが手に入れるアルゴリズムは、 整数因数分解のためのショールのアルゴリズムである。 ショールは彼のアルゴリズムを位相推定という観点から具体的に説明しなかったが、それがどのように機能するかを説明するには自然で直感的な方法だ。

まず、 次数探索問題として知られる中間問題について説明し、位相推定がこの問題の解決策となることを見ていく。 次に、順序探索問題の効率的な解法が、整数因数分解問題の効率的な解法にどのようにつながるかを見ていく。 (ある問題の解が、このように別の問題の解を提供するとき、2番目の問題は最初の問題に還元されると言う。つまり、この場合は整数因数分解を順序探索に還元しているのだ) このショーのアルゴリズムの2番目の部分は、量子計算をまったく利用していない。 量子コンピューターが必要なのは、秩序発見を解くことだけだ。

---

順序探索問題

いくつかの基本的な数論

次数探索問題と、それが位相推定を使ってどのように解けるかを説明するには、まず基本的な数論の概念から始め、その過程で便利な記法をいくつか紹介するのが役に立つだろう。

まず、任意の正の整数 $N$ に対し、集合 $\mathbb{Z}_N$ を次のように定義する。

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

例えば、こうだ、 $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ などなど。

これらは数の集合ですが、単なる集合以上のものとして捉えることもできます。 特に、 $\mathbb{Z}_N$ における加算や乗算といった算術演算について考えてみましょう。ここで、答えを常に $N$ による剰余として扱う（ つまり、 $N$ で割り、その余りを結果とする）ことにすれば、これらの演算を行う際、常にこの集合の範囲内に収まることになります。 加法と乗法という2つの具体的な演算（いずれも $N$ を法とする）により、 $\mathbb{Z}_N$ は環となり、これは代数において極めて重要な対象の一種である。

例えば、 $3$ と $5$ は $\mathbb{Z}_7$ の要素であり、これらを掛け合わせると $3\cdot 5 = 15$ となり、これを $7$ で割ると余りが $1$ となります。 これを次のように表すこともあります。

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

ただし、表記をできるだけ簡潔にするために、 $\mathbb{Z}_7$ を使用していることが明確になっていれば、単に $3 \cdot 5 = 1$ と書くこともできます。

例として、 $\mathbb{Z}_6$ の足し算と掛け算の九九を以下に示します。

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

$\mathbb{Z}_N$ の $N$ の要素のうち、 $\gcd(a,N) = 1$ を満たす $a\in\mathbb{Z}_N$ の要素は特別である。 多くの場合、これらの要素を含む集合は、このようにアスタリスクで表されます。

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

乗算の演算に注目すると、集合 $\mathbb{Z}_N^{\ast}$ は群 ――具体的にはアーベル群 ――をなしており、これは代数におけるもう一つの重要な対象である。 これらの集合（および一般の有限群）に関する基本的な事実として、任意の要素 $a\in\mathbb{Z}_N^{\ast}$ を選び、 $a$ を繰り返し自身と掛け合わせると、最終的には常に $1$ という数になることが挙げられます。

最初の例として、 $N=6$ を取り上げましょう。 $\gcd(5,6) = 1$ であるため、 $5\in\mathbb{Z}_6^{\ast}$ が成り立ちます。また、 $5$ を自身と掛け合わせると、 $1$ となります。 これは、上の表が示す通りです。

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

2つ目の例として、 $N = 21$ を取り上げましょう。 $0$ から $20$ までの数を調べていくと、 $21$ との最大公約数（GCD）が $1$ となるものは以下の通りです。

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

これらの各要素について、その数を正の整数の累乗にすることで、 $1$ を得ることができます。 これが成り立つ最小の累乗は以下の通りです：

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

当然のことながら、これらの方程式はすべて $\mathbb{Z}_{21}$、わざわざ書くまでもなく、物事の混乱を避けるために暗黙の了解としている。 このレッスンの残りの部分を通して、それを続けていく。

問題の定義と位相推定との関連性

これで、順序探索の問題を述べることができる。

入力：以下を満たす正の整数 $N$ と $a$ $\gcd(N,a) = 1$\ 出力： $a^r \equiv 1$ を満たす最小の正の整数 $r$ $(\textrm{mod } N)$

あるいは、上で紹介した表記法で言えば、 $a \in \mathbb{Z}_N^{\ast}$が与えられ、 $a^r = 1$となる最小の正の整数$r$を探しています。この数$r$は、 $a$の$N$を法とする位数と呼ばれます。

順序決定問題と位相推定を結びつけるために、古典状態が $\mathbb{Z}_N$ に対応する系上で定義される演算について考えてみましょう。ここで、固定された要素 $a\in\mathbb{Z}_N^{\ast}$ を乗算します。

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

明確にしておくと、乗算は $\mathbb{Z}_N$ で行っているため、式右辺のket内部では、 $N$ をモジュロとして積を計算していることが暗黙的に示されています。

例えば、 $N = 15$ および $a=2$ を考えるとき、 $M_2$ の標準基底 $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ に対する作用は次のようになる。

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

$\gcd(a,N)=1$ を満たす場合、これは単一演算である。これは、標準基底 $\{\vert 0\rangle,\ldots,\vert N-1\rangle\}$ の要素を並べ替えるものであり、行列として見れば置換行列となる。 その定義から、この演算が決定論的であることは明らかであり、それが可逆であることを確認する簡単な方法は、 $a$ を $N$ で割った商の順序 $r$ を考え、 $M_a$ の逆元が $M_a^{r-1}$ であることを認識することである。

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

逆関数について考える別の方法があります。この方法では、 $r$ に関する知識は一切必要ありません（結局のところ、私たちが計算しようとしているのはそれなのですから）。 任意の要素 $a\in\mathbb{Z}_N^{\ast}$ に対して、常に $ab=1$ を満たす一意な要素 $b\in\mathbb{Z}_N^{\ast}$ が存在する。 この要素 $b$ を $a^{-1}$ と表し、これは効率的に計算することができる。 ユークリッドの最大公約数アルゴリズムの拡張版を用いれば、 $\operatorname{lg}(N)$ の二乗に比例する計算量でこれを計算できる。 したがって、

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

つまり、演算 $M_a$ は決定論的であり、かつ反転可能である。 これは順列行列で記述されることを意味し、したがってユニタリーである。

それでは、 $a\in\mathbb{Z}_N^{\ast}$ と仮定して、演算 $M_a$ の固有ベクトルと固有値について考えてみましょう。 先ほど論じたように、この仮定から、 $M_a$ がユニタリであることがわかります。

$M_a$ には $N$ 個の固有値があり、同じ固有値が複数回繰り返される可能性もあります。また、一般に、対応する固有ベクトルを選ぶ際にはある程度の自由度がありますが、ここではすべての可能性について心配する必要はありません。 まずは簡単なところから始め、 $M_a$ の固有ベクトルを1つだけ求めてみましょう。

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

$r$ は、 $a$ の $N$ による剰余の位数であり、ここおよびこのレッスンの残りの部分においても同様である。 この固有ベクトルに対応する固有値は、 $a$ を乗じても変化しないため、 $1$ となります。

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

これは、 $a^r = 1$ であるためであり、したがって、各標準基底状態 $\vert a^k \rangle$ は、 $k\leq r-1$ において $\vert a^{k+1} \rangle$ へとシフトし、 $\vert a^{r-1} \rangle$ は $\vert 1\rangle$ へと元に戻る。 平たく言えば、 $\vert \psi_0 \rangle$ をゆっくりと撹拌しているようなものだが、すでに完全に撹拌されているため、何も変化しない。

$M_a$ の固有ベクトルのもう1つの例を以下に示します。 この例は、位相の決定や位相推定という観点から見ると、特に興味深いものです。

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

あるいは、このベクトルを次のように和を使って書くこともできる。

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

ここでは、 $a$ による乗算が $N$ を法としてどのように作用するかによって、複素数 $\omega_r = e^{2\pi i/r}$ が自然に現れているのがわかります。 この場合、対応する固有値は $\omega_r$ となります。 これを確認するために、まず次のように計算してみましょう。

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

ここで、 $\omega_r^{-r} = 1 = \omega_r^0$ かつ $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle$ であることから、次のことがわかる

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

つまり、 $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle$。

同様の考え方を用いて、 $M_a$ について、さらに固有ベクトル・固有値の組を特定することができる。 $j\in\{0,\ldots,r-1\}$ を任意に選んだ場合、次のことが成り立つ。

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

は、 $M_a$ の固有ベクトルであり、これに対応する固有値は $\omega_r^j$ である。

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

$M_a$ には他にも固有ベクトルが存在しますが、それらについては特に気にする必要はありません。ここでは、先ほど特定した固有ベクトル $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ のみに焦点を当てます。

---

位相推定によるオーダー検出

$a\in\mathbb{Z}_N^{\ast}$ が与えられた場合の軌道決定問題を解くには、 $M_a$ という演算に対して位相推定手順を適用することができる。

これを行うには、量子回路を用いて $M_a$ を効率的に実装するだけでなく、 $M_a^2$、 $M_a^4$、 $M_a^8$ なども実装し、位相推定手順から十分に正確な推定値が得られるよう、必要に応じてさらに踏み込んだ実装を行う必要があります。 ここでは、その方法について説明し、必要な精度は後ほど具体的に検討していきます。

まずは、 $M_a$ という演算自体について見ていきましょう。 当然のことながら、量子回路モデルを扱っているため、 $0$ から $N-1$ までの数値を符号化するには、2進法を用います。 符号化する必要のある最大の数は $N-1$ であるため、必要なビット数は

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

たとえば、 $N = 21$ の場合、 $n = \operatorname{lg}(N-1) = 5$ となります。 $\mathbb{Z}_{21}$ の各要素を、長さ $5$ のバイナリ文字列としてエンコードすると、次のようになります。

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

そして今、 $M_a$ がどのように $n$ -qubit操作として定義されるのか、ここに正確な定義がある。

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

重要なのは、 $M_a$ が $\vert 0\rangle,\ldots,\vert N-1\rangle$ に対してどのように作用するかにのみ関心があるとはいえ、残りの $2^n - N$ の標準基底状態に対してどのように作用するかを指定しなければならないという点です。そして、その指定は、依然としてユニタリ演算が得られるような方法で行わなければなりません。 残りの標準基底状態に対して何もしないように $M_a$ を定義することで、これが実現されます。

前回のレッスンで解説した整数の乗算および除算のアルゴリズムと、それらを可逆かつガベージフリーに実装するための手法を用いることで、任意の $a\in\mathbb{Z}_N^{\ast}$ に対して、 $M_a$ を実行する量子回路を、コスト $O(n^2)$ で構築することができます。 以下に、その実現方法の一例を示します。

1. 動作を実行する回路を作る

$$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

ここで

$$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

前回のレッスンで説明した方法を使って。 これにより、 $O(n^2)$ の大きさの回路が得られます。

2. 2つの $n$ -qubitシステムを、 $n$ スワップゲートを使って個別にスワップする。

3. 最初のステップと同じように、操作のための回路を作る

$$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

ここで、 $a^{-1}$ は、 $\mathbb{Z}_N^{\ast}$ における $a$ の逆行列である。

一番下の $n$ の量子ビットを初期化し、3つのステップを合成することで、この変換が得られる：

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

この手法ではワークスペース量子ビットが必要ですが、処理終了時にそれらは初期化された状態に戻されるため、これらの回路を位相推定に利用することができます。 この回路の総コストは、 $O(n^2)$ となります。

$M_a^2$、 $M_a^4$、 $M_a^8$ などを実行するには、まったく同じ手法を用いることができます。ただし、 $\mathbb{Z}_N^{\ast}$ の要素として、 $a$ を $a^2$、 $a^4$、 $a^8$ などに置き換える点が異なります。 つまり、任意の累乗 $k$ を選んだ場合、 $M_a^k$ 用の回路を作成するには、 $M_a$ 用の回路を $k$ 回繰り返すのではなく、 $b = a^k \in \mathbb{Z}_N^{\ast}$ を計算し、 $M_b$ 用の回路を使用すればよいのです。

$a^k \in \mathbb{Z}_N$ の累乗の計算は、前回のレッスンで触れたモジュラーべき乗問題です。 この計算は、前回のレッスンで触れたモジュラーべき乗のアルゴリズム（計算数論ではしばしば「 べき乗アルゴリズム 」と呼ばれる）を用いて、 従来の方法で行うことができます。 実際、必要なのは power-of-2 の $a$ 乗、具体的には $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast}$ のみであり、これらは $m-1$ を繰り返し 2 乗することで得ることができます。 各二乗演算は、サイズ $O(n^2)$ のブール回路によって実行できる。

要するに、ここで実質的に行っているのは、 $M_a$ を $2^{m-1}$ 回も反復処理するという問題を、効率的な古典計算に委ねているということです。 そして、それが可能だというのは本当に幸運なことだ！ 位相推定問題において、量子回路を任意に選択した場合、これは実現不可能である可能性が高い。その場合、位相推定にかかるコストは制御量子ビットの数に比例して指数関数的に増加する。 $m$。

便利な固有ベクトルが与えられた場合の解

位相推定を用いて順序決定問題をどのように解決できるかを理解するために、まずは、 固有ベクトル $\vert\psi_1\rangle$ を用いて、演算 $M_a$ に対して位相推定手順を実行すると仮定してみましょう。 実は、この固有ベクトルを入手するのは容易ではないため、話はこれで終わりではありませんが、ここから始めることは有益です。

固有ベクトル $\vert \psi_1\rangle$ に対応する $M_a$ の固有値は以下の通りである

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

つまり、 $\theta = 1/r$ に対して、 $\omega_r = e^{2\pi i \theta}$ となる。 したがって、固有ベクトル $\vert\psi_1\rangle$ を用いて $M_a$ に対して位相推定手順を実行すると、 $1/r$ の近似値が得られる。 逆数を計算することで、 $r$ を導き出すことができる――ただし、その近似が十分に正確である場合に限る。

より詳しく説明すると、 $m$ 個の制御量子ビットを用いて位相推定手順を実行すると、得られる値は $y\in\{0,\ldots,2^m-1\}$ となります。 次に、 $y/2^m$ を $\theta$ の推定値として用います。今回のケースでは、これは $1/r$ となります。 この近似値から $r$ が何であるかを求めるには、当然のことながら、この近似値の逆数を計算し、最も近い整数に丸めるのが自然です。

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

例えば、 $r = 6$ とし、固有ベクトル $\vert\psi_1\rangle$ を用いて、 $m = 5$ 個の制御ビットで $M_a$ に対する位相推定を行うと仮定する。 $1/r = 1/6$ に対する最良の $5$ ビット近似は $5/32$ であり、位相推定から $y=5$ という結果が得られる確率はかなり高い（この場合は約 $68\%$ ）。 弊社では

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

また、最も近い整数に丸めると $6$ となり、これが正解です。

一方で、十分な精度を用いないと、正しい答えが得られない可能性があります。 例えば、位相推定において $m = 4$ 個の制御量子ビットを用いると、 $1/r = 1/6$ に対する最良の $4$ ビット近似が得られる可能性があり、これは $3/16$ となる。 逆数を求めると、次のようになる。

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

また、最も近い整数に丸めると、 $5$ という誤った答えが出てしまいます。

では、正しい答えを導き出すには、どれほどの精度が必要なのでしょうか？ $r$ の次数は整数であることがわかっています。直感的に言えば、 $1/r$ と、 $1/(r+1)$ や $1/(r-1)$ といった近傍の候補を区別するのに十分な精度が必要となります。 $1/r$ に最も近い、考慮すべき数は $1/(r+1)$ であり、これら2つの数の間の距離は

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

したがって、 $1/r$ を $1/(r+1)$ と間違えないようにしたいのであれば、 $1/r$ に対する最良の近似値 $y/2^m$ が、 $1/(r+1)$ よりも $1/r$ に近いことを保証できるだけの十分な精度を用いればよい。 もし、次のような条件を満たすだけの十分な精度を用いるならば、

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

つまり、誤差が $1/r$ と $1/(r+1)$ の間の距離の半分未満となるようにすれば、 $y/2^m$ は、 $1/(r+1)$ や $1/(r-1)$ を含む他のどの可能性よりも、 $1/r$ に近いことになる。

これをダブルチェックすると、次のようになる。 仮に

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

$\varepsilon$ を満たす

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

逆数を取ると次のようになる

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

分子を最大化し、分母を最小化することで、 $r$。

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

「 $1/2$ 」と「 $r$ 」の差は未満なので、予想通り、四捨五入すると $r$ になります。

残念なことに、 $r$ が何なのかまだわかっていないため、それを使ってどれくらいの精度が必要なのかを知ることはできない。 その代わりにできることは、 $r$ が $N$ より小さくなければならないという事実を利用して、十分な精度を確保することである。 特に、 $1/r$ に対する最良の近似 $y/2^m$ が以下を満たすことを保証するのに十分な精度を用いるとする

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

そうすれば、逆数を取るときに $r$ を正しく決定するのに十分な精度が得られる。 $m = 2\operatorname{lg}(N)+1$ を取ることで、前述した方法でこの精度の推定値が得られる可能性が高くなる。 (成功確率の下限が40%でよければ、 $m = 2\operatorname{lg}(N)$。)

一般解

先ほど見たように、 $M_a$ の固有ベクトル $\vert \psi_1 \rangle$ があれば、十分な精度でこれを行うのに必要な数の制御量子ビットを使用する限り、位相推定を通じて $r$ を学習することができます。 残念ながら、固有ベクトル $\vert\psi_1\rangle$ を入手するのは容易ではないため、どう進めるべきかを考えなければなりません。

ひとまず、上記と同じように進めるが、 $\vert\psi_1\rangle$ の代わりに固有ベクトル $\vert\psi_k\rangle$ を用いると仮定しよう。ここで、 $k\in\{0,\ldots,r-1\}$ は任意に選んでよいとする。 位相推定手順から得られる結果は、近似値となります

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

$k$ も $r$ もわからないという前提に立てば、これにより $r$ を特定できる場合とできない場合がある。 例えば、 $k = 0$ であれば、 $0$ に対する近似値 $y/2^m$ が得られるが、残念ながらこれだけでは何もわからない。 しかし、これは特殊なケースです。 $k$ の他の値については、少なくとも $r$ について何かしらの知見を得ることができるでしょう。

もし近似が十分であれば、 $y/2^m$ を近傍の分数（ $k/r$ を含む）に変換するために、 継続分数アルゴリズムとして知られるアルゴリズムを使うことができる。 ここでは継続分数のアルゴリズムについては説明しない。 その代わりに、このアルゴリズムに関する既知の事実を説明しよう。

整数 $N\geq 2$ と実数 $\alpha\in(0,1)$ が与えられたとき、 $v\neq 0$ かつ $\gcd(u,v)=1$ を満たす整数 $u,v\in\{0,\ldots,N-1\}$ の組み合わせは、 $\vert \alpha - u/v\vert < \frac{1}{2N^2}$ を満たすものがせいぜい1つだけ存在する。 $\alpha$ と $N$ が与えられたとき、 連分数アルゴリズムは $u$ と $v$ を見つけるか、それらが存在しないことを報告する。 このアルゴリズムは、サイズが $O((\operatorname{lg}(N))^3)$ のブール回路として実装することができる。

もし、 $y/2^m$ が $k/r$ に非常に近い近似値であり、 $N$ および $\alpha = y/2^m$ について連分数のアルゴリズムを実行すると、事実で述べられているように、 $u$ および $v$ が得られる。 この事実を分析した結果、次のように結論づけることができる

$$\frac{u}{v} = \frac{k}{r}.$$

特に、 $k$ や $r$ を必ずしも学ぶわけではないことに注意してください。学ぶのは、 $k/r$ という最も単純な形のものだけです。

例えば、すでに気づいた通り、 $k=0$ からは何も得られません。 しかし、そのようなことが起こる $k$ の値は、これだけです。 $k$ が0でない場合、 $r$ と共通因数を持つ可能性がありますが、連分数法から得られる数 $v$ は、少なくとも $r$ を割り切らなければなりません。

一見すると明らかではないが、 $u$ および $v$ を、 $u/v = k/r$ および $k\in\{0,\ldots,r-1\}$ に対して一様ランダムに選択した場合、それらを学習する能力があれば、わずか数回のサンプリングだけで $r$ を復元できる可能性が非常に高いというのは事実である。 特に、 $r$ に対する推測値が、分母 $v$ について観測されたすべての値の最小公倍数である場合、その推測は高い確率で正しいことになる。 直感的に言えば、 $k$ の値の中には、 $r$ と共通因数を持つため適切でないものがあり、 $u$ や $v$ を学習する際には、それらの共通因数が隠れてしまう。 しかし、 $k$ をランダムに選んでも、 $r$ の因数が長く隠されたままになることはまずなく、観察された分母の最小公倍数をとることで $r$ を正しく推測できない確率は、サンプル数の増加に伴い指数関数的に低下する。

$\vert\psi_k\rangle$ あとは、位相推定手順を実行するための固有ベクトル $M_a$。 結局のところ、それを作る必要はないのだ！

その代わりに、状態 $\vert 1\rangle$ に対して位相推定手順を実行します。ここでとは、 $M_a$ の固有ベクトル $\vert\psi\rangle$ の代わりに、数 $1$ の $n$ ビットの2進符号化を表します。 これまで、特定の固有ベクトルに対して位相推定手順を実行することについてのみ述べてきましたが、 $M_a$ の固有ベクトルではない入力状態に対してこの手順を実行することを妨げるものは何もなく、それがここで状態 $\vert 1\rangle$ に対して行っていることです。 （ $a=1$ でない限り、これは $M_a$ の固有ベクトルではありません。しかし、 というケースは、ここでは検討対象外です。）

$M_a$ の固有ベクトルの代わりに状態 $\vert 1\rangle$ を選ぶ根拠は、以下の式が成り立つからである。

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

この方程式を検証する一つの方法は、右辺の結果を評価するのに役立つように、レッスンで前に述べた公式を使用して、各標準基底状態で両辺の内積を比較することである。 その結果、 $k\in\{0,\ldots,r-1\}$ を一様にランダムに選び、それを固有ベクトルとして使った場合とまったく同じ測定結果が得られる。 $\vert\psi_k\rangle$ を固有ベクトルとして使った場合と全く同じ測定結果が得られる。

より詳しく説明すると、固有ベクトル $\vert\psi_k\rangle$ の1つの代わりに、状態 $\vert 1\rangle$ を用いて位相推定手順を実行すると仮定しましょう。 逆量子フーリエ変換を実行すると、その結果、以下の状態が得られます。

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

ここで

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle.$$

ベクトル $\vert\gamma_k\rangle$ は、量子フーリエ変換の逆変換を行った後のトップ $m$ の量子ビットの状態を表している。

従って、 $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ が正規直交集合であるという事実により、 $m$ クビットのトップ を測定すると、 の値に近似することがわかる。 の測定は、 $k\in\{0,\ldots,r-1\}$ が一様にランダムに選ばれた値 $k/r$ の近似値 $y/2^m$ をもたらすことがわかります。 すでに説明したように、これによって、私たちの目標であった、何度かの独立した実行の後、高い信頼性をもって $r$。

合計コスト

各制御ユニタリ演算 $M_a^k$ の実行コストは、 $O(n^2)$ である。 制御ユニタリ演算は $m$ 個あり、 $m = O(n)$ であるため、制御ユニタリ演算の総コストは $O(n^3)$ となる。 さらに、 $m$ 個のハダマールゲートがあり（これによるコストは $O(n)$ ）、逆量子フーリエ変換によるコストは $O(n^2)$ である。 したがって、制御ユニタリ演算の計算コストが手順全体の計算コストの大部分を占めることになり、その結果、 $O(n^3)$ となる。

量子回路そのものに加え、その過程で実行する必要のあるいくつかの古典的な計算があります。 これには、制御ユニタリゲートを作成するために必要な、 $\mathbb{Z}_N$ における $k = 2, 4, 8, \ldots, 2^{m-1}$ に対する $a^k$ の冪の計算に加え、 $\theta$ の近似値を分数に変換する連分数アルゴリズムも含まれます。 これらの計算は、総コストが $O(n^3)$ のブール回路によって実行可能です。

典型的なように、これらの境界はすべて漸近的に高速なアルゴリズムを使って改善できる。これらの境界は、基本的な算術演算に標準的なアルゴリズムを使っていると仮定している。

---

受注ファクタリング

最後に論じなければならないのは、順序探索問題を解くことが因数分解にどのように役立つかということだ。 この部分は完全に古典的なもので、量子コンピューティングとは何の関係もない。

基本的な考え方は次のとおりです。 $N$ を因数分解したいのですが、これは再帰的に行うことができます。 具体的には、 $N$ を因数分解するという課題に焦点を当てることができます。これは、 $N = bc$ を満たす任意の 2 つの整数 $b,c\geq 2$ を見つけることを意味します。 $N$ が素数である場合はこれは不可能ですが、まず素数判定アルゴリズムを用いて $N$ が素数かどうかを効率的に判定し、 $N$ が素数でない場合は、その因数分解を試みます。 $N$ を因数分解したら、 $b$ および $c$ に対して再帰処理を繰り返すだけで、すべての因数が素数になるまで処理を進め、 $N$ の素因数分解を得ることができます。

偶数の整数を分解するのは簡単です。 $2$ と $N/2$ を出力すればよいのです。

また、整数 $s,j\geq 2$ に対する $N = s^j$ の形をした完全冪を、 根を $N^{1/2}$、 $N^{1/3}$、 $N^{1/4}$ などと近似し、 $s$ の候補として近傍の整数をチェックするだけで、簡単に分解することができます。 この数列を $\log(N)$ ステップ以上進める必要はありません。なぜなら、その時点で根は $2$ を下回り、それ以上の候補が現れなくなるからです。

これら両方ができるのは良いことです。なぜなら、順序を見つけるだけでは偶数や素数のべき乗を因数分解したり、 $s$ がたまたま素数である場合には役立たないからです。 ただし、 $N$ が奇数であり、かつ素数の冪でない場合、順序決定法を用いて $N$ を分解することができる。

1. $a\in\{2,\ldots,N-1\}$ をランダムに選択します。

2. $d=\gcd(a,N)$ を計算します。

3. $d > 1$ の場合は、 $b = d$ および $c = N/d$ を出力して終了する。 それ以外の場合は、 $a\in\mathbb{Z}_N^{\ast}$ であることを念頭に置いて、次の手順に進んでください。

4. $r$ を、 $a$ を $N$ で割った余りによる位数とする。 （ここで注文検索が必要になります。）

5. $r$ が偶数の場合：

   5.1 $x = a^{r/2} - 1$ を$N$ で割った余りを計算する。 5.2 $d = \gcd(x,N)$
   を計算する。 5.3 $d>1$
   であれば、$b=d$ および$c = N/d$ を出力し、処理を終了する。

6. この段階に達した場合、アルゴリズムは $N$ の因数を見つけることに失敗したことになる。

このアルゴリズムを実行しても、 $N$ の因数が見つからない場合があります。 具体的には、次の 2 つの状況でこれが起こります：

• $a$ modulo $N$ の次数は奇数である。
• $a$ を $N$ で割った余りは偶数であり、 $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1$ である。

基本的な整数論を用いれば、 $a$ をランダムに選んだ場合、少なくとも $1/2$ の確率で、これらの事象のいずれも起こらないことが証明できる。 実際、いずれかの事象が起こる確率は、 $2^{-(m-1)}$ 以下である。ここで、 $m$ は $N$ の異なる素因子の個数であり、 これが、 $N$ が素数の冪ではないという仮定が必要となる理由である。 （この事実が成り立つためには、 $N$ が奇数であるという仮定も必要となる。）

これは、各実行において、 $N$ を分割できる確率が少なくとも 50% あることを意味します。 したがって、アルゴリズムを $t$ 回実行し、そのたびに $a$ をランダムに選択すれば、 $N$ を分割することに成功する確率は、少なくとも $1 - 2^{-t}$ となります。

アルゴリズムの基本的な考え方は以下の通りである。 $a$ modulo $N$ の次数 $r$ が偶数である $a$ の選択肢がある場合、 $r/2$ は整数であり、次のように考えることができる。 数

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

式 $Z^2 - 1 = (Z+1)(Z-1)$ を用いると、次のことが導かれる

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

さて、順序の定義から、 $a^r \; (\textrm{mod}\; N) = 1$ であることがわかっています。これは、 $N$ が $a^r - 1$ を割り切る、という別の言い方でもあります。 つまり、 $N$ がその積を割り切るということです。

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

これが真実であるためには、 $N$ の素因数のすべてが、 $a^{r/2} - 1$ または $a^{r/2} + 1$ の素因数（あるいはその両方）でもなければならない。 $a$ を無作為に選択した場合、 $N$ の素因数のすべてが一方の項を分割し、もう一方の項を分割することはありえないことがわかる。 そうでなければ、 $N$ の素因数のいくつかが第1項を分割し、いくつかが第2項を分割する限り、第1項とのGCDを計算することによって、 $N$ の自明でない因数を見つけることができる。