量子ゲートの種類・表記・ユニバーサルゲートセットを整理してみた

はじめに

量子ゲートは、量子回路に並ぶ基本部品で、数学的にはユニタリ演算子で表されます。本記事では、そのゲートの種類と書き方について調べたことをまとめました。

アルゴリズムの解説では、同じゲートが行列・ブラケット・回路図とさまざまに書かれるため、表記が変わるたびに読みにくくなりがちです。そこで本記事では、ゲートの種類と書き方を整理したうえで、複数量子ビットのゲートとユニバーサルゲートセットまでを順に見ていきます。

誤りや分かりにくい点がありましたら、コメントでご指摘いただけると幸いです。

この記事で押さえること

本記事のゴールは次の5つです。

1. ユニタリ演算子：量子ゲートがユニタリ演算子で表され、ベクトルの長さと内積を保つことを理解する
2. ゲートの種類と表記：ゲートを「成分の入れ替え」「位相の埋め込み」「成分の混合」の3種類で整理し、行列・ブラケット・回路図で書けることを理解する
3. 代表的な1量子ビットゲート：$X$、$Y$、$Z$、$H$、$S$、$T$、位相ゲート $P(\varphi)$ と回転ゲート $R_x,R_y,R_z$ の定義と役割を押さえる
4. 複数量子ビットのゲート：制御付きゲート（$\mathrm{CNOT}$・$\mathrm{CZ}$）、$\mathrm{SWAP}$、$\mathrm{Toffoli}$（$\mathrm{CCNOT}$）と、量子状態はコピーできないこと（量子複製不可能定理）を押さえる
5. ユニバーサルゲートセット：任意のユニタリ操作を（近似を含めて）組み立てられるゲートの組があることを理解する

おさらい：状態と位相

量子ビットの「状態」と「位相」を整理した記事では、グローバル位相と相対位相の違いを確認しました。

詳しくは上記の記事に譲り、ここでは必要な部分だけ再掲します。

• 1量子ビットの状態は $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$ で、測定確率は $|\alpha|^2,|\beta|^2$、その合計は1（規格化条件 $|\alpha|^2+|\beta|^2=1$）
• 状態全体に掛かる位相（グローバル位相）は観測できず、成分間の位相差（相対位相）は干渉を通じて測定結果に影響する
• 1量子ビットの純粋状態（上の $|\psi\rangle$ のように1本のケットで書ける状態）は、ブロッホ球の表面の点で表せる（混合状態は球の内部の点になる）。$|\pm\rangle=(|0\rangle\pm|1\rangle)/\sqrt2$ は赤道上にあり、測定確率は同じだが相対位相が異なる
• ケット $|\psi\rangle$ は列ベクトル、ブラ $\langle\psi|$ はその複素共役転置で、ケットとブラを逆に並べた外積 $|a\rangle\langle b|$ は行列になる（例：$|0\rangle\langle0|=\mathrm{diag}(1,0)$）
• $\mathrm{diag}(a,b)$ は、対角成分が $a,b$ で、ほかは0の行列（対角行列）

ユニタリ演算子とは

量子ゲートは、量子状態を別の量子状態へ変化させる演算子（数学的には行列）です。ただし、どんな行列でもゲートになれるわけではなく、量子ゲートはユニタリ演算子 $U$ で表されます。ユニタリとは、

U^\dagger U=I \tag{1}

を満たすことです（$U^\dagger$ は複素共役転置、$I$ は単位行列）。ここから $U^{-1}=U^\dagger$ がいえるので、ユニタリ操作は必ず元に戻せます（可逆）。また、ベクトルの長さと内積を保ちます。式(1)を使うと、2つの状態 $|\phi\rangle,|\psi\rangle$ に $U$ をかけた後の内積は

\langle\phi|U^\dagger U|\psi\rangle=\langle\phi|\psi\rangle \tag{2}

となり、変わりません（$|\phi\rangle=|\psi\rangle$ とすれば、長さの2乗 $\langle\psi|\psi\rangle$ も変わらないことが分かります）。状態ベクトルの長さの2乗 $\langle\psi|\psi\rangle$ は、規格化条件 $|\alpha|^2+|\beta|^2=1$ そのものなので、ゲートをかけても規格化条件は壊れません。量子ゲートが「確率の合計を1に保ったまま、状態を回す操作」だと言われるのはこのためです。

$U$ という記号自体は、何量子ビットに作用するかを決めていません。$n$ 量子ビットに作用するゲートは $2^n\times2^n$ の行列です。2量子ビット以上の代表的なゲートは、後の節で見ます。

対象	行列サイズ	例
1量子ビット	$2\times2$	$X$、$Y$、$Z$、$H$
2量子ビット	$4\times4$	$\mathrm{CNOT}$、$\mathrm{CZ}$、$\mathrm{SWAP}$
3量子ビット	$8\times8$	$\mathrm{Toffoli}$（$\mathrm{CCNOT}$）

