ことを証明した。だがドィチェ・ゲート回路は古典可逆回路と同じ３入力―３出力回路であるので、各入力が２状態系に対応した量子ビットの場合、ユニタリ作用素は、２ｘ２ｘ２＝８という８次元となり、その行列表現は、８ｘ８行列となり、やっかいである。その後、IBMのディビンセンゾーD. Di’Vincenzoが、

「任意の２^ｎ次元ヒルベルト空間上のユニタリ作用素は２入力の位相回転回路とコントロールNOTの組み合わせで表現可能である」

ことを証明した。すなわち位相回転回路とコントロールNOTとは、量子計算の基本演算回路（ユニバーサル・ゲート回路）であることが証明された。もっとも簡単な位相回転回路は、アダマールHadamard変換であり、その行列表現は、

　　　　　　　　　

である。また、２入力のコントロールNOTの行列表現は、

　　　　　　　、　　　　　

である。

注）古典的なコントロールNOT回路と真理表は以下のようである。

A　 B　　 A’　　B’

0　 0　　　0　　0

0　 1　　　0　　1

1　 0　　　1　　1

1　 1　　　1　　0

コントロールNOT回路は、可逆のXOR回路である。

量子計算のアルゴリズム