ショアのアルゴリズム

2026年現在、量子コンピュータの高いエラー率と量子エラー訂正に利用できる物理的な量子ビットの数が限られているため、ショアのアルゴリズムの実験室での実証では、試行のごく一部でしか正しい結果が得られず、小さな半素数でのみ成功している。

2001年、 IBMのグループがショアのアルゴリズムを実証し、${\displaystyle 15}$の中へ${\displaystyle 3\times 5}$7つの量子ビットを持つ量子コンピュータのNMR実装を使用。 ^{[ 10 ]} IBMの実装後、2つの独立したグループが光子量子ビットを使用してショアのアルゴリズムを実装した。^{[ 11 ] [ 12 ]} 2012年には、${\displaystyle 15}$固体量子ビットを用いて実行された。^{[ 13 ]}その後、2012年に、${\displaystyle 21}$が達成された。^{[ 14 ]} 2016年に、の因数分解が達成された。${\displaystyle 15}$イオン捕捉量子ビットを使用して再度実行されました。^{[ 15 ]}しかし、これらのデモンストレーションはいずれもショアのアルゴリズムの要件を満たしていません。それらは、解の事前知識を使用して回路をコンパイルしており、中にはアルゴリズムを過度に単純化してコイン投げと同等にしているものもあります。^{[ 16 ]}

任意の数を効率的に因数分解できれば、完全な因数分解アルゴリズムが可能になる。${\displaystyle N}$2つの整数に${\displaystyle p}$そして${\displaystyle q}$1より大きい、なぜならどちらかが${\displaystyle p}$または${\displaystyle q}$素数でない場合は、素数だけが残るまで、素因数分解アルゴリズムをそれらに対して実行できます。

基本的な観察として、ユークリッドの互除法を用いると、2 つの整数間の最大公約数を常に効率的に計算できることがわかります。特に、これは、効率的にチェックできることを意味します。${\displaystyle N}$は偶数であり、その場合、2 は自明に因数である。したがって、${\displaystyle N}$この議論の残りの部分では、これは奇妙です。その後、効率的な古典的アルゴリズムを使用して、${\displaystyle N}$は素数のべき乗である。^{[ 17 ]}素数のべき乗については、効率的な古典的因数分解アルゴリズムが存在するため、^{[ 18 ]}量子アルゴリズムの残りの部分は、${\displaystyle N}$主要な勢力ではない。

これらの簡単なケースでは、非自明な係数は生成されません。${\displaystyle N}$アルゴリズムは残りのケースの処理に進みます。ランダムな整数を選択します。${\displaystyle 2\leq a<N{.}}$非自明な約数の可能性${\displaystyle N}$計算によって見つけることができる${\displaystyle \gcd(a,N)}$これは、ユークリッドアルゴリズムを使用して古典的かつ効率的に実行できます。これが非自明な因子（つまり、${\displaystyle \gcd(a,N)\neq 1}$)、アルゴリズムは完了し、もう1つの非自明な要因は${\displaystyle N/\gcd(a,N)}$非自明な要因が特定されなかった場合、これは次のことを意味します。${\displaystyle N}$そして選択${\displaystyle a}$互いに素なので、${\displaystyle a}$は、整数の乗法群に含まれる。${\displaystyle N}$乗法逆元が法として存在する${\displaystyle N}$。 したがって、${\displaystyle a}$乗法的な順序を持つ${\displaystyle r}$モジュロ${\displaystyle N}$、 意味

${\displaystyle a^{r}\equiv 1{\bmod {N}},}$

そして${\displaystyle r}$は、この合同式を満たす最小の正の整数である。

