1-3. 複数量子ビットの記述¶

ここまでは１量子ビットの状態とその操作（演算）の記述について学んできた。この章の締めくくりとして、$n$個の量子ビットがある場合の状態の記述について学んでいこう。テンソル積がたくさん出てきてややこしいが、コードをいじりながら身につけていってほしい。

$n$個の古典ビットの状態は$n$個の$0,1$の数字によって表現され、そのパターンの総数は$2^n$個ある。量子力学では、これらすべてのパターンの重ね合わせ状態が許されているので、$n$個の量子ビットの状態$|\psi \rangle$はどのビット列がどのような重みで重ね合わせになっているかという$2^n$個の複素確率振幅で記述される：

\[\begin{split}\begin{eqnarray} |\psi \rangle &= & c_{00...0} |00...0\rangle + c_{00...1} |00...1\rangle + \cdots + c_{11...1} |11...1\rangle = \left( \begin{array}{c} c_{00...0} \\ c_{00...1} \\ \vdots \\ c_{11...1} \end{array} \right). \end{eqnarray}\end{split}\]

ただし、複素確率振幅は規格化 $\sum _{i_1,..., i_n} |c_{i_1...i_n}|^2=1$ されているものとする。

そして、この$n$量子ビットの量子状態を測定するとビット列$i_1 ... i_n$が確率

\[\begin{eqnarray} p_{i_1 ... i_n} &=&|c_{i_1 ... i_n}|^2 \label{eq02} \end{eqnarray}\]

でランダムに得られ、測定後の状態は$|i_1 \dotsc i_n\rangle$となる。

このように$n$量子ビットの状態は、$n$に対して指数的に大きい$2^n$次元の複素ベクトルで記述する必要があり、ここに古典ビットと量子ビットの違いが顕著に現れる。そして、$n$量子ビット系に対する操作は$2^n \times 2^n$次元のユニタリ行列として表される。

言ってしまえば、量子コンピュータとは、量子ビット数に対して指数的なサイズの複素ベクトルを、物理法則に従ってユニタリ変換するコンピュータのことなのである。

※ここで、複数量子ビットの順番と表記の関係について注意しておく。状態をケットで記述する際に、「1番目」の量子ビット、「2番目」の量子ビット、……の状態に対応する0と1を左から順番に並べて表記した。例えば$|011\rangle$と書けば、1番目の量子ビットが0、2番目の量子ビットが1、3番目の量子ビットが1である状態を表す。一方、例えば011を2進数の表記と見た場合、上位ビットが左、下位ビットが右となることに注意しよう。すなわち、一番左の0は最上位ビットであって$2^2$の位に対応し、真ん中の1は$2^1$の位、一番右の1は最下位ビットであって$2^0=1$の位に対応する。つまり、「$i$番目」の量子ビットは、$n$桁の2進数表記の$n-i+1$桁目に対応している。このことは、SymPyなどのパッケージで複数量子ビットを扱う際に気を付ける必要がある（下記「SymPyを用いた演算子のテンソル積」も参照）。

(詳細は Nielsen-Chuang の 1.2.1 Multiple qbits を参照)

例：2量子ビットの場合¶

2量子ビットの場合は、 00, 01, 10, 11 の4通りの状態の重ね合わせをとりうるので、その状態は一般的に

\[\begin{split}c_{00} |00\rangle + c_{01} |01\rangle + c_{10}|10\rangle + c_{11} |11\rangle = \left( \begin{array}{c} c_{00} \\ c_{01} \\ c_{10} \\ c_{11} \end{array} \right)\end{split}\]

とかける。

このような2量子ビットに作用する演算としてもっとも重要なのが制御NOT演算（CNOT演算）であり、行列表示では

\[\begin{split}\begin{eqnarray} \Lambda(X) = \left( \begin{array}{cccc} 1 & 0 & 0& 0 \\ 0 & 1 & 0& 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1& 0 \end{array} \right) \end{eqnarray}\end{split}\]

となる。

CNOT演算が2つの量子ビットにどのように作用するか見てみよう。まず、1つ目の量子ビットが$|0\rangle$の場合、$c_{10} = c_{11} = 0$なので、

\[\begin{split}\Lambda(X) \left( \begin{array}{c} c_{00}\\ c_{01}\\ 0\\ 0 \end{array} \right) = \left( \begin{array}{c} c_{00}\\ c_{01}\\ 0\\ 0 \end{array} \right)\end{split}\]

