ショアのアルゴリズム

ショアのアルゴリズムは、整数の素因数を求める量子アルゴリズムです。1994年にアメリカの数学者ピーター・ショアによって開発されました。^{[1] [2]}これは、魅力的な潜在的応用と、最もよく知られている古典的（非量子）アルゴリズムと比較して超多項式による高速化の強力な証拠を持つ、数少ない既知の量子アルゴリズムの1つです。^[3]一方、実用的な意味を持つ数を因数分解するには、近い将来に利用できるよりもはるかに多くの量子ビットが必要です。 ^[4]もう1つの懸念は、量子回路のノイズが結果を損なう可能性があり、^[5]量子エラー訂正のために追加の量子ビットが必要になることです。

ショアは、因数分解問題、離散対数問題、周期探索問題を解くための複数の類似アルゴリズムを提案した。「ショアのアルゴリズム」は通常、因数分解アルゴリズムを指すが、3 つのアルゴリズムのいずれかを指すこともある。離散対数アルゴリズムと因数分解アルゴリズムは周期探索アルゴリズムの例であり、3 つすべてが隠れた部分群問題の例である。

量子コンピュータで整数 を因数分解する場合、ショアのアルゴリズムは多項式時間で実行されます。つまり、かかる時間は の多項式です。^[6]高速乗算を使用するとの量子ゲートが必要になります。 ^[7]または、Harvey と Van Der Hoven による現在知られている漸近的に最速の乗算アルゴリズム^{[8]を使用することで、}整数因数分解問題は量子コンピュータで効率的に解くことができ、その結果、複雑性クラスBQPに入ることが実証されています。これは、最も効率的な既知の古典的な因数分解アルゴリズムである一般数体ふるい よりも大幅に高速で、一般数体ふるいは指数関数的時間未満で動作します。^[9]${\displaystyle N}$${\displaystyle \logN}$${\displaystyle O\!\left((\log N)^{2}(\log \log N)(\log \log \log N)\right)}$${\displaystyle O\!\left((\log N)^{2}(\log \log N)\right)}$ ${\displaystyle O\!\left(e^{1.9(\log N)^{1/3}(\log \log N)^{2/3}}\right)}$

十分な数の量子ビットを持つ量子コンピュータが量子ノイズやその他の量子デコヒーレンス現象に屈することなく動作できる場合、ショアのアルゴリズムは、次のような 公開鍵暗号方式を破るために使用できます。

• RSAスキーム​
• 有限体ディフィー・ヘルマン鍵交換
• 楕円曲線ディフィー・ヘルマン鍵交換^[10]

RSA は、大きな整数の因数分解が計算的に実行可能であれば破ることができます。知られている限り、これは古典的 (非量子) コンピュータを使用しては不可能です。多項式時間で整数を因数分解できる古典的アルゴリズムは知られていません。ただし、ショアのアルゴリズムは、理想的な量子コンピュータでは整数の因数分解が効率的であることを示しているため、大規模な量子コンピュータを構築することで RSA を破ることは実現可能かもしれません。これはまた、量子コンピュータの設計と構築、および新しい量子コンピュータ アルゴリズムの研究の強力な動機でもありました。また、量子コンピュータから安全な新しい暗号システムの研究も促進しました。これらは総称してポスト量子暗号と呼ばれます。

現代の量子コンピュータのエラー率が高く、量子エラー訂正を使用するには量子ビットが少なすぎるため、実験室でのデモンストレーションでは、ほんの数回の試行でしか正しい結果が得られません。

2001年、 IBMのグループがショアのアルゴリズムを実証し、7量子ビットの量子コンピュータのNMR実装を使用して を因数分解しました。 ^[11] IBMの実装後、2つの独立したグループが光子量子ビットを使用してショアのアルゴリズムを実装し、ショアのアルゴリズム回路を実行するとマルチ量子ビットのエンタングルメントが観察されることを強調しました。 ^{[12] [13]} 2012年、 の因数分解が固体量子ビットで実行されました。 ^[14]その後、2012年に、 の因数分解が達成されました。^[15] 2016年、 の因数分解は、リサイクル技術を備えたトラップイオン量子ビットを使用して再度実行されました。^[16] 2019年、 IBM Q System Oneでショアのアルゴリズムを使用して数を因数分解する試みがなされましたが、エラーが蓄積したためにアルゴリズムは失敗しました。^[17]しかし、これらのデモンストレーションはすべて、答えに関する事前知識を利用してアルゴリズムをコンパイルしており、中にはコイン投げと同等になるほどアルゴリズムを単純化しすぎているものもある。^[18]さらに、他のアルゴリズムで量子コンピュータを使用する試みも行われている。^[19]しかし、これらのアルゴリズムは因数の古典的なブルートフォースチェックに似ているため、ショアのアルゴリズムとは異なり、古典的な因数分解アルゴリズムよりも優れたパフォーマンスを発揮することは期待されていない。^[20]${\displaystyle 15}$${\displaystyle 3\times 5}$${\displaystyle 15}$${\displaystyle 21}$${\displaystyle 15}$${\displaystyle 35}$

