从可逆经典计算到量子计算


最近在从新读有关可逆经典计算的文献,学到一些有趣的结果,在这里记录一下。我们知道经典逻辑门很多都是不可逆的,比如说与门,或门。后来Toffoli和Fredkin等人发现,实际上经典物理也允许可逆的逻辑门存在。比方说,Toffoli定义了一个可逆的Toffoli逻辑门,包含三个输入,三个输出。如果我们只用到其中的某个输出,那么可以构造出逻辑上不可逆的与非门,用这个逻辑门完全可以构造出任意的经典逻辑电路出来。换句话说,用Toffoli门就可以构造出可逆的经典计算电路。再完成计算之后,再把逻辑门按照逆序操作一次,我们会发现整个计算过程并没有消耗能量。

量子计算兴起之后,我们发现量子系统演化的幺正性天然保证了计算的可逆性。人们也在寻找什么是通用的量子逻辑门。最早确认的一组是两比特的控制非门和两个正交的单比特逻辑门。有没有可能找到更少的通用量子逻辑门呢?后来Yaoyun Shi发现只用Toffoli门加上单比特的Hadamard 门就可以构造出任意的量子电路。

这个结论有可以用下面这句话概况:量子计算超越经典计算的地方就在于多了单比特的Hadamard门,或者说所有的量子计算算法不过就是经典计算机加上Hadamard门

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s