となり、状態は変化しない。一方、1つ目の量子ビットが$|1\rangle$の場合、$c_{00} = c_{01} = 0$なので、

\[\begin{split}\Lambda(X) \left( \begin{array}{c} 0\\ 0\\ c_{10}\\ c_{11} \end{array} \right) = \left( \begin{array}{c} 0\\ 0\\ c_{11}\\ c_{10} \end{array} \right)\end{split}\]

となり、$|10\rangle$と$|11\rangle$の確率振幅が入れ替わる。すなわち、2つ目の量子ビットが反転している。

つまり、CNOT演算は１つ目の量子ビットをそのままに保ちつつ、

１つ目の量子ビットが$|0\rangle$の場合は、２つ目の量子ビットにも何もしない（恒等演算$I$が作用）
１つ目の量子ビットが$|1\rangle$の場合は、２つ目の量子ビットを反転させる（$X$が作用）

という効果を持つ。そこで、１つ目の量子ビットを制御量子ビット、２つ目の量子ビットをターゲット量子ビットと呼ぶ。

このCNOT演算の作用は、$\oplus$を mod 2の足し算、つまり古典計算における排他的論理和（XOR）とすると、

\[\begin{eqnarray} \Lambda(X) |ij \rangle = |i \;\; (i\oplus j)\rangle \:\:\: (i,j=0,1) \end{eqnarray}\]

とも書ける。よって、CNOT演算は古典計算でのXORを可逆にしたものとみなせる（ユニタリー行列は定義$U^\dagger U = U U^\dagger = I$より可逆であることに注意）。例えば、１つ目の量子ビットを$|0\rangle$と$|1\rangle$の重ね合わせ状態にし、２つ目の量子ビットを$|0\rangle$として

\[\begin{split}\begin{eqnarray} \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle )\otimes |0\rangle = \frac{1}{\sqrt{2}} \left( \begin{array}{c} 1 \\ 0 \\ 1 \\ 0 \end{array} \right) \end{eqnarray}\end{split}\]

にCNOTを作用させると、

\[\begin{split}\begin{eqnarray} \frac{1}{\sqrt{2}}( |00\rangle + |11\rangle ) = \frac{1}{\sqrt{2}} \left( \begin{array}{c} 1 \\ 0 \\ 0 \\ 1 \end{array} \right) \end{eqnarray}\end{split}\]

が得られ、2つ目の量子ビットがそのままである状態$|00\rangle$と反転された状態$|11\rangle$の重ね合わせになる。（記号$\otimes$については次節参照）

さらに、CNOT ゲートを組み合わせることで重要な2量子ビットゲートであるSWAP ゲートを作ることができる。

\[\Lambda(X)_{i,j}\]

を$i$番目の量子ビットを制御、$j$番目の量子ビットをターゲットとするCNOT ゲートとして、

\[\begin{split}\begin{align} \mathrm{SWAP} &= \Lambda(X)_{1,2} \Lambda(X)_{2,1} \Lambda(X)_{1,2}\\ &= \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right) \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right) \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right)\\ &= \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right) \end{align}\end{split}\]

のように書ける。これは1 番目の量子ビットと2 番目の量子ビットが交換するゲートであることが分かる。

このことは、上記のmod 2の足し算$\oplus$を使った表記で簡単に確かめることができる。3つのCNOTゲート$\Lambda(X)_{1,2} \Lambda(X)_{2,1} \Lambda(X)_{1,2}$の$|ij\rangle$への作用を1ステップずつ書くと、$i \oplus (i \oplus j) = (i \oplus i) \oplus j = 0 \oplus j = j$であることを使って、

\[\begin{split}\begin{align} |ij\rangle &\longrightarrow |i \;\; (i\oplus j)\rangle\\ &\longrightarrow |(i\oplus (i\oplus j)) \;\; (i\oplus j)\rangle = |j \;\; (i\oplus j)\rangle\\ &\longrightarrow |j \;\; (j\oplus (i\oplus j))\rangle = |ji\rangle \end{align}\end{split}\]

となり、2つの量子ビットが交換されていることが分かる。

(詳細は Nielsen-Chuang の 1.3.2 Multiple qbit gates を参照)

テンソル積の計算¶

手計算や解析計算で威力を発揮するのは、テンソル積（$\otimes$）である。これは、複数の量子ビットがある場合に、それをどのようにして、上で見た大きな一つのベクトルへと変換するのか？という計算のルールを与えてくれる。