量子サブルーチンは${\displaystyle r}$合同式から、${\displaystyle N}$分ける${\displaystyle a^{r}-1}$書かれた${\displaystyle N\mid a^{r}-1}$これは平方差を用いて因数分解できます。$${\displaystyle N\mid (a^{r/2}-1)(a^{r/2}+1).}$$このように式を因数分解したため、このアルゴリズムは奇数には適用されません。${\displaystyle r}$（なぜなら${\displaystyle a^{r/2}}$は整数でなければならない）つまり、アルゴリズムは新しい値で再開する必要がある。${\displaystyle a}$以降、我々は次のように仮定することができる。${\displaystyle r}$偶数である。${\displaystyle N\mid a^{r/2}-1}$これは、${\displaystyle a^{r/2}\equiv 1{\bmod {N}}}$これは矛盾して、${\displaystyle r/2}$順序は${\displaystyle a}$すでに${\displaystyle r}$現時点では、${\displaystyle N\mid a^{r/2}+1}$。 もし${\displaystyle N}$割り切れない${\displaystyle a^{r/2}+1}$つまり、非自明な因子を見つけることができるということである。${\displaystyle N}$計算します$${\displaystyle d=\gcd(N,a^{r/2}-1).}$$もし${\displaystyle d=1}$、 それから${\displaystyle N\mid a^{r/2}+1}$それは真実であり、${\displaystyle N}$達成できない${\displaystyle a}$、そしてアルゴリズムは新しい${\displaystyle a}$そうでなければ、非自明な因子が見つかりました。${\displaystyle N}$もう一方は${\displaystyle N/d}$、そしてアルゴリズムは完了です。このステップでは、 を計算することも同等です。${\displaystyle \gcd(N,a^{r/2}+1)}$; 非自明な因子を生成する場合${\displaystyle \gcd(N,a^{r/2}-1)}$は自明ではなく、自明であればそうはならない（${\displaystyle N\mid a^{r/2}+1}$)

アルゴリズムを改めて述べると次のようになる。${\displaystyle N}$奇数であり、素数のべき乗ではない。我々は、2 つの非自明な因数を出力したい。${\displaystyle N}$。

1. ランダムな数字を選ぶ${\displaystyle 1<a<N}$。
2. 計算する${\displaystyle K=\gcd(a,N)}$、の最大公約数${\displaystyle a}$そして${\displaystyle N}$。
3. もし${\displaystyle K\neq 1}$、 それから${\displaystyle K}$は、​${\displaystyle N}$もう一つの要因は${\displaystyle N/K}$これで終わりです。
4. それ以外の場合は、量子サブルーチンを使用して次数を見つけます。${\displaystyle r}$の${\displaystyle a}$。
5. もし${\displaystyle r}$が奇数の場合は、ステップ1に戻ります。
6. 計算する${\displaystyle g=\gcd(N,a^{r/2}+1)}$。 もし${\displaystyle g}$は些細なことではなく、もう1つの要因は${\displaystyle N/g}$これで完了です。そうでなければ、ステップ1に戻ってください。

数回実行すれば成功する可能性が高いことが示されている。^{[ 2 ]}実際には、量子順序探索サブルーチンを1回呼び出すだけで、完全に因数分解できる。${\displaystyle N}$より高度な還元法を用いれば、非常に高い確率で成功する。^{[ 19 ]}

ショアのアルゴリズムの量子サブルーチンの目標は、互いに素な整数が与えられたときに、${\displaystyle N}$そして${\displaystyle 1<a<N}$順序を見つける${\displaystyle r}$の${\displaystyle a}$モジュロ${\displaystyle N}$最小の正の整数${\displaystyle r}$そのため${\displaystyle a^{r}\equiv 1{\pmod {N}}}$これを実現するために、ショアのアルゴリズムは2つのレジスタを含む量子回路を使用する。2番目のレジスタは${\displaystyle n}$量子ビット、${\displaystyle n}$は、${\displaystyle N\leq 2^{n}}$つまり、${\displaystyle n=\left\lceil {\log _{2}N}\right\rceil }$最初のレジスタのサイズによって、回路が生成する近似の精度が決まります。${\displaystyle 2n}$量子ビットは、見つけるのに十分な精度を提供します${\displaystyle r}$正確な量子回路はパラメータに依存する${\displaystyle a}$そして${\displaystyle N}$問題を定義する。以下のアルゴリズムの説明では、量子状態を表すためにブラケット記法を使用し、${\displaystyle \otimes }$テンソル積を表す。

