🌐 This site is also available in English Visit English Site →
🌐 English
MENU
| 技術情報発信（素材技術を未来へ）
  1. ホーム
  2. 量子アルゴリズム 技術解説

量子アルゴリズム 技術解説

← 量子コンピューターの解説一覧へ戻る

TECHNOLOGY EXPLAINER

量子アルゴリズム
― なぜ量子で速くなるのか：干渉、Deutsch・Grover・Shor、位相推定、シミュレーション

量子コンピュータが一部の問題を速く解けるのは、「全部の答えを同時に計算するから」ではありません。正しい答えの波が強め合い、間違いの波が弱め合うように、計算を設計するからです。 この記事は、量子力学を知らない人にも読めるように、この「干渉の設計」という型を、Deutsch の問題（最小の例）、Grover の探索、Shor の因数分解、位相推定、量子シミュレーションの順に、図と小さな数値例で説明します。 後半では、どの問題で速くなり、どの問題では速くならないか、理論上の話と実機での話の違い、素材技術者から見た量子シミュレーションの現実をまとめます。「量子コンピュータの基礎」「量子ゲートと量子回路」「コヒーレンスとフィデリティ」編の次に読む記事です。

構成：総説（Montanaro、Dalzell ら）、査読論文（Physical Review、Nature、Science、SIAM J. Comput. など）、arXiv の論文、Quantum Algorithm Zoo、NIST・DARPA・ISO・IEEE の公式ページを使用／数値例は本稿で計算／確認日 2026年10月16日

量子アルゴリズムを、「波の干渉」の絵と回路図で考えている場面のイメージです。実際の研究室・資料を示すものではありません。
図1　概念画像（ImageGen生成）。量子アルゴリズムを、「波の干渉」の絵と回路図で考えている場面のイメージです。実際の研究室・資料を示すものではありません。 実際の製品・施設・寸法・測定結果ではありません。拡大模型と実物スケールの場面は区別してください。
この記事の構成
  1. 3行でわかる／読む前に知っておくこと／シリーズの中での位置
  2. なぜ速くなるのか：答えは「干渉」
  3. 最小の例：Deutsch の問題（と Deutsch–Jozsa）
  4. Grover の探索：「2乗根」の高速化
  5. Shor の因数分解：「周期」を見つける
  6. 量子位相推定：「回転の速さ」を読む
  7. 量子シミュレーション：Feynman の考え
  8. どの問題で速くなり、どの問題で速くならないか
  9. 理論上の話と、実機での話
  10. 素材技術者の視点：アルゴリズムの要求と、材料・装置
  11. 評価・標準の読み方
  12. 用語集
  13. 参考資料（一次情報）
  14. 主張と出典の対応表（監査）
本記事の表記ルール

事実＝公表資料に記載のある内容（出典リンクあり）
本稿の計算＝明示した前提をもとに本記事が算出・確認した値
未確定／将来＝資源推定、企業・国の計画、策定中の標準など、確定していない事項
このほか、素材分野への読み取りは「解説」として区別しています。推測は太字で示します。たとえ話には、必ず「たとえの限界」を書きます。

この記事の数値と、暗号について

第3〜6章の振幅・確率・回数・周期の数値は、本稿が計算した説明用の値で、実在の装置の測定結果ではありません。第9章の資源推定は、仮定つきの理論上の推定で、将来の予測ではありません。 Shor のアルゴリズムは、考え方の説明にとどめ、暗号を破る具体的な手順や実装は書きません。「量子コンピュータが暗号を破る時期」は、確実には予測できないことを前提に、標準・指針の説明（第11章）にとどめます。規格（NIST・ISO/IEC・IEEE）は題名・状態の確認にとどめ、本文は確認していません。この分野は変化が速いため、状態には確認日（2026年10月16日）を付けています。

1. 3行でわかる／読む前に知っておくこと／シリーズの中での位置

  • 速くなる理由は「干渉」：量子アルゴリズムは、準備して、問題の構造を波の符号に載せ、干渉で正解の波を強め、測る、という型をとります。「全部の答えを同時に計算する」のではありません事実［参考資料1・2］
  • 速くなる問題は限られ、速さの種類も違う：因数分解（Shor）は理論上、桁違いに速く、探索（Grover）は回数が「2乗根」になるだけです。大半の問題では、量子で速くなることは示されていません事実［参考資料3・4］
  • 理論と実機は別の話：理論上の高速化は、誤り訂正のある大きな装置を前提にします。実機での実演は、小さな例にとどまり、推定される必要規模は、現在の実験機より桁違いに大きいです事実／未確定／将来［参考資料6・5］
この記事を読む前に知っておくこと

「量子コンピュータの基礎」編の矢印、測定、干渉（波の足し算で、プラスとマイナスの振幅が打ち消し合う）、「量子ゲートと量子回路」編のゲート（H、CNOT など）を使います。読んでいなくても分かるよう、必要な部分は短く説明し直します。式は最小限で、難しい話は「もっと詳しく」の折りたたみに入れています。

シリーズの中での位置

この記事は、「コヒーレンスとフィデリティ」編の次に読む記事で、量子コンピュータの「入門の4部作」の最後です。誤り訂正、NISQ とハイブリッド計算、量子優位性の読み方、量子化学、耐量子暗号は、本シリーズの各編で詳しく扱います。

2. なぜ速くなるのか：答えは「干渉」

量子コンピュータの速さの説明で、よく聞くのは「並列計算」という言葉です。「量子ビットが0と1を同時にとるので、たくさんの計算を一度にできる」という説明ですが、「量子コンピュータの基礎」編で見たとおり、この言い方は誤解のもとです。測定で取り出せるのは1つの結果だけで、何も工夫しなければ、ランダムな1つの候補が出るだけだからです。

では、何が速さを生むのでしょうか。Cleve らは、計算の複数の経路の量子干渉で、正しい結果を強め、誤った結果を抑えることが、量子アルゴリズムに共通する型だと述べています事実［参考資料1］。次の図が、その型です。

量子アルゴリズムの型：「波を設計して、正解を強める」 ① 準備 すべての候補に同じ高さの波 ② 構造を位相に載せる 問題の「答えの印」を波の符号に ③ 干渉 波を足し引きして、正解を強める ④ 測定 強い波の候補が出やすい 候補（棒＝波の高さ） 正解だけ符号を反転 波の平均で折り返して強める 測ると正解が高い確率で出る この型は、3つの代表的なアルゴリズムに共通します Deutsch–Jozsa 「答えの印」＝関数が定数か均等か。干渉で、定数なら 0 が確実に出る Grover 探索 「答えの印」＝当たりの候補。折り返しをくり返して、当たりの波を高くする Shor 因数分解 「答えの印」＝周期。フーリエ変換の干渉で、周期に対応する値が強まる ※ 概念図です。波の高さ（振幅）は説明用で、特定のアルゴリズムの値ではありません。
図2　概念図（ベクター作図）。量子アルゴリズムに共通する4段階の型の概念図。Cleve らは、量子計算を、計算の経路の量子干渉で正しい結果を強め、誤った結果を抑えるものとして捉えられると述べています［参考資料1］。
よくある誤解：「量子コンピュータは並列に計算するから速い」は不正確

「すべての候補を同時に計算する」のではなく、すべての候補に波を割り当て、その波を干渉させて、正解に集めるのが、量子アルゴリズムです。この集め方は、問題の構造（周期、対称性、当たりの印など）を使えるときにしか、うまく設計できません。だから、速くなる問題は限られます（第8章）。

つまずきやすいところ：「問題の構造を波の符号に載せる」とは

たとえば「当たりの候補を見つけたい」とき、当たりかどうかを確かめる箱（オラクル）を使い、当たりの候補の波の符号だけを反転します（図の②）。符号の違いは、そのままでは測定に出ませんが、次の干渉で「強さの違い」に変わります。これは「量子ゲートと量子回路」編で見た、Z ゲートの「見えない変化」が、H ではさむと見える、という話と同じ仕組みです（本記事による解説）。

3. 最小の例：Deutsch の問題（と Deutsch–Jozsa）

干渉の型を、いちばん小さな例で確かめます。1985年に Deutsch が提案した問題で、「量子コンピュータが古典より少ない問い合わせで答えられる」ことを示した最初の例です事実［参考資料7・3］。

箱 f があり、入力が0か1のとき、それぞれ0か1を返します。f(0) と f(1) が同じ（定数）か違う（均等）か、どちらかだけを知りたい、という問題です。古典では、f(0) と f(1) を両方聞く必要があり、2回の問い合わせが要ります。量子では、H、オラクル、H の順に1回かけるだけで答えが分かります。

