proving-universality.ipynb

Kernel: Python 3

普遍性の証明

目次

1. はじめに

2. 行列を楽しむ 2.1 外積としての行列 2.2 ユニタリー行列とエルミート行列 2.3 パウリ行列分解

3. 普遍性の定義

4. 基本的なゲートセット 4.1 クリフォードゲート 4.2 非クリフォードゲート 4.3 ゲートセットの拡張

5. 普遍性の証明

6. 量子ゲートのユニバーサルセット

1. はじめに

与えられたコンピューターは何ができるでしょうか？一般に、計算可能とされるものの限界はどの程度なのでしょうか？ これらの問いは、コンピューターがどのようなものかがまだわからなかった時代にアラン・チューリングが挑戦した問題です。

古典コンピューターについて、つまり標準的なデジタル・コンピューターについて、この質問をするためには、スクリーン、スピーカーや手の込んだ入力デバイスを全て取り除く必要があります。そうすると、入力ビット列を出力ビット列に変換する単純な機械だけが残されます。ある装置が、任意の入力セットを任意の出力セットへ変換することができる場合、このことを 普遍的 である、と呼びます。

量子コンピューターも同様に入力状態を受け取り、それらを出力状態に変換します。ですので、同じような方法で普遍性を定義することができます。普遍性が達成できる場合とできない場合をより正確に証明するには、量子ゲートの行列表現を使用するのが良い方法です。ただし、最初にいくつかのテクニックを磨き直す必要があります。

2. 行列を楽しむ

2.1 外積としての行列

前のセクションでは、$\langle0|0\rangle =1$などの様々な内積を計算しました。内積は、ブラとケットから一つの数を求めます。ブラとケットを逆に置くと、行列が得られ、これを外積と呼びます。外積は、標準の行列の乗算で計算でき、 例えば、以下のように計算されます。

$$|0\rangle\langle0|= \begin{pmatrix} 1 \ 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \end{pmatrix} = \begin{pmatrix} 1&0 \ 0&0 \end{pmatrix},\ |0\rangle\langle1| = \begin{pmatrix} 1 \ 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \end{pmatrix} = \begin{pmatrix} 0&1 \ 0&0 \end{pmatrix},\ |1\rangle\langle0| = \begin{pmatrix} 0 \ 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \end{pmatrix} = \begin{pmatrix} 0&0 \ 1&0 \end{pmatrix},\ |1\rangle\langle1| = \begin{pmatrix} 0 \ 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \end{pmatrix} = \begin{pmatrix} 0&0 \ 0&1 \end{pmatrix}.\$$

また、純粋に外積として任意の行列も記述できます。上の例で、1量子ビットの行列の各要素を表す4つの行列を作成しましたが、これを使って、任意の1量子ビットの行列を外積として記述できます。

$$M= \begin{pmatrix} m_{0,0}&m_{0,1} \ m_{1,0}&m_{1,1} \end{pmatrix} = m_{0,0} |0\rangle\langle0|+ m_{0,1} |0\rangle\langle1|+ m_{1,0} |1\rangle\langle0|+ m_{1,1} |1\rangle\langle1|$$

この性質は、$n$ビットの外積に拡張するだけで、任意の数の量子ビット$n$の行列にも拡張できます。

2.2 ユニタリー行列とエルミート行列

行列$M$のエルミート共役$M^\dagger$は、行列$M$を転置（左下の要素を右上に置き換えるなど）し、各要素を複素共役にしたものです。これから紹介する、量子コンピューティングにとって非常に重要な2つの行列は、エルミート共役の関係によって定義されます。その1つは、ユニタリー行列です。

$$U U^\dagger = U^\dagger U = 1.$$

上記は、ユニタリー行列のエルミート共役がその逆行列（$U$の効果を元に戻す力を持つ別のユニタリー$U^\dagger$）であることを意味しています。量子コンピューティングにおいて、測定とリセット操作以外のすべてのゲートは、ユニタリー行列で表すことができます。

