第4章: 量子アルゴリズム

ビデオ講義

このビデオは以下のテキストと同じ内容をカバーしています。お好みの学習形式をお選びください。

🌐 JP | 🇬🇧 EN | Last sync: 2026-08-16

第3章でゲートと回路が手に入りました。ここで、本当に重要な問いを立てましょう。それらを使って、古典コンピュータが同じ速さでは計算できない何を計算できるのか、という問いです。本章では、この分野を定義した3つのアルゴリズム — Deutsch–Jozsa、Groverの探索、Shorの素因数分解 — を扱い、さらに同じくらい重要なことを行います。真に指数的な高速化と、単に2乗にすぎない高速化を区別し、さらにその両方を、量子コンピュータが何の優位性ももたらさない非常に広い問題クラスから区別します。この物語の正直な版は誇大宣伝より面白く、量子コンピューティングを実務で評価するつもりなら必要になるのはこちらの版です。

4.1 オラクルとクエリ計算量

初期の量子アルゴリズムの多くは クエリモデル（ブラックボックスモデル とも呼ばれます）で述べられます。このモデルでは、中身を調べることのできない関数 \(f\) が与えられ、自分で選んだ入力に対して評価することだけができます。評価を行う装置を オラクル と呼び、アルゴリズムのコストはオラクルの呼び出し回数、すなわち クエリ計算量 で測られます。それ以外（通常のゲート、古典的な後処理）はすべて無料と見なされます。

これは意図的な単純化であり、なぜ有用でどこで誤解を招くのかをはっきりさせておく価値があります。有用なのは、クエリ計算量が厳密に解析できるからです。どんな古典アルゴリズムもある回数より少ないクエリでは済まないことを証明できる場合が多く、これによって「量子の方が速い」という願望が定理に変わります。誤解を招くのは、現実のオラクルが現実のゲートで作られなければならないことを忘れた場合です。回路が巨大なオラクルは、クエリ回数の優位性を丸ごと帳消しにしかねません。

量子オラクルはユニタリでなければならないので、入力を単純に上書きすることはできません。標準的な2つの構成がこれを解決します。

XOR（ビット反転）オラクル は、追加の出力量子ビットを使って答えを可逆的に書き込みます。

\[ U_f |x\rangle |y\rangle = |x\rangle |y \oplus f(x)\rangle \]

2回適用すると元の状態に戻るので、自分自身が逆操作であり、したがってユニタリです。

位相オラクル は、答えを代わりに符号に符号化します。

\[ U_f |x\rangle = (-1)^{f(x)} |x\rangle \]

両者は等価です。XORオラクルの出力量子ビットを状態 \(|-\rangle = (|0\rangle - |1\rangle)/\sqrt{2}\) に準備すると、\(|y \oplus f(x)\rangle\) が因子 \((-1)^{f(x)}\) を拾い、出力量子ビットは変化しないまま切り離せます。この技法は 位相キックバック と呼ばれ、量子アルゴリズム設計で最も繰り返し使われる着想の1つです。位相オラクルは対角行列なので、コードで書き下すのが非常に容易です。4.6節ではまさにこれを使います。

要点は、量子アルゴリズムはすべての入力の 重ね合わせ に対してオラクルに問い合わせられる、ということです。それ自体は何の役にも立ちません。測定はランダムに選ばれた結果を1つしか返さないからです。量子アルゴリズム設計の妙は、クエリの後に来るもの、すなわち誤った答えが打ち消し合い、正しい答えの振幅が増大するように干渉を仕組むことにあります。

4.2 Deutsch–Jozsaアルゴリズム

📚 問題設定

関数 \(f: \{0,1\}^n \to \{0,1\}\) が約束（promise）付きで与えられます。\(f\) は定数（\(2^n\) 個すべての入力で同じ値）であるか、均衡（ちょうど半分の入力で0、残り半分で1を返す）であるかのどちらかです。どちらであるかを確実に判定しなければなりません。