最小の例：Deutsch の問題（H・オラクル・H の1回） 問題：箱 f の中身を、できるだけ少ない問い合わせで知る 箱 f は、入力 0 と 1 に、それぞれ 0 か 1 を返す。 f(0) と f(1) が「同じ」なら定数、「違う」なら均等。 どちらかだけを知りたい（値は知らなくてよい） |0⟩ H U_f H オラクル（箱 f を1回だけ使う） 古典：f(0) と f(1) の2回が必要。量子：1回（オラクルの意味で） 結果：|0⟩ の振幅を足して決まる f(0) f(1) 種類 |0⟩の振幅 測定 0 0 定数 +1 0 1 1 定数 −1 0 0 1 均等 0 1 1 0 均等 0 1 定数なら必ず 0、均等なら必ず 1 が出る Deutsch–Jozsa（入力が n ビットの場合）でも、この「1回」は変わらない。ただし、注意： ・古典の「決定的」な方法は、最悪で 2^(n−1) + 1 回（n = 20 なら 524,289 回）の問い合わせが必要 ・でも、古典でも「乱数」を使えば、10回ほどの問い合わせで誤り 0.2% 以下で見分けられる（本稿の計算：n = 20、10回で 約0.195%） ・つまり指数的な差は、「決定的な古典」に対してだけ。実用の速さの証明ではない ・「オラクル」は、中身を知らない箱として数える約束。箱の中身を作るコストは、別に必要
図3　本稿の計算を含む作図（ベクター作図）。Deutsch の問題の回路と結果の表（位相で印をつけるオラクルを使った版）。振幅は本稿の計算で、行列計算で4つの関数すべてを確認しました。Deutsch–Jozsa の古典側の評価は Quantum Algorithm Zoo［参考資料3］と Cleve ら［参考資料1］によります。

なぜ分かるのでしょうか。1回目の H で、0 と 1 に同じ高さの波（0.71 ずつ）を作ります。オラクルが、f の値に応じて、各波の符号を反転します。2回目の H で、2つの波を足し合わせると、f が定数なら「0」に強め合い、均等なら「0」が弱め合って消えます。「量子コンピュータの基礎」編で見た「H を2回かけると元に戻る」の、間に符号反転をはさんだ版です。4つの関数すべてで、「0」の振幅は +1、−1（定数）または 0（均等）になることを、行列計算で確認しました本稿の計算。

よくある誤解：「Deutsch–Jozsa は、量子の指数的な高速化の証拠」は不正確

入力が n ビットの Deutsch–Jozsa の問題（Deutsch と Jozsa、1992）でも、量子は1回の問い合わせで足ります［参考資料8］。古典の決定的（乱数を使わない）な方法は、最悪で 2n−1 + 1 回が必要で、n = 20 なら 524,289 回です。ところが、古典でも乱数を使えば、確率的には少ない問い合わせで見分けられます。Quantum Algorithm Zoo は、この問題を「確率的には O(1) 回の問い合わせで簡単に解ける」とし、速さの差を「決定的な古典に対しては指数的、確率的な古典に対してはなし」としています事実［参考資料3］。本稿の計算では、n = 20 で10回の問い合わせの誤りは約0.195% です本稿の計算（均等な関数が、10回とも同じ値に見える確率 21−10 に近い値）。つまり、指数的な差は「決定的な古典」に対してだけで、実用の速さの証明ではありません。「オラクル」は、中身を知らない箱を1回と数える約束で、箱の中身を作るコストは別に必要です。

つまずきやすいところ：なぜ、役に立たない問題を例にするのか

Deutsch の問題そのものは、実用的な問題ではありません。干渉で答えを選び出す仕組みを、いちばん小さく見せるための教材です。Simon の問題（Simon、1997）や Bernstein–Vazirani の問題（Bernstein と Vazirani、1997）も、同じ型で、オラクルを使った問題です事実［参考資料9・10］。これらは、Shor のアルゴリズムの考え方につながりました（本記事による解説）。

4. Grover の探索：「2乗根」の高速化

Grover（1996）の探索は、「N 個の候補から、当たりを1個探す」問題で、当たりかどうかは、オラクルで確かめられる、という設定です。古典では、平均で N/2 回、最悪で N 回の問い合わせが要ります。Grover のアルゴリズムは、約 √N 回で見つけます事実［参考資料11・3］。しくみは、次の「折り返し」のくり返しです。

Grover の探索（候補8個、当たり1個）：「折り返し」をくり返す 0回：最初 当たりが出る確率 12.5% 当たりの振幅 0.35 1回 当たりが出る確率 78.1% 当たりの振幅 0.88 2回：ほぼ最適 当たりが出る確率 94.5% 当たりの振幅 0.97 3回：やりすぎ 当たりが出る確率 33.0% 当たりの振幅 0.57 1回の「折り返し」は2つの操作：①当たりの波だけ符号を反転、②全部の波の平均を軸に折り返す。 ①でマイナスになった当たりは、平均より遠くなるので、②で大きく上がる。他の波は少し下がる。 でも、くり返しすぎると、当たりの波が行き過ぎて、また下がってしまう（3回のとき 33%）。 赤＝当たり、青＝他の候補（負の棒は波が負）。
図4　本稿の計算を含む作図（ベクター作図）。N = 8 の Grover 探索を、行列計算でたどった各段階の振幅（本稿の計算）。当たりの振幅は 0.35 → 0.88 → 0.97 → 0.57、確率は 12.5% → 78.1% → 94.5% → 33.0%。実在の装置の結果ではありません。仕組みは Grover の論文［参考資料11］によります。

候補が8個（N = 8）、当たりが1個の例で、振幅を行列計算でたどりました。最初は、どの候補の波も同じ高さ（0.35）で、当たりの確率は 12.5%（= 1/8）です。1回の折り返しで当たりの振幅は 0.88（確率 78.1%）、2回で 0.97（確率 94.5%）になり、3回では行き過ぎて 0.57（確率 33.0%）に下がります本稿の計算。つまり、回数は多ければ良いわけではなく、最適な回数があります。最適な回数は、約 (π/4)·√N です。

反復の回数と成功確率、そして「2乗根」の意味（本稿の計算） 反復回数 k と、当たりが出る確率 0% 50% 100% 0 2 4 6 8 10 12 反復の回数 k 青：N = 8（最適 2回） 赤：N = 64（最適 6回） 最適な回数のまわりで山になり、行き過ぎると下がる 当たりを見つける問い合わせ回数（対数目盛） 10 10³ 10⁵ 10⁷ 10⁹ N = 10⁶ 古典（平均）500,000 Grover 約 785 N = 10⁹ 古典（平均）500,000,000 Grover 約 24,836 注意：減るのは「回数が N から √N に」で、「瞬時」ではない。1回ごとの中身（オラクル）の実行コストは別。 N を 1000倍にしても、量子の回数は約 32倍。ただし、誤り訂正の負担が大きいと、2乗の高速化は得にならないことがある（第8章）。
図5　本稿の計算を含む作図（ベクター作図）。Grover の反復回数と成功確率（N = 8 と 64）、および古典の平均の回数（N/2）との比較（本稿の計算）。回数は (π/4)√N に近い値で、N = 10⁶ で 785 回、N = 10⁹ で 24,836 回です。Grover の回数が最適であること（Ω(√N)）は Bennett ら・Zalka・Boyer らが示しています［参考資料4・13・12］。
候補の数 N古典（平均）の問い合わせ回数 N/2Grover の最適な反復回数（約 (π/4)√N）そのときの成功確率
84294.5%
6432699.7%
1,0005002499.96%
106500,000785約 100%
109500,000,00024,836約 100%

本稿の計算。Grover の成功確率 sin²((2k+1)θ)（θ = arcsin(1/√N)）と、最適な反復回数を計算しました。古典の平均は N/2 回としました。実在の装置の結果ではありません。

この「2乗根」が、最適であること（これ以上は減らせない）は、Bennett ら（1997）、Boyer ら（1998）、Zalka（1999）が示しています事実［参考資料4・12・13］。「何も構造のない探索」では、量子でも、総当たりの回数の2乗根までしか減らせない、ということです。

よくある誤解：「Grover は、データベース検索（Web 検索）を一瞬にする」は誤り

Grover の「データベース検索」は、名前から誤解されやすいのですが、構造のない候補の中から、当たりかどうかを確かめる箱（オラクル）で探す問題です。Web 検索のように整理された大量のデータを扱うものではなく、また、「一瞬」でもありません（回数が √N になるだけ）。データを量子状態として読み込むコスト（入力の問題）や、1回ごとのオラクルの実行コストは、別に必要です（本記事による解説）。

つまずきやすいところ：2乗の高速化は、誤り訂正のコストで「得にならない」ことがある

回数が √N になっても、1回の反復が、誤り訂正のために非常に重いと、全体の時間は、古典の総当たりより長くなることがあります。Babbush らは、計算が現実的な時間に終わる必要がある一方、誤り訂正の大きな定数倍の負担を、小さな多項式の高速化では埋め合わせにくいことを計算し、2乗の高速化は、誤り訂正の実現方法が大きく改善しない限り、初期の誤り耐性のある装置では量子優位性を生まないと結論しています（4乗の高速化のほうが、はるかに実用的に見える、とも述べている）事実［参考資料14］。

