レッスン3：量子ゲートと量子回路——Bell 状態から Grover・Shor まで

このレッスンで学ぶこと

量子ゲートの概念と、古典論理ゲートとの違いを整理できる
Hadamard・Pauli・CNOT ゲートの基本動作を説明できる
Deutsch アルゴリズム 1985 の意義を語れる
Grover アルゴリズム 1996 が探索問題を √N 加速する直感的な意味を理解できる
Shor アルゴリズム 1994 が素因数分解を指数加速する直感的な意味を語れる

前のレッスンでは、qubit・重ね合わせ・もつれの 2 本柱を扱いました。このレッスンでは、それらを操作する量子ゲートと、それを組み合わせた量子回路を扱います。3 つの代表的なアルゴリズム（Deutsch、Grover、Shor）を直感的なイメージで整理します。

量子ゲートとは何か

古典コンピュータは NOT・AND・OR などの論理ゲートの組み合わせで計算します。量子コンピュータも同様に「量子ゲート」の組み合わせで計算しますが、量子ゲートは以下の 3 つの特徴を持ちます。

可逆：入力と出力が 1 対 1 対応し、逆演算が必ず存在する（古典 AND ゲートは可逆でない）
ユニタリ変換：ブロッホ球上の状態を「回転」させる操作として表現できる
線形性：重ね合わせ状態にゲートを作用させると、各成分に同時に作用する

これらの制約により、量子回路の設計は古典論理回路と根本的に発想が異なります。

Hadamard・Pauli・CNOT ゲート——3 大基本ゲート

量子回路で最も頻繁に使われる 3 種のゲートを押さえます。

Hadamard ゲート（H ゲート）

|0⟩ を (|0⟩ + |1⟩) / √2 に、|1⟩ を (|0⟩ - |1⟩) / √2 に変換します。「決定的な状態から重ね合わせを作る」ゲートで、ほぼすべての量子アルゴリズムの最初に使われます。ブロッホ球上では、北極（|0⟩）を赤道に移す回転として理解できます。

Pauli ゲート（X, Y, Z ゲート）

X ゲート：|0⟩ と |1⟩ を入れ替える（古典 NOT に対応）
Y ゲート：ブロッホ球の Y 軸周りの 180 度回転
Z ゲート：|0⟩ はそのまま、|1⟩ に -1 の位相をかける

これら 3 つは、qubit 1 つに作用する基本的な操作で、量子回路の構成要素として頻繁に使われます。

CNOT ゲート（Controlled-NOT）

2 qubit ゲートで、制御 qubit が |1⟩ のとき標的 qubit を反転させる（|0⟩ ↔ |1⟩）操作です。CNOT ゲートともつれ生成の関係が深く、Hadamard + CNOT の組み合わせでベル状態を作れます。

flowchart LR
  A[初期状態<br/>|00⟩] --> B[Hadamard を<br/>1 qubit 目に]
  B --> C[(|00⟩ + |10⟩) / √2]
  C --> D[CNOT<br/>制御 qubit 1<br/>標的 qubit 2]
  D --> E[Bell 状態<br/>(|00⟩ + |11⟩) / √2]

Hadamard + CNOT の 2 段組みが「ベル状態を作る最短の回路」で、量子計算の入門で必ず出てくる構成です。

Deutsch アルゴリズム——1985 年、最初の量子アルゴリズム

David Deutsch が 1985 年に発表した Deutsch アルゴリズムは、量子コンピュータが古典コンピュータより高速に解ける最初の問題を示しました。「ある 1 ビット入力・1 ビット出力の関数 f が、定数関数か均衡関数かを判定する」問題で、古典では f を 2 回呼び出す必要があるところ、量子では 1 回の呼び出しで判定できます。

Deutsch アルゴリズム自体は実用性のあるものではありませんが、「量子コンピュータが古典より本質的に速い問題が存在する」ことを初めて示した意義があります。この論文が、以降 40 年の量子コンピュータ研究の起点になりました。

Grover アルゴリズム——1996 年、√N 加速の探索