量子力学の世界では、２つの量子系があってそれぞれの状態が$|\psi \rangle$と$|\phi \rangle$のとき、

\[|\psi \rangle \otimes |\phi\rangle\]

とテンソル積 $\otimes$ を用いて書く。このような複数の量子系からなる系のことを複合系と呼ぶ。例えば２量子ビット系は複合系である。

基本的にはテンソル積は、多項式と同じような計算ルールで計算してよい。例えば、

のように計算する。列ベクトル表示すると、$|00\rangle$, $|01\rangle$, $|10\rangle$, $|11\rangle$に対応する4次元ベクトル、

\[\begin{split}\left( \begin{array}{c} \alpha \\ \beta \end{array} \right) \otimes \left( \begin{array}{c} \gamma \\ \delta \end{array} \right) = \left( \begin{array}{c} \alpha \gamma \\ \alpha \delta \\ \beta \gamma \\ \beta \delta \end{array} \right)\end{split}\]

を得る計算になっている。

SymPyを用いたテンソル積の計算¶

[8]:

from IPython.display import Image, display_png
from sympy import *
from sympy.physics.quantum import *
from sympy.physics.quantum.qubit import Qubit,QubitBra
from sympy.physics.quantum.gate import X,Y,Z,H,S,T,CNOT,SWAP, CPHASE
init_printing() # ベクトルや行列を綺麗に表示するため

[3]:

a,b,c,d = symbols('alpha,beta,gamma,delta')
psi = a*Qubit('0')+b*Qubit('1')
phi = c*Qubit('0')+d*Qubit('1')

[4]:

TensorProduct(psi, phi) #テンソル積

[4]:

$$\left({\alpha {\left|0\right\rangle } + \beta {\left|1\right\rangle }}\right)\otimes \left({\delta {\left|1\right\rangle } + \gamma {\left|0\right\rangle }}\right)$$

[5]:

represent(TensorProduct(psi, phi))

[5]:

$$\left[\begin{matrix}\alpha \gamma\\\alpha \delta\\\beta \gamma\\\beta \delta\end{matrix}\right]$$

さらに$|\psi\rangle$とのテンソル積をとると８次元のベクトルになる：

[6]:

represent(TensorProduct(psi,TensorProduct(psi, phi)))

[6]:

$$\left[\begin{matrix}\alpha^{2} \gamma\\\alpha^{2} \delta\\\alpha \beta \gamma\\\alpha \beta \delta\\\alpha \beta \gamma\\\alpha \beta \delta\\\beta^{2} \gamma\\\beta^{2} \delta\end{matrix}\right]$$

演算子のテンソル積¶

演算子についても何番目の量子ビットに作用するのか、というのをテンソル積をもちいて表現することができる。たとえば、1つめの量子ビットには$A$という演算子、2つめの量子ビットには$B$という演算子を作用させるという場合には、

\[A \otimes B\]

としてテンソル積演算子が与えられる。 $A$と$B$をそれぞれ、2×2の行列とすると、$A\otimes B$は4×4の行列として

\[\begin{split}\left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right) \otimes \left( \begin{array}{cc} b_{11} & b_{12} \\ b_{21} & b_{22} \end{array} \right) = \left( \begin{array}{cccc} a_{11} b_{11} & a_{11} b_{12} & a_{12} b_{11} & a_{12} b_{12} \\ a_{11} b_{21} & a_{11} b_{22} & a_{12} b_{21} & a_{12} b_{22} \\ a_{21} b_{11} & a_{21} b_{12} & a_{22} b_{11} & a_{22} b_{12} \\ a_{21} b_{21} & a_{21} b_{22} & a_{22} b_{21} & a_{22} b_{22} \end{array} \right)\end{split}\]

のように計算される。

テンソル積状態

\[|\psi \rangle \otimes | \phi \rangle\]

に対する作用は、

\[(A|\psi \rangle ) \otimes (B |\phi \rangle )\]

となり、それぞれの部分系$|\psi \rangle$と$|\phi\rangle$に$A$と$B$が作用する。足し算に対しては、多項式のように展開してそれぞれの項を作用させればよい。