なお、閉じた量子系に対する通常の量子ゲートはユニタリですが、測定・リセット・ノイズはユニタリ操作ではありません。

ゲートの種類

ゲートは、計算基底 $|0\rangle,|1\rangle$ の成分に何をするかで、大きく次の3つに分けて考えると整理しやすくなります。この分類は計算基底で見たときのものです。厳密な分類ではなく、本記事を読むための見取り図です。

種類	何をするか	例	行列の形
成分の入れ替え	$\vert0\rangle$ と $\vert1\rangle$ の成分を入れ替える	$X$	0と1だけが並ぶ（置換行列）
位相の埋め込み	各成分に位相 $e^{i\varphi}$ を掛ける。成分の大きさは変えない	$Z$、$S$、$T$、$P(\varphi)$	対角行列
成分の混合	$\vert0\rangle$ と $\vert1\rangle$ の成分を足し引きして混ぜる（重ね合わせを作る・干渉させる）	$H$	対角以外にも0でない成分がある

$Y$ は「入れ替え」と「位相の埋め込み」の組み合わせです（$Y=iXZ$）。後で見る $R_x(\theta)$ や $R_y(\theta)$ は、角度によって「混合」から「入れ替え」まで連続的に変わります。表の例は1量子ビットのゲートですが、複数量子ビットのゲートも同じ3種類で整理できます（後の節で触れます）。

この3種類は、量子アルゴリズムを読むうえでも役に立ちます。測定確率に効くのは $|0\rangle$ と $|1\rangle$ の成分の間の相対位相で、これは「位相の埋め込み」で入れても、そのままでは測定確率に現れません。「成分の混合」で干渉させて初めて、測定確率に現れます。量子アルゴリズムでは、「混合で重ね合わせを作る → 位相を埋め込む → 混合で干渉させて読み出す」という流れが多いです。なお、$X$ は計算基底では入れ替えですが、$|\pm\rangle$ 基底で見ると、$|+\rangle$ に $+1$、$|-\rangle$ に $-1$ を掛ける位相のゲートです。そのため、$|+\rangle$ と $|-\rangle$ の重ね合わせに対しては、位相の埋め込みとして働きます。

ゲートの表記

同じゲートでも、書き方は複数あります。ここでは1量子ビットのゲートを例に、次の3通りを見ます。

• 行列：1量子ビットゲートは $2\times2$ なので、4つの数を並べて書けます。計算基底の列ベクトルに掛けると状態が変わります。
• 作用：$|0\rangle,|1\rangle$ がそれぞれ何に変わるかを書きます。
• ブラケット（外積）：外積が行列になることを使い、基底の送り先を並べて書きます。

行列と作用は上の説明で足りるので、ブラケットの書き方だけ補足します。

まず、外積 $|0\rangle\langle0|$ と $|1\rangle\langle1|$ は、それぞれ $\mathrm{diag}(1,0)$、$\mathrm{diag}(0,1)$ です。足すと単位行列になります。

|0\rangle\langle0|+|1\rangle\langle1|=
\begin{pmatrix}1&0\\0&0\end{pmatrix}+\begin{pmatrix}0&0\\0&1\end{pmatrix}
=I \tag{3}

ゲート $U$ に単位行列を掛けても $U$ のままなので、式(3)を使って次のように変形できます。

U=UI=U\left(|0\rangle\langle0|+|1\rangle\langle1|\right)=U|0\rangle\langle0|+U|1\rangle\langle1| \tag{4}

ここで $U|0\rangle$ と $U|1\rangle$ は、ゲートが $|0\rangle$ と $|1\rangle$ を送る先の状態です。式(4)を状態 $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$ にかけて展開すると、そのことが確認できます。

\begin{aligned}
U|\psi\rangle&=\left(U|0\rangle\langle0|+U|1\rangle\langle1|\right)\left(\alpha|0\rangle+\beta|1\rangle\right) \\
&=U|0\rangle\langle0|\left(\alpha|0\rangle+\beta|1\rangle\right)+U|1\rangle\langle1|\left(\alpha|0\rangle+\beta|1\rangle\right) \\
&=U|0\rangle\left(\alpha\underbrace{\langle0|0\rangle}_{=1}+\beta\underbrace{\langle0|1\rangle}_{=0}\right)+U|1\rangle\left(\alpha\underbrace{\langle1|0\rangle}_{=0}+\beta\underbrace{\langle1|1\rangle}_{=1}\right) \\
&=\alpha\,U|0\rangle+\beta\,U|1\rangle
\end{aligned} \tag{5}

