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 が実装できれば、量子回路は