複数量子ビットと普遍ゲート集合

量子情報入門　第1章 §1.2

テンソル積とレジスタ

$n$ 量子ビット系のHilbert空間は $\mathbb C^2$ の $n$ 個のテンソル積 $(\mathbb C^2)^{\otimes n}\cong \mathbb C^{2^n}$ である。計算基底は

$$\ket{x_1 x_2 \cdots x_n} \equiv \ket{x_1}\otimes\ket{x_2}\otimes\cdots\otimes\ket{x_n},\qquad x_i\in\{0,1\}$$

で、$2^n$ 個ある。$x=x_1 x_2\cdots x_n$ を2進整数と見なして $\ket{x}$ とも書く。

$n$ 量子ビット状態は $2^n$ 個の複素振幅で指定されるため、次元は $n$ に対し指数的に増える。これが古典計算に対する量子計算の潜在的優位性の源泉の一つである。

CNOTゲートともつれの生成

2量子ビット系で最も基本的な多量子ビットゲートは制御NOTゲート(CNOT)である:

$$\mathrm{CNOT} = \ket{0}\!\bra{0}\otimes I + \ket{1}\!\bra{1}\otimes X = \begin{pmatrix} 1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0 \end{pmatrix}.$$

第1量子ビットが $\ket 1$ のとき、かつそのときのみ第2量子ビットに $X$ を作用させる。

CNOTはHadamardと組み合わせてもつれた状態を生成する。$\ket 0\otimes\ket 0$ から出発し、第1量子ビットにHadamardを作用させ、続いてCNOTを作用させれば

$$\ket{00} \xrightarrow{H\otimes I} \frac{\ket{00}+\ket{10}}{\sqrt2} \xrightarrow{\mathrm{CNOT}} \frac{\ket{00}+\ket{11}}{\sqrt2} \equiv \ket{\Phi^+}.$$

これはベル状態の1つであり、2量子ビットの最大もつれ状態である。

ベル基底

2量子ビット系の最大もつれ状態は4つあり、ベル基底をなす:

$$\ket{\Phi^\pm} = \frac{\ket{00}\pm\ket{11}}{\sqrt2},\qquad \ket{\Psi^\pm} = \frac{\ket{01}\pm\ket{10}}{\sqrt2}.$$

これらは互いに1量子ビットのPauli作用素で移り合う。例えば $(X\otimes I)\ket{\Phi^+}=\ket{\Psi^+}$, $(Z\otimes I)\ket{\Phi^+}=\ket{\Phi^-}$。

例題:テンソル積の計算とCNOTの等価回路

テンソル積とゲートの取り扱いに慣れるため、いくつかの基本的な計算を実行しておく。

CNOTのブロック構造

CNOTの $4\times4$ 行列を $2\times2$ のブロックに区切って眺めると

$$\mathrm{CNOT} = \begin{pmatrix} I & 0\\ 0 & X\end{pmatrix}$$

というブロック対角構造が見える。左上ブロックが「制御が $\ket 0$ の部分空間では恒等 $I$」、右下ブロックが「制御が $\ket 1$ の部分空間では $X$」に対応しており、定義式 $\ket{0}\!\bra{0}\otimes I + \ket{1}\!\bra{1}\otimes X$ の視覚的表現になっている。標的ビットの変換 $\ket t\to\ket{t\oplus c}$($\oplus$ は排他的論理和 XOR)は、$c=0$ なら恒等、$c=1$ なら反転、という古典の条件分岐をユニタリとして実装したものである。古典と決定的に違うのは、制御ビットが重ね合わせ $\ket +$ にあるとき「何もしない」と「反転する」が同時に起こり、前小節のようにもつれが生成される点である。

1量子ビットゲートの埋め込み(演習4.16相当)

2量子ビット系で第1ビットだけにHadamardを作用させる演算子は

$$H\otimes I = \frac{1}{\sqrt2}\begin{pmatrix} I & I\\ I & -I\end{pmatrix} = \frac{1}{\sqrt2}\begin{pmatrix}1&0&1&0\\0&1&0&1\\1&0&-1&0\\0&1&0&-1\end{pmatrix}, \qquad I\otimes H = \begin{pmatrix} H & 0\\ 0 & H\end{pmatrix}.$$

Kronecker積の規則「左因子の各成分を右因子のブロックに置き換える」を使えば機械的に書ける。ブロック単位で見る習慣は、制御ゲートの解析(上のCNOTのブロック構造)と一貫している。