古典的に、確実に判定する場合、最悪ケースでは \(2^{n-1} + 1\) 回のクエリが必要です。\(2^{n-1}\) 回のクエリがすべて同じ値を返した後でも、関数は定数かもしれないし、たまたま調べた範囲すべてで一致した均衡関数かもしれません。もう1回のクエリでそれが決着します。

量子的には、任意の \(n\) に対して1回のクエリで十分です。

📚 回路と直観

アルゴリズムは3ステップです。

\(n\) 個の量子ビットを \(|0\rangle^{\otimes n}\) に準備し、それぞれに \(H\) を適用して一様な重ね合わせ \(\frac{1}{\sqrt{2^n}}\sum_x |x\rangle\) を作る。
位相オラクルを1回だけ適用する: \(\frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle\)。
各量子ビットに再び \(H\) を適用し、すべてを測定する。

答えは次のとおりです。すべての量子ビットが0を返せば \(f\) は定数、そうでなければ均衡です。

なぜうまくいくのでしょうか。最後のHadamardの後に、全ゼロという結果の振幅を見てみましょう。2層目のHadamardは各 \(|x\rangle\) を重ね合わせに写しますが、その中で \(|0\cdots 0\rangle\) は常に同じ係数 \(1/\sqrt{2^n}\) で現れます。したがって最終的な \(|0\cdots 0\rangle\) の振幅は

\[ \alpha_{0\cdots 0} = \frac{1}{2^n}\sum_{x}(-1)^{f(x)} \]

です。\(f\) が定数なら、すべての項が同じ符号を持ち、合計は \(\pm 1\) になります。すなわち結果 \(|0\cdots 0\rangle\) が確率1で得られます。\(f\) が均衡なら、ちょうど半分の項が \(+1\)、半分が \(-1\) なので 厳密に 打ち消し合い、\(|0\cdots 0\rangle\) の確率は0になります。ここでは相殺的干渉が仕事をしており、この分野全体で最も明快な例になっています。

📚 正直な評価

Deutsch–Jozsaは教育用のアルゴリズムであって実用的なものではありません。その理由をはっきり述べておく価値があります。

\(1\) 回対 \(2^{n-1}+1\) 回というクエリ数の差は、決定論的な 古典アルゴリズムに対してのみ成り立ちます。乱択古典アルゴリズムは量子アルゴリズムとほぼ同じ性能を出します。ランダムな入力をいくつかサンプリングし、異なる出力が2つ見つかれば関数は均衡です。同じ出力が \(k\) 回続いたなら、均衡関数がその検査を通り抜ける確率は \(2^{-(k-1)}\) です。21回のランダムなクエリで誤り確率は百万分の1を下回り、これは \(n\) によりません。したがって、わずかな誤り確率を許した途端に、指数的な差は消えてしまいます。

問題そのものも人工的です。定数関数と均衡関数を区別する必要がある人など誰もいません。Deutsch–Jozsaが1990年代初頭に本当に確立したのは、量子と古典のクエリ計算量の間に証明可能な差が そもそも存在する ということでした。それが概念実証となり、人々が実際に関心を持つ問題を解くアルゴリズムの探索を促したのです。そのうちの2つを次に見ていきます。

4.3 Groverのアルゴリズム: 構造なし探索

📚 問題と結果

\(N\) 個の要素があり、任意の要素が求めるものかどうかを判定する手段はあるが、利用できる構造は一切ない — ソートも索引もなく、判定だけがある、という状況を考えます。古典的には、目印の付いた要素を見つけるには平均で約 \(N/2\) 個、最悪で \(N\) 個を調べる必要があり、\(O(N)\) 回のクエリになります。

1996年に発表されたGroverのアルゴリズムは、\(O(\sqrt{N})\) 回のクエリで目印の付いた要素を見つけます。\(N = 10^6\) なら、100万回ではなくおよそ1000回のクエリで済みます。

📚 振幅増幅