ユニタリー性のもう1つの特徴は、2つの任意の状態の間で内積を保持することです。具体的には、$\left| \psi_0 \right\rangle$と$\left| \psi_1 \right\rangle$の2つの状態があるとき、これらの内積は$\left\langle \psi_0 | \psi_1 \right\rangle$となりますが、同じユニタリー行列$U$をそれぞれに適用すると、結果となる内積はまったく同じになります。

$$\left( \left\langle \psi_0 \right| U^\dagger \right) \left( U \left| \psi_1 \right\rangle \right) = \left\langle \psi_0 |U^\dagger U| \psi_1 \right\rangle = \left\langle \psi_0 | \psi_1 \right\rangle.$$

この性質は、ゲートについての便利な考え方を与えてくれます。つまり、システムの正規直交基底を与える状態のセット ${ \left| \psi_j \right\rangle }$があるとき、${ \left| \phi_j \right\rangle = U \left| \psi_j \right\rangle }$である状態のセットも正規直交基底になります。よって、ユニタリー行列は、基底の回転と考えることができ、次のように書くことができます。

$$U = \sum_j \left| \phi_j \right\rangle \left\langle \psi_j \right|.$$

これは本質的に、古典的なブーリアン・ゲートの動作を記述する「真理値表」の量子バージョンとなっています。

もう一つの重要な行列は、エルミート行列です。エルミート行列は、エルミート共役を取っても影響を受けません。

$$H = H^\dagger.$$

行列$X$、$Y$、$Z$、$H$ は、すでに見てきたようにエルミート行列の例です（偶然にも、これらの行列は自身の逆行列であるため、すべてユニタリー行列です）。

すべてのユニタリー行列とエルミート行列には、対角化可能であるという特徴があります。これは、この二つの行列が次の形で記述できることを意味します。

$$M = \sum_j \lambda_j |h_j\rangle\langle h_j|,$$

ここで、$\lambda_j$はこの行列の固有値であり、$|h_j\rangle$はその固有状態です。

ユニタリー行列の場合、この対角形式で$U U^\dagger=1$ の条件を適用すると、$\lambda_j \lambda_j^* = 1$が得られます。よって、ユニタリー行列の固有値は常に大きさ1の複素数であり、ある実数$h_j$を使って$e^{ih_j}$で表すことができます。 エルミート行列の場合、条件$H = H^\dagger$ から$\lambda_j = \lambda_j^*$となり、つまりエルミート行列の固有値は実数となります。

よって、この2つの行列の違いは、固有値が実数か、実数の複素指数かという点のみです。これは、すべてのユニタリー行列に対して、対応するエルミート行列を定義できることを意味します。これを定義するためには、同じ固有状態を用い、その固有値は$h_j$を使って$e^{ih_j}$とします。

同様に、各エルミート行列にはそれぞれ対応するユニタリー行列が存在します。 同じ固有状態を使い、$h_j$をべき乗して、固有値$e^{ih_j}$を作成して、次のように表すことができます。

$$U = e^{iH}$$

ここでは、行列をべき乗する標準的な定義を使用しました。これには、固有状態の保持と固有値のべき乗という、私たちが必要としている特性が正確に含まれています。

2.3 パウリ行列分解

上記でも示したように、任意の1量子ビットの行列を外積を使って表すことができます。

$$M= \begin{pmatrix} m_{0,0}&m_{0,1} \ m_{1,0}&m_{1,1} \end{pmatrix} = m_{0,0} |0\rangle\langle0|+ m_{0,1} |0\rangle\langle1|+ m_{1,0} |1\rangle\langle0|+ m_{1,1} |1\rangle\langle1|$$

次に、パウリ演算子で行列を完全に記述できることを見ていきましょう。そのために注意すべき重要なことは、以下です。