制御ZとHadamardによるCNOTの構成(演習4.17相当)

制御Zゲート $\mathrm{CZ}=\mathrm{diag}(1,1,1,-1)$ は「両方が $\ket 1$ のときだけ符号を反転する」ゲートで、制御と標的の区別がない(対称)。共役関係 $HZH = X$ を標的ビット側に適用すると

$$(I\otimes H)\,\mathrm{CZ}\,(I\otimes H) = \mathrm{CNOT}$$

が成り立つ(行列の直接計算で数値的にも確認済み)。仕組みは単純で、$\mathrm{CZ}=\ket{0}\!\bra{0}\otimes I+\ket{1}\!\bra{1}\otimes Z$ の標的側を $H(\cdot)H$ で挟むと、$HIH=I$、$HZH=X$ により $\ket{0}\!\bra{0}\otimes I+\ket{1}\!\bra{1}\otimes X=\mathrm{CNOT}$ となる。ここで $H^2=I$(Hadamardは自分自身が逆元)が効いている。物理実装(第1.1.7節)で自然に作れる2量子ビットゲートがCZである場合が多く、この等価回路はCNOTをCZ+1量子ビットゲートに還元する実用的な変換である。

普遍ゲート集合とは何か

古典計算で「NANDゲートさえあれば任意のブール関数を実現できる」(NANDが普遍)ように、量子計算でも「これだけあれば任意のユニタリを実現できる」小さなゲート集合が存在する。ただし量子ユニタリは連続群 $\mathrm U(2^n)$ の元なので、有限個のゲートで厳密に任意のユニタリを作ることはできない。そこで「任意精度で近似できれば十分」とする。

ここで「$\mathrm U(2^n)$ が連続群である」とは何か、パラメータの正体を明確にしておく。$n=1$ ならZYZ分解(定理1.1)がそのままパラメータ表示であり、$(\alpha,\beta,\gamma,\delta)$ という4つの実数(回転角)が連続に動く——$\gamma$ を $0.7$ から $0.7001$ にわずかに変えれば、わずかに違うユニタリが得られる。一般の $\mathrm U(2^n)$ でも、任意のユニタリはHermite行列 $H$ で $U=e^{iH}$ と書け、$2^n\times2^n$ Hermite行列は実対角 $2^n$ 個+複素上三角 $\binom{2^n}{2}$ 個、計 $(2^n)^2=4^n$ 個の実パラメータで指定される。物理的には「$4^n$ 個の独立な回転角を持つ一般化回転の連続体」である(実装レベルでも回転角はパルスの振幅・時間という文字通り連続な実験ノブに対応する;第1.1.7節)。これに対し $H,S,T,\mathrm{CNOT}$ のような個々のゲートは角度が固定された1点であり、有限個の固定ゲートの有限積で作れるユニタリは可算個しかない。可算集合で $4^n$ 次元の連続体を厳密に埋め尽くすことはできないから、普遍性は上の定義のように「稠密な近似」として定式化するほかない——その近似コストを保証するのが次の定理である。

すなわち、精度を上げるコストが $\log$ のべき乗にしかならない、というのが定量的な保証である。

以下のゲート集合は普遍である:

• $\{H, T, \mathrm{CNOT}\}$(標準的な普遍集合)
• $\{H, S, T, \mathrm{CNOT}\}$($S=T^2$ を明示的に加えたもの)
• $\{H, T, \mathrm{Toffoli}\}$

一方、$\{H, S, \mathrm{CNOT}\}$ からは離散的なユニタリ群(Clifford群)しか生成できず、普遍にならない。これがGottesman–Knill定理(第2.7.4節)の内容で、Clifford回路は古典的に効率シミュレート可能だから、量子的優位性を発揮するには $T$ ゲート(または Toffoli)のような Clifford の外側にあるゲートが不可欠、というメッセージにつながる。

第2部の量子誤り訂正では、これらの集合のうちどのゲートが横断的に(=フォールトトレラントに簡便に)実装できるかが決定的に重要になる。多くのスタビライザー符号では $H,S,\mathrm{CNOT}$ は横断的に実装できるが、$T$ ゲートは横断的に実装できず、特別な工夫(魔法状態蒸留、ゲートテレポーテーションなど)が必要になる。この非対称性がフォールトトレラント計算の技術的核心の一つである。

