可逆经典线路

阐述

• 一位可逆经典门：NOT
• 两位可逆经典门可以看成是 CNOT（$(a,b)\to(a,a\oplus b)$）、SWAP 和 NOT 构成的门

不能使用 CNOT、SWAP 和 NOT 构造出所有的经典可逆函数，但可以用 Toffoli (CCNOT, $(a,b,c)\to(a,b,c\oplus(a\wedge b))$) 和非门构造。

实例

性质

相关内容

定理

如果存在一个由 $a$ 个门实现的 $x\to y$ 的经典线路，那么存在一个由 $O(a+|y|)$ 个门（NOT、CNOT、Toffoli）构成的经典可逆线路实现 $(x,0,0)\to(x,y,0)$。

定理

如果存在一个由 $a$ 个门实现的 $x\to y$ 的经典线路，同时存在一个由 $b$ 个门实现的 $y\to x$ 的经典线路，那么存在一个由 $O(a+b+|x|+|y|)$ 个门实现的可逆经典线路实现 $(x,0)\to(y,0)$。

参考文献