アルゴリズムは一様な重ね合わせ \(|s\rangle = \frac{1}{\sqrt{N}}\sum_x |x\rangle\) から始まります。ここで目印の付いた状態 \(|w\rangle\) の振幅は \(1/\sqrt{N}\)、したがって確率は \(1/N\) であり、ランダムな推測と変わりません。そこから次の2段階の Grover反復 を繰り返します。

オラクル \(U_w = I - 2|w\rangle\langle w|\) が、目印の付いた振幅の符号を反転させ、他はそのままにします。
拡散演算子 \(U_s = 2|s\rangle\langle s| - I\) が、すべての振幅を全振幅の平均について反転させます。

2段目はしばしば「平均についての反転（inversion about the average）」と説明され、この説明が仕組みを可視化します。オラクルの後、目印の付いた振幅は平均より下にあり、他はすべてわずかに上にあります。したがって平均について反転させると、目印の付いた振幅はその差のおよそ2倍だけ押し上げられ、目印のない振幅はわずかに引き下げられます。これを繰り返すと、目印の付いた振幅は着実に増大します。

幾何学的な描像 は、\(\sqrt{N}\) とその限界の両方を説明します。状態は、\(|w\rangle\) と目印のない状態の一様な重ね合わせが張る2次元平面から決して出ません。初期状態を

\[ |s\rangle = \sin\theta\,|w\rangle + \cos\theta\,|w^{\perp}\rangle, \qquad \sin\theta = \frac{1}{\sqrt{N}} \]

と書くと、各Grover反復は2つの反転の積であり、これは \(|w\rangle\) へ向かう \(2\theta\) の回転になります。\(k\) 回の反復後の成功確率は

\[ P(k) = \sin^2\big((2k+1)\theta\big) \]

です。\((2k+1)\theta \approx \pi/2\) となってほしいので、大きな \(N\) では \(\theta \approx 1/\sqrt{N}\) となり、最適な反復回数は

\[ k_{\text{opt}} \approx \frac{\pi}{4}\sqrt{N} \]

です。

📚 見落とされがちな2つの帰結

回しすぎ（over-rotation）は現実の問題です。 力学が回転であるため、最適回数より多く反復すると状態は \(|w\rangle\) を通り過ぎ、成功確率は周期的に 下がって いきます。Groverのアルゴリズムは単調に収束する過程ではありません。正しい時点で止めなければなりません。4.6節ではこれが数値的に起こる様子を示します。

高速化は2乗であって指数的ではありません。 この点は強調に値します。量子コンピューティングについて最もよくある誤解だからです。\(N\) から \(\sqrt{N}\) になるということは、\(2^{100}\) 個の要素の探索に \(2^{50}\) 回の量子クエリがかかるということであり、依然として全く実行不可能です。Groverは指数的に難しい問題を容易にはしません。128ビットの総当たり鍵探索を64ビット相当の労力に変えるにすぎず、これこそが対称鍵暗号に対する標準的な推奨が「暗号を捨てる」ではなく「単に鍵長を2倍にする」である理由です。

さらに、\(\sqrt{N}\) は可能な限り最良であることが証明されています。構造なし探索に対するどんな量子アルゴリズムも \(\Omega(\sqrt{N})\) 回のクエリを必要とします。より賢い量子探索が発見されるのを待っている、ということはありません。そして実務上、2乗の利得は脆弱です。誤り訂正されたハードウェア上でGroverを走らせると、論理演算1回あたりに大きな定数倍のオーバーヘッドがかかるため、現実的な多くの問題サイズでは、高度に最適化された探索を走らせる古典コンピュータの方が依然として勝ちます。Groverによる実用的な高速化の主張は、定数倍が机上に載るまで懐疑的に扱ってください。

4.4 Shorのアルゴリズム: 素因数分解

📚 素因数分解が重要な理由

インターネットの安全性の大きな部分を支えるRSA暗号は、大きな整数の素因数分解が困難であるという信念に立脚しています。最良の既知の古典アルゴリズムである一般数体篩法は、桁数に対して劣指数的だが超多項式的な時間で動作します。小さな数を分解するには十分速く、2048ビット鍵には絶望的です。