ショアのアルゴリズムの理論的分析では、量子コンピュータにはノイズやエラーがないと想定しています。しかし、近い将来の実用化では、このような望ましくない現象に対処する必要があります (より多くの量子ビットが利用可能になると、量子エラー訂正が役立ちます)。2023 年に、Jin-Yi Cai は、ノイズが存在する場合、OEISシーケンス A073024の 2 つの素数の積である大きな半素数に対して、ショアのアルゴリズムがほぼ確実に漸近的に失敗することを示しました。 ^[5]これらの素数は、よりも大きい素因数を持ち、すべての素数の集合内で正の密度を持つという特性を持っています。したがって、ショアのアルゴリズムですべての数を因数分解できるようにするには、エラー訂正が必要になります。 ${\displaystyle p}$${\displaystyle p-1}$${\displaystyle p^{2/3}}$

私たちが解こうとしている問題は、奇数の合成数 が与えられたときに、その整数因数を${\displaystyle N}$見つけることです。

これを実現するために、Shor のアルゴリズムは次の 2 つの部分で構成されます。

1. 因数分解問題を順序検索問題に古典的に還元したもの。この還元は、二次ふるいなどの他の因数分解アルゴリズムに使用されるものと類似しています。
2. 順序発見問題を解決するための量子アルゴリズム。

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

基本的な観察は、ユークリッドの互除法を使用すると、常に2つの整数間のGCDを効率的に計算できるということです。特に、これは が偶数かどうかを効率的に確認できることを意味し、その場合、2は明らかに因数です。したがって、この議論の残りの部分では が奇数であると仮定しましょう。その後、効率的な古典的アルゴリズムを使用して が素数累乗であるかどうかを確認できます。^[21]素数累乗については、効率的な古典的因数分解アルゴリズムが存在するため、^[22]量子アルゴリズムの残りの部分では が素数累乗ではないと想定できます。 ${\displaystyle N}$${\displaystyle N}$${\displaystyle N}$${\displaystyle N}$

これらの簡単なケースで の非自明な因数が求められない場合、アルゴリズムは残りのケースの処理に進みます。ランダムな整数 を選びます。 の可能な非自明な約数は を計算することで見つけることができます。これは、ユークリッドのアルゴリズム を使って古典的かつ効率的に行うことができます。これによって非自明な因数が求められた場合 (つまり)、アルゴリズムは終了し、もう 1 つの非自明な因数は です。非自明な因数が特定されなかった場合、 はと の選択が互いに素であることを意味し、したがって はを法とする整数の乗法群に含まれ、を法とする乗法逆数を持ちます。したがって、はを法とする乗法順序を持ち、つまり ${\displaystyle N}$${\displaystyle 2\leq a<N}$${\displaystyle N}$${\displaystyle \gcd(a,N)}$${\displaystyle \gcd(a,N)\neq 1}$${\textstyle {\frac {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}$

量子サブルーチンは を見つけます。これは、を割り切る合同式 からわかります。これは、 と書きます。これは、二乗の差を使用して因数分解できます。このように式を因数分解したので、アルゴリズムは奇数に対しては機能しません(は整数でなければならないため)。つまり、アルゴリズムは新しい で再開する必要があります。したがって、これ以降はが偶数であると仮定できます。 となることはできません。これは を意味し、これは矛盾して がの順序になることを意味し、これはすでに でした。この時点では、 となる場合とそうでない場合があります。 が真でない場合、 は の非自明な因数を見つけることができることを意味します。 を計算します。の場合、 は真であることを意味し、 から の非自明な因数を得ることはできないため、アルゴリズムは新しい で再開する必要があります。それ以外の場合は、 の非自明な因数(もう 1 つは )を見つけたので、アルゴリズムは終了します。このステップでは、 を計算することと同等です。が非自明な場合は非自明な因数を生成し、 が自明な場合は ( の場合) 非自明な因数を生成しません。 ${\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}}}$${\textstyle {\frac {r}{2}}}$${\displaystyle a}$${\displaystyle r}$${\displaystyle N\mid a^{r/2}+1}$${\displaystyle N\mid 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}$${\textstyle {\frac {N}{d}}}$${\displaystyle \gcd(N,a^{r/2}+1)}$${\displaystyle \gcd(N,a^{r/2}-1)}$${\displaystyle N\mid a^{r/2}+1}$