5. Shor の因数分解：「周期」を見つける

Shor（1997）のアルゴリズムは、大きな整数を素因数に分解する問題を、量子コンピュータで多項式の時間で解く方法です事実［参考資料15］。因数分解は、素数の積（たとえば 15 = 3 × 5）を、もとの素数に戻す問題で、数が大きくなると、古典では急に難しくなります。Quantum Algorithm Zoo によれば、Shor のアルゴリズムは、n ビットの整数を、おおよそ n3 に比例する時間（Õ(n3)）で分解し、古典で知られている最も速い方法（数体ふるい法）は、約 2Õ(n1/3) の時間（と信じられている）です事実［参考資料3］。

(1) 考え方：因数分解を「周期を見つける問題」に変える

Shor のアルゴリズムの核心は、因数分解を、周期を見つける問題に言い換えることです。小さな例（N = 15）で見てみましょう。a = 7 を選び、7x を 15 で割った余りを x = 0, 1, 2, … と並べると、1, 7, 4, 13, 1, 7, 4, 13, 1 … と、4 個ごとに同じ並びがくり返されます。この「4」が周期 r です。周期が分かれば、ar/2 ± 1 と 15 の最大公約数から、約数が見つかります（49 − 1 = 48 と 15 の最大公約数は 3、49 + 1 = 50 と 15 の最大公約数は 5）本稿の計算。

Shor の因数分解：「周期」を見つけると、約数が見つかる（N = 15） ① a = 7 を選び、7ˣ を 15 で割った余りを並べる 1 x = 0 7 x = 1 4 x = 2 13 x = 3 1 x = 4 7 x = 5 4 x = 6 13 x = 7 1 x = 8 1 周期（r = 4） ② 周期 r を、量子で見つける（干渉） 0 16 32 48 測って出る値 y（0〜63）：0・16・32・48 だけが、25% ずつ 間隔 16 ＝ 64 ÷ r から、r = 4 が分かる ③ 約数を計算する（ふつうの計算） a^(r/2) = 7² = 49 49 − 1 = 48 → 15 との最大公約数 3 49 + 1 = 50 → 15 との最大公約数 5 15 ＝ 3 × 5（小さな数なので、頭でも分かる） Shor の核心は ② だけ。だから、量子のしくみ（干渉）が使われるのは「周期を見つける」部分 大きな数では、②を動かすために、非常に多くの量子ビットと長い回路が必要（第9章）。 古典で知られている最良の方法は、桁数に対して指数関数より遅い増え方（準指数）。Shor は桁数の3乗程度［参考資料3］。 ※ 15 = 3 × 5 は教科書的な例で、実在の暗号の鍵の大きさとは桁違いです。攻撃の手順の説明ではありません。
図6　本稿の計算を含む作図（ベクター作図）。Shor のアルゴリズムの考え方を、N = 15・a = 7 で追った図（本稿の計算：7ˣ mod 15 の周期 4、64点のフーリエ変換で 0・16・32・48 に 25% ずつのピーク、gcd(48,15) = 3、gcd(50,15) = 5）。仕組みは Shor の論文［参考資料15］によります。

(2) 量子コンピュータが担当するのは「周期の発見」だけ

周期を見つける部分に、量子の干渉が使われます。余りの並びを「量子状態」として用意し、量子フーリエ変換（周期的なパターンを、周波数に変える変換）をかけると、周期に対応する値に波が強め合って集まります。上の図の例（周期4、64点の変換）では、測って出る値が 0、16、32、48 の4つだけになり（各25%）、その間隔 16 = 64 ÷ 4 から、周期 4 が分かります本稿の計算。周期がきれいに割り切れない場合は、ピークが少しぼやけますが、近くの値に集まり、そこから周期が推定できます（本稿の計算：N = 21、a = 2 の周期 6、128点の変換で、ピークが 0、21、43、64、85、107 のあたりに集まる）。

つまずきやすいところ：「周期」と「干渉」の関係

周期的な並びの波を足し合わせると、周期に合った周波数でだけ波が強め合い、他では打ち消し合います。これは、音の「うなり」や、光の回折格子で特定の方向にだけ光が強まる現象と同じ種類の干渉です。たとえの限界：実際の量子フーリエ変換は、振幅に作用する量子ゲートの列で、音や光そのものではありません（本記事による解説）。

よくある誤解：「Shor のアルゴリズムは、実機で大きな数を因数分解した」は誤り

最初の実演は、Vandersypen ら（2001）による N = 15 の因数分解で、分子の中の7個の核スピンを核磁気共鳴で操作したものです。論文自身が、この方法は原理的にはスケールするが、今回の実験がそれを意味するわけではない、と述べています事実［参考資料16］。さらに Smolin ら（2013）は、小規模の実演の多くが、答えの因数を先に知っていることに頼った簡略化を使っていたこと、Shor のアルゴリズムの実装の難しさの正しい尺度は、因数分解する数の大きさではなく、見つける周期の長さであることを指摘しています事実［参考資料17］。「15 = 3 × 5」の実演は、実用規模への到達を意味しません。

6. 量子位相推定：「回転の速さ」を読む

Shor の周期発見の考え方を一般化したのが、量子位相推定です。Kitaev（1995）が定式化し、Cleve ら（1998）が、多くの量子アルゴリズムが位相推定の異なる場合として理解できることを示しました事実［参考資料18・1］。

身近なたとえでいえば、時計の針の回る速さを、何周も重ねて測り、精度よく読み取る方法です。ある操作 U をかけると、特定の状態（固有状態）は、状態の向きだけが回ります。その回転の角度（位相 φ）を、読み出しの量子ビット n 個と干渉を使って、2進数の n 桁で読み取ります。

量子位相推定：「回転の速さ」を、干渉で読み取る 回路の形（読み出し 4 ビット） q0 H q1 H q2 H q3 H U U² U⁴ U⁸ |ψ⟩ U の固有状態 |ψ⟩ QFT† 逆 制御つきの U を、1・2・4・8 回ぶん → 逆フーリエ変換 → 測定 例：位相 φ = 1/3 を、4ビットで読む 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 68% 17% 読み出し y → 位相の推定値 y/16 y = 5 → 0.3125、y = 6 → 0.375（真の値は 0.3333） ・読み出しのビットが1つ増えると、位相の精度は2倍よくなる（精度 ≒ 1/2ⁿ） ・0.25 のように、n ビットで正確に書ける位相は、確実に（100%）読める（2ビットの例で確認） ・φ = 1/3 のように書き切れない位相は、近い2つの値に確率が集まる（本稿の計算：y = 5 が 68.5%、y = 6 が 17.2%、真の値から 1/16 以内 に入る確率は 85.7%） ・位相は、U の「固有値」、つまりその系のエネルギーに関係する。だから、分子のエネルギーを読む部品に使われる（第7章）
図7　本稿の計算を含む作図（ベクター作図）。量子位相推定の回路の形と、位相 1/3 を4ビットで読んだときの確率の分布（本稿の計算）。位相推定は Kitaev［参考資料18］と Cleve ら［参考資料1］が定式化しました。回路は概念図です。

位相 φ = 0.25（2進数で 0.01）のように、2ビットで正確に書ける位相は、確実に読めます。φ = 1/3 のように書き切れない位相は、4ビットで読むと、近い2つの値に確率が集まります。本稿の計算では、y = 5（位相の推定値 0.3125）が 68.5%、y = 6（0.375）が 17.2% で、真の値から 1/16 以内に入る確率の合計は 85.7% でした本稿の計算。読み出しのビットを増やすと、精度は 2 倍ずつよくなります。

位相推定は、Shor のアルゴリズム（周期は位相として現れる）と、次章の量子シミュレーション（エネルギーが位相として現れる）の、共通の部品です。

7. 量子シミュレーション：Feynman の考え

Feynman は1982年に、古典の計算機で量子の系を追うと、系の大きさとともに計算量が急に増えてしまうことを指摘し、量子の系は、量子の部品で模擬するのが自然だという考えを示しました事実［参考資料19］。Lloyd（1996）は、これが実際に可能であることを示しました（ユニバーサル量子シミュレータ）事実［参考資料20］。Aspuru-Guzik ら（2005）は、分子のエネルギーを量子計算で求める方法を提案しました事実［参考資料21］。