1994年に発表されたShorのアルゴリズムは、\(n\) ビット整数を \(n\) の多項式時間で素因数分解します。これは本物の 指数的高速化 であり、各国政府や企業が量子コンピューティングに注目するきっかけとなった結果です。

📚 アルゴリズムの構造

Shorのアルゴリズムは大半が古典的です。量子的なのは1ステップだけです。

ステップ1 — 素因数分解を周期発見に帰着させる（古典）。 \(N\) を素因数分解するために、\(N\) と互いに素な \(a < N\) をランダムに選び、次の関数を考えます。

\[ f(x) = a^x \bmod N \]

この関数は周期的です。\(a^r \equiv 1 \pmod N\) を満たす最小の \(r > 0\) が存在します。この \(r\) を \(a\) の位数（order）と呼びます。\(r\) が偶数で、かつ \(a^{r/2} \not\equiv -1 \pmod N\) であれば、

\[ \gcd\left(a^{r/2} - 1,\, N\right) \quad \text{と} \quad \gcd\left(a^{r/2} + 1,\, N\right) \]

は \(N\) の自明でない因数になります。この帰着は純粋な整数論であって量子力学を含みません。ランダムに選んだ \(a\) はそこそこの確率で条件を満たすので、数回試せば十分です。

ステップ2 — 周期を求める（量子）。 \(r\) を求めることが古典的には困難な部分です。量子的には、すべての \(x\) の重ね合わせに対して \(f\) を評価し、振幅が周期 \(r\) で周期的な状態を作ります。そこに 量子フーリエ変換（QFT）を適用します。これは離散フーリエ変換の量子版であり、振幅の周期性を \(1/r\) の倍数における鋭いピークに変換します。測定すると、古典的な連分数アルゴリズムによって \(r\) を抽出できる値が得られます。

ここでの原動力はQFTであり、その効率こそが全体を成立させています。QFTは \(2^n\) 個の振幅に \(O(n^2)\) 個のゲートだけで作用しますが、高速な古典FFTですら \(2^n\) 個の数に対して \(O(n 2^n)\) 回の演算を要します。QFTが与えて くれない ものにも注意してください。\(2^n\) 個のフーリエ係数をすべて読み出すことはできません。得られるのは、変換後の分布からサンプリングされた1つの測定結果だけです。Shorのアルゴリズムが優雅なのは、周期発見がまさにそのような1サンプルで答えられる問いだからです。

📚 RSAにとって何を意味するのか — 注意深く述べる

ここは議論が両方向に脱線しやすい場所なので、正確に述べましょう。

脅威は原理的には現実です。 Shorのアルゴリズムを走らせる十分に大きな誤り耐性量子コンピュータは、RSAと楕円曲線暗号を破ります。この数学に疑いの余地はありません。

それは今日の能力ではありません。 Shorのアルゴリズムは 誤り耐性（フォールトトレラント） なマシンを必要とします。今日のデバイスは誤り率が高すぎて、必要となる深い回路を実行できませんし、量子誤り訂正は1つの論理量子ビットを多数の物理量子ビットに符号化することを要求します。2048ビットのRSA鍵を素因数分解するための公表されたリソース見積もりは、今日最良のハードウェアと同程度の物理誤り率を仮定して、数百万個の物理量子ビット を 数時間 動作させる規模です。現在のデバイスは数百から数千個程度の物理量子ビットです。その差は数桁あり、これを埋めるのは月単位ではなく年単位で測られる工学プログラムです。

小さな数が「量子コンピュータで素因数分解された」という見出しには懐疑的であってください。15や21のような数を分解する実証は、通常、答えをあらかじめ知った上で簡略化された回路を使っており、スケールしません。