アルゴリズムを簡単に言い換えると、 は奇数であり、素数べき乗ではないとします。 の 2 つの非自明な因数を出力します。 ${\textstyle N}$${\textstyle N}$

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

ショアのアルゴリズムの量子サブルーチンの目的は、互いに素な整数 と が与えられたときに、を法としての位数を見つけることです。これは、 となる最小の正の整数です。これを実現するために、ショアのアルゴリズムは 2 つのレジスタを含む量子回路を使用します。2 番目のレジスタは量子ビットを使用します。ここで、 はとなる最小の整数、つまりです。最初のレジスタのサイズによって、回路が生成する近似値の精度が決まります。量子ビットを使用すると、 を見つけるのに十分な精度が得られることがわかります。正確な量子回路は、問題を定義するパラメータ と に依存します。アルゴリズムの次の説明では、量子状態を表すのに論理積ではなくブラケット表記法を使用し、テンソル積を表します。 ${\displaystyle N}$${\displaystyle 1<a<N}$${\displaystyle r}$${\displaystyle a}$${\displaystyle N}$${\displaystyle a^{r}\equiv 1{\pmod {N}}}$${\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. を(法)で乗算する演算を表すユニタリと、入力状態(2 番目のレジスタは量子ビットから作成されます)を使用して量子位相推定を使用します。この の固有値は周期に関する情報をエンコードし、その固有ベクトルの合計として書き込み可能であると見なすことができます。これらの特性により、量子位相推定ステージは、ランダム に対して の形式のランダムな整数を出力として返します。${\displaystyle U}$${\displaystyle a}$${\displaystyle N}$${\displaystyle |0\rangle ^{\otimes 2n}\otimes |1\rangle }$${\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]、後にキタエフによって提案された。^[24]

一般に、量子位相推定アルゴリズム は、となる任意のユニタリおよび 固有状態に対して、入力状態を に近い出力状態に送ります。ここで、 はに近い整数の重ね合わせです。言い換えると、の各固有状態を、関連付けられた固有値に近い情報を含む状態に送ります。 量子順序検出の目的で、 の作用によって定義されるユニタリ を使用してこの戦略を採用します。 の状態に対するの作用は、アルゴリズムの機能にとって重要ではありませんが、全体的な変換が明確に定義された量子ゲートであることを保証するために含められる必要があります。での量子位相推定用の回路を実装するには、ゲート を効率的に実装できることが必要です。これは、アルゴリズムの中で最も遅い部分であるモジュラ指数によって実現できます。このように定義されたゲートは を満たし、これは直ちにその固有値が1 の-乗根であることを意味します。さらに、各固有値には という形式の固有ベクトルがあり、これらの固有ベクトルは という式になります。ここで最後の恒等式は等比級数公式に従っており、 となります。 ${\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}$ ${\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}$

入力状態に対して量子位相推定を使用すると、高い確率で整数が返されます。より正確には、量子位相推定回路はを に送信し、結果として得られる確率分布は付近でピークに達し、 となります。この確率は、追加の量子ビットを使用して 1 に任意に近づけることができます。 ${\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}}$${\textstyle k=2^{2n}j/r}$${\textstyle p_{2^{2n}j/r}\geq {\frac {4}{\pi ^{2}}}\approx 0.4053}$

上記の推論を入力 に適用すると、量子位相推定は次のように展開されます。最初のレジスタを測定すると、各 を見つけるためのバランスの取れた確率が得られます。各 は の整数近似値を与え、これを で割ると の小数近似値が得られます。 ${\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}$