式(5)のとおり、$\langle0|$ は $|\psi\rangle$ における $|0\rangle$ の係数 $\alpha$ だけを、$\langle1|$ は $|1\rangle$ の係数 $\beta$ だけを取り出し、その係数が左側の $U|0\rangle$、$U|1\rangle$ にかかります。式(4)は、この「$|\psi\rangle$ に作用させると、$|0\rangle$ の成分を $U|0\rangle$ へ、$|1\rangle$ の成分を $U|1\rangle$ へ送る」という内容をそのまま式にしたものです。例えば $X$ ゲートは、$|\psi\rangle$ に作用させると、$|0\rangle$ の成分を $|1\rangle$ に、$|1\rangle$ の成分を $|0\rangle$ に送るので、$X=|1\rangle\langle0|+|0\rangle\langle1|$ と書けます。

次の表は、代表的な1量子ビットゲートを、行列・ブラケット・回路図の形で並べたものです。

ゲート	行列	ブラケット（外積）表記	回路図
$X$	$\begin{pmatrix}0&1\cr 1&0\end{pmatrix}$	$\vert0\rangle\langle1\vert+\vert1\rangle\langle0\vert$
$Y$	$\begin{pmatrix}0&-i\cr i&0\end{pmatrix}$	$-i\vert0\rangle\langle1\vert+i\vert1\rangle\langle0\vert$
$Z$	$\begin{pmatrix}1&0\cr 0&-1\end{pmatrix}$	$\vert0\rangle\langle0\vert-\vert1\rangle\langle1\vert$
$H$	$\dfrac{1}{\sqrt2}\begin{pmatrix}1&1\cr 1&-1\end{pmatrix}$	$\vert+\rangle\langle0\vert+\vert-\rangle\langle1\vert$
$S$	$\begin{pmatrix}1&0\cr 0&i\end{pmatrix}$	$\vert0\rangle\langle0\vert+i\vert1\rangle\langle1\vert$
$T$	$\begin{pmatrix}1&0\cr 0&e^{i\pi/4}\end{pmatrix}$	$\vert0\rangle\langle0\vert+e^{i\pi/4}\vert1\rangle\langle1\vert$
$P(\varphi)$	$\begin{pmatrix}1&0\cr 0&e^{i\varphi}\end{pmatrix}$	$\vert0\rangle\langle0\vert+e^{i\varphi}\vert1\rangle\langle1\vert$
$R_x(\theta)$	$\begin{pmatrix}c&-is\cr -is&c\end{pmatrix}$	$c(\vert0\rangle\langle0\vert+\vert1\rangle\langle1\vert)-is(\vert0\rangle\langle1\vert+\vert1\rangle\langle0\vert)$
$R_y(\theta)$	$\begin{pmatrix}c&-s\cr s&c\end{pmatrix}$	$c(\vert0\rangle\langle0\vert+\vert1\rangle\langle1\vert)-s\vert0\rangle\langle1\vert+s\vert1\rangle\langle0\vert$
$R_z(\theta)$	$\begin{pmatrix}e^{-i\theta/2}&0\cr 0&e^{i\theta/2}\end{pmatrix}$	$e^{-i\theta/2}\vert0\rangle\langle0\vert+e^{i\theta/2}\vert1\rangle\langle1\vert$

表中の $c=\cos\frac{\theta}{2}$、$s=\sin\frac{\theta}{2}$ です。各ゲートの呼び方と作用を整理しておきます。

ゲート	呼び方	作用
$X$	パウリ $X$ ゲート、NOT ゲート、ビット反転ゲート（古典の NOT に相当）	$\vert0\rangle\to\vert1\rangle$、$\vert1\rangle\to\vert0\rangle$。成分の入れ替え
$Y$	パウリ $Y$ ゲート（$Y=iXZ$）	$\vert0\rangle\to i\vert1\rangle$、$\vert1\rangle\to-i\vert0\rangle$（ビット反転と位相反転の両方を起こす）。成分の入れ替えと位相の埋め込み
$Z$	パウリ $Z$ ゲート、位相反転ゲート	$\vert1\rangle$ の符号だけを反転する（z 軸の周りに $\pi$ 回す）。位相の埋め込み
$H$	アダマールゲート	$\vert0\rangle\to\vert+\rangle$、$\vert1\rangle\to\vert-\rangle$（計算基底と $\vert\pm\rangle$ を相互に変換する。重ね合わせを作る・干渉させるときに使う）。成分の混合
$S$	$S$ ゲート、$\sqrt{Z}$ ゲート（$S^2=Z$）	$\vert1\rangle$ に $i$ を掛ける（z 軸の周りに $\pi/2$ 回す）。位相の埋め込み
$T$	$T$ ゲート（$T^2=S$）	$\vert1\rangle$ に $e^{i\pi/4}$ を掛ける（z 軸の周りに $\pi/4$ 回す）。位相の埋め込み
$P(\varphi)$	位相ゲート（$Z=P(\pi)$、$S=P(\pi/2)$、$T=P(\pi/4)$）	$\vert1\rangle$ に任意の位相 $e^{i\varphi}$ を掛ける（z 軸の周りに $\varphi$ 回す）。位相の埋め込み
$R_x,R_y,R_z$	回転ゲート	ブロッホ球の x 軸・y 軸・z 軸の周りに回す（後の節で説明）。$R_x,R_y$：混合から入れ替えまで、$R_z$：位相の埋め込み

