ショアのアルゴリズム

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

まず、 次数探索問題として知られる中間問題について説明し、位相推定がこの問題の解決策となることを見ていく。 次に、順序探索問題の効率的な解法が、整数因数分解問題の効率的な解法にどのようにつながるかを見ていく。 (ある問題の解が、このように別の問題の解を提供するとき、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,$ となり、 $1$ で割ると余りが残る。 $7.$ これを次のように表現することもある。

$$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.$ $5\in\mathbb{Z}_6^{\ast}$、 $\gcd(5,6) = 1,$、 $5$ を自分自身に掛けると、次のようになる。 $1,$ となる。

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

第二の例として、次のものを考えてみよう。 $N = 21.$ $0$ から $20,$ までの数を調べると、GCDが $1$ と $21$ に等しいものは次のようになる。

$$\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},$ が与えられ、次のような最小の正の整数 $r$ を探すことになる。 $a^r = 1.$ この数 $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,$ で掛け算をしているので、式の右辺のケの内側でモジュロ $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}$$

$\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ これはユニタリー演算であり、 $\gcd(a,N)=1;$ 標準基底の要素をシャッフルする。 この演算が決定論的であることは、その定義から明らかである。反転可能であることを知る簡単な方法は、 $a$ modulo $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}$ を満たす一意な要素 $b\in\mathbb{Z}_N^{\ast}$ が必ず存在する。 $ab=1.$ この要素 $b$ を $a^{-1},$ と呼ぶことにする； ユークリッドのGCDアルゴリズムの拡張は、この計算を2次関数のコストで行う。 $\operatorname{lg}(N).$ したがって

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

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

ここで、 $M_a,$ の演算の固有ベクトルと固有値について考えてみよう。 $a\in\mathbb{Z}_N^{\ast}.$ 先ほど論じたように、この仮定は $M_a$ がユニタリーであることを物語っている。

$M_a,$ の固有値は $N$ 個あり、同じ固有値が複数回繰り返されることもある。一般に、対応する固有ベクトルの選択には自由度があるが、すべての可能性について心配する必要はないだろう。 の固有ベクトルを1つだけ特定してみよう。 $M_a.$

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

$r$ という数字は、こことレッスンの残りの部分を通して、 $a$ のモジュロ $N,$ の順番である。 この固有ベクトルに関連する固有値は $1$。 $a.$

$$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$ が $\vert a^{k+1} \rangle$ にシフトされ、 $k\leq r-1,$、 $\vert a^{r-1} \rangle$ が にシフトされるからである。 $\vert 1\rangle.$ 非公式に言えば、 $\vert \psi_0 \rangle,$ をゆっくりとかき混ぜているようなものだが、すでに完全にかき混ぜられた状態なので何も変わらない。

の固有ベクトルのもう一つの例である。 $M_a.$ この固有ベクトルは、次数発見と位相推定の文脈でより興味深い。

$$\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$ による乗算がモジュロとして機能するため、複素数 $\omega_r = e^{2\pi i/r}$ が自然に現れている。 $N.$ 今回対応する固有値は $\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$ から までの数を符号化するために2進数表記を使う。 $N-1.$ エンコードする必要がある最大の数は $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}$ は $a$ の逆数である。 $\mathbb{Z}_N^{\ast}.$

一番下の $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,$ などを実行するには、 $a$ を $a^2,$ $a^4,$ $a^8,$ などの要素に置き換える以外は、まったく同じ方法を使うことができる。 $\mathbb{Z}_N^{\ast}.$ つまり、選択したどの電力 $k$ についても、 $k$ を $M_a,$ の回路で繰り返し計算するのではなく、 $b = a^k \in \mathbb{Z}_N^{\ast}$ を計算し、 $M_a^k$ の回路を作成することができる。 $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.$

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

位相推定を使ってどのように次数探索問題を解くことができるかを理解するために、まず次のように仮定してみよう。 の固有ベクトルを用いて、 $M_a$ の操作で位相推定を実行する。 $\vert\psi_1\rangle.$ この固有ベクトルを手に入れるのは簡単ではないので、これで話が終わるわけではないが、ここから始めると役に立つ。

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

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

すなわち、 $\omega_r = e^{2\pi i \theta}$ $\theta = 1/r.$ 従って、固有ベクトル $\vert\psi_1\rangle,$ を使って $M_a$ で位相推定手順を実行すると、次の近似が得られる。 $1/r.$ この逆数を計算することで、 $r$ を学習することができる。近似が十分であればの話だが。

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

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

例えば、 $r = 6$、 $m = 5$ 制御ビットを用いて固有ベクトル $\vert\psi_1\rangle$ を用いて $M_a$ の位相推定を行うとする。 $1/r = 1/6$ に対する最良の $5$ -bit近似は $5/32,$、位相推定から結果 $y=5$ を得る可能性はかなり高い（この場合 $68\%$ ）。 我々は

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

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

逆に、十分な精度を使わなければ、正しい答えが得られないかもしれない。 例えば、位相推定に $m = 4$ 制御量子ビットを用いると、 $4$ -bit の最良近似値 $1/r = 1/6,$ が得られるかもしれない。 $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),$ と間違えないようにするには、 $y/2^m$ から $1/r$ への最良近似が、 $1/r$ に近いことを保証するのに十分な精度を使えば十分である。 $1/(r+1).$ 十分な精度を使えば

