計算量クラスの理論: P, NP, BPP, BQP

量子情報入門　第1章 §1.7　★★ Shor や Grover の「速い」を厳密な主張として述べるための言語。クラスの定義群と包含関係の全体像、そして Simon のオラクル分離までが、量子計算の理論的到達点の見取り図になる

何を測るのか: 決定問題と多項式時間

計算量理論の目的は、個々のアルゴリズムの巧拙ではなく、問題そのものの本質的な難しさを入力サイズ $n$ の関数として分類することにある。「どんなアルゴリズムを使っても最低これだけの資源が要る」という下界と、「このアルゴリズムならこれだけで解ける」という上界で問題を挟み、必要資源の水準ごとに問題をクラスへ組織する。本節の古典側の枠組みは N&C 第3章 § 3.2.2–3.2.4、量子側(BQP)は第4章 § 4.5.5 に対応する。

出自の異なる問題を同じ土俵で比べるため、まず問題の形を標準化する。

答えが数値で返る問題も判定版に直せる。たとえば「$N$ の非自明な約数を求めよ」は、判定版「$N$ は $k$ 以下の非自明な約数を持つか」を $O(\log N)$ 回呼ぶ二分探索で元の答えを復元できるから、決定問題への制限で難しさの分類は変わらない。

資源の主役は時間(計算のステップ数。回路モデルではゲート数)と領域(使うメモリ量)である。「効率的」の線は多項式時間 $O(n^k)$に引く。この線引きには2つの理由がある。第一に合成で閉じる: 多項式時間のアルゴリズムが多項式時間のサブルーチンを呼んでも全体は多項式時間のままで、「効率的な部品の組み合わせは効率的」という直観が保たれる。第二に計算モデルに依らない: チューリング機械・RAM・論理回路といった古典モデルは互いに多項式時間の変換で行き来できるので、多項式か指数かの区別はモデルの細部に左右されない。一方 $O(2^n)$ の指数時間は $n$ が数百になった時点で現実の手に負えなくなる。素因数分解が古典で(準)指数時間、Shor で多項式時間(第1.6.3節)という対比が劇的なのは、この線を跨ぐからである。

P と NP: 解けることと検証できること

★★　「自力で解く」と「証拠を検証する」の区別が NP の核心。P vs NP は、後で BQP の位置を論じるときの背景になる

例は整列、最短経路(Dijkstra)、行列積、線形計画法、AKS アルゴリズムによる素数判定など。「効率的に解ける」の基準クラスである。

• 巡回セールスマン問題(判定版)「長さ $\le L$ の巡回路はあるか」。巡回路そのものが証拠で、長さの計算は多項式時間で済む。
• 素因数分解(判定版)「$N$ は $k$ 以下の非自明な約数を持つか」。約数が証拠で、割り算1回で検証できる。
• 充足可能性問題 SAT「この論理式を真にする変数割り当てはあるか」。割り当てが証拠で、式の評価は多項式時間。

$\mathrm P\subseteq\mathrm{NP}$ は自明である(自力で解けるなら、検証者は証拠を無視して自分で解けばよい)。逆向きの $\mathrm{NP}\subseteq\mathrm P$、すなわち「検証が易しい問題は必ず自力でも易しく解けるか」がP vs NP 問題(ミレニアム懸賞問題)で、$\mathrm P\neq\mathrm{NP}$ と広く信じられているが未解決である。$\mathrm{NP}$ の中にはNP 完全と呼ばれる最難の問題群があり(SAT が代表。Cook–Levin の定理)、任意の NP 問題は多項式時間の変換で NP 完全問題に帰着する。したがって NP 完全問題が1つでも多項式時間で解ければ $\mathrm P=\mathrm{NP}$ が従う。

領域で切ったクラスも用意しておく。PSPACE は多項式領域で解ける決定問題のクラスで、時間はいくらかかってもよい。証拠の候補 $w$ を1本ずつ生成しては検証し、領域を使い回せば NP 問題は多項式領域で解けるから、$\mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}$ が並ぶ。

乱数を許す: BPP

★★　「定数の誤り確率は多数決で指数的に潰せる」が確率的クラス設計の要。BQP の $2/3$ も同じ理屈で正当化される

乱数を資源として認めたときの「効率的」が次のクラスである。

$2/3$ という定数に意味はない。同じアルゴリズムを $2k+1$ 回走らせて多数決を取れば、誤り確率は $\frac13(8/9)^k$ 以下と指数的に減衰する(導出と具体的な反復回数は演習1)。したがって閾値は、多項式時間を保ったまま $1/2+1/n^c$ から $1-2^{-n^c}$ まで自由に取り替えられる。$1/2$ ちょうどでは当てずっぽうと区別が付かず増幅の足場が無いので、そこだけが本質的な境界である。