\[\begin{split}(A+C)\otimes (B+D) |\psi \rangle \otimes | \phi \rangle = (A \otimes B +A \otimes D + C \otimes B + C \otimes D) |\psi \rangle \otimes | \phi \rangle\\ = (A|\psi \rangle) \otimes (B| \phi \rangle) +(A|\psi \rangle) \otimes (D| \phi \rangle) +(C|\psi \rangle) \otimes (B| \phi \rangle) +(C|\psi \rangle) \otimes (D| \phi \rangle)\end{split}\]

テンソル積やテンソル積演算子は左右横並びで書いているが、本当は

\[\begin{split}\left( \begin{array}{c} A \\ \otimes \\ B \end{array} \right) \begin{array}{c} |\psi \rangle \\ \otimes \\ |\phi\rangle \end{array}\end{split}\]

のように縦に並べた方がその作用の仕方がわかりやすいのかもしれない。

例えば、CNOT演算を用いて作られるエンタングル状態は、

\[\begin{split}\left( \begin{array}{c} |0\rangle \langle 0| \\ \otimes \\ I \end{array} + \begin{array}{c} |1\rangle \langle 1| \\ \otimes \\ X \end{array} \right) \left( \begin{array}{c} \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \\ \otimes \\ |0\rangle \end{array} \right) = \frac{1}{\sqrt{2}}\left( \begin{array}{c} |0 \rangle \\ \otimes \\ |0\rangle \end{array} + \begin{array}{c} |1 \rangle \\ \otimes \\ |1\rangle \end{array} \right)\end{split}\]

のようになる。

SymPyを用いた演算子のテンソル積¶

SymPyで演算子を使用する時は、何桁目の量子ビットに作用する演算子かを常に指定する。「何番目」ではなく2進数表記の「何桁目」であることに注意しよう。$n$量子ビットのうちの左から$i$番目の量子ビットを指定する場合、SymPyのコードではn-iを指定する（0を基点とするインデックス）。

H(0) は、1量子ビット空間で表示すると

[9]:

represent(H(0),nqubits=1)

[9]:

$$\left[\begin{matrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}} & - \frac{\sqrt{2}}{2}\end{matrix}\right]$$

2量子ビット空間では$H \otimes I$に対応しており、その表示は

[10]:

represent(H(1),nqubits=2)

[10]:

$$\left[\begin{matrix}\frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} & 0\\0 & \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}} & 0 & - \frac{\sqrt{2}}{2} & 0\\0 & \frac{1}{\sqrt{2}} & 0 & - \frac{\sqrt{2}}{2}\end{matrix}\right]$$

CNOT演算は、

[11]:

represent(CNOT(1,0),nqubits=2)

[11]:

$$\left[\begin{matrix}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 0 & 1\\0 & 0 & 1 & 0\end{matrix}\right]$$

パウリ演算子のテンソル積$X\otimes Y \otimes Z$も、

[12]:

represent(X(2)*Y(1)*Z(0),nqubits=3)

[12]:

$$\left[\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & - i & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & i\\0 & 0 & 0 & 0 & i & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & - i & 0 & 0\\0 & 0 & - i & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & i & 0 & 0 & 0 & 0\\i & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & - i & 0 & 0 & 0 & 0 & 0 & 0\end{matrix}\right]$$

このようにして、上記のテンソル積のルールを実際にたしかめてみることができる。

複数の量子ビットの一部分だけを測定した場合¶

複数の量子ビットを全て測定した場合の測定結果の確率については既に説明した。複数の量子ビットのうち、一部だけを測定することもできる。その場合、測定結果の確率は、測定結果に対応する（部分系の）基底で射影したベクトルの長さの2乗になり、測定後の状態は射影されたベクトルを規格化したものになる。

具体的に見ていこう。以下の$n$量子ビットの状態を考える。 \begin{align} |\psi\rangle &= c_{00...0} |00...0\rangle + c_{00...1} |00...1\rangle + \cdots + c_{11...1} |11...1\rangle\\ &= \sum_{i_1 \dotsc i_n} c_{i_1 \dotsc i_n} |i_1 \dotsc i_n\rangle = \sum_{i_1 \dotsc i_n} c_{i_1 \dotsc i_n} |i_1\rangle \otimes \cdots \otimes |i_n\rangle \end{align} 1番目の量子ビットを測定するとしよう。1つ目の量子ビットの状態空間の正規直交基底$|0\rangle$, $|1\rangle$に対する射影演算子はそれぞれ$|0\rangle\langle0|$, $|1\rangle\langle1|$と書ける。1番目の量子ビットを$|0\rangle$に射影し、他の量子ビットには何もしない演算子