物理系のモデルから回路を作り、量子装置で得た測定を古典側で解析する流れです。すべての問題が速く解けることを表すものではありません。
図8　概念画像（ImageGen生成）。物理系のモデルから回路を作り、量子装置で得た測定を古典側で解析する流れです。すべての問題が速く解けることを表すものではありません。 実際の製品・施設・寸法・測定結果ではありません。拡大模型と実物スケールの場面は区別してください。
元のSVG・数値・出典を確認する
量子シミュレーション：「量子の系を、量子の部品で模擬する」 ① 分子・材料 触媒・電池材料など ② 式にする エネルギーの式 ③ 回路にする 時間発展をゲートに ④ エネルギーを読む 位相推定／変分法 ⑤ 予測 エネルギー・反応 なぜ量子で模擬するのか（Feynman, 1982） 古典：n 量子ビット相当の状態を、そのまま書くと 2ⁿ 個の数 量子：n 量子ビットで、自然に表せる → 量子の系の「実験」を、量子コンピュータの上で行う ただし、古典にも優れた近似法がある（下） 決め手は「古典の最良手法との比較」 古典側：密度汎関数法、結合クラスター法、 テンソルネットワーク法など（解説） 問題ごとに、古典で十分な場合と、足りない場合がある → 量子の利点は「問題ごと」に評価する 実機での到達：水素分子や小さな分子、小さな磁性モデルなど、小規模な例（Kandala ら、2017。Xue ら、2022 のシリコンスピンでも、変分法で分子のエネ ルギーを計算） 将来の見込み：FeMoco（窒素固定の酵素）などの資源推定が報告されている（Reiher ら、2017。Lee ら、2021）。これは理論上の推定で、実機の結果では ない 評価：基底状態エネルギーで、化学全般に指数的な量子の利点が見込めるという証拠は、まだ見つかっていない（Lee ら、2023）

元SVGの説明：概念図（ベクター作図）。量子シミュレーションの流れと、評価の考え方の概念図。実機の例は Kandala ら［参考資料22］、Xue ら［参考資料23］、資源推定は Reiher ら［参考資料24］と Lee ら［参考資料25］、評価は Lee ら［参考資料26］によります。

流れは、分子や材料を「エネルギーの式（ハミルトニアン）」で表し、その時間発展をゲートの列に分解し、位相推定（または変分法）でエネルギーを読み取る、というものです。量子化学では、基底状態のエネルギーが、反応のしやすさや、触媒の働き、電池材料の電圧などに関係します（本記事による解説）。

実機での到達と、資源推定、評価

  • 実機：Kandala ら（2017）は、超伝導の量子プロセッサ（最大6量子ビット）で、水素化リチウムやベリリウムの水素化物などの小さな分子と、小さな磁性モデルを、変分法で計算しました事実［参考資料22］。Xue ら（2022）のシリコンスピンの装置でも、変分法で分子の基底状態のエネルギーが計算されています事実［参考資料23］。いずれも小規模な例です
  • 資源推定：Reiher ら（2017）は、窒素固定の酵素（FeMoco）を例に、量子コンピュータで反応の機構を調べる資源推定を示し、Lee ら（2021）は、テンソル超縮約を使って、必要な資源を減らす方法を示しました事実［参考資料24・25］。これらは理論上の推定で、実機の結果ではありません（未確定／将来）
  • 評価：Lee ら（2023）は、基底状態のエネルギーについて、化学の全般にわたる指数的な量子の利点の証拠は、まだ見つかっていないと結論しています（ただし、多項式の高速化は、ありうる）事実［参考資料26］。決め手は、古典の最良の手法（密度汎関数法、結合クラスター法、テンソルネットワーク法など）との比較です
つまずきやすいところ：「シミュレーション」とは、コンピュータの中の模型ではなく…

ふつうの「シミュレーション」は、現象を、数式で書いて、コンピュータで計算することです。量子シミュレーションは、計算に使う部品そのものが量子的な系で、「系の振る舞いを、似た量子系で再現する」ことです。たとえの限界：どんな量子系でも、量子コンピュータで速く模擬できるわけではなく、問題の性質（古典の近似法が使える範囲か）によって、利点が変わります（本記事による解説。『量子化学・材料シミュレーション』編）。

8. どの問題で速くなり、どの問題で速くならないか

ここまでの例から、量子アルゴリズムの高速化は、種類で整理できます。Montanaro の総説は、量子アルゴリズムを、高速化の大きさ（指数的、2乗、小さな多項式など）ごとに整理しています事実［参考資料2］。Dalzell らの総説は、応用ごとに、技術的な注意点（誤り訂正を含めた全体の計算量など）を整理しています事実［参考資料27］。

速さの種類の地図：どの問題で、どれくらい速くなるか（概念図） 指数的（超多項式） Shor（因数分解・離散対数）、量子系のシミュレーション（問題による） 理論：示されている／実機：小規模のみ／実用規模：誤り訂正が必要 2乗（√ になる） Grover 探索、振幅増幅、その応用（量子モンテカルロなど） 理論：最適と示されている／誤り訂正の負担で得にならない場合がある 「オラクル」でだけ示された差 Deutsch–Jozsa（決定的な古典に対してのみ）、Simon、Bernstein–Vazirani アルゴリズムの仕組みを学ぶ最小の例。実用の速さの証明ではない 条件つき・示されていない 線形方程式（HHL）と機械学習、NP完全問題の一般解法、大量データの入出力 入出力・古典側の対抗（Tang 2019）などの条件を確認。NP 全体は 2乗根まで ※ 緑→赤の順に「実用的な高速化の見込み」が弱くなる、という整理ではありません。種類と、実用性は別です（第9章）。 ※ 根拠：参考資料2・3・4・29・30・14（Montanaro、Zoo、Bennett ら、Aaronson、Tang、Babbush ら）
図9　概念図（ベクター作図）。量子アルゴリズムの速さの種類と、実用性の確認状況の地図（概念図）。それぞれの高速化は、理論上の評価、または「オラクル」での評価で、実機で確認された実用的な高速化ではありません。
問題の種類高速化の種類（理論上）注意点
因数分解・離散対数（Shor）超多項式（古典で知られた最良の方法に対して、桁違い）［3］実用規模は、誤り訂正のある大きな装置が必要（第9章）
量子系のシミュレーション問題による。多項式の高速化は期待できるが、化学全般の指数的な利点の証拠は未確認［26］古典の最良手法との比較が決め手
構造のない探索（Grover）2乗（√N）。これ以上は減らせない［13・4］誤り訂正の負担で得にならない場合がある［14］
一般の難問（NP完全問題など）オラクルに対しては、総当たりの2乗根まで（2n/2 未満にはできない）［4］NP 全体が量子の多項式時間で解けるかは、未解決の問い
線形方程式・機械学習（HHL など）条件つきで超多項式（Harrow ら、2009）［28］Aaronson は、入力の読み込み、出力の読み出し、条件数などの細部（fine print）を確認する必要があると述べる［29］。Tang（2019）は、推薦システムについて、古典のアルゴリズムで同様の速さを達成した［30］
日常の計算（表計算・文書・動画・Web）量子にする利点は、一般にない量子コンピュータは、置き換えではなく、特定の問題を速く解く別種の機械（基礎編）

整理は本記事の解説です（根拠：参考資料2・3・4・14・28・29・30）。計算量の表記（Õ など）は、対数の因子を無視した目安です。

よくある誤解：「量子コンピュータは、NP 完全問題（最適化・組合せ問題）をすべて速く解く」は誤り

NP 完全問題は、多数の候補から最良のものを選ぶ最適化・組合せ問題の多くを含みます。しかし、Bennett らは、乱数で選んだオラクルに対して、NP のクラスが、2n/2 より速い量子時間では解けない（確率1で）ことを示しています事実［参考資料4］。つまり、一般的な最適化問題では、量子でも、総当たりの2乗根程度の高速化が上限と考えられています（オラクルに対する結果で、すべての具体的な問題に当てはまる証明ではありません）。個別の問題に特有の構造を使えば、別の高速化がありうるかどうかは、問題ごとの研究課題です（本記事による解説）。

つまずきやすいところ：「機械学習が量子で速くなる」という話の読み方

「量子で機械学習が指数的に速くなる」という期待は、HHL などのアルゴリズムから生まれました。しかし Aaronson は、入力データを量子状態に読み込むコストや、結果の取り出し方などの細部を確認しないと、実際の高速化は分からない、と指摘しています［参考資料29］。また Tang は、そのうちの推薦システムの問題で、古典のアルゴリズムが同等の速さを達成できることを示しました［参考資料30］。「量子で速い」という主張は、入出力を含めた全体と、古典の最良手法との比較で読む必要があります。AI 材料探索は、本シリーズ『マテリアルインフォマティクス』編で扱います（本記事による解説）。

9. 理論上の話と、実機での話

量子アルゴリズムの話を読むときに、いちばん大切なのは、「理論上こうなる」と「実機でこうなった」を区別することです。理論上の高速化は、誤りのない（または誤り訂正された）大きな装置と、オラクルなどの理想化を前提にします。実機は、いまのところ、小さく、ノイズがあります。次の表は、本稿が確認した範囲で、両者を並べたものです。

