量子コンピュータのアルゴリズム

量子コンピュータは、古典コンピュータとはまったく異なる原理で動作する。
そのため、同じ問題を解く場合でも、古典計算とは全く別の「量子アルゴリズム」という手法が必要。
量子コンピュータには主に量子ゲート型と量子アニーリング型があるが、
ここでは、量子ゲート型の代表的なアルゴリズムを噛み砕いて整理する。

量子アルゴリズムの基本構造

量子アルゴリズムの多くは、以下のようなステップで構成される。

①初期化

すべての量子ビットを「0」にして準備する。

②重ね合わせの作成

アダマールゲートなどを使い、すべての可能性を同時に表す量子状態にする。

③干渉による絞り込み

正解の可能性を強め、間違いの可能性を弱める操作を繰り返す。

④測定

最終的に測定して、1つの答えを得る。

ブラ-ケット記法

量子コンピュータでは量子ビットは次のような形で記載される。

|0\rangle = 
\begin{pmatrix}
1 \\
0
\end{pmatrix}, \quad
|1\rangle = 
\begin{pmatrix}
0 \\
1
\end{pmatrix}

このように⟩が右向きのものをケットベクトル(列ベクトル)、
逆に以下のように左向きのものをブラベクトル(行ベクトル)と呼ぶ。

\langle 0| = 
\begin{pmatrix}
1 & 0
\end{pmatrix}, \quad
\langle 1| = 
\begin{pmatrix}
0 & 1
\end{pmatrix}

▼代表的な量子アルゴリズム

1. Shorのアルゴリズム（素因数分解）

アルゴリズム

量子フーリエ変換で周期を見つけて、素因数を効率的に求めるイメージ

① 素因数分解したい整数 N を用意

N

② ランダムな整数 a を選ぶ

1 < a < N を満たして、最大公約数 gcd(a, N) = 1 となる整数 a をランダムに選ぶ

gcd(a, N) = 1

もし gcd(a, N) ≠ 1 なら、すぐに N の因数が見つかる(ラッキー)
例：gcd(5, 15) = 5 → すぐに因数 5 がわかる ＝ 互いに素ではない

③ 関数 f(x) を定義

「a を x 回かけた余り」を計算する関数を用意する

f(x) = a^x mod N

この関数の、 f(x+r) = f(x) が成り立つ周期 r (位数とも言うらしい)を見つける

例：N=15, a=2の時、
　　f(1)=2, f(2)=4, f(3)=8, f(4)=1, f(5)=2,... という周期になる

④ 量子ビットを用意して重ね合わせ状態を作る

「x の候補」を全部同時に調べられるように、量子コンピュータの「重ね合わせの状態」を利用する

(\frac{1}{\sqrt{Q}}) * \sum_{x=0}^{Q-1} |x⟩ |0⟩

上段レジスタ( |x⟩ の前の部分)に x の重ね合わせ状態を格納

⑤ f(x) を計算して下段レジスタに格納

下段レジスタ( |x⟩ の後の部分)に③のf(x)が入る

(\frac{1}{\sqrt{Q}}) * \sum_{x=0}^{Q-1} |x⟩ |f(x)⟩

ここで全部の x に対して 同時並行で計算される(量子並列性)

⑥ 下段レジスタを測定して状態を固定

f(x)の方を測定してしまうと、値は1つに決まる

これにより、上段レジスタに残った x の候補は「その値を出す周期的な x たち」だけに絞られる(周期 r の整数倍の重ね合わせになる)

⑦ 量子フーリエ変換 (QFT) を上段に適用

|x⟩ -> \frac{1}{\sqrt{Q}} * \sum_{y=0}^{Q-1} exp(\frac{2π i x y }{Q}) |y⟩

上段レジスタに QFT をかけると、「その周期 r がどれくらいの間隔か」という情報が振幅に変換される

測定すると、周期 r を推測できる整数 y が得られる

⑧ 周期 r から因数を計算

y と、計算で使った全体の大きさ Q（だいたい N² より少し大きい）を組み合わせると、
「 y / Q ≈ k / r 」という関係が成り立つ
ここで「分数の近似（連分数展開）」という技を使って、 r を求める
→簡単に言うと、この数字は分母がいくつの分数に近いか？を探す

r が偶数なら、因数は次で求まる

factor = gcd(a^{r/2} ± 1, N)

もし奇数なら、別の a を選んで②からやり直し

⑨ 因数を出力

これで N の素因数が求まる

何をするアルゴリズムか

大きな整数を素数に分解する（素因数分解）ための量子アルゴリズム。

すごい理由

古典コンピュータでは非常に時間がかかる素因数分解を、量子コンピュータなら指数関数的に高速化できる。
理論値では、古典計算で24時間かかる規模の素因数分解が、量子計算では数分〜数秒で終わる。