ParseError: KaTeX parse error: Undefined control sequence: \0 at position 59: …atrix} 1&0 \̲0̲&1 \end{pma…

これは、$|0\rangle\langle0|$ と $|1\rangle\langle1|$が単位行列と$Z$を使って表せることを示しています。これで、$X|0\rangle = |1\rangle$という特性を使用して、次の式も生成できます。

$$|0\rangle\langle1| = |0\rangle\langle0|X = \frac{1}{2}(1+Z)~X = \frac{X+iY}{2},\ |1\rangle\langle0| = X|0\rangle\langle0| = X~\frac{1}{2}(1+Z) = \frac{X-iY}{2}.$$

すべての外積が書き換えられたので、これを使って、パウリ行列として行列を記述できます。

$$M = \frac{m_{0,0}+m_{1,1}}{2}~1~+~\frac{m_{0,1}+m_{1,0}}{2}~X~+~i\frac{m_{0,1}-m_{1,0}}{2}~Y~+~\frac{m_{0,0}-m_{1,1}}{2}~Z.$$

この例は一般的な単一量子ビット行列の場合ですが、任意の数の量子ビットの行列にも当てはまります。簡単な次の式から見てみましょう。

$$\left(\frac{1+Z}{2}\right)\otimes\left(\frac{1+Z}{2}\right)\otimes\ldots\otimes\left(\frac{1+Z}{2}\right) = |00\ldots0\rangle\langle00\ldots0|,$$

上記と同じ方法で変形を進めることができ、最終的に、任意の数の量子ビットの行列がパウリ行列のテンソル積で表せることが分かります。

$$M = \sum_{P_{n-1},\ldots,P_0 \in {1,X,Y,Z}} C_{P_{n-1}\ldots,P_0}~~P_{n-1} \otimes P_{n-2}\otimes\ldots\otimes P_0.$$

エルミート行列の場合、ここでの係数$C_{P_{n-1}\ldots,P_0}$ はすべて実数になることに注意してください。

3. 普遍性の定義

各量子ゲートをユニタリー行列で表すことができるのと同じように、（非常に大きな）ユニタリー演算で量子計算全体を記述することもできます。このユニタリー演算による効果で、入力状態が回転して出力状態になります。

このユニタリー演算の特殊なケースの1つは、入力状態と出力状態が量子形式で表現されたビット列を記述することです。各入力$x$の出力$f(x)$へのマッピングは、いくつかの（可逆的な）古典的な計算によって記述できます。したがって、そのような計算はすべてユニタリー行列として表すことができます。

$$U = \sum_j \left| f(x) \right\rangle \left\langle x \right|.$$

したがって、どんなユニタリー演算でも実装することができれば、標準的なデジタルコンピューターと同じように普遍性を実現できます。

もう1つの特殊なケースは、入力状態と出力状態が物理システムを表す可能性があることです。その場合、実行する計算は、そのシステムのダイナミクスをシミュレートすることを意味します。これは、古典コンピューターでは実用的ではない重要な問題ですが、量子コンピューターの自然な応用です。この場合、システムの時間発展は、ユニタリー演算に対応し、エルミート行列は、システムのハミルトニアンに対応します。したがって、ユニタリー演算を実施することは、時間発展をシミュレートし、ハミルトニアンの効果を実験することに対応します。

これらの洞察を組み合わせることで、量子コンピューターが普遍的であることの意味を定義できます。それは端的にいうと、任意の数の量子ビットで任意のユニタリー演算を実行できる能力です。これができれば、デジタルコンピューターでできることは何でも再現でき、また、どのような量子システムでもシミュレートでき、量子コンピューターで可能なすべてのことを実行できる、ということです。

4. 基本的なゲートセット

基本的なゲートのセットからユニタリー演算を構築できるかどうかは、どのような基本ゲートにアクセスできるかに大きく依存します。誤り耐性のある量子コンピューティングを実現するために、最も簡単に実現できる量子操作のセットがあります。 多くの場合、この組み合わせは1量子ビットゲートと2量子ビットゲートで構成され、そのほとんどはいわゆるクリフォードゲートのセットです。このセットは非常に重要な一連の操作であり、量子アルゴリズムでの大変な作業の多くを担っています。

4.1 クリフォードゲート

クリフォードゲートを理解するために、すでに何度も見てきた例であるアダマールから始めましょう。

$$H = |+\rangle\langle0|~+~ |-\rangle\langle1| = |0\rangle\langle+|~+~ |1\rangle\langle-|.$$

このゲートは、上記のように外積を使って表現できます。この形式で表現すると、その有名な効果が明らかになります：つまり、$|0\rangle$を、$|+\rangle$に回転します。より一般的には、z測定の基底状態${ |0\rangle,|1\rangle }$をx測定の基底状態${ |+\rangle,|-\rangle }$に回転させ、その逆も行います。

このように、アダマールの効果は、情報を量子ビットの周りに移動させることです。これは、以前にx測定された情報をz測定の情報と交換します。

アダマールを他のゲートと組み合わせて、次のようなさまざまな操作を実行できます：

$$H X H = Z,\ H Z H = X.$$

$X$の前後でアダマールを実行することにより、以前にz基底状態に適用されていた動作が、x基底状態に転送されます。この効果は、$Z$の効果と同じです。同様に、アダマールと$Z$から$X$を作成できます。

$S$ゲートとそのエルミート共役についても同様の動作が見られます。

$$S X S^{\dagger} = Y,\ S Y S^{\dagger} = -X,\ S Z S^{\dagger} = Z.$$

これには、アダマールと同様の効果がありますが、$X$と$Z$ではなく$X$と$Y$を交換します。また、アダマールと組み合わせて、情報をyとzの間でシフトする複合ゲートも作成できるでしょう。

パウリ行列を他のパウリ行列に変えるこの特性が、クリフォードゲートの特徴です。1量子ビットの場合については、次のように明らかに述べられます：$U$がクリフォードで$P$がパウリ行列の場合、$U P U^{\dagger}$ もパウリ行列になる。アダマールのようなエルミート行列の場合、$U P U$です。

1量子ビットのクリフォードゲートのさらなる例は、パウリ行列それ自体です。これらは、作用するパウリ行列を変えず、代わりに、反交換する2つの行列に$-1$の位相を割り当てます。 例えば、

$$Z X Z = -X,\ Z Y Z = -Y,\ Z Z Z= ~~~~Z.$$

$S$ゲートでも同じ位相が発生することに気づいたかもしれません。これをパウリ行列と組み合わせることで、この位相をキャンセルする複合ゲートを作成し、アダマール行列による$X$と$Z$の交換に似た方法で、$X$と$Y$を交換することができます。

複数量子ビットのクリフォードゲートの場合、パウリ行列のテンソル積を他のパウリ行列のテンソル積に変換することが特徴として定義されます。例えば、最も有名な2量子ビットのクリフォードゲートはCNOTです。この章で使用するCNOTの特性は次のとおりです。

$${ CX}*{j,k}~ (X \otimes 1)~{ CX}*{j,k} = X \otimes X.$$

これにより、$X$が制御量子ビットからターゲット量子ビットに「コピー」されます。

ユニタリー演算とそのエルミート共役の間に行列を挟むプロセスは、そのユニタリー演算による共役化として知られています。このプロセスは、行列の固有状態を変換しますが、固有値は変わりません。クリフォード行列で共役化することがパウリ行列間での変換となる理由は、すべてのパウリ行列が同じ固有値のセットを持っているためです。

4.2 非クリフォードゲート

クリフォードゲートは非常に重要ですが、それ自体では強力ではありません。量子計算を行うには、クリフォードではないゲートが必要です。クリフォードではないゲートには、3つの重要な例があり、それは、量子ビットの3つの軸を中心とした任意の回転、$R_x(\theta)$、$R_y(\theta)$ 、 $R_z(\theta)$です。

$R_x(\theta)$に注目してみます。上記で見たように、任意のユニタリー演算はエルミート行列を使用して指数形式で表現できます。$R_x(\theta)$は、以下のように書くことができます。

$$R_x(\theta) = e^{i \frac{\theta}{2} X}.$$

前のセクションでは、ユニタリー演算とそれに対応するエルミート行列が同じ固有状態を持っていることも示しました。 このセクションでは、ユニタリー演算による共役化が固有状態を変換するけれど、固有値はそのままであることを確認しました。これを念頭に置いて、次のことを示すことができます

$$U R_x(\theta)U^\dagger = e^{i \frac{\theta}{2} ~U X U^\dagger}.$$

したがって、この回転をクリフォードゲートで共役化することで、別の軸を中心とした同じ回転に変換できます。つまり、$R_y(\theta)$と$R_z(\theta)$を直接実行する方法がなかったとしても、$R_x(\theta)$をクリフォードゲートと組み合わせて実行することができます。非クリフォードゲートをクリフォードゲートと組み合わせてパワーを高めるこの手法は、量子コンピューティングで非常によく活用されています。

4.3 ゲートセットの拡張

$R_x(\theta)$をクリフォードと組み合わせる別の例として、CNOTで共役化してみましょう。

$$CX_{j,k} ~(R_x(\theta) \otimes 1)~ CX_{j,k} = CX_{j,k} ~ e^{i \frac{\theta}{2} ~ (X\otimes 1)}~ CX_{j,k} = e^{i \frac{\theta}{2} ~CX_{j,k} ~ (X\otimes 1)~ CX_{j,k}} = e^{i \frac{\theta}{2} ~ X\otimes X}$$

これにより、単純な1量子ビットの回転がはるかに強力な2量子ビットゲートに変換されます。これは、それぞれの量子ビットで独立して回転を実行するのではなく、もつれ状態を生成し、操作することができるゲートです。

それだけにとどまる必要はありません。同じトリックを使用して、この操作を任意の数の量子ビットに拡張できます。必要なのは、$X$を新しい量子ビットにコピーし続けるためにCNOTによってより多くの共役をすることです。

さらに、1量子ビットのクリフォードゲートを使用して、異なる量子ビットにパウリ行列を変換することができます。例えば、2量子ビットの例では、右側の量子ビットを$S$で共役化して、$X$を$Y$に変換できます。

$$\left( I \otimes S \right) ~e^{i \frac{\theta}{2} ~ X\otimes X}~\left( I \otimes S^\dagger \right) = e^{i \frac{\theta}{2} ~ X\otimes Y}.$$

これらの手法を使用すると、任意の数の複数量子ビットに作用する複雑なもつれ演算を作成することができます。

$$U = e^{i\frac{\theta}{2} ~ P_{n-1}\otimes P_{n-2}\otimes...\otimes P_0}, ~~~ P_j \in {I,X,Y,Z}.$$

これはすべて、1量子ビットと2量子ビットのクリフォードゲートをx軸を中心とした回転と組み合わせると、強力な可能性が得られることを示しています。普遍性の証明のために残されている課題は、これらを使用して何でもできることを示すことです。

5. 普遍性の証明

古典コンピューターと同じように、この大きな仕事を扱いやすいかたまりに分割する必要があります。普遍性を実現するための基本的なゲートのセットを見つける必要があります。それは、後で見るように、前の章の1量子ビットゲートおよび2量子ビットゲートで十分です。

以下のようにユニタリー演算を実装するとします。

$$U = e^{i(aX + bZ)},$$

ただし、使えるゲートは$R_x(\theta) = e^{i \frac{\theta}{2} X}$ と $R_z(\theta) = e^{i \frac{\theta}{2} Z}$のみです。 この問題を解決する最善の方法は、オイラー角を使用することです。 しかし、代わりに別の方法を考えてみましょう。

$U$の指数関数のエルミート行列は、$R_x(\theta)$回転と $R_z(\theta)$回転のエルミート行列の和です。これは、問題を解決するための素朴なアプローチを示しています：たぶん、$R_z(2b) = e^{i bZ}$ に続いて $R_x(2a) = e^{i a X}$ を適用できるでしょう。しかし、残念ながら、可換でない行列を累乗に使っているため、このアプローチは使えません。

$$e^{i a X} e^{i b Z} \neq e^{i(aX + bZ)}$$

ただし、次の変形バージョンを使用できます：

$$U = \lim_{n\rightarrow\infty} ~ \left(e^{iaX/n}e^{ibZ/n}\right)^n.$$

ここで、$U$を$n$個の小さなスライスに分割します。 各スライスについて、次のように言うのは良い近似です。

$$e^{iaX/n}e^{ibZ/n} = e^{i(aX + bZ)/n}$$

この近似の誤差は、$1/n^2$としてスケーリングされます。 $n$個のスライスを組み合わせると、エラーが$1/n$にスケールする目標とするユニタリー演算の近似値が得られます。したがって、スライスの数を増やすだけで、必要なだけ$U$に近づけることができます。更に正確なユニタリー演算を得るために、シーケンスを作成する方法もあります。

この方法の利点は、1量子ビットだけでなく、複雑なケースでも使用できることです。 たとえば、以下のユニタリー演算を考えます。

$$U = e^{i(aX\otimes X\otimes X + bZ\otimes Z\otimes Z)}.$$

私たちは、1量子ビット$R_x(\theta)$と2つの制御NOTからユニタリー行列$e^{i\frac{\theta}{2} X\otimes X\otimes X}$を作成する方法を知っています。

qc.cx(0,2)
qc.cx(0,1)
qc.rx(theta,0)
qc.cx(0,1)
qc.cx(0,2)

いくつかのアダマールがあれば、$e^{i\frac{\theta}{2} Z\otimes Z\otimes Z}$にも同じことができます。

qc.h(0)
qc.h(1)
qc.h(2)
qc.cx(0,2)
qc.cx(0,1)
qc.rx(theta,0)
qc.cx(0,1)
qc.cx(0,2)
qc.h(2)
qc.h(1)
qc.h(0)

これにより、新しい3量子ビットの$U$の小さなスライスを再現できます：

$$e^{iaX\otimes X\otimes X/n}e^{ibZ\otimes Z\otimes Z/n} = e^{i(aX\otimes X\otimes X + bZ\otimes Z\otimes Z)/n}.$$

前にやったのと同じ方法で、スライスを結合して、$U$の任意の正確な近似を取得できます。

この方法は、量子ビットの数、およびシミュレーションが必要な項の数を増やしても機能し続けます。近似が正確であることを保証するために注意が必要ですが、それは妥当なリソースで行うことができます。シミュレーションに追加の項を追加したり、必要な精度を高めたりするには、メソッドの複雑さを多項式で増やすだけで済みます。

この形式の方法は、$H$がパウリ行列のテンソル積の和として表現される任意のユニタリー演算子$U = e^{iH}$を再現できます。すべての行列をこのように表現できることを以前に示したので、これはすべてのユニタリー演算子を再現できることを示すのに十分です。実際には他の方法の方が良いかもしれませんが、この章から学ぶ主な概念は、Qiskitにある基本的な操作のみを使用してすべての複数量子ビットユニタリー演算子を再現する方法が確かにあるということです。これで量子普遍性を実現できます！

普遍性を実現できるのは、このゲートセットだけではありません。例えば、アダマールとトフォリだけで十分であることを示すことができます。他の複数のゲートセットでも、普遍性があることが証明されており、フォールトトレラントなゲートセット実現のために様々な方法が期待されています。

このテキストブックで説明した計算はすべて、回路モデルに従います。しかし、回路モデルは量子計算の唯一の普遍的な形式ではありません。断熱量子コンピューティングや測定ベースの量子コンピューターなど、他の量子コンピューティングの形式が存在します。それらが普遍的であるという事実は、回路モデルからこれらの計算形式への多項式の時間とリソースのマッピングが証明されていることを意味します。この他の形式は、計算を実行するために、他の量子力学的特性を利用することがよくあります。また、その利点はハードウェアに依存していることに注意してください。量子計算の普遍的モデルは任意の量子アルゴリズムを実行できるために、私たちは、回路モデルのみに着目する必要があり、他の形式を無視できます。

普遍的ではありませんが、特定のアプリケーションに適用可能な別の量子計算の形式があります。たとえば、量子アニーリングは最適化とサンプリングの問題に非常に役立ちます。アニーリング（焼きなまし）は、金属を高温に加熱してからゆっくりと冷却するプロセスです。これにより、溶融金属が金属片の表面上を流れ、再配置します。このプロセスは、問題の金属の多くの特性を変更します。量子アニーリングは、ある意味でこれに類似していて、問題をある種のエネルギー地形にエンコードしてから、量子状態にランドスケープを探索させることが含まれます。通常の波は周囲よりも低いトラフ（ローカルな極小値）に閉じ込められる可能性がありますが、量子効果により、量子状態がランドスケープの真の最低点（グローバルな極小値）を見つける速度が向上します。

import qiskit.tools.jupyter
%qiskit_version_table