表中の「z 軸の周りに〜回す」は、グローバル位相を除いた説明です。

行列は成分の数字が一目で分かり、ブラケットは各基底がどこへ行くかが一目で分かります。

X・Y・Z・H ゲートの性質

上の表のゲートのうち、$X,Y,Z,H$ は、2回かけると元に戻ります。

X^2=Y^2=Z^2=H^2=I \tag{6}

つまり、これらのゲートは自分自身が逆演算になっています。例えば $H|0\rangle=|+\rangle$ にもう一度 $H$ をかけると $|0\rangle$ に戻るので、$H$ が計算基底と $|\pm\rangle$ を相互に変換することが分かります。

量子フーリエ変換（QFT）は、$n$ 量子ビットの $N=2^n$ 個の計算基底の確率振幅の列に離散フーリエ変換（DFT）をかけて、新しい確率振幅の列に写すユニタリ変換です。1量子ビット（$n=1$、$N=2$）の QFT は $H$ ゲートに一致します。この場合は、次のように確率振幅の和と差を作ることになります。

a_0|0\rangle+a_1|1\rangle\ \mapsto\ \frac{a_0+a_1}{\sqrt2}|0\rangle+\frac{a_0-a_1}{\sqrt2}|1\rangle \tag{7}

つまり $H$ ゲートは、$|0\rangle$ と $|1\rangle$ の確率振幅を足し引きして干渉させる操作です。$|\pm\rangle$ が $|0\rangle,|1\rangle$ に変わるのも、この足し引きの結果です。2量子ビット以上のQFTは、$H$ のような1量子ビットゲートだけでは作れず、制御位相ゲート（後述の $\mathrm{CP}$）のような2量子ビットゲートも必要になります。

回転ゲート

パウリ行列 $\sigma=X,Y,Z$ は、式(6)のとおり $\sigma^2=I$ を満たします。この性質のおかげで、$\sigma$ を指数の肩に載せた $e^{-i\theta\sigma/2}$ は、次のように $I$ と $\sigma$ の和で書けます。

R_x(\theta)=e^{-i\theta X/2}=\cos\frac{\theta}{2}\,I-i\sin\frac{\theta}{2}\,X \tag{8}

$R_y(\theta)$、$R_z(\theta)$ も同様に、式(8)の $X$ を $Y$、$Z$ に置き換えたものです。これらが回転ゲート（回転演算子）で、ブロッホ球の x 軸・y 軸・z 軸の周りに角度 $\theta$ だけ回す操作にあたります。

回転ゲートについて、押さえておきたい点が4つあります。

• 角度が半分で入る：ブロッホ球で $\theta$ 回すとき、行列の中には $\theta/2$ が現れます。$\theta=2\pi$ まで回すと行列は $-I$ になり、グローバル位相が違うだけで、ブロッホ球上の点は元に戻ります。
• 混合と位相の埋め込み：$R_x,R_y$ は、角度によって成分の混合から入れ替えまで変わります。2つの係数を混ぜ合わせるので、測定確率が変わります（例：$R_x(\theta)|0\rangle=\cos\frac{\theta}{2}|0\rangle-i\sin\frac{\theta}{2}|1\rangle$）。一方、$R_z$ は位相の埋め込みで、$|0\rangle,|1\rangle$ の係数に位相を掛けるだけなので、計算基底での測定確率は変わりません。
• 位相ゲートとの関係：$R_z$ は位相ゲート $P(\theta)$ とグローバル位相 $e^{-i\theta/2}$ だけ違うので（式(9)）、実質的に $P(\theta)$ と同じ操作です。そのため $Z$、$S$、$T$ は、グローバル位相を除いて、それぞれ z 軸の周りに $\pi$、$\pi/2$、$\pi/4$ 回す $R_z$ と同じです（例：$T=e^{i\pi/8}R_z(\pi/4)$）。
• 半回転でパウリ行列になる：$\theta=\pi$ のとき、パウリ行列の $-i$ 倍になります（式(10)）。グローバル位相を除けば、$R_x(\pi)$ は $X$、$R_y(\pi)$ は $Y$、$R_z(\pi)$ は $Z$ と同じ操作です。

R_z(\theta)=e^{-i\theta/2}P(\theta) \tag{9}

R_x(\pi)=-iX,\qquad R_y(\pi)=-iY,\qquad R_z(\pi)=-iZ \tag{10}

複数量子ビットのゲート