それでも「今収穫し、後で復号する」は正当な懸念です。 敵対者は今日の暗号化通信を記録し、能力のあるマシンが登場するまで保存しておけます。10年以上にわたって機密性を保たなければならないデータ — 医療記録、国家機密、長期間有効な資格情報 — は、現在ではなく将来の能力に晒されています。だからこそ 耐量子計算機暗号 への移行が後回しではなく今、進められています。NISTは2024年に、効率的な量子アルゴリズムが知られていない数学的問題（構造付き格子など）に基づく最初の耐量子暗号標準を公表しました。Shorに対する正しい応答は、狼狽ではなく移行スケジュールです。

4.5 量子高速化の分類

本章から持ち帰るべき最も重要なことは、「量子高速化」が一枚岩ではないということです。

高速化	例	何を意味するか
指数的	Shorの素因数分解、量子系のシミュレーション	古典的には永久に手の届かない問題サイズが扱えるようになる
多項式（多くは2乗）	Grover探索、一部の最適化とモンテカルロ法	\(N \to \sqrt{N}\)。本物だが控えめで、定数倍に容易に打ち消される
知られていない	日常的な計算の大半: データベース、Webサーバ、表計算、一般のソフトウェア	量子コンピュータは「速いコンピュータ」ではない

この表から3つの警告が導かれます。

量子コンピュータはすべてを速くするわけではありません。 より高速なプロセッサではないのです。計算課題の圧倒的多数において、量子コンピュータには何の優位性もありません。それどころか、確率的で、誤りが起きやすく、極低温冷却が必要である以上、はるかに劣ります。正しいメンタルモデルは、適切な数学的構造を持つ狭い問題クラス向けの専用アクセラレータであって、CPUの置き換えではありません。

量子コンピュータがNP完全問題を効率的に解けるとは考えられていません。 これは広く見られる誤解です。NP完全問題（巡回セールスマン、充足可能性問題、その他数千の問題）を多項式時間で解く量子アルゴリズムは知られておらず、計算量理論の研究者は一般にそのようなものが存在するとは期待していません。Groverの2乗高速化は解候補に対する総当たり探索には適用できますが、2乗では指数的増大を飼いならすには足りません。特筆すべきことに、Shorが解く問題である素因数分解は、NP完全であるとは 知られていません。それは珍しい中間地帯にあり、それが扱いやすかった理由の一部でもあります。

機械学習における「指数的高速化」の主張には注意してください。 いくつかの量子機械学習アルゴリズムは、古典データをどのように量子状態に読み込むかについての仮定に依存した指数的高速化を宣伝していました。\(N\) 個の古典データ点を量子レジスタに読み込むこと自体に \(O(N)\) 回の演算がかかりうるので、それだけで優位性は消え去ります。そうした主張のいくつかは後に「脱量子化（dequantized）」されました。同じ仮定を古典側にも認めれば、同程度のスケーリングを持つ古典アルゴリズムが見つかったのです。量子高速化の主張に出会ったら、次の3つを問うてください。古典的ベースラインは正確に何か、データはどうやって入るのか、そして答えはどうやって出てくるのか。

最も信頼できる近未来の応用は、Feynmanが最初に示唆したもの、すなわち量子系を使って量子系をシミュレートすることです。第5章でそれを取り上げます。

4.6 Python: 振幅が動く様子を見る

本節の2つのアルゴリズムはいずれも、NumPyだけで状態ベクトルに直接書き下せます。振幅が数値として発展していく様子を見ることが、干渉の議論を具体化する最短の道です。

必要環境: Python 3.9以上とNumPyのみ。

コード例1: 4要素に対するGroverのアルゴリズム

"""N = 4（2量子ビット）に対するGroverのアルゴリズムを、振幅を追跡しながら実行する。"""

import numpy as np

N = 4                     # 探索空間のサイズ = 2^2
marked = 2                # 探しているインデックス、すなわち |10>
labels = ["00", "01", "10", "11"]

# --- ステップ1: 両方の量子ビットへのHで作る一様な重ね合わせ ---
s = np.ones(N, dtype=complex) / np.sqrt(N)
psi = s.copy()

# --- ステップ2: オラクル。目印の符号を反転する対角ユニタリ ---
oracle = np.eye(N, dtype=complex)
oracle[marked, marked] = -1.0