\[|0\rangle\langle0| \otimes I \otimes \cdots \otimes I\]

を使って、測定値0が得られる確率は

である。ここで

\[\bigl(|0\rangle\langle0| \otimes I \otimes \cdots \otimes I\bigr) | \psi \rangle = \sum_{i_2 \dotsc i_n} c_{0 i_2 \dotsc i_n} |0\rangle \otimes |i_2\rangle \otimes \cdots \otimes |i_n\rangle\]

なので、求める確率は

\[p_0 = \sum_{i_2 \dotsc i_n} |c_{0 i_2 \dotsc i_n}|^2\]

となり、測定後の状態は

\[\frac{1}{\sqrt{p_0}}\sum_{i_2 \dotsc i_n} c_{0 i_2 \dotsc i_n} |0\rangle \otimes |i_2\rangle \otimes \cdots \otimes |i_n\rangle\]

となる。0と1を入れ替えれば、測定値1が得られる確率と測定後の状態が得られる。

ここで求めた$p_0$, $p_1$の表式は、測定値$i_1, \dotsc, i_n$が得られる同時確率分布$p_{i_1, \dotsc, i_n}$から計算される$i_1$の周辺確率分布と一致することに注意しよう。実際、

\[\sum_{i_2, \dotsc, i_n} p_{i_1, \dotsc, i_n} = \sum_{i_2, \dotsc, i_n} |c_{i_1, \dotsc, i_n}|^2 = p_{i_1}\]

である。

測定される量子ビットを増やし、最初の$k$個の量子ビットを測定する場合も同様に計算できる。測定結果$i_1, \dotsc, i_k$を得る確率は

\[p_{i_1, \dotsc, i_k} = \sum_{i_{k+1}, \dotsc, i_n} |c_{i_1, \dotsc, i_n}|^2\]

であり、測定後の状態は

\[\frac{1}{\sqrt{p_{i_1, \dotsc, i_k}}}\sum_{i_{k+1} \dotsc i_n} c_{i_1 \dotsc i_n} |i_1 \rangle \otimes \cdots \otimes |i_n\rangle\]

となる。（和をとるのは$i_{k+1},\cdots,i_n$だけであることに注意）

SymPyを使ってさらに具体的な例を見てみよう。H演算とCNOT演算を組み合わせて作られる次の状態を考える。

\[|\psi\rangle = \Lambda(X) (H \otimes H) |0\rangle \otimes |0\rangle = \frac{|00\rangle + |10\rangle + |01\rangle + |11\rangle}{2}\]

[13]:

psi = qapply(CNOT(1, 0)*H(1)*H(0)*Qubit('00'))
psi

[13]:

$$\frac{{\left|00\right\rangle }}{2} + \frac{{\left|01\right\rangle }}{2} + \frac{{\left|10\right\rangle }}{2} + \frac{{\left|11\right\rangle }}{2}$$

この状態の1つ目の量子ビットを測定して0になる確率は

\[p_0 = \langle \psi | \bigl( |0\rangle\langle0| \otimes I \bigr) | \psi \rangle = \left(\frac{\langle 00 | + \langle 10 | + \langle 01 | + \langle 11 |}{2}\right) \left(\frac{| 00 \rangle + | 01 \rangle}{2}\right) = \frac{1}{2}\]

で、測定後の状態は

\[\frac{1}{\sqrt{p_0}} \bigl( |0\rangle\langle0| \otimes I \bigr) | \psi \rangle = \frac{| 00 \rangle + | 01 \rangle}{\sqrt{2}}\]

である。

この結果をSymPyでも計算してみよう。SymPyには測定用の関数が数種類用意されていて、一部の量子ビットを測定した場合の確率と測定後の状態を計算するには、measure_partialを用いればよい。測定する状態と、測定を行う量子ビットのインデックスを引数として渡すと、測定後の状態と測定の確率の組がリストとして出力される。1つめの量子ビットが0だった場合の量子状態と確率は[0]要素を参照すればよい。

[14]:

from sympy.physics.quantum.qubit import measure_all, measure_partial
measured_state_and_probability = measure_partial(psi, (1,))

[28]:

measured_state_and_probability[0]

[28]:

$$\left ( \frac{\sqrt{2} {\left|00\right\rangle }}{2} + \frac{\sqrt{2} {\left|01\right\rangle }}{2}, \quad \frac{1}{2}\right )$$