ここまでは1量子ビットのゲートでした。2量子ビット以上のゲートも、表記の考え方は同じです。行列は $2^n\times2^n$ になるので、基底の並びを決めておきます。2量子ビットでは $|00\rangle,|01\rangle,|10\rangle,|11\rangle$ の順に並べ、左側を制御量子ビット、右側を標的量子ビットとします。回路図では、上の線を制御量子ビットとして描きます。

複数量子ビットの状態や演算は、テンソル積 $\otimes$ で書きます。$|a\rangle\otimes|b\rangle$ は、1つ目の量子ビットが $|a\rangle$、2つ目が $|b\rangle$ の状態で、$|a,b\rangle$ や $|ab\rangle$ とも書きます。演算についても、1つ目に $A$、2つ目に $B$ を作用させる演算を $A\otimes B$ と書き、次の性質があります。

(A\otimes B)\left(|a\rangle\otimes|b\rangle\right)=A|a\rangle\otimes B|b\rangle \tag{11}

つまり、各量子ビットに、それぞれの演算を別々にかけるだけです。例えば $I\otimes X$ は、1つ目には何もせず、2つ目に $X$ をかける演算です。

複数量子ビットのゲートで基本になるのは、制御量子ビットが $|1\rangle$ のときだけ標的量子ビットに $U$ をかける制御付きゲートです。ブラケットでは、次のように書けます。

C(U)=|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes U \tag{12}

$|0\rangle\langle0|\otimes I$ は「制御に $|0\rangle\langle0|$、標的に $I$ を作用させる」演算で、順序を入れ替えた $I\otimes|0\rangle\langle0|$ では制御と標的の役割が逆になります。実際に $|a,b\rangle$ に作用させると、式(11)と $\langle i|a\rangle=\delta_{ia}$（$i=a$ のとき1、それ以外は0）より、次のようになります。

\begin{aligned}
C(U)|a,b\rangle&=\left(|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes U\right)\left(|a\rangle\otimes|b\rangle\right)\\
&=\left(|0\rangle\langle0|a\rangle\right)\otimes\left(I|b\rangle\right)+\left(|1\rangle\langle1|a\rangle\right)\otimes\left(U|b\rangle\right)\\
&=\langle0|a\rangle\,|0\rangle\otimes|b\rangle+\langle1|a\rangle\,|1\rangle\otimes U|b\rangle\\
&=\begin{cases}|0\rangle\otimes|b\rangle & (a=0)\\ |1\rangle\otimes U|b\rangle & (a=1)\end{cases}
\end{aligned} \tag{13}

$U=X$ なら $\mathrm{CNOT}$（制御 $X$ ゲート）、$U=Z$ なら $\mathrm{CZ}$ です。例えば $\mathrm{CNOT}$ では、$|1,0\rangle\to|1\rangle\otimes X|0\rangle=|1,1\rangle$ となります。代表的なゲートを、行列・ブラケット・回路図の形で並べます。

ゲート	行列	ブラケット（外積）表記	回路図
$\mathrm{CNOT}$ ($\mathrm{CX}$)	$\begin{pmatrix}1&0&0&0\cr 0&1&0&0\cr 0&0&0&1\cr 0&0&1&0\end{pmatrix}$	$\vert0\rangle\langle0\vert\otimes I+\vert1\rangle\langle1\vert\otimes X$
$\mathrm{CZ}$	$\mathrm{diag}(1,1,1,-1)$	$\vert0\rangle\langle0\vert\otimes I+\vert1\rangle\langle1\vert\otimes Z$
$\mathrm{CP}(\varphi)$	$\mathrm{diag}(1,1,1,e^{i\varphi})$	$\vert0\rangle\langle0\vert\otimes I+\vert1\rangle\langle1\vert\otimes P(\varphi)$
$\mathrm{SWAP}$	$\begin{pmatrix}1&0&0&0\cr 0&0&1&0\cr 0&1&0&0\cr 0&0&0&1\end{pmatrix}$	$\vert00\rangle\langle00\vert+\vert10\rangle\langle01\vert+\vert01\rangle\langle10\vert+\vert11\rangle\langle11\vert$
$\mathrm{Toffoli}$($\mathrm{CCNOT}$)	$\begin{pmatrix}I_6&0\cr 0&X\end{pmatrix}$（$8\times8$）	$(I_4-\vert11\rangle\langle11\vert)\otimes I+\vert11\rangle\langle11\vert\otimes X$

各ゲートの呼び方と作用を整理しておきます。