アルゴリズム・課題理論上の話実機・実験での話注意
Deutsch・Deutsch–Jozsa・Simonオラクルを使った問題での差。Deutsch–Jozsa の指数的な差は、決定的な古典に対してだけ［3］本稿では、実機の実演の一次情報を確認していない教材としての最小の例で、実用の速さの証明ではない
Grover の探索回数は √N で、最適［13・4］本稿では、実機の実演の一次情報を確認していない誤り訂正の負担で得にならない場合がある［14］
Shor の因数分解桁数のおおよそ3乗の時間［3］。RSA-2048 の資源推定：2000万個の物理量子ビットで約8時間（2019・2021）、100万個未満で1週間未満（2025）［31・6］N = 15 の実演（2001、核磁気共鳴、7個の核スピン）［16］。多くの小規模な実演は、答えを先に知っていることに頼った簡略化を使った［17］資源推定は、仮定つきの理論上の推定（未確定／将来）
位相推定・量子シミュレーションFeMoco などの資源推定［24・25］。化学全般の指数的な利点の証拠は未確認［26］小さな分子と磁性モデルの変分計算（最大6量子ビット、BeH2 まで）［22］。シリコンスピンでの分子のエネルギー［23］実機の結果は、小規模。古典の最良手法との比較が決め手
ランダム回路サンプリング・ユーティリティ実験—（アルゴリズムではなく、装置の力を測る課題）Google は2019年に、53量子ビットで約200秒、古典で約1万年と見積もったと報告した（企業の主張）［32］。Pan らは、古典のテンソルネットワーク法で、同じ課題を512個の GPU で約15時間で解いたと報告［33］。IBM の研究チームは2023年に、ノイズのある127量子ビットの装置で、力ずくの古典計算の及ばない規模の回路の期待値を測れたとして、ユーティリティ（実用性）の証拠だと主張した（企業の主張）［34］。Tindall らは、その実験を、テンソルネットワークの古典シミュレーションが、量子プロセッサの結果より正確に再現した、と報告［35］主張と再評価を並べて読む。詳しくは本シリーズ『量子優位性の読み方』編

事実（各論文の要旨の記載）。表の整理は本稿の解説です。「確認していない」は、本稿の調査範囲で、一次情報から確認できなかったものです。

Shor の資源推定：どれだけの規模が必要と見積もられているか

Gidney と Ekerå（2019年に arXiv、2021年に Quantum 誌）は、2048ビットの RSA の整数を、2000万個のノイズのある量子ビットで、8時間で因数分解できると推定しました。Gidney（2025）は、同じ仮定のまま、100万個未満の量子ビットで、1週間未満に減らせると推定しました（近似的な剰余算術、誤り訂正の符号の工夫、魔法状態の作り方の改善などによる）事実［参考資料31・6］。

資源推定（理論）と、実験で動いている規模：物理量子ビットの数（対数目盛） 10 10² 10³ 10⁴ 10⁵ 10⁶ 10⁷ 誤り訂正の実験機：101量子ビット Google Quantum AI（2024）。距離7の表面符号 101 RSA-2048 の推定（2025） 100万個未満・1週間未満（Gidney） < 1,000,000 RSA-2048 の推定（2019・2021） 2000万個・8時間（Gidney と Ekerå） 20,000,000 推定の前提（どちらも同じ）： ・量子ビットは格子状に並び、隣どうしだけ接続　・物理ゲートの誤り率は一律 0.1%（10⁻³） ・表面符号の1周期は 1 µs　・制御系の反応時間は 10 µs ・これらは「推定」で、将来の予測ではない。誤り率・符号・設計が変われば数字は変わる ※ 実験の 101 は誤り訂正の実験機の量子ビット数で、推定の「数百万個」は誤り訂正つきの Shor 用です。目的が違い、直接の比較ではありません。
図10　概念図（ベクター作図）。Shor のアルゴリズムで RSA-2048 を因数分解するための資源推定（Gidney と Ekerå、2021；Gidney、2025）と、誤り訂正の実験機の規模（Google Quantum AI、2024）の概念図。推定は仮定つきの理論で、攻撃の時期の予測ではありません。
  • 仮定：量子ビットが格子状に並び、隣どうしだけが接続される。物理ゲートの誤り率は一律0.1%。表面符号の1周期は1 µs。制御系の反応時間は10 µs。（超伝導の量子ビットを念頭においた「もっともらしい」仮定として、Gidney と Ekerå が述べている）
  • 実験との差：誤り訂正の実験機（Google Quantum AI、2024）は、距離7の表面符号で101量子ビットです事実［参考資料5］。推定の「100万個未満」は、その1万倍弱、「2000万個」は約20万倍です本稿の計算（約9,900倍と約198,000倍）
  • この推定は、「いつ暗号が破られるか」の予測ではありません。誤り率、符号、アルゴリズムの工夫が変われば数字は変わります（2019年の推定から2025年の推定で、必要な量子ビット数は20分の1未満になりました）。「何年に実現する」とは、書けません
DARPA の量子ベンチマーク計画（QBI）：「2033年」は目標

DARPA の QBI は、「2033年までに、産業的に有用な量子コンピュータを作ることが可能かどうか」を判定する計画で、どの方式であれ、「計算の価値が費用を上回る」実用規模（ユーティリティ・スケール）に到達できるかを、厳密に検証する、としています（DARPA の公式ページ。確認日 2026年10月16日）事実／未確定／将来［参考資料36］。これは、国の評価プログラムの目標で、達成の保証ではありません。

10. 素材技術者の視点：アルゴリズムの要求と、材料・装置

アルゴリズムが要求する「規模」と「質」は、そのまま、材料と装置への要求に翻訳されます。この章では、素材の側から、アルゴリズムを読み直します。

材料（触媒）と分子のシミュレーションを結びつける場面のイメージです。量子シミュレーションの対象は、このような材料の電子の振る舞いです。実際の施設・製品・計算結果を示すものではありません。
図11　概念画像（ImageGen生成）。材料（触媒）と分子のシミュレーションを結びつける場面のイメージです。量子シミュレーションの対象は、このような材料の電子の振る舞いです。実際の施設・製品・計算結果を示すものではありません。 実際の製品・施設・寸法・測定結果ではありません。拡大模型と実物スケールの場面は区別してください。
素材技術者の視点①：材料シミュレーションに、量子コンピュータが「いつ、どこで」効くのか

触媒、電池材料、磁性体、超伝導体などの材料の性質は、電子の量子的な振る舞いで決まります。量子シミュレーションは、これを直接扱う手法として期待されます。ところが、評価は慎重です。Lee らは、基底状態のエネルギーについて、化学の全般にわたって、指数的な量子の利点の証拠は、まだ見つかっていないと結論しています事実［参考資料26］。資源推定は、FeMoco のような特定の対象で示されていますが、実機の結果は、小さな分子にとどまります［参考資料24・25・22］。

素材から見ると、古典の最良の手法（密度汎関数法など）で十分な問題と、そうでない問題（電子の相関が強い遷移金属の触媒、強相関の磁性体・超伝導体など）を見分けることが、量子コンピュータを材料に使う入口です（本記事による解説。AI を使った材料探索は、本シリーズ『マテリアルインフォマティクス』編、量子化学は『量子化学・材料シミュレーション』編で扱います）。

素材技術者の視点②：アルゴリズムの「回数」が、必要な「誤り率」を決める

「コヒーレンスとフィデリティ」編で見たとおり、誤りを訂正しないとき、約 1/ε 回のゲートで、成功確率は約37%まで下がります。これを Grover に当てはめてみましょう。N = 109 の探索では、反復が約24,836回で、1回の反復に、オラクルと折り返しで、仮に100個のゲートが要るとすると、ゲートの総数は約250万個です。誤り訂正なしで、これを成功させるには、1ゲートあたりの誤り率を、約4×10−7 以下にする必要があります本稿の計算（1/250万 ≒ 4×10−7。「100個」は説明用の仮定）。この水準は、第3編で見た報告例（たとえば 10−4〜10−3 の水準）より、はるかに低いです。だから、実用規模のアルゴリズムは、量子誤り訂正を前提にしています［参考資料14・6］。

素材から見ると、誤り訂正は、物理量子ビットを数百万個、同じ質で、並べて制御することを意味します。ジョセフソン接合の周波数のそろえ方（周波数の衝突）、配線とパッケージ、極低温の熱負荷、材料の欠陥のばらつきが、そのまま規模拡大の制約になります（本記事による解説。「量子ゲートと量子回路」編の第10章、『極低温と制御』編、『量子コンピュータの材料と製造』編）。

素材技術者の視点③：「入力」と「出力」の問題：データを量子状態にするコスト