次に、連分数アルゴリズムを適用して整数と を見つけます。ここで、 は、 と が互いに素であるときに、回路から測定された近似値の最良の分数近似値を与えます。近似値の精度を決定する最初のレジスタ の量子ビット数 により、の重ね合わせから最良の近似値が測定された場合に^[2]が保証されます(これは、追加ビットの使用と出力の切り捨てによって任意の確率で実現できます)。ただし、とは互いに素ですが、と は互いに素でない場合があります。そのため、と は、およびにあったいくつかの因子を失っている可能性があります。これは、量子順序検索サブルーチンを任意の回数再実行して分数近似値のリストを生成することで修正できます。ここで、 はサブルーチンが実行された回数です。回路は (おそらく) の複数の異なる可能な値を測定したため、それぞれから取り除かれる因子は異なります。実際の値を復元するには、それぞれの最小公倍数を取ることができます。最小公倍数は、高い確率で元の整数の順序になります。実際には、より高度な後処理を使用する場合、量子順序検索サブルーチンを1回実行するだけで十分です。^[25]${\textstyle b}$${\textstyle c}$${\textstyle {\frac {b}{c}}}$${\textstyle b,c<N}$ ${\textstyle b}$${\textstyle c}$${\displaystyle 2n}$$${\displaystyle {\frac {b}{c}}={\frac {j}{r}}}$$${\textstyle |\phi _{j}\rangle }$${\textstyle b}$${\textstyle c}$${\textstyle j}$${\textstyle r}$${\textstyle b}$${\textstyle c}$${\textstyle j}$${\textstyle r}$$${\displaystyle {\frac {b_{1}}{c_{1}}}_{\textstyle ,}\;{\frac {b_{2}}{c_{2}}}_{\textstyle ,}\ldots {\vphantom {\frac {b_{1}}{c_{1}}}}_{\textstyle ,}\;{\frac {b_{s}}{c_{s}}}}$$${\textstyle s}$${\textstyle c_{k}}$${\textstyle j}$${\textstyle r}$${\textstyle c_{k}}$$${\displaystyle \mathrm {lcm} (c_{1},c_{2},\ldots ,c_{s})}$$${\textstyle r}$${\textstyle a}$

位相推定では、アルゴリズムの精度を決定するために最初のレジスタのサイズを選択する必要があり、ショアのアルゴリズムの量子サブルーチンの場合、位相推定から測定された最適なビット文字列（つまり、位相推定からの位相の最も正確な近似値）によっての実際の値が回復されることを保証するには、量子ビットで十分です。 ${\displaystyle 2n}$${\displaystyle |k\rangle }$${\textstyle k/2^{2n}}$${\displaystyle r}$

ショアのアルゴリズムにおける各事前測定は、 を近似する整数の重ね合わせを表します。が における最適な整数を表すものとします。次の定理は、連分数アルゴリズムが から回復することを保証します。 ${\displaystyle |\phi _{j}\rangle }$${\displaystyle 2^{2n}j/r}$${\displaystyle |k\rangle }$${\displaystyle |\phi _{j}\rangle }$${\displaystyle j/r}$${\displaystyle k/2^{2{n}}}$

^[3]位相推定からの最適ビット列はビットまで正確です。したがって、これは連分数アルゴリズムが および（または最大公約数を取り除いたもの）を回復することを意味します。 ${\displaystyle k}$${\displaystyle k/2^{2{n}}}$${\displaystyle j/r}$${\displaystyle 2n}$$${\displaystyle \left\vert {\frac {j}{r}}-{\frac {k}{2^{2n}}}\right\vert \leq {\frac {1}{2^{2{n}+1}}}\leq {\frac {1}{2N^{2}}}\leq {\frac {1}{2r^{2}}}}$$${\displaystyle j}$${\displaystyle r}$

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

離散対数問題と順序検索問題に対するショアのアルゴリズムは、周期検索問題を解くアルゴリズムの例です。^{[引用が必要]}。これら 3 つはすべて、隠れたサブグループ問題の例です。

位数と生成元を持つ群 が与えられ、ある に対して であることがわかっていて、離散対数を計算したいとします。アーベル群 を考えます。ここで、各因子は値のモジュラー加算に対応します。ここで、関数を考えます。 ${\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}.}$

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

順序探索問題は、隠れた部分群問題として見ることもできる。^[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).}$

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

• GEECMは因数分解アルゴリズムで、「ショアのアルゴリズムよりもはるかに高速であることが多い」と言われている^[28]
• グローバーのアルゴリズム