このアルゴリズムは主に2つのステップから構成されています。

1. ユニタリ行列を用いた量子位相推定を使用する${\displaystyle U}$乗算演算を表す${\displaystyle a}$(モジュロ)${\displaystyle N}$）、および入力状態${\displaystyle |0\rangle ^{\otimes 2n}\otimes |1\rangle }$（ここで2番目のレジスタは${\displaystyle |1\rangle }$から作られた${\displaystyle n}$（量子ビット）。${\displaystyle U}$期間に関する情報をエンコードし、${\displaystyle |1\rangle }$は、その固有ベクトルの和として表すことができることがわかる。これらの性質のおかげで、量子位相推定段階では、次の形式のランダムな整数が出力される。${\displaystyle {\frac {j}{r}}2^{2n}}$ランダムに${\displaystyle j=0,1,...,r-1}$。
2. 連分数アルゴリズムを使用して周期を抽出します${\displaystyle r}$これは、前の段階で得られた測定結果から周期を推定する手順です。出力量子状態の測定から得られた測定データを（古典コンピュータを用いて）後処理し、周期を推定します。

量子位相推定との関連性は、ショアのアルゴリズムの元の定式化では議論されていませんでしたが、^{[ 2 ]}後にアレクセイ・キタエフによって提案されました。^{[ 20 ]}

量子位相推定

