CNOT + Hadamard + π/8 が Turing 完全であることの証明のアウトラインを書いてみた

Turing 完全とは？

ここでは、Turing 完全の厳密な定義には踏み込みませんが・・・、AND や OR を組み合わせたいわゆる論理演算回路は、「AND, XOR, NOT」の3種類の演算があれば、これらの組み合わせですべて実現することができます。デジタルコンピューター（すなわち、古典計算機）が実行可能なアルゴリズムは、原理的には、この3つの論理演算の組み合わせで実行可能です。ここでは、この3つの論理演算を実装できることを持って、Turing 完全と呼ぶことにしておきます。

NAND があれば何でもできる

次に示すように、NAND を用いて、NOT, AND, XOR を実装することができます。

つまり、NAND を実装できれば、Turing 完全となります。

おまけ

www.kmc.gr.jp

FANOUT の必要性

というわけで、量子回路で NAND が実装できれば、量子回路は Turing 完全、すなわち、量子計算機で古典計算機をシミュレーションすることが可能となります。

ただし・・・、厳密に言うと、NAND だけでは不十分で、量子回路の場合は FANOUT という演算も必要となります。

これは何かと言うと、上記の「おまけ」の先にある、NAND で構成した全加算器の例を見ると、● で回路が枝分かれしている部分があります。このように1つの線を流れる値を2つの線に分岐させる演算を FANOUT と言います。古典回路の場合、このような分岐が実装できるのは自明で、特に必要性が明示されることはありませんが、量子回路の場合、これは、量子ビットの間で値を複製する処理になるので、決して自明に実装できるわけでありません。

したがって、量子回路の場合、NAND と FANOUT が実装できれば、Turing 完全と言えます。

Toffoli gate

3つの量子ビットを用いた次の演算回路を Toffoli gate と呼びます。

f:id:enakai00:20180606073638p:plain

これは何かと言うと、上から順番に入力値を a, b, c、出力値を p, q, r とした時に、次の演算を行う回路です。

def toffoli(a, b, c):
    p = a
    q = b
    if a == 1 and b == 1:
        r = int(not c)
    else:
        r = c
    return p, q, r

これは量子回路なので、a, b, c などは、0 / 1 の重ね合わせ値をとることができますが、ここでは、古典回路のシミュレーションを考えているので、a, b, c などは、0 か 1 のどちらかの値（デジタル値）を取るものとしてください。

要するに、a と b がどちらも 1 なら、c のビットを反転するという演算です。

Toffoli gate で何でもできる

そして、Toffoli gate で NAND と FANOUT を実装することができます。

まず、Toffoli gate において、c = 1 に固定すると、「r = a NAND b」が成り立ちます。これで NAND が実装できました。

同じく、a = 1, c = 0 に固定すると、「q = b, r = b」が成り立ちます。これで、FANOUT が実装できました。

つまり、量子回路において、Toffoli gate が実装できれば、量子回路は Turing 完全になります。

古典回路（デジタル演算）的な議論は、ここまでです。ここから先は、量子回路によって、どうやって Toffoli gate を実装できるかという、量子計算の議論となります。

ユニバーサル量子計算機とは？

量子計算機の動作原理は、根源的には、「量子ビットの集合に対するユニタリ変換」となります。

　( ﾟдﾟ) なにいってんだこいつ

・・・という方は、ぜひ下記のシリーズを一読ください。

enakai00.hatenablog.com

結論をまとめると、まず、n 個の量子ビットの状態は、 ${\mid 0...00\rangle},\ {\mid 0...01\rangle},\ {\mid 0...10\rangle},\cdots,{\mid 1...11\rangle}$ の $2^n$ 個の状態を基底ベクトルとする複素ベクトル

　 ${\mid\psi\rangle} = c_{0...00}{\mid 0...00\rangle} + c_{0...01}{\mid 0...01\rangle} + \cdots + c_{1...11}{\mid 1...11\rangle}$

で表されます。この時、係数には、次の束縛条件が付きます。

　 $|c_{0...00}|^2 + |c_{0...01}|^2 + \cdots + |c_{1...11}|^2 = 1$

そして、量子ビットの状態を変化させる演算は、一般には、上記の複素ベクトルに対する一次変換として表されます。行列で表すならば、 $2^n\times 2^n$ の複素数の行列 $U$ です。ただし、変換後の状態も上記の束縛条件を満たす必要があるので、 $U$ は、

　 $U^\dagger = U^{-1}$

を満たすユニタリ行列に限定されます。（ $\dagger$ は転置して複素共役を取る操作を示します。）

言葉がちょっとややこしいですが、このようにユニタリ行列で表される一次変換をユニタリ変換と言います。

そして、任意のユニタリ変換を実行可能な量子計算機のことを「ユニバーサルな量子計算機」と言います。

ユニバーサル量子計算機はなんでもできる

ここで言う「なんでもできる」は、古典的な意味で言っています。前述の Toffoli gate の処理は、落ち着いて考えると、 $2^3\times 2^3$ のユニタリ行列で表すことができます。というか、実際に表すと次になります。

$https://wikimedia.org/api/rest_v1/media/math/render/svg/70d00c695dd6889b6a71c6aad344f7a13a409c64$

詳細は Wikipedia を参照ください。

・トフォリゲート - Wikipedia

したがって、ユニバーサル量子計算機は、Turing 完全になります。

CNOT + 1qbit ユニタリ演算はユニバーサル

さて・・・ここらあたりから、まじめに証明すると計算が大変なので、結論だけを大雑把に言っておきます。

まず、CNOT は、次の量子回路です。Toffoli gate をちょっと単純化したもので、上の量子ビットが 1 であれば、下の量子ビットを反転します。

これもまた、ユニタリ変換になっており、次のユニタリ行列で表すことができます。

　 $C_N = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$

次に、1 qbit ユニタリ演算というのは、1 量子ビットに対するユニタリ変換です。n 量子ビット全体は、 $2^n$ 次元の巨大なベクトル空間を構成しますが、その中で、特定の 1 量子ビット、つまり、2次元の部分空間だけを操作する $2\times 2$ のユニタリ行列による一次変換が 1 qbit ユニタリ演算です。

実は、任意のユニタリ変換は、CNOT と任意の 1 量子ビットに対する 1 qbit ユニタリ演算の組み合わせに分解することができます。（この部分は、純粋に線形代数の演習問題ですね。感覚的に言うと、1 量子ビットに対する変換を CNOT で伝搬させていくことで、複数の量子ビットにまたがった変換が実現できます。）

したがって、CNOT + 1qbit ユニタリ演算を実装可能な量子計算機は、ユニバーサル量子計算機であり、Turing 完全となります。

CNOT + Hadamard + π/8 があれば何でもできる。

Hadamard と π/8 は、それぞれ、次の行列で表される、1 量子ビットに対するユニタリ変換です。

　 $H = \frac{1}{\sqrt{2}}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$

　 $T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}$

そして・・・ここがなかなかすごいところなのですが、実は、Hadamard と π/8 を組み合わせていくと、任意の 1qbit ユニタリ演算が近似的に表現できます。つまり、任意の $2\times 2$ のユニタリ行列は、H と T をどんどん掛け合わせることで近似的に表現できるのです。また、掛け合わせる個数を増やせば、近似の精度は任意に高めることができます。