• ニールセン、マイケル A.、チュアン、アイザック L. (2010)。量子計算と量子情報: 10 周年記念版。ケンブリッジ大学出版局。ISBN 978-1-107-00217-3。
• Kaye, Phillip; Laflamme, Raymond; Mosca, Michele (2006).量子コンピューティング入門. doi :10.1093/oso/9780198570004.001.0001. ISBN 978-0-19-857000-4。
• Scott Aaronsonによる「一般人向けの説明」、Peter Shor による「承認」。(Shor は「素晴らしい記事です、Scott! 量子コンピューティングを一般人に説明するものとしては、私が見た中で最高です」と書いています)。コメントの 1 つで、QFT の別のメタファーが提示されました。Scott Aaronson は、さらに読むべきものとして次の 12 の参考文献を提案しています (「Web 上にすでに存在する 10 ^{10 5000 の}量子アルゴリズム チュートリアル」のうち)。
• Shor, Peter W. (1997)、「量子コンピュータによる素因数分解と離散対数の多項式時間アルゴリズム」、SIAM J. Comput.、26 (5): 1484–1509、arXiv : quant-ph/9508027v2、Bibcode :1999SIAMR..41..303S、doi :10.1137/S0036144598347011Peter Shor によるオリジナル論文の改訂版 (「28 ページ、LaTeX。これは、1994 年 11 月 20 日から 22 日までニューメキシコ州サンタフェで開催された第 35 回コンピュータ サイエンスの基礎に関する年次シンポジウムの議事録に掲載された論文の拡張版です。1996 年 1 月に若干の改訂が行われました」)。
• 量子コンピューティングとショアのアルゴリズム、Matthew Hayward の量子アルゴリズム ページ、2005-02-17、imsa.edu、元の LaTeX ドキュメントの LaTeX2HTML バージョン。PDF または PostScript ドキュメントとしても利用可能。
• 量子計算とショアの因数分解アルゴリズム、ロナルド・デ・ウルフ、CWI およびアムステルダム大学、1999 年 1 月 12 日、9 ページの追記文書。
• Shor の因数分解アルゴリズム、Berkeley CS 294–2 の講義 9 のノート、2004 年 10 月 4 日付、7 ページの追記文書。
• 第 6 章 量子コンピューティング Archived 2020-04-30 at the Wayback Machine、91 ページの追記文書、Caltech、Preskill、PH229。
• 量子計算: Samuel L. Braunstein によるチュートリアル。
• ショアのアルゴリズムの量子状態、Neal Young 著、最終更新日: 1996 年 5 月 21 日火曜日 11:47:38。
• III. 量子コンピュータによる RSA 暗号の解読: ショアの因数分解アルゴリズム、量子計算に関する講義ノート、コーネル大学、物理学 481-681、CS 483、2006 年春、N. David Mermin 著。最終更新日 2006-03-28、30 ページの PDF ドキュメント。
• Lavor, C.; Manssur, LRU; Portugal, R. (2003). 「大きな整数を因数分解する Shor のアルゴリズム」. arXiv : quant-ph/0303175 .
• Lomonaco, Jr (2000). 「Shor の量子因数分解アルゴリズム」. arXiv : quant-ph/0010034 . この論文は、ピーター・ショアの量子因数分解アルゴリズムに関する 1 時間の講義を文書化したもので、22 ページあります。
• 第 20 章 量子計算、計算複雑性: 現代的アプローチ、本の草稿: 2007 年 1 月、Sanjeev Arora および Boaz Barak、プリンストン大学。Sanjeev Arora、Boaz Barak の第 10 章 量子計算として出版、「計算複雑性: 現代的アプローチ」、ケンブリッジ大学出版、2009 年、ISBN 978-0-521-42426-4 
• 量子コンピューティングへの第一歩: 100 億個の粒子の絡み合い、Wayback Machineに 2011 年 1 月 20 日にアーカイブ、2011 年 1 月 19 日付の「Discover Magazine」より。
• Josef Gruska - 量子コンピューティングの課題、Mathematics unlimited: 2001 and beyond、編集者 Björn Engquist、Wilfried Schmid、Springer、2001、ISBN 978-3-540-66913-5にも掲載 

• libquantum のバージョン 1.0.0: シミュレートされた量子コンピュータ ライブラリを使用した Shor アルゴリズムの C 言語実装が含まれていますが、実行時の複雑さを改善するには、shor.c の width 変数を 1 に設定する必要があります。
• PBS Infinite Series は、ショアのアルゴリズムの背後にある数学を説明する 2 つのビデオ「暗号を破る方法」と「ショアのアルゴリズムによる量子速度でのハッキング」を作成しました。
• ClassiciqによるShorのアルゴリズムの完全実装