ゲート	呼び方	作用
$\mathrm{CNOT}$	Controlled-NOT（制御 NOT）の略。	$\vert a,b\rangle\to\vert a,b\oplus a\rangle$（$\oplus$ は排他的論理和）。標的に NOT ゲート（$X$）を使った制御付きゲート。成分の入れ替え
$\mathrm{CZ}$	Controlled-Z（制御 Z）の略	$\vert a,b\rangle\to(-1)^{ab}\vert a,b\rangle$。標的に $Z$ を使った制御付きゲート。位相の埋め込み
$\mathrm{CP}(\varphi)$	Controlled-Phase（制御位相ゲート）の略。	$\vert a,b\rangle\to e^{i\varphi ab}\vert a,b\rangle$（$\mathrm{CZ}=\mathrm{CP}(\pi)$）。標的に $P(\varphi)$ を使った制御付きゲート。位相の埋め込み
$\mathrm{SWAP}$	スワップ（入れ替え）ゲート	$\vert a,b\rangle\to\vert b,a\rangle$。成分の入れ替え
$\mathrm{Toffoli}$	$\mathrm{CCNOT}$ とも呼ぶ。Controlled-Controlled-NOT（制御が2つの NOT）の略	$\vert a,b,c\rangle\to\vert a,b,c\oplus ab\rangle$。成分の入れ替え

$\mathrm{CZ}$ は制御と標的を入れ替えても同じゲートになります。これは、作用 $|a,b\rangle\to(-1)^{ab}|a,b\rangle$ の位相 $(-1)^{ab}$ が、$a$ と $b$ について対称だからです。

例えば $|+\rangle|+\rangle$ に $\mathrm{CZ}$ をかけると、次のようになります。

\mathrm{CZ}\,|+\rangle|+\rangle=\mathrm{CZ}\,\frac{|00\rangle+|01\rangle+|10\rangle+|11\rangle}{2}=\frac{|00\rangle+|01\rangle+|10\rangle-|11\rangle}{2} \tag{14}

式(14)の右辺を、制御量子ビットの値ごとにまとめると、次のように書けます。

\frac{|00\rangle+|01\rangle+|10\rangle-|11\rangle}{2}=\frac{1}{\sqrt2}\left(|0\rangle|+\rangle+|1\rangle|-\rangle\right) \tag{15}

制御が $|0\rangle$ の成分では標的は $|+\rangle$ のまま、$|1\rangle$ の成分では標的が $|-\rangle$ に変わっています。$|11\rangle$ に付いた符号（位相）が、標的の状態の違いとして現れているわけです。この状態は1量子ビットずつの状態の積に分けられない、もつれた状態です。

また、$\mathrm{CZ}$ は $\mathrm{CNOT}$ の標的を $H$ ではさんだもの（$\mathrm{CZ}=(I\otimes H)\mathrm{CNOT}(I\otimes H)$）に等しくなります。これは $HXH=Z$ から分かります。

$\mathrm{CNOT}$ と $\mathrm{Toffoli}$ は、古典の可逆な論理ゲート（出力から入力が一意に決まるゲート）でもあります。例えば通常の AND は、出力が0のとき入力が $(0,0),(0,1),(1,0)$ のどれか分からないので、可逆ではありません。$\mathrm{Toffoli}$ ゲートは、入力 $a,b$ をそのまま出力に残すので可逆です。標的 $c$ を $0$ にして入力すると標的に AND（$ab$）が、$1$ にして入力すると NAND（$ab$ の否定）が現れます。NAND があれば任意の古典の論理回路が作れるため、補助ビット（$0$ や $1$ に固定した入力）を使えば、古典の可逆回路は $\mathrm{Toffoli}$ ゲートだけで作れることが知られています。

量子複製不可能定理

$\mathrm{CNOT}$ は、標的が $|0\rangle$ のとき、制御の値を標的にコピーしているように見えます（$|a\rangle|0\rangle\to|a\rangle|a\rangle$、$a=0,1$）。しかし、制御が重ね合わせ状態 $\alpha|0\rangle+\beta|1\rangle$ の場合、$\mathrm{CNOT}$ を作用させた結果は $\alpha|00\rangle+\beta|11\rangle$ となり、コピーした状態 $(\alpha|0\rangle+\beta|1\rangle)(\alpha|0\rangle+\beta|1\rangle)$ とは一致しません（$\alpha,\beta$ の一方が0の場合を除く）。

実は、これは $\mathrm{CNOT}$ に限った話ではありません。量子複製不可能定理（クローン禁止定理、no-cloning theorem）は、任意の未知の状態 $|\psi\rangle$ に対して $|\psi\rangle|0\rangle\to|\psi\rangle|\psi\rangle$ となるユニタリ操作は存在しない、という定理です。

これは、式(2)の内積の保存から分かります。そのようなユニタリ $U$ があったとして、2つの状態 $|\phi\rangle,|\psi\rangle$ をコピーする前と後で内積を比べると、次のようになります。

\langle\phi|\psi\rangle=\left(\langle\phi|\langle0|\right)U^\dagger U\left(|\psi\rangle|0\rangle\right)=\left(\langle\phi|\langle\phi|\right)\left(|\psi\rangle|\psi\rangle\right)=\langle\phi|\psi\rangle^2 \tag{16}