例は Miller–Rabin の確率的素数判定(のちに AKS により素数判定自体は $\mathrm P$ と判明)や、多項式恒等式検査(与えられた式が恒等的に $0$ かを乱数代入で高確率判定する。こちらは $\mathrm P$ に入るかが現在も未解明の代表例)。乱数を使わないアルゴリズムはその特別な場合だから $\mathrm P\subseteq\mathrm{BPP}$、また乱数列 $2^{\mathrm{poly}(n)}$ 通りをすべて試して多数決を集計すれば(領域は使い回せる)$\mathrm{BPP}\subseteq\mathrm{PSPACE}$ である。なお擬似乱数生成器の理論から $\mathrm P=\mathrm{BPP}$(乱数は実は省ける)と予想されているが、これも未解決である。

量子多項式時間: BQP

★★★　本書の主役クラス。「一様な多項式サイズ量子回路族＋有界誤差」の3点セットで定義する

量子計算での「多項式時間」は回路モデル(第1.2節)で定義する。入力長 $n$ ごとに回路 $Q_n$ を1つ用意した族 $\{Q_n\}$ を使うが、このとき一様性(uniformity)を課す: 回路の記述(どのゲートをどこに置くか)が、$n$ を入力とする古典多項式時間アルゴリズムで生成できることを要求する。一様性を課さないと、たとえば難しい問題の答えの表を回路の設計図そのものに埋め込む反則(計算せずに表を引くのと同じ)が可能になり、クラスが計算の難しさを測らなくなる。

ここでも $2/3$ は本質的でない。回路を独立に $2k+1$ 回走らせて多数決を取る増幅は量子でもそのまま通用する(多数決の計算は Toffoli による可逆計算として回路に含められる)。また、普遍ゲート集合をどれに取るかもクラスを変えない。Solovay–Kitaev の定理(定理1.3)により、あるゲート集合の回路は別のゲート集合で誤差 $\varepsilon$ まで $O(\log^c(1/\varepsilon))$ 倍のゲート数で近似できるからである。

古典多項式時間アルゴリズムが知られていない代表的な BQP 問題は次の2系統である。

• 因数分解・離散対数・位数発見: いずれも Shor 型のアルゴリズム(第1.6.3節)で多項式時間。RSA や楕円曲線暗号を破るという応用面でも、後述の「NP 完全とは信じられていない」という理論的位置づけの面でも、BQP の看板問題である。
• 量子系のシミュレーション: 局所ハミルトニアンによる時間発展の近似。Feynman が量子計算機を着想した動機であり、化学・物性計算への応用の中心。

Grover の探索(第1.6節)は $\sqrt N$ 倍の加速なので、多項式か指数かの線引きでは古典と同じ側にとどまる。BQP の外形を広げるのは上の2系統のような指数的加速である。

包含関係の全体像

★★★　何が証明済みで何が予想かの区別が最重要。BQP と NP は、どちらも他方を含むとは思われていない

3つの包含の理由を順に見る。

• $\mathrm P\subseteq\mathrm{BPP}$: 乱数を使わないアルゴリズムは、乱数を使えるアルゴリズムの特別な場合である。
• $\mathrm{BPP}\subseteq\mathrm{BQP}$: 材料は2つ。(i) 公平なコインは $H\ket0$ を測定すれば作れる(測定は回路の最後まで遅らせてもよい)。(ii) 古典回路は Toffoli ゲートで可逆化して量子回路に埋め込める(第1.2節)。この2つを合わせると、BPP アルゴリズム全体が多項式サイズの一様な量子回路になる。
• $\mathrm{BQP}\subseteq\mathrm{PSPACE}$: ゲート数 $m$ の回路の出力振幅は、ゲートの間に計算基底の完全系を挟むと

$$\bra{y} G_m\cdots G_2 G_1\ket{0\cdots0} = \sum_{z_1,\ldots,z_{m-1}} \bra{y}G_m\ket{z_{m-1}}\cdots\bra{z_2}G_2\ket{z_1}\bra{z_1}G_1\ket{0\cdots0}$$

というFeynman 経路和になる。経路(中間状態の列 $z_1,\ldots,z_{m-1}$)の総数は指数個だが、1本の経路の寄与は $m$ 個の行列要素の積として多項式時間・多項式領域で計算でき、経路にわたる和は1本ずつ計算しては累積すれば領域を使い回せる。時間は指数的にかかるものの領域は多項式で済むから、出力確率が多項式領域で求まる。「指数個の振幅」は時間の壁ではあっても領域の壁ではない、というのがこの証明の教訓である。