用途

RSA暗号の解読など（暗号の安全性、発展に直結）。

イメージ

2つの鍵を同時に差し込まないと開かない金庫がある。
目の前には100本の鍵があり、ヒントは「正しい2本の鍵を同時に振って鳴らしたときの金属音」だけ。

▼古典コンピュータ
「まず1本目を選んで…2本目を片っ端から合わせてみよう。
うーん、C(100, 2) = 4,950通りあるから時間かかるな…」

▼量子コンピュータ
「金属音のパターンから、2本の鍵それぞれの“固有の音色”を一瞬で解析できる。
だから全部のペアを試さなくても、計算だけで正しい2本を特定できる」

2. Groverのアルゴリズム（探索）

アルゴリズム

解の振幅の山を反復で押し上げていくイメージ

① 全ての状態の重ね合わせ状態を初期状態とする

|s⟩ = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x⟩

② Oracle（答えを反転）を適用

入力が解であるときだけ反転させることで、解の状態とそれ以外の状態との間に位相の差が生まれ、解の振幅を増幅しやすくする

U_f |x⟩ = 
\begin{cases}
-|x⟩, & \text{if } x \text{ is the solution} \\
|x⟩, & \text{otherwise}
\end{cases}

③ 拡散演算（平均反転）を適用

全ての状態の重ね合わせ |s⟩ を対象軸に反転を行う
これにより全体の平均を基準にして振幅を反転させ、解の振幅を増幅する

D = 2|s⟩⟨s| - I

④ Grover 反復

②③を繰り返す。

G = D U_f

反復回数 r はおおよそ：

r \approx \frac{\pi}{4} \sqrt{N}

⑤ 答えの測定

反復後、測定するとほぼ答えの状態

|x_\text{sol}⟩

が得られる

何をするアルゴリズムか

たくさんの選択肢から、特定の条件に合う答えを探す。

すごい理由

古典計算ではO(N)かかる探索が、量子計算では O(√N) に短縮できる。
例えば、古典計算で24時間かかる総当たり探索が、量子計算では約2時間で済む。

用途

データベース検索、最適化問題の一部、暗号の総当たり攻撃の高速化。

イメージ

同じような形の100個の鍵の中から、鍵穴に合致する鍵を1個見つけなければならない。

▼古典コンピュータ
「1個ずつ順番に試していくか。50回くらい試したら合うやろ」
※期待試行回数は𝔼[K]=(1+100)/2=50.5(回)

▼量子コンピュータ
「鍵の形を大体覚えているから、目星をつけた鍵を選んで8回くらい試したら当てられる自信があります」

3. 量子フーリエ変換（QFT）

何をするアルゴリズムか

古典のフーリエ変換を量子計算で行う。

すごい理由

古典ではO(n·2ⁿ)かかる場合がある処理を、量子計算では O(n²) で行える。
例えば古典で24時間かかる周期検出が、量子計算では数秒で可能。

用途

Shorのアルゴリズムなどの基盤技術、波の解析、周期性の検出。

イメージ

「音楽の耳コピ職人の究極版」

4. 量子位相推定（QPE）

何をするアルゴリズムか

ある量子状態の“位相”を高精度で推定する。

すごい理由

分子シミュレーションや量子化学計算の基盤となる膨大な試行が必要な計算を、効率的に実行可能。
例えば古典で24時間かかる分子エネルギーの計算が、量子計算では数分で完了。

用途

エネルギー準位の計算、化学反応シミュレーション。

イメージ

「ギターの弦を弾いたとき、耳で「これは A の音だな」と判別する絶対音感」

---

アルゴリズム	古典計算の複雑度	量子計算の複雑度	古典での例	量子での例	主な用途
Shor	指数時間	多項式時間O((logN)3)	24時間	数秒〜数分	素因数分解、暗号解読
Grover	O(N)	O(√N)	24時間	約2時間	検索、最適化
QFT	O(n·2ⁿ)	O(n²)	24時間	数秒	周期検出、信号処理
QPE	高コスト	高効率	24時間	数分	シミュレーション

※ここでは量子ゲート方式についてアルゴリズムを挙げたが、量子アニーリング方式ではQUBOやイジングモデルといった数式が用いられる

現在の課題と展望

これらのアルゴリズムは理論的には強力だが、実機ではまだ大規模に動かせない。
エラー率の高さや量子ビット数の不足がボトルネック。
ただし、量子ハードウェアが進化すれば、暗号解読や科学シミュレーションの分野で大きなブレイクスルーが期待される。

次回は、実際に「量子アルゴリズムを動かすプログラミング」について触れていく。