# --- ステップ3: 拡散演算子 2|s><s| - I ---
diffusion = 2 * np.outer(s, s.conj()) - np.eye(N, dtype=complex)


def show(tag, state):
    amps = "  ".join(f"|{l}>{v.real:+.4f}" for l, v in zip(labels, state))
    print(f"{tag:<22}{amps}   P(marked)={abs(state[marked])**2:.4f}")


show("initial", psi)
for k in range(1, 4):
    psi = oracle @ psi
    show(f"iter {k}: after oracle", psi)
    psi = diffusion @ psi
    show(f"iter {k}: after diff.", psi)

print("\nunitary checks:")
print("  oracle unitary   :", np.allclose(oracle.conj().T @ oracle, np.eye(N)))
print("  diffusion unitary:", np.allclose(diffusion.conj().T @ diffusion, np.eye(N)))

# --- より大きなNに対する最適反復回数 ---
print("\nsuccess probability vs. iterations for N = 16 (1 marked item):")
N2, marked2 = 16, 9
s2 = np.ones(N2, dtype=complex) / np.sqrt(N2)
o2 = np.eye(N2, dtype=complex)
o2[marked2, marked2] = -1.0
d2 = 2 * np.outer(s2, s2.conj()) - np.eye(N2, dtype=complex)
state = s2.copy()
for k in range(9):
    print(f"  after {k} iteration(s): P(marked) = {abs(state[marked2])**2:.4f}")
    state = d2 @ (o2 @ state)
print(f"  pi/4 * sqrt(N) = {np.pi / 4 * np.sqrt(N2):.2f}")

検証済みの出力:

initial               |00>+0.5000  |01>+0.5000  |10>+0.5000  |11>+0.5000   P(marked)=0.2500
iter 1: after oracle  |00>+0.5000  |01>+0.5000  |10>-0.5000  |11>+0.5000   P(marked)=0.2500
iter 1: after diff.   |00>+0.0000  |01>+0.0000  |10>+1.0000  |11>+0.0000   P(marked)=1.0000
iter 2: after oracle  |00>+0.0000  |01>+0.0000  |10>-1.0000  |11>+0.0000   P(marked)=1.0000
iter 2: after diff.   |00>-0.5000  |01>-0.5000  |10>+0.5000  |11>-0.5000   P(marked)=0.2500
iter 3: after oracle  |00>-0.5000  |01>-0.5000  |10>-0.5000  |11>-0.5000   P(marked)=0.2500
iter 3: after diff.   |00>-0.5000  |01>-0.5000  |10>-0.5000  |11>-0.5000   P(marked)=0.2500

unitary checks:
  oracle unitary   : True
  diffusion unitary: True

success probability vs. iterations for N = 16 (1 marked item):
  after 0 iteration(s): P(marked) = 0.0625
  after 1 iteration(s): P(marked) = 0.4727
  after 2 iteration(s): P(marked) = 0.9084
  after 3 iteration(s): P(marked) = 0.9613
  after 4 iteration(s): P(marked) = 0.5817
  after 5 iteration(s): P(marked) = 0.1255
  after 6 iteration(s): P(marked) = 0.0204
  after 7 iteration(s): P(marked) = 0.3649
  after 8 iteration(s): P(marked) = 0.8361
  pi/4 * sqrt(N) = 3.14

最初のブロックを注意深く読んでください。7行で仕組みの全体が示されています。

オラクルは確率には何もしません。符号を反転するだけであり、\(|-0.5|^2 = |0.5|^2\) です。増幅はすべて拡散のステップで起こります。オラクルの後、4つの振幅は \((0.5, 0.5, -0.5, 0.5)\) で平均は \(0.25\)。それぞれをこの平均について反転させると \((0, 0, 1, 0)\) になります。\(N = 4\) では1回の反復で 厳密に 答えに到達し、確率は1です。これは特別な場合で、\(\theta = \pi/6\) かつ \(3\theta = \pi/2\) がちょうど成り立つためです。