注意すべきは、定理1.9のどの包含についても真の包含($\neq$)は証明されていないことである。両端ですら $\mathrm P\neq\mathrm{PSPACE}$ が未証明なのだから、鎖のどこかが潰れて等号になっている可能性を論理的には排除できない。「量子計算機は古典より真に強い」という主張は、現時点では定理ではなく、強く支持された予想である。

$\mathrm{NP}$ との関係はさらに微妙で、どちらの向きの包含も知られていない。

• $\mathrm{NP}\subseteq\mathrm{BQP}$ を支持する証拠は乏しい。Grover のアルゴリズムは NP 問題の証拠探索を $O(\sqrt{2^n})$ に加速するだけで多項式には届かず、しかも BBBV 下界(第1.6節)により、問題の構造を使わない探索では平方根の加速が量子の限界である。NP 完全問題を量子で多項式時間で解くには、SAT などに未発見の代数的構造が必要になる。
• 逆の $\mathrm{BQP}\subseteq\mathrm{NP}$ も期待されていない。Shor が解く因数分解(判定版)は $\mathrm{NP}\cap\mathrm{coNP}$ に属する(素因数分解の一意性により、完全な素因数分解を証拠とすれば Yes と No のどちら側も多項式時間で検証できる)。この位置の問題は NP 完全ではないと信じられており、因数分解は「NP の中の、完全でも P でもない中間層」の住人と目されている。量子の得意領域は NP と斜めに交わる別の領域であって、NP を覆う形にはなっていない。

実線の包含($\mathrm P\subseteq\mathrm{BPP}\subseteq\mathrm{BQP}\subseteq\mathrm{PSPACE}$)はいずれも証明済み。NP を点線にしたのは、$\mathrm{NP}\subseteq\mathrm{PSPACE}$ 自体は証明済みだが、BPP・BQP との重なり方(因数分解が BPP の外にあること、SAT が BQP の外にあること)が $\mathrm P\neq\mathrm{NP}$ などの未解決予想に依る描像だからである。

オラクル分離: Simon の問題

★★★　乱択古典に対する指数的分離を無条件に証明できる最初の例であり、Shor の位数発見の直接の原型

前小節の結論のとおり、絶対的な分離($\mathrm{BPP}\neq\mathrm{BQP}$ など)は現在の数学では手が届かない。そこで計算量理論は問題設定を絞る。クエリ模型(オラクル模型)では、未知の関数 $f$ がオラクル(中身の見えないブラックボックス)として与えられ、アルゴリズムは $f$ へのクエリ(問い合わせ。量子なら $U_f\colon\ket x\ket q\mapsto\ket x\ket{q\oplus f(x)}$ を1回使うこと)によってのみ $f$ の情報を得る。数える資源はクエリ回数だけである。この模型の利点は下界が実際に証明できることにあり、量子と古典の分離を予想ではなく定理として示せる。

第1.6.1節の Deutsch–Jozsa 問題はこの模型の例で、量子1回対古典決定的 $2^{n-1}+1$ 回という分離を与える。しかしこの分離は、乱択の古典アルゴリズムに対しては消えてしまう: ランダムに数点サンプルするだけで誤り確率を指数的に潰せるからである(演習3)。BPP 対 BQP の分離の証拠と呼ぶには、乱択にも耐える例が要る。それを初めて与えたのが Simon の問題である(N&C では第5章 § 5.4.3 の隠れ部分群問題の表と演習 5.29 で触れられている。以下の分離の議論の構成は本書のオリジナル)。

$x\mapsto x\oplus s$ は群 $(\mathbb Z/2\mathbb Z)^n$ における「$s$ だけの平行移動」だから、これは$(\mathbb Z/2\mathbb Z)^n$ 上の周期発見である。Shor の位数発見(第1.6.3節)は同じ問いを群 $\mathbb Z$ で立てたものにあたり、使う変換も Hadamard 変換($(\mathbb Z/2\mathbb Z)^n$ 上のフーリエ変換。第1.5節)から QFT($\mathbb Z/2^n\mathbb Z$ 上)へ置き換わる。歴史的にも、Simon の1994年の結果を見た Shor が同年のうちに因数分解へ拡張したという直接の系譜がある。

量子アルゴリズム

2本の $n$ 量子ビットレジスタを使う。

$$\ket{0\cdots0}\ket{0\cdots0} \ \xrightarrow{\ H^{\otimes n}\otimes I\ }\ \frac{1}{\sqrt{2^n}}\sum_{x}\ket x\ket{0\cdots0} \ \xrightarrow{\ U_f\ }\ \frac{1}{\sqrt{2^n}}\sum_{x}\ket x\ket{f(x)}.$$

ここで第2レジスタを測定し、値 $f(x_0)$ が出たとする(測定は回路の最後まで遅らせても以下の分布は変わらない。$n=3$ の数値検証では両方の描像で同じ分布になることを確かめている)。$f$ の逆像が $\{x_0,\,x_0\oplus s\}$ の2点であることから、第1レジスタは