これを満たすのは、$\langle\phi|\psi\rangle$ が0か1のとき、つまり2つの状態が直交しているか、同じ状態のときだけです。$|0\rangle$ と $|1\rangle$ のように互いに直交する状態どうしならコピーできますが（$\mathrm{CNOT}$ がその例です）、任意の状態をコピーするユニタリは作れません。古典のビットは自由にコピーできますが、量子ビットではそれができません。

ユニバーサルゲートセット

ここまでに見たゲートを組み合わせると、どんな量子操作でも作れるのか、という疑問が出てきます。この問いに答えるのが、ユニバーサルゲートセット（万能ゲート集合、universal gate set）です。

ユニバーサルゲートセットとは、任意のユニタリ操作を、有限個のゲートの並びで好きな精度まで近似できるゲートの集合のことです。有限種類のゲートの並びでは、すべてのユニタリ操作を厳密には作れないため、通常は近似で定義します。代表的なゲートの組を、次の表にまとめます。

ゲートの組	万能か	備考
回転ゲート $R_x,R_y,R_z$、$\mathrm{CNOT}$	万能	よく使われる組。角度を連続的に選べるので、任意のユニタリを（グローバル位相を除いて）近似でなく厳密に作れる
$H$、$S$、$\mathrm{CNOT}$（Clifford ゲート）	万能でない	古典計算機で効率よくシミュレートできる（後述）
$H$、$S$、$T$、$\mathrm{CNOT}$	万能	Clifford ゲートに $T$ ゲートを加えたもの。$T$ は非 Clifford ゲート
$\mathrm{Toffoli}$	古典の可逆計算には万能。量子計算には万能でない	単独では量子操作を作れない

$H$、$S$、$T$、$\mathrm{CNOT}$ の4つは、有限種類のゲートだけで万能になる組です。ここまでに見たゲートが、そのまま万能な組の部品になっています。

Clifford ゲート

表に出てきた Clifford ゲートとは、$n$ 量子ビットのパウリ行列のテンソル積 $Q$（例：$X\otimes Z$）に対して、$UQU^\dagger$ が再び、符号 $\pm$ を除いてパウリ行列のテンソル積になるゲート $U$ のことです。$H$、$S$、$\mathrm{CNOT}$ の3つを組み合わせると、グローバル位相を除いて、Clifford ゲートはすべて作れます。パウリゲート $X,Y,Z$ も Clifford ゲートに含まれます。一方、$T$ ゲートは含まれません。

この性質は、実際に計算して確かめられます。$H$ と $S$ は、$X,Y,Z$ を次のように、符号を除いてパウリ行列に移します。

\begin{aligned}
HXH^\dagger&=Z, & HYH^\dagger&=-Y, & HZH^\dagger&=X\\
SXS^\dagger&=Y, & SYS^\dagger&=-X, & SZS^\dagger&=Z
\end{aligned} \tag{17}

$\mathrm{CNOT}$ は、2量子ビットのパウリ積を次のように移します（1つ目が制御、2つ目が標的）。

\begin{aligned}
\mathrm{CNOT}\,(X\otimes I)\,\mathrm{CNOT}^\dagger&=X\otimes X, & \mathrm{CNOT}\,(I\otimes X)\,\mathrm{CNOT}^\dagger&=I\otimes X\\
\mathrm{CNOT}\,(Z\otimes I)\,\mathrm{CNOT}^\dagger&=Z\otimes I, & \mathrm{CNOT}\,(I\otimes Z)\,\mathrm{CNOT}^\dagger&=Z\otimes Z
\end{aligned} \tag{18}

パウリ行列は $X$ と $Z$ の積で書け（$Y=iXZ$）、$U(Q_1Q_2)U^\dagger=(UQ_1U^\dagger)(UQ_2U^\dagger)$ が成り立つので、各量子ビットの $X$ と $Z$ について確認すれば十分です。また、ゲートを続けてかけても、$(VU)Q(VU)^\dagger=V(UQU^\dagger)V^\dagger$ のように、パウリ積から次のパウリ積へ移るだけなので、性質は保たれます。

一方、$T$ ゲートは、次のようにパウリ行列の1つではなく、$X$ と $Y$ の和になってしまいます。

TXT^\dagger=\frac{X+Y}{\sqrt2} \tag{19}

一方、Clifford ゲートだけでは、ユニバーサルゲートセットになりません。量子ビット数を決めると、Clifford ゲートで作れるゲートは有限個（1量子ビットでは、グローバル位相を除いて24個）なので、任意のゲートには近づけないためです。

さらに、量子優位性の面でも限界があります。Gottesman–Knill の定理によると、次の3つだけからなる量子回路は、古典計算機で効率よくシミュレートできます。

• 計算基底の状態で、量子ビットを準備する
• Clifford ゲートをかける
• 計算基底で測定する