そのまま続けるとどうなるかを見てください。反復2は目標を 通り過ぎ て、振幅の大きさが一様な状態に戻します。反復3は全体のマイナス符号（大域位相なので物理的には出発点と同一）を除いて一様な重ね合わせに戻します。成功確率は収束せず、周期3で振動します。これが4.3節で警告した回しすぎであり、生の数値として目に見えています。

\(N = 16\) のブロックは数え方の規則を確認します。予測される最適値 \(\frac{\pi}{4}\sqrt{16} \approx 3.14\) は3回の反復に丸められ、実際に最大確率0.9613が \(k = 3\) で現れます。そこを過ぎると確率は反復6で0.0204まで崩れ、その後また上昇します。いつ止めるかを知ることも、アルゴリズムの一部です。

コード例2: 位相オラクルによるDeutsch–Jozsa

"""位相オラクルを使ったDeutsch-Jozsaを、状態ベクトルに直接書き下す。"""

import numpy as np


def hadamard_n(n):
    """Hのn重テンソル積。クロネッカー積の繰り返しで構成する。"""
    H = np.array([[1, 1], [1, -1]], dtype=complex) / np.sqrt(2)
    M = np.array([[1]], dtype=complex)
    for _ in range(n):
        M = np.kron(M, H)
    return M


def phase_oracle(f, n):
    """対角ユニタリ U_f |x> = (-1)^f(x) |x>"""
    return np.diag([(-1.0) ** f(x) for x in range(2 ** n)]).astype(complex)


def deutsch_jozsa(f, n):
    psi = np.zeros(2 ** n, dtype=complex)
    psi[0] = 1.0                       # |0...0>
    Hn = hadamard_n(n)
    psi = Hn @ psi                     # 一様な重ね合わせ
    psi = phase_oracle(f, n) @ psi     # オラクルへのクエリは1回だけ
    psi = Hn @ psi                     # 干渉
    return psi


n = 3
constant = lambda x: 1                                  # すべてのxで f(x) = 1
balanced = lambda x: x & 1                              # 半分が0、半分が1
also_balanced = lambda x: bin(x).count("1") % 2         # パリティ

for name, f in [("constant", constant),
                ("balanced (x & 1)", balanced),
                ("balanced (parity)", also_balanced)]:
    psi = deutsch_jozsa(f, n)
    p_all_zero = abs(psi[0]) ** 2
    verdict = "CONSTANT" if p_all_zero > 0.5 else "BALANCED"
    print(f"{name:<20} P(|000>) = {p_all_zero:.4f}  ->  {verdict}")

# クエリが1回で済むことこそが要点である。決定論的な古典アルゴリズムは
# 最悪ケースで 2^(n-1) + 1 回のfの評価を必要としうる。
print(f"\nn = {n}: quantum queries = 1, "
      f"classical worst case (deterministic) = {2 ** (n - 1) + 1}")

検証済みの出力:

constant             P(|000>) = 1.0000  ->  CONSTANT
balanced (x & 1)     P(|000>) = 0.0000  ->  BALANCED
balanced (parity)    P(|000>) = 0.0000  ->  BALANCED

n = 3: quantum queries = 1, classical worst case (deterministic) = 5

確率は1と0に近いというだけではなく、厳密に1と0です。干渉が完全だからです。定数関数は同じ符号の \(2^n\) 個の項を寄与させ、それらはコヒーレントに足し合わさります。均衡関数は同数の \(+1\) と \(-1\) の項を寄与させ、完全に打ち消し合います。2つの均衡関数の例は構造が大きく異なるのに同じ判定を与えており、それこそが「ブラックボックス」の意味するところです。n を5や6に変えても答えは厳密なままで、古典的な最悪ケースは17回、33回へと増えていきます。

🎯 演習問題