機械学習や線形代数の量子アルゴリズムでは、大量のデータを量子状態として読み込むコスト（入力）と、結果を取り出すコスト（出力）が、全体の速さを左右します。Aaronson は、この点を含む「細部」を確認しないと、本当の高速化は分からない、と述べています事実［参考資料29］。材料の測定データ（スペクトル、顕微鏡像など）を量子コンピュータで解析する、という話を読むときは、データをどう量子状態にするのかを、まず確認してください（本記事による解説）。

11. 評価・標準の読み方

量子アルゴリズムの「性能」は、計算量（回数・ゲート数の増え方）、必要な資源の推定（物理・論理量子ビットの数、時間）、実機での実行結果の3つの層で読みます。それぞれ、測り方が違い、標準もほとんどありません。ここでは、確認できた範囲で表にします（確認日 2026年10月16日）。

評価項目代表的なベンチマーク・評価手法（名称・出典）標準・指針（NIST・ISO/IEC・IEEE など）読み方の注意
アルゴリズムの理論的な速さ計算量（クエリ回数、ゲート数）の解析。Montanaro の総説［2］、Dalzell らの総説（誤り訂正を含めた全体の計算量）［27］、Quantum Algorithm Zoo［3］事実確認できなかった（標準はない）漸近的な評価で、定数倍や、誤り訂正の負担を含まないことが多い［14］
必要な資源の推定Gidney と Ekerå（2021）、Gidney（2025）、Reiher ら（2017）、Lee ら（2021）［31・6・24・25］事実確認できなかった仮定（誤り率、符号、接続、時間）つきの推定。予測ではない未確定／将来
実機での実行小規模な実演（Vandersypen ら、Kandala ら、Xue ら）［16・22・23］。古典の再評価（Pan ら、Tindall ら）［33・35］事実確認できなかった簡略化（答えを先に知っている）に注意［17］。企業の主張と古典の再評価を並べて読む
アプリケーション指向の性能アプリケーション指向のベンチマーク（Lubinski ら、2023）［37］事実／DARPA QBI（実用規模の検証計画。2033年を目標としている）［36］未確定／将来確認できなかった（IEEE P7131 は性能指標の標準化を扱う作業部会が活動中で、発行済みの標準は確認できなかった）［38］QBI は国の評価プログラムで、標準ではない。目標年は、保証ではない
暗号への影響（Shor に備える標準）—（評価ではなく、移行の標準・指針）NIST FIPS 203（Module-Lattice-Based Key-Encapsulation Mechanism Standard）、FIPS 204（Module-Lattice-Based Digital Signature Standard）、FIPS 205（Stateless Hash-Based Digital Signature Standard）：いずれも2024年8月13日に確定［39・40・41］事実／NIST IR 8547（Transition to Post-Quantum Cryptography Standards）：初版の公開草案は2024年11月12日。最終版は確認日時点で確認できなかった［42］未確定／将来標準・指針の存在の説明にとどめる。暗号が破られる時期は、確実には予測できない。耐量子暗号は、本シリーズ『耐量子計算機暗号』『耐量子暗号への移行』編
用語—（評価ではなく用語）ISO/IEC 4879:2024 "Information technology — Quantum computing — Vocabulary"（第1版、2024年5月、IEC/ISO JTC 3）［43］事実／IEEE P7130 "Standard for Quantum Technologies Definitions"（IEEE のページでは策定中の Active PAR。PAR 承認は2021年9月23日）［44］未確定／将来用語集で、性能の合否を決める規格ではない。規格の本文は未確認で、定義の中身は書いていない

表の整理は本稿の計算（整理）。NIST の番号・題名・日付は NIST CSRC の公式ページ、ISO の番号・題名・発行年月は ISO の委員会ページ、IEEE の状態は IEEE SA のページで確認（確認日 2026年10月16日）。規格の本文は有料または未確認のため、題名・適用範囲の記載にとどめています。

読み方の注意（素材技術者向け）

  • 「速くなる」は、種類と条件つきで読みます：指数的か、2乗か、オラクルだけか。誤り訂正の負担、入出力のコスト、古典の最良手法との比較を、確認してください
  • 資源推定は、予測ではありません：仮定（誤り率0.1%、表面符号の1周期1 µs など）が変われば、数字は変わります。「何年に暗号が破られる」とは、書けません
  • 実機の実演と、企業の主張は、再評価と並べて読みます：古典の手法の進歩で、「古典で不可能」とされた課題が、古典で解かれることがあります［参考資料33・35］
  • 標準は、推奨か要求かを確認します：NIST の FIPS は、連邦政府の標準（暗号の方式の標準）で、量子アルゴリズムの性能の標準ではありません。ISO/IEC 4879 は用語集、IEEE P7130・P7131 は策定中です

12. 用語集

量子アルゴリズム
量子ゲートと測定で、問題を解く手順。干渉で、正解を強める設計。
干渉
波の足し算。正解の波を強め、間違いの波を弱める。量子アルゴリズムの核心。
振幅
確率の元になる数（波の高さ）。プラスとマイナスがあり、打ち消し合える。
オラクル
中身を知らない箱として1回の問い合わせと数える約束。当たりかどうかを確かめる箱など。
クエリ（問い合わせ）
オラクルを使う回数。アルゴリズムの速さを数える1つの尺度。
Deutsch の問題
関数が定数か均等かを、1回の問い合わせで判定する最小の例。
Deutsch–Jozsa
入力が n ビットの Deutsch の問題。指数的な差は、決定的な古典に対してだけ。
Grover の探索
構造のない探索を約 √N 回で行うアルゴリズム。2乗の高速化で、最適。
振幅増幅
当たりの波を、折り返しのくり返しで大きくする手法（Grover の一般化）。
Shor のアルゴリズム
因数分解・離散対数を多項式時間で解く。周期の発見に量子フーリエ変換を使う。
周期（位数）
ax を N で割った余りが、くり返す長さ。Shor はこれを見つける。
量子フーリエ変換
周期的なパターンを周波数に変える量子の変換。干渉で周期を取り出す。
量子位相推定
操作 U の固有値（回転の角度）を、読み出しビットと干渉で読み取る部品。
固有状態・固有値
操作をかけても向きが変わらない状態と、そのとき掛かる位相（またはエネルギー）。
ハミルトニアン
系のエネルギーを表す式（演算子）。
量子シミュレーション
量子の系を、量子コンピュータで模擬すること（Feynman）。
変分法（VQE）
古典の最適化と量子回路を組み合わせ、基底状態のエネルギーを探す方法。
HHL
線形方程式を解く量子アルゴリズム。入出力などの条件に注意が必要。
BQP
量子コンピュータが、誤りの確率を小さく抑えて、多項式時間で解ける問題のクラス。
NP完全問題
多数の候補から条件を満たすものを探す、難しい問題の代表。
資源推定
アルゴリズムを実行するのに必要な量子ビットの数と時間を、仮定つきで見積もること。
耐量子暗号（PQC）
量子コンピュータでも破れないと考えられている暗号。NIST が標準を発表。
ユーティリティ
古典の力ずくの計算の及ばない規模で、意味のある結果が得られること。企業の主張として扱う。