上で手計算した結果と合っていることが分かる。測定結果が1だった場合も同様に計算できる。

[15]:

measured_state_and_probability[1]

[15]:

$$\left ( \frac{\sqrt{2} {\left|10\right\rangle }}{2} + \frac{\sqrt{2} {\left|11\right\rangle }}{2}, \quad \frac{1}{2}\right )$$

コラム：ユニバーサルゲートセットとは¶

古典計算機では、NANDゲート（論理積ANDの出力を反転したもの）さえあれば、これをいくつか組み合わせることで、任意の論理演算が実行できることが知られている。
それでは、量子計算における対応物、すなわち任意の量子計算を実行するために最低限必要な量子ゲートは何であろうか？
実は、本節で学んだ

\[\{H, T, {\rm CNOT} \}\]

の3種類のゲートがその役割を果たしている、いわゆるユニバーサルゲートセットであることが知られている。

これらをうまく組み合わせることで、任意の量子計算を実行できる、すなわち「万能量子計算」が可能である。

【より詳しく知りたい人のための注】¶

以下では$\{H, T, {\rm CNOT} \}$の3種のゲートの組が如何にしてユニバーサルゲートセットを構成するかを、順を追って説明する。

流れとしては、一般の$n$量子ビットユニタリ演算からスタートし、これをより細かい部品にブレイクダウンしていくことで、最終的に上記3種のゲートに行き着くことを見る。

◆ $n$量子ビットユニタリ演算の分解¶

まず、任意の$n$量子ビットユニタリ演算は、以下の手順を経て、いくつかの1量子ビットユニタリ演算とCNOTゲートに分解できる。

任意の$n$量子ビットユニタリ演算は、いくつかの2準位ユニタリ演算の積に分解できる。ここで2準位ユニタリ演算とは、例として3量子ビットの場合、$2^3=8$次元空間のうち2つの基底(e.g., $\{|000\rangle, |111\rangle \}$)の張る2次元部分空間にのみ作用するユニタリ演算である
任意の2準位ユニタリ演算は、制御$U$ゲート（CNOTゲートのNOT部分を任意の1量子ビットユニタリ演算$U$に置き換えたもの）とToffoliゲート（CNOTゲートの制御量子ビットが2つになったもの）から構成できる
制御$U$ゲートとToffoliゲートは、どちらも1量子ビットユニタリ演算とCNOTゲートから構成できる

◆ 1量子ビットユニタリ演算の構成¶

さらに、任意の1量子ビットユニタリ演算は、$\{H, T\}$の2つで構成できる。

任意の1量子ビットユニタリ演算は、オイラーの回転角の法則から、回転ゲート$\{R_X(\theta), R_Z(\theta)\}$で（厳密に）実現可能である
実は、ブロッホ球上の任意の回転は、$\{H, T\}$のみを用いることで実現可能である(注1)。これはある軸に関する$\pi$の無理数倍の回転が$\{H, T\}$のみから実現できること（Solovay-Kitaevアルゴリズム）に起因する

(注1) ブロッホ球上の連続的な回転を、離散的な演算である$\{H, T\}$で実現できるか疑問に思われる読者もいるかもしれない。実際、厳密な意味で1量子ビットユニタリ演算を離散的なゲート操作で実現しようとすると、無限個のゲートが必要となる。しかし実際には厳密なユニタリ演算を実現する必要はなく、必要な計算精度$\epsilon$で任意のユニタリ演算を近似できれば十分である。ここでは、多項式個の$\{H, T\}$を用いることで、任意の1量子ビットユニタリ演算を十分良い精度で近似的に構成できることが、Solovay-Kitaevの定理 [3] により保証されている。

以上の議論により、3種のゲート$\{H, T, {\rm CNOT} \}$があれば、任意の$n$量子ビットユニタリ演算が実現できることがわかる。

ユニバーサルゲートセットや万能量子計算について、より詳しくは以下を参照されたい:
[1] Nielsen-Chuang の 4.5 Universal quantum gates
[2] 藤井 啓祐 「量子コンピュータの基礎と物理との接点」（第62回物性若手夏の学校　講義）DOI: 10.14989/229039 http://mercury.yukawa.kyoto-u.ac.jp/~bussei.kenkyu/archives/1274.html
[3] レビューとして、C. M. Dawson, M. A. Nielsen, “The Solovay-Kitaev algorithm“, https://arxiv.org/abs/quant-ph/0505030