位相キックバック: 第2レジスタを \(|-\rangle\) にしてXORオラクル \(U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle\) を適用すると \((-1)^{f(x)}|x\rangle|-\rangle\) が得られることを示してください。
Groverの幾何: \(\sin\theta = 1/\sqrt{N}\) として \(P(k) = \sin^2((2k+1)\theta)\) を使い、\(N = 64\) に対する最適な \(k\) と最大成功確率を計算し、コード例1を改変して確認してください。
複数の目印: コード例1を修正して、4つの状態のうち2つに目印を付けてください。必要な反復回数はどうなりますか。成功確率はどうなりますか。
乱択の古典Deutsch–Jozsa: \(n = 10\) のとき、古典アルゴリズムが誤り確率 \(10^{-6}\) 未満で均衡関数を判定するには、何回のランダムなクエリが必要ですか。\(2^{n-1}+1\) と比較してください。
高速化の見積もり: ある対称鍵暗号の鍵長が256ビットです。総当たり鍵探索に必要なGrover反復の回数を見積もり、なぜ鍵長を2倍にすることが適切な対応と見なされるのかを説明してください。

まとめ

本章では、量子アルゴリズムが実際に何をもたらすのかを学びました。クエリモデル はコストをオラクル呼び出し回数で測り、量子計算と古典計算の分離を証明することを可能にします。位相キックバック はXORオラクルを、大半のアルゴリズムが使う位相オラクルに変換します。Deutsch–Jozsaアルゴリズム は、決定論的な古典アルゴリズムが \(2^{n-1}+1\) 回を要しうる定数か均衡かの判定を、完全な相殺的干渉によってわずか1回のクエリで行います。ただし乱択の古典アルゴリズムに対しては差が劇的に縮まり、問題自体も人工的です。Groverのアルゴリズム は、振幅増幅 によって構造のない \(N\) 要素の空間を \(O(\sqrt{N})\) 回のクエリで探索します。これは2次元平面内の回転であり、およそ \(\frac{\pi}{4}\sqrt{N}\) 回で止めなければ回しすぎになります。その高速化は 指数的ではなく2乗 であり、かつ最適であることが証明されています。Shorのアルゴリズム は、素因数分解を 周期発見 に帰着させ 量子フーリエ変換 を用いることで、本物の 指数的高速化 を達成します。数百万個規模の物理量子ビットを要する 誤り耐性 マシン上ではRSAを破りますが、それは現在のハードウェアをはるかに超えています。それでも 「今収穫し、後で復号する」 ゆえに、耐量子計算機暗号への移行は現在の課題です。そして何より、高速化の分類 を学びました。素因数分解と量子シミュレーションでは指数的、探索と一部の最適化では多項式的、そして計算の大部分では 何もなし です。量子コンピュータは専用アクセラレータであって速いコンピュータではなく、NP完全問題を効率的に解くとは期待されていません。

次章では、今日実際に存在する機械 — ノイズあり中規模量子デバイス — と、そもそもこの分野を動機づけた応用、すなわち分子と材料のシミュレーションを見ていきます。

← 第3章: 量子ゲートと量子回路第5章: NISQ時代と化学・材料への応用 →

免責事項

本コンテンツは教育・研究・情報提供のみを目的としており、専門的な助言(法律・会計・技術的保証など)を提供するものではありません。
本コンテンツおよび付随するCode examplesは「現状有姿(AS IS)」で提供され、明示または黙示を問わず、商品性、特定目的適合性、権利非侵害、正確性・完全性、動作・安全性等いかなる保証もしません。
外部リンク、第三者が提供するデータ・ツール・ライブラリ等の内容・可用性・安全性について、作成者および東北大学は一切の責任を負いません。
本コンテンツの利用・実行・解釈により直接的・間接的・付随的・特別・結果的・懲罰的損害が生じた場合でも、適用法で許容される最大限の範囲で、作成者および東北大学は責任を負いません。
本コンテンツの内容は、予告なく変更・更新・提供停止されることがあります。
本コンテンツの著作権・ライセンスは明記された条件(例: CC BY 4.0)に従います。当該ライセンスは通常、無保証条項を含みます。