Lov Grover が 1996 年に発表した Grover アルゴリズムは、「N 個の要素から特定の要素を探す」問題を古典より √N 倍高速に解けます。古典では平均 N/2 回の試行が必要な問題（例：無秩序な電話帳から名前で電話番号を探す）を、量子では √N 回で解けます。

Grover の直感的な動作

すべての要素を重ね合わせで表現（Hadamard を全 qubit にかける）
探したい要素の振幅を「増幅」する操作（Grover Operator）を √N 回繰り返す
観測すると、探したい要素が確率高く得られる

Grover アルゴリズムは「探索問題を √N 加速する」量子コンピュータの代表例で、以下の応用可能性があります。

暗号解読の一部：AES など対称鍵暗号のブルートフォース探索の高速化
データベース検索：無秩序なデータからの高速検索
組合せ最適化の一部：候補群から最適解を探す用途

ただし、√N 倍加速は「指数加速」ではなく「多項式加速」で、Shor ほどの衝撃的な効果はありません。実用化には量子誤り訂正が整備された FTQC の登場が前提です。

Shor アルゴリズム——1994 年、素因数分解の指数加速

Peter Shor が 1994 年に発表した Shor アルゴリズムは、「大きな整数の素因数分解を、古典コンピュータより指数関数的に高速に解く」ことができます。素因数分解の困難性は RSA 暗号の安全性の基礎になっているため、Shor アルゴリズムの完成は「現在の RSA が使えなくなる」ことを意味します。

Shor の直感的な動作

Shor アルゴリズムの内部構造は複雑ですが、要点は「素因数分解を『関数の周期を見つける問題』に変換し、その周期を量子フーリエ変換で高速に検出する」ことです。量子フーリエ変換（QFT、Quantum Fourier Transform）が量子コンピュータで指数的に高速に実行できるため、素因数分解も指数加速できます。

Shor の実用化には何が必要か

Shor アルゴリズムで 2048 ビット RSA を破るには、数百万 qubit と量子誤り訂正が必要と推定されます。2026 年 7 月時点で最大の量子コンピュータでも 1,000-2,000 qubit 程度、しかも誤り訂正なし（NISQ）です。実用化までには 10 年以上の技術進歩が必要という見方が主流ですが、正確な時期は業界プレイヤーによって幅があります。

⚠️ 注意 Shor アルゴリズムの実用化時期は「今すぐ」ではありませんが、「Harvest Now, Decrypt Later（今収穫、あとで復号）」という攻撃モデルがあります。攻撃者が今の RSA 暗号化通信を盗聴・保管し、将来 Shor アルゴリズムが実用化した時点で復号する、というシナリオです。長期的な機密性が必要な情報（政府機密、企業の長期戦略、個人の医療情報など）は、今から PQC（耐量子暗号）への移行を計画するのが定石です。PQC の詳細は既刊のクラウド系入門コースを参照してください。

Deutsch・Grover・Shor の比較

3 つのアルゴリズムの位置づけを整理します。

アルゴリズム	発表年	解く問題	加速度	実用性
Deutsch	1985	関数の判定	2 → 1 呼び出し	実用性はない（歴史的意義）
Grover	1996	探索問題	√N 倍加速	探索・組合せ最適化の一部
Shor	1994	素因数分解	指数加速	暗号解読（RSA/ECC）

Shor が「暗号世界の 30 年の再設計」を促し、Grover が「探索と最適化」の道具になる可能性があり、Deutsch が「量子で本質的に速い問題が存在する」ことを示した——という位置づけです。

次のレッスンの予告

次のレッスンでは、これらのアルゴリズムを実際に動かすハードウェアを扱います。超伝導（IBM/Google/Rigetti）、イオントラップ（IonQ/Quantinuum）、中性原子（QuEra）、光（PsiQuantum）、量子アニーリング（D-Wave）、国産（理研「叡」2023 年 3 月 27 日クラウド公開の 64 qubit）——6 方式の位置づけと選定軸を比較します。

確認クイズ

理解の定着のために、6 問のクイズを解いてみてください。