$$\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/(r-1).$

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

$$\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}$$

$r,$ まであと $1/2$ 以下なので、予想通り、一周したら $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$ の場合、 $y/2^m$ から $0,$ までの近似値が得られるが、これは残念ながら何も教えてくれない。 しかし、これは例外的なケースである。 $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\}$ の選択肢は最大で1つである． $\vert \alpha - u/v\vert < \frac{1}{2N^2}.$ $\alpha$ と $N,$ が与えられたとき， 連分数アルゴリズムは $u$ と $v,$ を見つけるか，あるいは存在しないことを報告する． このアルゴリズムは、以下のサイズを持つブール回路として実装できる。 $O((\operatorname{lg}(N))^3).$

$k/r,$ に非常に近い近似値 $y/2^m$ があり、 $N$ と $\alpha = y/2^m,$ に対して継続分数アルゴリズムを実行すると、 $u$ と $v,$ が得られる。 この事実を分析すると、次のように結論づけられる

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

特に、 $k$ と $r,$ は必ずしも学ぶ必要はなく、 $k/r$ を学ぶのは最低条件のみであることに注意。

例えば、すでにお気づきのように、我々は次のようなことから何も学ぼうとはしない。 $k=0.$ しかし、このようなことが起こるのは $k$。 $k$ がゼロでない場合、 $r,$ と共通因子を持つ可能性があるが、継続分数アルゴリズムから得られる数 $v$ は、少なくとも次のように割り切らなければならない。 $r.$

自明とは言い難いが、 一様に無作為に選ばれた $k\in\{0,\ldots,r-1\}$ に対する $u/v = k/r$ の $u$ と $v$ を学習する能力があれば、わずか数サンプルの後に $r$ を復元できる可能性が非常に高いことは事実である。 特に、 $r$ の推測が、観測された分母 $v$ のすべての値の最小公倍数であれば、高い確率で正しいだろう。 直感的に言えば、 $k$ のいくつかの値は、 $r,$ と共通因子を共有し、それらの共通因子は、 $u$ と を学習するときに私たちから隠されてしまうので、良くない。 $v.$ しかし、 $k$ のランダムな選択は、 $r$ の因子を長い間隠すことはないだろう。そして、我々が観察した分母の最小公倍数を取ることによって、 $r$ を正しく推測できない確率は、サンプルの数だけ指数関数的に低下する。

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

$\vert 1\rangle,$ この状態とは、 $1,$ の固有ベクトル $\vert\psi\rangle$ の代わりに、 $n$ -bitの数値のバイナリ符号化 を意味する。 $M_a.$ ここまでは、位相推定手順を特定の固有ベクトルで実行することについてのみ説明しましたが、 $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$ を固有ベクトルとして使った場合と全く同じ測定結果が得られる。

より詳細には、固有ベクトルの1つの代わりに状態 $\vert 1\rangle$、位相推定手順を実行することを想像してみましょう。 $\vert\psi_k\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).$

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

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

---

受注ファクタリング

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

これが基本的な考え方だ。 $N,$ の因数分解をしたいのだが、これは再帰的にできる。 具体的には、 $N,$ を分割するタスクに集中することができる。これは、 $b,c\geq 2$ が素数である2つの整数を見つけることを意味する。 $N = bc.$ $N$ が素数である場合、これは不可能であるが、 $N$ が素数であるかどうかを、まず一次性検定アルゴリズムを使って効率的に検定することができる。 $N$ が素数でなければ、それを分割しようとする。 いったん $N,$ を分割すれば、すべての因数が素数になるまで $b$ と $c$ を再帰するだけで、以下の素因数分解が得られる。 $N.$

$2$ 偶数の整数を分割するのは簡単だ。 $N/2.$

$N = s^j$ $s,j\geq 2,$ また、完全累乗を分割するのも簡単である。 $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. $a$ modulo $N.$ の次数を $r$ とする（ここで次数探索が必要になる）

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

   5.1 $x = a^{r/2} - 1$ modulo を計算する を計算する。 もし なら、 と を出力し、停止する。 $N$ \5.2 $d = \gcd(x,N).$ \5.3 $d>1$ $b=d$ $c = N/d$

6. このポイントに到達した場合、アルゴリズムは以下の係数を見つけることに失敗している。 $N.$

の因数を見つけるのに失敗することがある。 $N.$ 具体的には、これは2つの状況で起こる：

• $a$ modulo $N$ の次数は奇数である。
• $a$ modulo $N$ の次数は偶数である。 $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1.$

基本的な数論を用いれば、少なくとも $1/2$ の確率で $a,$ をランダムに選択した場合、どちらの事象も起こらないことが証明できる。 の素因数の個数を $m$ とすると、どちらかの事象が起こる確率は最大でも $2^{-(m-1)}$ である。 $N,$ これが、 $N$ が素乗ではないという仮定が必要な理由である。 (この事実が真であるためには、 $N$ が奇数であるという仮定も必要である）

これは、各実行が少なくとも50％の確率で分割されることを意味する。 $N.$ したがって、 $a$ を毎回ランダムに選びながら $t$ 回アルゴリズムを実行すれば、少なくとも以下の確率で $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$ の自明でない因数を見つけることができる。