13. 参考資料（一次情報）

  1. Cleve R. ほか "Quantum algorithms revisited", Proc. R. Soc. Lond. A 454, 339–354 (1998), DOI 10.1098/rspa.1998.0164 — doi.org/10.1098/rspa.1998.0164
  2. Montanaro A. "Quantum algorithms: an overview", npj Quantum Inf. 2, 15023 (2016), DOI 10.1038/npjqi.2015.23 — doi.org/10.1038/npjqi.2015.23
  3. Jordan S. "Quantum Algorithm Zoo" (catalog of quantum algorithms) （確認日 2026年10月16日） — quantumalgorithmzoo.org
  4. Bennett C. H., Bernstein E., Brassard G., Vazirani U. "Strengths and Weaknesses of Quantum Computing", SIAM J. Comput. 26, 1510–1523 (1997), DOI 10.1137/S0097539796300933 — doi.org/10.1137/S0097539796300933
  5. Google Quantum AI "Quantum error correction below the surface code threshold", Nature 638, 920–926 (2025), DOI 10.1038/s41586-024-08449-y (arXiv:2408.13687) — doi.org/10.1038/s41586-024-08449-y
  6. Gidney C. "How to factor 2048 bit RSA integers with less than a million noisy qubits", arXiv:2505.15917 (2025) — arxiv.org/abs/2505.15917
  7. Deutsch D. "Quantum theory, the Church–Turing principle and the universal quantum computer", Proc. R. Soc. Lond. A 400, 97–117 (1985), DOI 10.1098/rspa.1985.0070 — doi.org/10.1098/rspa.1985.0070
  8. Deutsch D., Jozsa R. "Rapid solution of problems by quantum computation", Proc. R. Soc. Lond. A 439, 553–558 (1992), DOI 10.1098/rspa.1992.0167 — doi.org/10.1098/rspa.1992.0167
  9. Simon D. R. "On the Power of Quantum Computation", SIAM J. Comput. 26, 1474–1483 (1997), DOI 10.1137/S0097539796298637 — doi.org/10.1137/S0097539796298637
  10. Bernstein E., Vazirani U. "Quantum Complexity Theory", SIAM J. Comput. 26, 1411–1473 (1997), DOI 10.1137/S0097539796300921 — doi.org/10.1137/S0097539796300921
  11. Grover L. K. "A fast quantum mechanical algorithm for database search", Proc. 28th ACM STOC, 212–219 (1996), DOI 10.1145/237814.237866 — doi.org/10.1145/237814.237866
  12. Boyer M. ほか "Tight Bounds on Quantum Searching", Fortschr. Phys. 46, 493–505 (1998), arXiv:quant-ph/9605034 — arxiv.org/abs/quant-ph/9605034
  13. Zalka C. "Grover's quantum searching algorithm is optimal", Phys. Rev. A 60, 2746–2751 (1999), DOI 10.1103/PhysRevA.60.2746 — doi.org/10.1103/PhysRevA.60.2746
  14. Babbush R. ほか "Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage", PRX Quantum 2, 010103 (2021), DOI 10.1103/PRXQuantum.2.010103 — doi.org/10.1103/PRXQuantum.2.010103
  15. Shor P. W. "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput. 26, 1484–1509 (1997), DOI 10.1137/S0097539795293172 — doi.org/10.1137/S0097539795293172
  16. Vandersypen L. M. K. ほか "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance", Nature 414, 883–887 (2001), DOI 10.1038/414883a — doi.org/10.1038/414883a
  17. Smolin J. A., Smith G., Vargo A. "Oversimplifying quantum factoring", Nature 499, 163–165 (2013), DOI 10.1038/nature12290 (arXiv:1301.7007 "Pretending to factor large numbers on a quantum computer") — doi.org/10.1038/nature12290
  18. Kitaev A. Yu. "Quantum measurements and the Abelian Stabilizer Problem", arXiv:quant-ph/9511026 (1995) — arxiv.org/abs/quant-ph/9511026
  19. Feynman R. P. "Simulating physics with computers", Int. J. Theor. Phys. 21, 467–488 (1982), DOI 10.1007/BF02650179 — doi.org/10.1007/BF02650179
  20. Lloyd S. "Universal Quantum Simulators", Science 273, 1073–1078 (1996), DOI 10.1126/science.273.5278.1073 — doi.org/10.1126/science.273.5278.1073
  21. Aspuru-Guzik A. ほか "Simulated Quantum Computation of Molecular Energies", Science 309, 1704–1707 (2005), DOI 10.1126/science.1113479 — doi.org/10.1126/science.1113479
  22. Kandala A. ほか "Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets", Nature 549, 242–246 (2017), DOI 10.1038/nature23879 — doi.org/10.1038/nature23879
  23. Xue X. ほか "Quantum logic with spin qubits crossing the surface code threshold", Nature 601, 343–347 (2022), DOI 10.1038/s41586-021-04273-w — doi.org/10.1038/s41586-021-04273-w
  24. Reiher M. ほか "Elucidating reaction mechanisms on quantum computers", Proc. Natl. Acad. Sci. USA 114, 7555–7560 (2017), DOI 10.1073/pnas.1619152114 — doi.org/10.1073/pnas.1619152114
  25. Lee J. ほか "Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction", PRX Quantum 2, 030305 (2021), DOI 10.1103/PRXQuantum.2.030305 — doi.org/10.1103/PRXQuantum.2.030305
  26. Lee S. ほか "Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry", Nat. Commun. 14, 1952 (2023), DOI 10.1038/s41467-023-37587-6 — doi.org/10.1038/s41467-023-37587-6
  27. Dalzell A. M. ほか "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011 (2023); Cambridge University Press (2025) — arxiv.org/abs/2310.03011
  28. Harrow A. W., Hassidim A., Lloyd S. "Quantum Algorithm for Linear Systems of Equations", Phys. Rev. Lett. 103, 150502 (2009), DOI 10.1103/PhysRevLett.103.150502 — doi.org/10.1103/PhysRevLett.103.150502
  29. Aaronson S. "Read the fine print", Nat. Phys. 11, 291–293 (2015), DOI 10.1038/nphys3272 — doi.org/10.1038/nphys3272
  30. Tang E. "A quantum-inspired classical algorithm for recommendation systems", Proc. 51st ACM STOC, 217–228 (2019), DOI 10.1145/3313276.3316310 — doi.org/10.1145/3313276.3316310
  31. Gidney C., Ekerå M. "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", Quantum 5, 433 (2021), DOI 10.22331/q-2021-04-15-433 — doi.org/10.22331/q-2021-04-15-433
  32. Arute F. ほか (Google AI Quantum) "Quantum supremacy using a programmable superconducting processor", Nature 574, 505–510 (2019), DOI 10.1038/s41586-019-1666-5 — doi.org/10.1038/s41586-019-1666-5
  33. Pan F., Chen K., Zhang P. "Solving the Sampling Problem of the Sycamore Quantum Circuits", Phys. Rev. Lett. 129, 090502 (2022), DOI 10.1103/PhysRevLett.129.090502 — doi.org/10.1103/PhysRevLett.129.090502
  34. Kim Y. ほか "Evidence for the utility of quantum computing before fault tolerance", Nature 618, 500–505 (2023), DOI 10.1038/s41586-023-06096-3 — doi.org/10.1038/s41586-023-06096-3
  35. Tindall J. ほか "Efficient Tensor Network Simulation of IBM's Eagle Kicked Ising Experiment", PRX Quantum 5, 010308 (2024), DOI 10.1103/PRXQuantum.5.010308 — doi.org/10.1103/PRXQuantum.5.010308
  36. DARPA "Quantum Benchmarking Initiative (QBI)" （確認日 2026年10月16日） — darpa.mil/research/programs/quantum-benchmarking-initiative
  37. Lubinski T. ほか "Application-Oriented Performance Benchmarks for Quantum Computing", IEEE Trans. Quantum Eng. 4, 1–32 (2023), DOI 10.1109/TQE.2023.3253761 — doi.org/10.1109/TQE.2023.3253761
  38. IEEE SA "Quantum Benchmarking Working Group P7131" （量子コンピューティングの性能指標の標準化の作業部会のページ。確認日 2026年10月16日） — sagroups.ieee.org/7131
  39. NIST "FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard" （2024年8月13日。確認日 2026年10月16日） — csrc.nist.gov/pubs/fips/203/final
  40. NIST "FIPS 204, Module-Lattice-Based Digital Signature Standard" （2024年8月13日。確認日 2026年10月16日） — csrc.nist.gov/pubs/fips/204/final
  41. NIST "FIPS 205, Stateless Hash-Based Digital Signature Standard" （2024年8月13日。確認日 2026年10月16日） — csrc.nist.gov/pubs/fips/205/final
  42. NIST "IR 8547, Transition to Post-Quantum Cryptography Standards" (initial public draft) （初版の公開草案、2024年11月12日。最終版は確認日時点で確認できなかった） — csrc.nist.gov/pubs/ir/8547/ipd
  43. ISO/IEC "ISO/IEC 4879:2024 Information technology — Quantum computing — Vocabulary" （第1版、2024年5月、IEC/ISO JTC 3。ISO の委員会ページで確認） — iso.org/standard/80432.html
  44. IEEE SA "IEEE P7130 Draft Standard for Quantum Technologies Definitions" (project page) （Active PAR、PAR 承認 2021年9月23日。確認日 2026年10月16日） — standards.ieee.org/ieee/7130/10680/

14. 主張と出典の対応表（監査）