一般に、任意のユニタリ${\displaystyle U}$および固有状態${\displaystyle |\psi \rangle }$そのため${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$入力状態を送信します${\displaystyle |0\rangle |\psi \rangle }$出力状態に近い${\displaystyle |\phi \rangle |\psi \rangle }$、 どこ${\displaystyle \phi }$は、${\displaystyle 2^{2n}\theta }$言い換えれば、各固有状態を送信する${\displaystyle |\psi _{j}\rangle }$の${\displaystyle U}$関連する固有値に近い情報を含む状態へ。量子順序探索の目的で、我々はこの戦略を、作用によって定義されるユニタリを使用して採用する。$${\displaystyle U|k\rangle ={\begin{cases}|ak{\pmod {N}}\rangle &0\leq k<N,\\|k\rangle &N\leq k<2^{n}.\end{cases}}}$$の行動${\displaystyle U}$州について${\displaystyle |k\rangle }$と${\displaystyle N\leq k<2^{n}}$はアルゴリズムの機能に不可欠ではありませんが、全体の変換が明確に定義された量子ゲートであることを保証するために含める必要があります。量子位相推定のための回路を実装するには、${\displaystyle U}$ゲートを効率的に実装できることが求められる${\displaystyle U^{2^{j}}}$これはモジュラべき乗によって実現できますが、これはアルゴリズムの中で最も処理速度の遅い部分です。

このように定義されたゲートは以下を満たす。${\displaystyle U^{r}=I}$これは、その固有値が${\displaystyle r}$1の-乗根${\displaystyle \omega _{r}^{k}=e^{2\pi ik/r}}$さらに、各固有値は${\displaystyle \omega _{r}^{j}}$の形の固有ベクトルを持つ${\textstyle |\psi _{j}\rangle =r^{-1/2}\sum _{k=0}^{r-1}\omega _{r}^{-kj}|a^{k}\rangle }$、そしてこれらの固有ベクトルは、$${\displaystyle {\begin{aligned}{\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\psi _{j}\rangle &={\frac {1}{r}}\sum _{j=0}^{r-1}\sum _{k=0}^{r-1}\omega _{r}^{jk}|a^{k}\rangle \\&=|1\rangle +{\frac {1}{r}}\sum _{k=1}^{r-1}\left(\sum _{j=0}^{r-1}\omega _{r}^{jk}\right)|a^{k}\rangle =|1\rangle ,\end{aligned}}}$$ ここで最後の恒等式は幾何級数の公式から導かれ、それは${\textstyle \sum _{j=0}^{r-1}\omega _{r}^{jk}=0}$。

入力状態に対する量子位相推定の使用${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$すると整数が返されます${\displaystyle 2^{2n}j/r}$高い確率で。より正確には、量子位相推定回路は${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$に${\displaystyle |\phi _{j}\rangle |\psi _{j}\rangle }$結果として得られる確率分布${\displaystyle p_{k}\equiv |\langle k|\phi _{j}\rangle |^{2}}$ピークは${\displaystyle k=2^{2n}j/r}$、 と${\displaystyle p_{2^{2n}j/r}\geq 4/\pi ^{2}\approx 0.4053}$この確率は、追加の量子ビットを用いることで、1にいくらでも近づけることができる。

上記の推論を入力に適用すると${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle }$量子位相推定は、進化をもたらす。$${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle ={\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|0\rangle ^{\otimes 2n}|\psi _{j}\rangle \to {\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\phi _{j}\rangle |\psi _{j}\rangle .}$$最初のレジスターを測定すると、バランスのとれた確率が得られます。${\displaystyle 1/r}$それぞれを見つける${\displaystyle |\phi _{j}\rangle }$それぞれが整数近似値を与える${\displaystyle 2^{2n}j/r}$で割り切れる${\displaystyle 2^{2n}}$小数近似値を得るには${\displaystyle j/r}$。

ショアのアルゴリズムの実行時ボトルネックは量子モジュラーべき乗であり、これは量子フーリエ変換や古典的な前処理/後処理よりもはるかに遅い。モジュラーべき乗のための回路を構築および最適化するにはいくつかの方法がある。最も単純で（現在）最も実用的な方法は、リップルキャリー加算器から始めて、可逆ゲートで従来の算術回路を模倣することである。べき乗の基数とモジュラスがわかっていると、さらなる最適化が容易になる。^{[ 22 ] [ 23 ]}可逆回路は通常、オーダーの${\displaystyle n^{3}}$ゲート${\displaystyle n}$量子ビット。代替技術では、量子フーリエ変換を使用することでゲート数を漸近的に向上させますが、定数が大きいため、600 量子ビット未満では競争力がありません。

グループが与えられた場合${\displaystyle G}$注文と共に${\displaystyle p}$発電機${\displaystyle g\in G}$仮に、${\displaystyle x=g^{r}\in G}$一部の人にとって${\displaystyle r\in \mathbb {Z} _{p}}$、そして我々は計算したい${\displaystyle r}$これは離散対数です。${\displaystyle r={\log _{g}}(x)}$アーベル群を考える${\displaystyle \mathbb {Z} _{p}\times \mathbb {Z} _{p}}$ここで、各因子は値のモジュラー加算に対応します。次に、関数を考えます。

${\displaystyle f\colon \mathbb {Z} _{p}\times \mathbb {Z} _{p}\to G\;;\;f(a,b)=g^{a}x^{-b}.}$

これにより、アーベル隠れ部分群問題が得られます。${\displaystyle f}$は群準同型に対応する。核はの倍数に対応する。${\displaystyle (r,1)}$カーネルを見つけることができれば、${\displaystyle r}$この問題を解決するための量子アルゴリズムが存在する。このアルゴリズムは、因子探索アルゴリズムと同様にピーター・ショアによるものであり、どちらもアダマールゲートを使用して重ね合わせ状態を作成し、その後実装することで実現される。${\displaystyle f}$量子変換として始まり、最後に量子フーリエ変換が続きます。^{[ 3 ]}このため、離散対数を計算する量子アルゴリズムは、「ショアのアルゴリズム」と呼ばれることもあります。

順序探索問題は、隠れた部分群問題と見なすこともできる。^{[ 3 ]}これを理解するには、加算の対象となる整数群を考え、与えられたに対して、${\displaystyle a\in \mathbb {Z} }$すなわち、${\displaystyle a^{r}=1}$関数

${\displaystyle f\colon \mathbb {Z} \to \mathbb {Z} \;;\;f(x)=a^{x},\;f(x+r)=f(x).}$

任意の有限アーベル群に対して${\displaystyle G}$、隠れた部分群を解くための量子アルゴリズムが存在する。${\displaystyle G}$多項式時間で。^{[ 3 ]}