「効率よく」とは、量子ビットが増えても、古典計算機で、現実的な時間で計算できる、という意味です。一般の量子回路では、量子ビットが1つ増えるごとに状態ベクトルの成分数が2倍になるため、古典計算機での計算はすぐに困難になります。Clifford ゲートには $H$ や $\mathrm{CNOT}$ が含まれ、重ね合わせやもつれ状態も作れます。それでも効率よく計算できるのは、式(17)、式(18)のとおり、Clifford ゲートがパウリ積をパウリ積に移すためです。状態を、その状態を変えないパウリ積の組（$n$ 量子ビットなら $n$ 個。例えば $|00\rangle$ は $Z\otimes I$ と $I\otimes Z$）で表しておけば、$2^n$ 個の成分を追う代わりに、$n$ 個のパウリ積の移り先だけを追えば済みます。

つまり、Clifford ゲートだけでは、ユニバーサルでないだけでなく、量子優位性も得られません。したがって、量子計算が古典計算を上回るには、$T$ ゲートのような、Clifford の範囲を超える要素（非 Clifford ゲート）が必要です。ほかに、Clifford ゲートだけでは作れない特殊な状態を用意して使う方法もあります。さらに、Clifford ゲートに $T$ ゲートを加えた $H$、$S$、$T$、$\mathrm{CNOT}$ の組は、ユニバーサルゲートセットにもなります。

有限種類のゲートで任意のゲートを近似する

ユニバーサルゲートセットは、有限種類のゲートの並びで任意のユニタリ操作を近似できる集合でした。では、精度を上げるとき、必要なゲート数はどれだけ増えるのでしょうか。これに答えるのが Solovay–Kitaev の定理です。

$\mathrm{SU}(2)$（特殊ユニタリ群：行列式が1の $2\times2$ ユニタリ行列全体）は、グローバル位相を除いた1量子ビットゲート全体にあたります。1量子ビットゲートの有限集合（逆のゲートも含めるものとします）が、$\mathrm{SU}(2)$ の中で稠密な部分群を生成するとします。「稠密」とは、$\mathrm{SU}(2)$ のどの1量子ビットゲートにも、その集合のゲートを続けてかけたもので、いくらでも近づける、という意味です。

このとき、任意の1量子ビットゲートを、好きな誤差 $\epsilon$ 以内で近似するゲート列が、その集合のゲートだけで作れます。必要なゲート数は、$\log(1/\epsilon)$ の多項式程度（$O(\log^c(1/\epsilon))$、$c$ は定数）にしか増えません。つまり、精度の桁数を増やしても、ゲート数は桁数の多項式程度で済みます。そのゲート列は、古典計算機で効率よく見つけられます。これが Solovay–Kitaev の定理です。この定理のおかげで、有限種類のゲートを実装すれば、任意の1量子ビットゲートを、現実的なゲート数で近似として実現できます。

さらに、任意の多量子ビットゲートは、1量子ビットゲートと $\mathrm{CNOT}$ の組み合わせで厳密に作れることが知られています。そこで、その1量子ビットゲートの部分を、この定理で有限集合のゲート列に置き換えれば、有限集合のゲートと $\mathrm{CNOT}$ だけで、任意の量子ゲートを近似できます。

最後に

本記事では、次の5点を確認しました。

1. ユニタリ演算子：量子ゲートはユニタリ演算子で表され、$U^\dagger U=I$ から、ベクトルの長さと内積が保たれる
2. ゲートの種類と表記：ゲートは、成分の入れ替え・位相の埋め込み・成分の混合の3種類に整理でき、行列・ブラケット・回路図のいずれでも書ける
3. 代表的な1量子ビットゲート：$X,Y,Z,H$ は2回かけると元に戻り、$S,T$ は位相ゲート $P(\varphi)$ の特別な場合（$S=P(\pi/2)$、$T=P(\pi/4)$）。回転ゲートは角度の半分が行列に入り、$\theta=\pi$ でパウリ行列の $-i$ 倍になる
4. 複数量子ビットのゲート：制御付きゲートが基本で、$\mathrm{CNOT}$・$\mathrm{CZ}$・$\mathrm{SWAP}$・$\mathrm{Toffoli}$（$\mathrm{CCNOT}$）が代表的。未知の量子状態はコピーできない（量子複製不可能定理）
5. ユニバーサルゲートセット：Clifford ゲート（$H$、$S$、$\mathrm{CNOT}$）だけでは万能でなく、$T$ ゲートを加えると万能になる

最後まで読んでいただきありがとうございました。ご質問やご指摘等ありましたらコメントまでお願いいたします。

参考文献

• 宮野健次郎, 古澤明, 『量子コンピュータ入門 第2版』, 日本評論社
• 嶋田義皓, 『量子コンピューティング 基本アルゴリズムから量子機械学習まで』, 情報処理学会出版委員会 監修, オーム社