量子計算(quantum computation)とは、計算の状態を $\mathbb{C}^{2^n}$ の単位ベクトルで表し、少数の量子ビットに働くユニタリ行列(量子門)で更新し、最後に振幅の絶対値の 2 乗を確率として値を読み出す計算のモデルである。振幅の打ち消し合いにより、定数か均衡かが約束された関数を 1 回の問い合わせで判定でき(Deutsch–Jozsa)、$N$ 点中 $M$ 点($0< M< N$)の解を約 $\frac{\pi}{4}\sqrt{N/M}$ 回の問い合わせで確率 $1-M/N$ 以上で見つけられる(Grover)。多項式時間の量子計算で誤り $1/3$ 以下で判定できる言語のクラス BQP は $\mathrm{BPP}\subset\mathrm{BQP}\subset\mathrm{PSPACE}$ を満たし、素因数分解の判定版を含む(Shor)。
量子計算(quantum computation)は、計算の途中の状態を、確率分布ではなく複素数の係数(振幅)をもつ単位ベクトルで表し、それをユニタリ行列で更新し、最後に振幅の絶対値の 2 乗を確率として値を読み出す、という計算のモデルである。状態は $2^n$ 次元の複素ベクトル空間の単位ベクトルで、計算の 1 歩はその空間のユニタリ変換である。数学としては有限次元の線形代数の上に組み立てられ、物理の解釈を持ち込まなくても定義と定理を述べられる。
確率的な計算では、異なる計算の道筋の確率は足し合わされるだけである。量子計算では振幅が足し合わされ、符号や位相の違いで打ち消し合うことがある。この打ち消し合いを使うと、古典の計算より少ない回数の問い合わせで関数の性質を判定できる場合がある。
この記事では、量子ビットの状態・量子門・量子回路・測定を定め、古典の回路を量子回路に埋め込む方法を示したうえで、Deutsch–Jozsa のアルゴリズムと Grover の探索アルゴリズムを完全に証明する。多項式時間の量子計算で解ける問題のクラス BQP を定義し、普遍性、Shor の素因数分解のアルゴリズム、BQP と古典のクラスの関係は、文献の所在を示して主張として述べる。量子計算機を物理的にどう作るかは扱わない。
$\mathbb{C}^2$ の標準基底を $|0\rangle,|1\rangle$ と書く。
$n\ge1$ とする。$n$ 量子ビットの状態空間 を $\mathcal{H}_n:=(\mathbb{C}^2)^{\otimes n}$ とする。$x=x_1x_2\cdots x_n\in\{0,1\}^n$ に対して $|x\rangle:=|x_1\rangle\otimes\cdots\otimes|x_n\rangle$ とおくと、$\{|x\rangle\}_{x\in\{0,1\}^n}$ は $\mathcal{H}_n$ の基底(計算基底)であり、これを正規直交基底とする内積で $\mathcal{H}_n\cong\mathbb{C}^{2^n}$ と見る。
$\mathcal{H}_n$ の単位ベクトル
$$
\psi=\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle,\qquad \sum_x|\alpha_x|^2=1
$$
を 状態 といい、$\alpha_x$ を $x$ の 振幅 という。状態 $\psi\in\mathcal{H}_n$ と $\varphi\in\mathcal{H}_m$ のテンソル積 $\psi\otimes\varphi\in\mathcal{H}_{n+m}$ を $|\psi\rangle|\varphi\rangle$ とも書く。
状態 $\psi=\sum_x\alpha_x|x\rangle\in\mathcal{H}_n$ を 測定 すると、$x\in\{0,1\}^n$ が確率 $|\alpha_x|^2$ で得られる。最初の $k$ 量子ビットだけを測定すると、$y\in\{0,1\}^k$ が確率 $\sum_{z\in\{0,1\}^{n-k}}|\alpha_{yz}|^2$ で得られる。
$\sum_x|\alpha_x|^2=1$ なので、これらは確率分布である。$\theta\in\mathbb{R}$ について $\psi$ と $e^{i\theta}\psi$ は、どのユニタリ変換を施したあとでも同じ測定の分布を与える。そこで、全体にかかる絶対値 $1$ の定数(大域的な位相)の違いは無視してよい。
$k$ 量子ビットの門 とは $2^k$ 次のユニタリ行列 $U$ である。相異なる番号 $i_1,\dots,i_k\in\{1,\dots,n\}$ に $U$ を 施す とは、$\mathcal{H}_n$ のユニタリ変換
$$
|x\rangle\longmapsto\sum_{y\in\{0,1\}^k}U_{y,\,x_{i_1}\cdots x_{i_k}}\,|x[y]\rangle
$$
を施すことをいう。ここで $x[y]$ は $x$ の $i_j$ 番目の文字を $y_j$ に置き換えた語である。量子ビットの番号を並べ替えれば、これは $U\otimes I_{2^{n-k}}$ と同じ形である。
$n$ 量子ビットの量子回路 とは、門とそれを施す番号の組の有限列 $(G_1,\dots,G_T)$ であり、$T$ を回路の 大きさ という。回路は $\mathcal{H}_n$ のユニタリ変換 $C:=G_T\cdots G_1$ を定める。
1 量子ビットの門として
$$
H=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\qquad X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}
$$
を使う。$H$ を Hadamard 門 という。$H|0\rangle=(|0\rangle+|1\rangle)/\sqrt2$、$H|1\rangle=(|0\rangle-|1\rangle)/\sqrt2$ で、$H^2=I$ である。2 量子ビットの 制御 NOT 門(CNOT)は $|a\rangle|b\rangle\mapsto|a\rangle|a\oplus b\rangle$、3 量子ビットの Toffoli 門 は $|a\rangle|b\rangle|c\rangle\mapsto|a\rangle|b\rangle|c\oplus ab\rangle$ である($\oplus$ は 2 を法とする和)。$\{0,1\}^k$ の全単射は計算基底の置換を引き起こし、置換行列はユニタリなので、どれも $k$ 量子ビットの門である。CNOT と Toffoli 門はこの形で、どちらも 2 回施すと恒等変換になる。
Hadamard 門を全部の量子ビットに施すと、計算基底が $\pm$ の符号をもつ一様な重ね合わせに移る。
$x,y\in\{0,1\}^n$ に対し $x\cdot y:=\sum_i x_iy_i\bmod 2$ とおく。
1.$b\in\{0,1\}$ について $H|b\rangle=2^{-1/2}\sum_{c\in\{0,1\}}(-1)^{bc}|c\rangle$ である。テンソル積の多重線形性から $\displaystyle H^{\otimes n}|x\rangle=\bigotimes_{i=1}^n\Big(2^{-1/2}\sum_{y_i}(-1)^{x_iy_i}|y_i\rangle\Big)=2^{-n/2}\sum_{y}(-1)^{\sum_ix_iy_i}|y\rangle$ となり、$(-1)^{\sum_ix_iy_i}=(-1)^{x\cdot y}$ である。
2.$y=0^n$ なら各項は $1$ である。$y_j=1$ となる $j$ があれば、$x$ の $j$ 番目の文字を反転する写像は $\{0,1\}^n$ の全単射で、$(-1)^{x\cdot y}$ の符号を反転する。和は自分自身の $-1$ 倍に等しいので $0$ である。$\square$
関数 $f$ を量子回路から使うには、$f$ をユニタリ変換の形にする必要がある。
$f\colon\{0,1\}^n\to\{0,1\}$ に対し、$\mathcal{H}_{n+1}$ のユニタリ変換
$$
O_f|x\rangle|b\rangle:=|x\rangle|b\oplus f(x)\rangle\qquad(x\in\{0,1\}^n,\ b\in\{0,1\})
$$
を $f$ の 神託(oracle)という。$O_f$ は計算基底の置換なのでユニタリで、$O_f^2=I$ である。$O_f$ を施した回数を、$f$ への 問い合わせの回数 という。
$f$ が論理回路で与えられていれば、神託は量子回路で実現できる。補助の量子ビットは、計算の終わりに $|0\rangle$ に戻しておく必要がある。戻さないと、補助の量子ビットと残りの量子ビットが絡み合ったままになり、後の打ち消し合いが起こらなくなるからである。
$f\colon\{0,1\}^n\to\{0,1\}$ が、入次数 $2$ 以下の AND・OR 門と NOT 門 $s$ 個の論理回路(回路計算量)で計算されるとする。このとき、$X$・CNOT・Toffoli 門だけからなる $n+1+s$ 量子ビットの大きさ $12s+1$ 以下の量子回路で、すべての $x\in\{0,1\}^n$、$b\in\{0,1\}$ について
$$
|x\rangle|b\rangle|0^s\rangle\longmapsto|x\rangle|b\oplus f(x)\rangle|0^s\rangle
$$
となるものがある。
論理回路の門を計算の順に $g_1,\dots,g_s$ とし、門 $g_j$ の値を $j$ 番目の補助の量子ビット $c_j$(初めは $0$)に書き込む。値が書き込まれた量子ビット $a,b$ について、AND 門は Toffoli 門 $|a,b,c_j\rangle\mapsto|a,b,c_j\oplus ab\rangle$ の 1 個、NOT 門は CNOT で $a$ を $c_j$ に写してから $c_j$ に $X$ を施す 2 個、OR 門は $a\vee b=\neg(\neg a\wedge\neg b)$ により「$a,b$ に $X$、Toffoli、$a,b$ に $X$、$c_j$ に $X$」の 6 個で実現できる。AND 門・OR 門の 2 つの入力が同じ量子ビットなら、値はその量子ビットの値なので CNOT 1 個で $c_j$ に写す。どれも計算基底を計算基底に移し、$c_j=0$ のとき $c_j$ に門の値が入り、ほかの量子ビットは元に戻る。これを $j=1,\dots,s$ の順に行う列を $F$ とすると、$F$ の大きさは $6s$ 以下で、$F|x\rangle|b\rangle|0^s\rangle=|x\rangle|b\rangle|v(x)\rangle$ となる。$v(x)$ は各門の値を並べた語で、出力の頂点の値は $f(x)$ である。
次に、出力の頂点の値をもつ量子ビット(出力の頂点が門 $g_j$ なら $c_j$、入力の頂点 $x_i$ なら $x_i$ の量子ビット)から $b$ の量子ビットへ CNOT を 1 個施して $|x\rangle|b\oplus f(x)\rangle|v(x)\rangle$ とする。最後に $F$ の門を逆の順に施す。$X$・CNOT・Toffoli はどれも自分自身の逆なので、逆の順の列は $F^{-1}$ である。$F$ の門は $b$ の量子ビットを読み書きしないので、$F^{-1}$ は $|x\rangle|b'\rangle|v(x)\rangle$ を $|x\rangle|b'\rangle|0^s\rangle$ に移す($b'$ は任意)。大きさは合わせて $12s+1$ 以下である。$\square$
これと Hadamard 門で公平な硬貨を投げられることから、多項式時間の確率的な計算は多項式時間の量子計算で模倣できる(AB07 Theorem 20.17、p. 416)。
神託の出力の量子ビットを特別な状態にしておくと、$f$ の値は振幅の符号として書き込まれる。
$|-\rangle:=HX|0\rangle=(|0\rangle-|1\rangle)/\sqrt2$ とおく。すべての $x\in\{0,1\}^n$ について $O_f\big(|x\rangle|-\rangle\big)=(-1)^{f(x)}|x\rangle|-\rangle$ である。
$f(x)=0$ なら $O_f$ は $|x\rangle|0\rangle,|x\rangle|1\rangle$ をそれぞれ動かさない。$f(x)=1$ なら両者を入れ替えるので、$|x\rangle(|0\rangle-|1\rangle)$ は $|x\rangle(|1\rangle-|0\rangle)=-|x\rangle(|0\rangle-|1\rangle)$ に移る。$\square$
$f\colon\{0,1\}^n\to\{0,1\}$ が 定数 であるとは $f$ が一定値をとることをいい、均衡 であるとはちょうど $2^{n-1}$ 個の $x$ で $f(x)=1$ となることをいう。$f$ が定数か均衡のどちらかであることが前もって分かっている(約束)とき、どちらであるかを判定する問題を考える。この問題と次の解法は Deutsch と Jozsa による。
$n\ge1$ とし、$f$ は定数か均衡であるとする。$\mathcal{H}_{n+1}$ の状態 $|0^n\rangle|0\rangle$ から始めて、
1 と 2 のあとの状態は、lem-qc-hadamard の 1 と $HX|0\rangle=|-\rangle$ により
$$
\Big(2^{-n/2}\sum_{x\in\{0,1\}^n}|x\rangle\Big)|-\rangle
$$
である。3 では、lem-qc-kickback と線形性により、状態は
$$
\Big(2^{-n/2}\sum_{x}(-1)^{f(x)}|x\rangle\Big)|-\rangle
$$
になる。4 では、再び lem-qc-hadamard の 1 により、最初の $n$ 量子ビットの部分は
$$
2^{-n/2}\sum_x(-1)^{f(x)}\,2^{-n/2}\sum_y(-1)^{x\cdot y}|y\rangle=\sum_{y\in\{0,1\}^n}\Big(2^{-n}\sum_x(-1)^{f(x)+x\cdot y}\Big)|y\rangle
$$
に移る。最後の量子ビットは $|-\rangle$ のままなので、def-qc-measure により $0^n$ を得る確率は $y=0^n$ の振幅の絶対値の 2 乗
$$
\Big|\,2^{-n}\sum_x(-1)^{f(x)}\Big|^2
$$
に等しい。$f$ が定数 $c$ なら和は $(-1)^c2^n$ で、確率は $1$ である。$f$ が均衡なら、$(-1)^{f(x)}$ は $+1$ と $-1$ をちょうど $2^{n-1}$ 回ずつとるので和は $0$ で、確率は $0$ である。$\square$
均衡な $f$ では、$2^n$ 個の道筋の振幅が打ち消し合って $0^n$ の振幅が $0$ になる。一方、古典の決定的な算法で誤りなく判定するには、最悪の場合に半分を超える点を問い合わせる必要がある。
$f(x)$ の値を $1$ 点ずつ問い合わせる決定的な算法が、約束を満たすすべての $f$ について正しく判定するなら、ある $f$ について $2^{n-1}+1$ 回以上問い合わせる。
算法が問い合わせるたびに $0$ を答える相手を考える。同じ点を 2 度問い合わせても情報は増えないので、問い合わせた点は相異なるとしてよい。算法が $2^{n-1}$ 回以下の問い合わせで答えを出すとし、問い合わせた点の集合を $Q$($|Q|\le2^{n-1}$)とする。定数関数 $0$ はこれまでのすべての答えと合う。また $Q$ を含む大きさ $2^{n-1}$ の集合 $Q'$ をとり、$Q'$ の上で $0$、その外で $1$ となる $f$ は均衡で、やはりすべての答えと合う。算法は決定的で、同じ答えの列には同じ出力を返すから、2 つの $f$ のどちらかで誤る。$\square$
$f\colon\{0,1\}^n\to\{0,1\}$ とし、$N:=2^n$、$A:=f^{-1}(1)$、$M:=|A|$ とおき、$0< M< N$ とする。$A$ の元を $1$ つ見つける問題を考える。$\mathcal{H}_n$ の単位ベクトル
$$
|A\rangle:=\frac{1}{\sqrt M}\sum_{x\in A}|x\rangle,\qquad |B\rangle:=\frac{1}{\sqrt{N-M}}\sum_{x\notin A}|x\rangle,\qquad u:=H^{\otimes n}|0^n\rangle=\frac{1}{\sqrt N}\sum_x|x\rangle
$$
を考え、$\theta\in(0,\pi/2)$ を $\sin\theta=\sqrt{M/N}$ で定める。$|A\rangle,|B\rangle$ は正規直交で、$u=\sin\theta\,|A\rangle+\cos\theta\,|B\rangle$ である。
$\mathcal{H}_n$ の 2 つのユニタリ変換
$$
S_f|x\rangle:=(-1)^{f(x)}|x\rangle,\qquad D:=2u\,u^{*}-I
$$
を考え($u^*$ は $u$ の共役転置)、$G:=DS_f$ を Grover の反復 という。$S_f$ は補助の量子ビット $|-\rangle$ と $O_f$ $1$ 回で実現できる(lem-qc-kickback)。$H^{\otimes n}$ は自分自身の逆なので $D=H^{\otimes n}(2|0^n\rangle\langle0^n|-I)H^{\otimes n}$ であり、$2|0^n\rangle\langle0^n|-I$ は $g(x):=[x=0^n]$ についての $-S_g$ に等しい。$g$ は $n$ 変数の論理回路で計算できるので、$D$ は大域的な位相を除いて lem-qc-reversible と lem-qc-kickback で実現でき、$f$ への問い合わせを使わない。
上の記号のもとで、すべての整数 $k\ge0$ について
$$
G^ku=\sin\big((2k+1)\theta\big)|A\rangle+\cos\big((2k+1)\theta\big)|B\rangle
$$
が成り立つ。したがって、$u$ に $G$ を $k$ 回施して測定すると、$A$ の元が確率 $\sin^2((2k+1)\theta)$ で得られる。とくに $k:=\lfloor\pi/(4\theta)\rfloor$ とすると、問い合わせの回数は $k\le\frac{\pi}{4}\sqrt{N/M}$ で、$A$ の元を得る確率は $1-M/N$ 以上である。
$W$ を $|A\rangle,|B\rangle$ で張られる実 2 次元の部分空間 $\{a|A\rangle+b|B\rangle:a,b\in\mathbb{R}\}$ とし、$\varphi\in\mathbb{R}$ について $w(\varphi):=\sin\varphi\,|A\rangle+\cos\varphi\,|B\rangle$ とおく。$u=w(\theta)$ である。
$S_f$ は $A$ の元の振幅の符号だけを反転するので、$S_f|A\rangle=-|A\rangle$、$S_f|B\rangle=|B\rangle$ であり、$S_fw(\varphi)=w(-\varphi)$ となる。
$D$ は、$v\in\mathcal{H}_n$ を $u$ の方向の成分 $\langle u,v\rangle u$ とその直交補の成分に分け、後者の符号を反転する写像である。$u\in W$ なので $D$ は $W$ を $W$ に移し、$W$ の上では直線 $\mathbb{R}u$ に関する鏡映である。$|B\rangle,|A\rangle$ を座標軸とする平面で、$w(\varphi)$ は $|B\rangle$ から角 $\varphi$ の方向の単位ベクトルであり、$u$ は角 $\theta$ の方向にある。角 $\theta$ の直線に関する鏡映は角 $\psi$ の方向を角 $2\theta-\psi$ の方向に移すので、$Dw(\psi)=w(2\theta-\psi)$ である。
よって
$$
Gw(\varphi)=D\,w(-\varphi)=w(2\theta+\varphi)
$$
であり、$k$ についての帰納法で $G^ku=G^kw(\theta)=w((2k+1)\theta)$ が従う。
$w(\varphi)$ の各 $x\in A$ の振幅は $\sin\varphi/\sqrt M$ なので、測定で $A$ の元を得る確率は $M\cdot\sin^2\varphi/M=\sin^2\varphi$ である。
$k=\lfloor\pi/(4\theta)\rfloor$ とすると $\pi/(4\theta)-1< k\le\pi/(4\theta)$ なので、$\pi/2-\theta< (2k+1)\theta\le\pi/2+\theta$ である。$\sin^2$ は $\pi/2$ に関して対称で、$[\pi/2-\theta,\pi/2]$ で増加するから、$\sin^2((2k+1)\theta)\ge\sin^2(\pi/2-\theta)=\cos^2\theta=1-M/N$ である。また $0< \theta< \pi/2$ では $\theta\ge\sin\theta=\sqrt{M/N}$ なので、$k\le\pi/(4\theta)\le\frac{\pi}{4}\sqrt{N/M}$ である。各 $G$ は $f$ への問い合わせを $1$ 回だけ使う。$\square$
$M=1$ なら、およそ $\frac{\pi}{4}\sqrt N$ 回の問い合わせで、確率 $1-1/N$ 以上で唯一の解が見つかる。古典の算法では、確率 $1/2$ で解を見つけるのに約 $N/2$ 回の問い合わせが必要である。$f$ が大きさ $s$ の論理回路で与えられていれば、lem-qc-reversible により全体は $O\big(\sqrt N\,(s+n)\big)$ 個の門で書ける。
$n=2$、$M=1$ とする。$\sin\theta=1/2$ より $\theta=\pi/6$ で、$k=\lfloor\pi/(4\theta)\rfloor=\lfloor3/2\rfloor=1$ である。$(2k+1)\theta=\pi/2$ なので、$G$ を $1$ 回施した状態はちょうど $|A\rangle$ であり、問い合わせ $1$ 回で解が確率 $1$ で得られる。実際、$A=\{a\}$ とすると $u$ の各振幅は $1/2$ なので $S_fu=u-|a\rangle$ で、$Du=u$、$D|a\rangle=2\cdot\frac12u-|a\rangle=u-|a\rangle$ だから、$Gu=u-(u-|a\rangle)=|a\rangle$ である。
反復の回数の位数 $\sqrt N$ は改善できない。
ランダムに選んだ神託に相対化すると、確率 $1$ で、NP は時間 $o(2^{n/2})$ の量子計算で判定できる言語の族に含まれない(BBBV97 Theorem 3.5)。この記事では証明しない。
実際の回路では、決まった有限個の門しか使えないことが多い。そこで、ほかの門を有限個の門の積で近似したときの誤差を評価しておく。行列のノルム $\|U\|$ は作用素ノルムとする。
1.入れ替える位置で分けて $\displaystyle U_T\cdots U_1-V_T\cdots V_1=\sum_{i=1}^T U_T\cdots U_{i+1}\,(U_i-V_i)\,V_{i-1}\cdots V_1$ と書ける(右辺の和は隣り合う項が打ち消し合う)。ユニタリ行列の作用素ノルムは $1$ なので、各項のノルムは $\|U_i-V_i\|$ 以下である。
2.$\psi=\sum\alpha_x|x\rangle$、$\varphi=\sum\beta_x|x\rangle$ とすると、$\big||\alpha_x|^2-|\beta_x|^2\big|=\big||\alpha_x|-|\beta_x|\big|(|\alpha_x|+|\beta_x|)\le|\alpha_x-\beta_x|(|\alpha_x|+|\beta_x|)$ である。$x$ について足し、Cauchy–Schwarz の不等式を使うと、和は $\|\psi-\varphi\|\,\big(\|\psi\|+\|\varphi\|\big)=2\|\psi-\varphi\|$ 以下である。$\square$
大きさ $T$ の回路の各門を誤差 $\varepsilon/T$ 以下の積で置き換えると、lem-qc-error により、最後の状態の差は $\varepsilon$ 以下、測定の分布の差(各点の差の和)は $2\varepsilon$ 以下である。したがって、少数の門の積で任意の門をよく近似できれば、どの回路もその少数の門で模倣できる。
2 の長さは $\log(1/\varepsilon)$ の多項式なので、門を近似で置き換えても回路の大きさは多項式の範囲で増えるだけである。
以下、門の有限集合 $\mathcal{G}$ を $1$ つ固定し、$H$・$X$・CNOT・Toffoli 門を含み、どの門も 3 量子ビット以下に働き、成分がすべて代数的数であるものとする。
言語 $L\subset\{0,1\}^*$ が BQP に属するとは、多項式 $p$ と、$1^n$ を入力として $\mathcal{G}$ の門からなる $n+p(n)$ 量子ビット・大きさ $p(n)$ 以下の量子回路 $C_n$ を出力する多項式時間の決定的な Turing機械 があって、すべての $x\in\{0,1\}^n$ について、状態 $C_n|x\rangle|0^{p(n)}\rangle$ の最初の量子ビットを測定して $1$ を得る確率が、$x\in L$ なら $2/3$ 以上、$x\notin L$ なら $1/3$ 以下であることをいう。
AB07 Definitions 20.13–20.14(p. 412)は、3 量子ビット以下に働く基本演算の列でこのクラスを定め、基本演算は Hadamard 門と Toffoli 門で十分よく近似できると同書 §20.3.1(p. 413)は述べている。$2/3$ と $1/3$ は、独立に $t$ 回くり返して多数決をとれば $1-2^{-\Omega(t)}$ と $2^{-\Omega(t)}$ にできる(Hoeffdingの不等式)。
$\mathrm{P}\subset\mathrm{BPP}\subset\mathrm{BQP}\subset\mathrm{PSPACE}$ である(AB07 Theorem 20.17、p. 416、Theorem 20.25、p. 429)。さらに $\mathrm{BQP}\subset\mathrm{P}^{\#\mathrm{P}}$ である(同書 p. 429)。この記事では $\mathrm{BQP}\subset\mathrm{PSPACE}$ と $\mathrm{BQP}\subset\mathrm{P}^{\#\mathrm{P}}$ を証明しない。
$\mathrm{P}\subset\mathrm{BQP}$ は、多項式時間の機械を多項式の大きさの論理回路で模倣し(回路計算量)、それを lem-qc-reversible で量子回路にすれば得られる。BPP は乱数を使う多項式時間の計算で誤り $1/3$ 以下で判定できる言語のクラスで、乱数のビットは Hadamard 門を施した補助の量子ビットで作れる。
BQP が BPP より真に大きいか、NP を含むかは、AB07 §20.8(p. 429)の時点で未解決である。thm-qc-bbbv は、神託に相対化した世界では、NP の問題を Grover の探索より本質的に速く解く量子計算がないことを示している。
素因数分解は、$\gcd(a,N)=1$ となる $a$ の $N$ を法とする 位数(群) $r$ を求める問題に、古典の初等整数論で帰着される(AB07 §20.7.3、p. 428)。位数 $r$ は、$x\mapsto a^x\bmod N$ の周期である。周期は、$2^m$ を法とする 離散Fourier変換 を $O(m^2)$ 個の門で実現する量子 Fourier 変換(AB07 Lemma 20.20、p. 424)で振幅の山として取り出し、測定値の 連分数 展開から復元する。RSA 暗号などの 公開鍵暗号 が頼る問題が多項式時間で解けることになるため、この結果は 暗号理論 に大きな影響を与えた。
| 外す条件 | 例 | 成り立たなくなること |
|---|---|---|
| thm-qc-dj の約束(定数か均衡) | $n=2$ で、$1$ 点だけで値 $1$ をとる $f$ | $0^n$ を得る確率が $1/4$ で、$0$ でも $1$ でもない |
| 門がユニタリであること(振幅の打ち消し合い) | thm-qc-dj の $H$ を、確率行列 $\frac12\begin{pmatrix}1&1\\1&1\end{pmatrix}$(公平な硬貨)に替える | どの $f$ でも $0^n$ を得る確率は $2^{-n}$ で、定数と均衡を区別できない |
| thm-qc-grover で $M$ を正しく知っていること | $N=16$、実際は $M=4$ なのに $M=1$ として $k=3$ を選ぶ | $A$ の元を得る確率が $1/4$ に落ちる($M=1$ なら約 $0.96$) |
| prop-qc-dj-classical の誤りを許さないこと | 古典の算法で、独立に一様な点を $t$ 回問い合わせ、値が全部同じなら定数と答える | 誤りの確率は $2^{1-t}$ 以下で、$t$ は $n$ によらない定数で済む |
どの行も、表の左の条件のほかは定理の設定のままである。
1 行目:prf-qc-dj の計算はどの $f$ にも通用し、$0^n$ の確率は $|2^{-n}\sum_x(-1)^{f(x)}|^2$ である。$1$ 点だけで $1$ をとる $f$ では和が $2^n-2$ なので、確率は $(1-2^{1-n})^2$ で、$n=2$ なら $1/4$ である。出力は確率 $1/4$ と $3/4$ でばらつき、定理の「確率 $1$ か $0$」の二者択一が成り立たない。
2 行目:確率行列 $\frac12\begin{pmatrix}1&1\\1&1\end{pmatrix}$ はどの分布も一様分布に移す。最後の段で最初の $n$ ビットのそれぞれにこれを施すので、神託の前に何があっても最初の $n$ ビットは一様に分布し、$0^n$ の確率は $2^{-n}$ である。外したのは振幅を足し合わせることだけで、問い合わせの回数は同じ $1$ 回である。
3 行目:$M=1$ なら $\sin\theta=1/4$、$k=\lfloor\pi/(4\theta)\rfloor=3$ で、成功の確率は $\sin^2(7\theta)\approx0.96$ である。実際は $M=4$ なので $\theta=\pi/6$ で、$\sin^2(7\pi/6)=1/4$ である。$k$ が大きすぎて、回転が $|A\rangle$ を通り過ぎた。
4 行目:定数の $f$ では必ず正しく答える。均衡な $f$ では、$t$ 個の値が全部 $0$ か全部 $1$ になる確率が $2\cdot2^{-t}$ である。下界 $2^{n-1}+1$ は誤りを許さない算法についてだけ成り立つ。乱数を使っても誤りを許さない算法なら、乱数の値を固定するごとに prop-qc-dj-classical の仮定を満たす決定的な算法になるので、問い合わせの回数の最大値は $2^{n-1}+1$ 以上のままである。外したのは誤りを許さないことだけである。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する