Toffoliゲート

古典計算の可逆な普遍ゲートであるToffoliゲート(制御制御NOT、CCNOT)は3量子ビットゲートで、真理値表は「$a$ と $b$ が両方 $1$ のときだけ $c$ を反転する」:

$$\mathrm{Toffoli}\ket{a,b,c} = \ket{a,b,c\oplus ab}.$$

制御ビットを2つ持つ CNOT の拡張版と思えばよい。

Toffoli の重要性は次の2点に集約される。

1. 古典計算の可逆な埋め込み:古典 NAND は $\mathrm{NAND}(a,b) = \neg(a\wedge b)$。Toffoli で $c=1$ に固定すれば出力は $1\oplus ab = \neg(a\wedge b)$。すなわち Toffoli で NAND が作れる。NAND が古典で普遍であることと合わせれば、Toffoli で古典計算の全てを可逆に(=ユニタリとして)埋め込める。量子アルゴリズムでよく登場する「モジュラー累乗を可逆回路で実装する」といった操作は、この事実に依拠している。
2. 量子的普遍性:Hadamard を加えた $\{H,\mathrm{Toffoli}\}$ は量子計算に対しても普遍。すなわち古典可逆計算の道具(Toffoli)と重ね合わせを作る道具(Hadamard)だけあれば、量子計算のすべてを近似できる。

多重制御ゲート $C^n(U)$

CNOT($n=1$)とToffoli($n=2$)の考え方は、任意個の制御ビットへそのまま拡張できる。$n$重制御NOT

$$C^n(X)\ket{x_1,\ldots,x_n,t} = \ket{x_1,\ldots,x_n,\ t\oplus(x_1\wedge\cdots\wedge x_n)}$$

は「制御ビットがすべて $\ket1$ のときだけ標的を反転する」ゲートである。$\mathrm U(2^{n+1})$ の元であり、ブロック構造で見れば $2^{n+1}\times2^{n+1}$ 行列の右下 $2\times2$ ブロックだけが $X$、残りは恒等——CNOTのブロック対角構造(第2.4節)の素直な一般化になっている。標的を $X$ の代わりに任意の $U$ にした $C^n(U)$ も同様に定義される。

重要なのは、$C^n(X)$ を基本ゲートに加える必要はないという点である。補助ビット(アンシラ)を使う標準的な構成を $C^3(X)$(制御 $a,b,c$、標的 $t$)で示す。補助 $w_1,w_2$(初期値 $\ket0$)を用意し、

1. Toffoli$(a,b\to w_1)$で $w_1=a\wedge b$ を計算
2. Toffoli$(w_1,c\to w_2)$で $w_2=a\wedge b\wedge c$ を計算
3. CNOT$(w_2\to t)$で標的に反映
4. 手順2、1を逆順にもう一度実行し、$w_1,w_2$ を $\ket0$ に戻す

一般の $n$ でもANDを二分木状に集約すれば、Toffoli約 $2(n-1)$ 個・補助 $n-1$ 個で組める。手順4の巻き戻し(uncomputation)は省略できない:省くと補助ビットに中間結果 $a\wedge b$ が残り、主レジスタが重ね合わせにあるとき補助ともつれたままになって、以降の干渉(Deutsch–JozsaやGroverの心臓部;第1.6節)を破壊する。可逆計算では「計算したら消す」が作法である——これが上記1.の「古典計算の可逆な埋め込み」を実際に運用するときの最重要の注意点である。

補助ビットを使わない分解も可能で、たとえば $C^2(U)$ は $V^2=U$ なる $V$ を用いて「制御$V$、CNOT、制御$V^\dagger$、CNOT、制御$V$」の5個の2量子ビットゲートに分解できる(Toffoliなら $V=\sqrt X$)。一般の $C^n(U)$ も1量子ビットゲートとCNOTだけで $O(n^2)$(工夫すれば $O(n)$)個に落とせる。

応用上も多重制御ゲートはよく使う実用部品である。たとえばGroverの拡散変換(第1.6節)に要る「$\ket{0\cdots0}$ のときだけ位相反転」は、全制御ビットを $X$ で挟んで条件を反転した $C^{n-1}(Z)$ にほかならず、$C^{n-1}(Z)$ は標的を $H$ で挟めば $C^{n-1}(X)$ に変換できる(第2.4節の $\mathrm{CZ}$–CNOT等価回路と同じ理屈)。