$$\frac{\ket{x_0}+\ket{x_0\oplus s}}{\sqrt2}$$

に崩壊する。この状態に $H^{\otimes n}$ を作用させる。1量子ビットの $H\ket{x_i}=(\ket0+(-1)^{x_i}\ket1)/\sqrt2$ を $n$ 本束ねると

$$H^{\otimes n}\ket x=\frac{1}{\sqrt{2^n}}\sum_{y}(-1)^{x\cdot y}\ket y,\qquad x\cdot y\equiv x_1y_1\oplus\cdots\oplus x_ny_n\ (\bmod\ 2)$$

だから、測定直前の $\ket y$ の振幅は

$$\frac{1}{\sqrt{2^{n+1}}}\Bigl[(-1)^{x_0\cdot y}+(-1)^{(x_0\oplus s)\cdot y}\Bigr] =\frac{(-1)^{x_0\cdot y}}{\sqrt{2^{n+1}}}\Bigl[1+(-1)^{s\cdot y}\Bigr]$$

となる。$s\cdot y=1$ なら角括弧の中が $0$、$s\cdot y=0$ なら振幅の大きさは $2^{-(n-1)/2}$ である。

$n=3$, $s=101$ では $s^\perp=\{000,010,101,111\}$ で、6量子ビットの状態ベクトルを直接計算すると分布が正確に $1/4$ ずつになる(検算スクリプト で検証済み。テンソル積の順序は第1.2節の規約どおり $x_1$ が最上位で、$X\otimes I\otimes I\ket{000}=\ket{100}$ を先に確認してから状態計算をしている)。

後処理と全体のクエリ数

実行結果 $y^{(1)},\ldots,y^{(n-1)}$ が1次独立に集まれば、連立方程式 $y^{(i)}\cdot s=0$ の解空間は $\{0\cdots0,\ s\}$ の2点に絞られ、約束 $s\neq 0\cdots0$ から $s$ が確定する($\mathbb F_2$ 上の Gauss 消去で多項式時間)。独立に集まるかは確率の問題だが、既に $i-1$ 本が $i-1$ 次元を張っているとき、次の1本(張られた部分空間の $2^{i-1}$ 点を含む $s^\perp$ 上の一様サンプル)がその中に落ちる確率は $2^{i-1}/2^{n-1}$ だから、$n-1$ 回の実行がそのまま $s^\perp$ を張る確率は

$$\prod_{i=1}^{n-1}\Bigl(1-\frac{2^{i-1}}{2^{n-1}}\Bigr) =\prod_{j=1}^{n-1}\bigl(1-2^{-j}\bigr) \ >\ \prod_{j=1}^{\infty}\bigl(1-2^{-j}\bigr)=0.2887\ldots\ >\ \frac14$$

である($j=n-i$ と置き換えた。無限積の値、および $n=3,\ldots,6$ での閉形式と Monte Carlo の一致は数値確認済み)。1バッチ($n-1$ クエリ)の成功確率が $1/4$ を下回らないので、失敗したら独立にやり直せば期待4バッチ以内に成功する。まとめると、期待 $O(n)$ クエリと多項式時間の古典後処理で $s$ が求まる。

古典の下界

古典アルゴリズムは、乱択を許しても $\Omega(2^{n/2})$ クエリを要する。核心は、$s$ の情報は衝突だけが運ぶことにある。約束を満たす範囲で $f$ の値の割り当ては任意だから、問い合わせた点の値がすべて異なっている限り、その値自体は $s$ について何も語らない。$s$ を教えるのは $f(x_i)=f(x_j)$ という衝突で、このとき $x_i\oplus x_j=s$ と即座に分かる。そこで $s$ が非零の $2^n-1$ 通りから一様ランダムに選ばれているとしよう。相異なる $m$ 点を問い合わせたとき、点のペアは $\binom m2$ 組で、各ペア $\{x_i,x_j\}$ が衝突する事象は「$s$ がちょうど $x_i\oplus x_j$ に等しい」ことだから、和集合の確率の上界(union bound)により

$$\Pr[\text{どこかで衝突する}]\ \le\ \binom m2\,\frac{1}{2^n-1}$$

である(クエリを適応的に選ぶ場合も、無衝突の履歴で条件づけた $s$ は排除済みの候補を除いて一様のままなので、同じ評価が1問い合わせずつ通る)。この確率が定数に達するには $\binom m2=\Omega(2^n)$、すなわち $m=\Omega(2^{n/2})$ が必要で、衝突を見ていないアルゴリズムは2対1の $f$ と単射の $f$ すら区別できない($n=10$, $m=10$ の Monte Carlo で上界との整合を確認済み)。

演習