本文の主張根拠区分
量子アルゴリズムの共通の型：計算の経路の量子干渉で、正しい結果を強め、誤った結果を抑える。多くのアルゴリズムが位相推定の場合として理解できることCleve ら（1998）の要旨
出典1 https://doi.org/10.1098/rspa.1998.0164		事実
量子アルゴリズムを高速化の大きさ（指数的、2乗など）で整理した総説。応用ごとの技術的注意（誤り訂正を含む全体の計算量）の総説。アルゴリズムの一覧と各高速化の種類Montanaro（2016）、Dalzell ら、Quantum Algorithm Zoo
出典2 https://doi.org/10.1038/npjqi.2015.23
出典27 https://arxiv.org/abs/2310.03011
出典3 https://quantumalgorithmzoo.org		事実
Deutsch の問題が、n = 1 で量子1回・古典決定的2回であること。Deutsch–Jozsa が、確率的には O(1) 回で簡単に解け、速さの差が決定的な古典に対してだけであること。Simon、Bernstein–Vazirani の問題Deutsch（1985）、Deutsch と Jozsa（1992）、Simon、Bernstein と Vazirani の題名・書誌、Quantum Algorithm Zoo
出典7 https://doi.org/10.1098/rspa.1985.0070
出典8 https://doi.org/10.1098/rspa.1992.0167
出典9 https://doi.org/10.1137/S0097539796298637
出典10 https://doi.org/10.1137/S0097539796300921
出典3 https://quantumalgorithmzoo.org		事実
Grover の探索が O(√N) 回で、古典の Ω(N) に対し2乗の高速化であり、最適であること。構造のない探索で、NP が 2^(n/2) 未満の量子時間で解けないこと（オラクルに対して）Grover（1996）、Bennett ら、Boyer ら、Zalka の題名・要旨、Quantum Algorithm Zoo
出典11 https://doi.org/10.1145/237814.237866
出典4 https://doi.org/10.1137/S0097539796300933
出典12 https://arxiv.org/abs/quant-ph/9605034
出典13 https://doi.org/10.1103/PhysRevA.60.2746
出典3 https://quantumalgorithmzoo.org		事実
2乗の高速化は、誤り訂正の定数倍の負担のため、初期の誤り耐性のある装置では量子優位性を生まない（4乗の高速化のほうが実用的に見える）という結論Babbush ら（2021）の要旨
出典14 https://doi.org/10.1103/PRXQuantum.2.010103		事実
Shor の因数分解が多項式時間であること。Õ(n³) と、古典の数体ふるい法 2^Õ(n^(1/3))（と信じられている）Shor（1997）の題名、Quantum Algorithm Zoo
出典15 https://doi.org/10.1137/S0097539795293172
出典3 https://quantumalgorithmzoo.org		事実
N = 15 の核磁気共鳴での因数分解（7個の核スピン、2001年）と、多くの小規模な実演が答えを先に知っていることに頼った簡略化であること。難しさの尺度は周期の長さであることVandersypen ら（2001）、Smolin ら（2013）の要旨
出典16 https://doi.org/10.1038/414883a
出典17 https://doi.org/10.1038/nature12290		事実
量子位相推定の定式化と、アルゴリズムとの関係Kitaev（1995）、Cleve ら（1998）の要旨
出典18 https://arxiv.org/abs/quant-ph/9511026
出典1 https://doi.org/10.1098/rspa.1998.0164		事実
量子シミュレーションの考え方（Feynman、Lloyd、Aspuru-Guzik ら）。実機の小規模な例（最大6量子ビット、BeH2 まで。シリコンスピンでの分子のエネルギー）各論文の題名・要旨
出典19 https://doi.org/10.1007/BF02650179
出典20 https://doi.org/10.1126/science.273.5278.1073
出典21 https://doi.org/10.1126/science.1113479
出典22 https://doi.org/10.1038/nature23879
出典23 https://doi.org/10.1038/s41586-021-04273-w		事実
FeMoco などの資源推定（理論上の推定）。化学の基底状態エネルギーで、指数的な量子の利点の証拠はまだ見つかっていないという評価Reiher ら（2017）、Lee ら（2021・2023）の要旨
出典24 https://doi.org/10.1073/pnas.1619152114
出典25 https://doi.org/10.1103/PRXQuantum.2.030305
出典26 https://doi.org/10.1038/s41467-023-37587-6		事実
HHL の超多項式の高速化の提案。入出力などの細部の確認が必要であること。推薦システムの問題で古典のアルゴリズムが同様の速さを達成したことHarrow ら（2009）の題名、Aaronson（2015）、Tang（2019）
出典28 https://doi.org/10.1103/PhysRevLett.103.150502
出典29 https://doi.org/10.1038/nphys3272
出典30 https://doi.org/10.1145/3313276.3316310		事実
RSA-2048 の資源推定：2000万個の量子ビットで8時間（2019・2021）、100万個未満で1週間未満（2025）。仮定は、格子状の接続、誤り率0.1%、表面符号の1周期1 µs、反応時間10 µsGidney と Ekerå（2021）、Gidney（2025）の要旨
出典31 https://doi.org/10.22331/q-2021-04-15-433
出典6 https://arxiv.org/abs/2505.15917		事実
誤り訂正の実験機：距離7の表面符号、101量子ビット（企業の報告）Google Quantum AI（2024・2025）の要旨
出典5 https://doi.org/10.1038/s41586-024-08449-y		事実
ランダム回路サンプリングの企業の主張（約200秒対約1万年の見積り）と、古典の再評価（512 GPU・約15時間）。ユーティリティの主張と、テンソルネットワークによる古典シミュレーションArute ら（2019）、Pan ら（2022）、Kim ら（2023）、Tindall ら（2024）の要旨
出典32 https://doi.org/10.1038/s41586-019-1666-5
出典33 https://doi.org/10.1103/PhysRevLett.129.090502
出典34 https://doi.org/10.1038/s41586-023-06096-3
出典35 https://doi.org/10.1103/PRXQuantum.5.010308		事実
DARPA QBI が、2033年までに産業的に有用な量子コンピュータが可能かを検証する計画であること（国の評価プログラムの目標）DARPA の公式ページ（確認日 2026年10月16日）
出典36 https://www.darpa.mil/research/programs/quantum-benchmarking-initiative		未確定／将来
アプリケーション指向のベンチマークの提案。IEEE P7131 の作業部会が活動し、発行済みの標準は確認できなかったことLubinski ら（2023）の題名、IEEE SA のページ
出典37 https://doi.org/10.1109/TQE.2023.3253761
出典38 https://sagroups.ieee.org/7131		未確定／将来
NIST FIPS 203・204・205 が2024年8月13日に確定したこと（題名）。NIST IR 8547 の初版の公開草案が2024年11月12日であること（最終版は確認できなかった）NIST CSRC の公式ページ
出典39 https://csrc.nist.gov/pubs/fips/203/final
出典40 https://csrc.nist.gov/pubs/fips/204/final
出典41 https://csrc.nist.gov/pubs/fips/205/final
出典42 https://csrc.nist.gov/pubs/ir/8547/ipd		事実
ISO/IEC 4879:2024「Information technology — Quantum computing — Vocabulary」（第1版、2024年5月、IEC/ISO JTC 3）の番号・題名・発行年月。IEEE P7130 が策定中（Active PAR、2021年9月23日承認）であることISO の委員会ページ、IEEE SA のページ
出典43 https://www.iso.org/standard/80432.html
出典44 https://standards.ieee.org/ieee/7130/10680/		事実
Deutsch の振幅表（4つの関数）、乱数を使った古典の誤り（n = 20・10回で約0.195%）、Grover の振幅と確率（N = 8）、最適回数の表、N = 15 の周期、64点・128点のフーリエ変換のピーク、位相推定の確率分布（φ = 1/3、4ビット）、Grover の反復と誤り率の概算（約250万ゲート、約4×10⁻⁷）、倍率（9,900倍・198,000倍）本稿の計算（Python・NumPy）。実在の装置の結果ではない。ゲート数の「100個」は説明用の仮定本稿の計算
実機の実演の一次情報（Deutsch・Grover の実機での実行）、ISO/IEC 4879 の定義の本文、IEEE P7131 の発行状態、NIST IR 8547 の最終版は、本稿の調査範囲でアクセスできた一次情報では確認できなかったため記載していない本稿の調査範囲では確認できなかった解説
「並列計算で速いは不正確」「Deutsch–Jozsa は決定的な古典に対してだけ」「Grover は Web 検索を一瞬にしない」「量子は NP 完全問題をすべて速く解くは誤り」などの読み取りと、たとえ話・その限界公表内容にもとづく本記事の整理・解説。各機関が表明した見解ではない解説
図1〜図11が実データの観察ではなく説明のための作図であること。図1と図11がImageGen生成の概念画像であること本記事による注記解説

最終更新：2026年10月16日／出典は一次情報（総説、査読論文、arXiv の論文、Quantum Algorithm Zoo、NIST・DARPA・ISO・IEEE の公式ページ）に限定しています。企業の主張は企業の主張として扱い、古典の再評価がある場合は並べて示しました。 数値例（振幅、確率、回数、周期、位相推定の分布、誤り率の概算）は本稿が作った説明用の計算で、実在の装置の結果ではありません。資源推定は、仮定つきの理論上の推定で、将来の予測ではありません。暗号を破る手順や時期は書いていません。 実機の実演の一次情報の一部、規格の本文、IEEE P7131 の発行状態、NIST IR 8547 の最終版については、確認できなかったため記載していません。 図はすべて説明用の概念図または本稿の計算を含む作図で、図1と図11はImageGen生成の概念画像です。

図版更新：2026年10月17日。本文・出典整理表のベクター作図という表記は、保存した元SVGの由来を示します。現在の主図の形式と読み方は各図下の説明を参照してください。ImageGen画像は実測や実在製品の写真ではなく、元SVG・数値・出典は展開して確認できます。