量子电路简介 左芬专栏

2024-05-14 09:58:59

　　万博体育官网经典计算机发展过程中曾经出现过多种计算模型，影响最广的可能是图灵机模型，而现代计算机实际采用的是冯·诺依曼架构。

　　量子计算发展早期人们也曾仿照图灵机构想过量子图灵机，但并没有被广泛采纳。现在广泛使用的是多伊奇1989年推广经典的数字逻辑电路而提出的量子电路模型。

　　人们在70年代曾经试图引入随机性来改进图灵机的效率。在数据层次上，这相当于引入比特的概率态（下图中轴线）：

　　但是因为总概率为1，我们并不能同时独立地操控0和1。现在我们试着将这里的概率态在复数上开平方，就可以形式上得到所谓的量子比特态和相应的概率幅：

　　注意此时的概率幅a和b在一定程度上是相互独立的。这就使得我们可以同时独立地操控0⟩态和1⟩态，从而有可能实现计算效率的飞跃。

　　我们的宏观世界当然并不是量子的。所以当我们读取量子比特时，它会坍缩回经典的概率态并丢失部分信息：

　　量子比特态覆盖了整个Bloch球面，因而是不可数的。如果我们只选择有限的门集，反复作用也只能得到可数多个态，不可能遍历整个球面。

　　于是我们退而求其次，希望找到有限门集，使得反复作用可以逼近任意态，就好比我们能用有理数逼近任意实数。

　　我们可以通过绕y轴转 π/2角度将z轴转到x轴。但人们通常在这个转动上复合一个绕x轴的π角转动，并把它叫做阿达马（Hadamard）门，简称H门，见下图。

　　有了H门和S门，我们可以遍历坐标轴上的六个态了，但同时我们也被困在了其中：无论我们怎么反复作用也逃不出去。

　　我们可以把这个八面体看成前面的概率态的某种推广。事实上，整个八面体中的态都无法超出概率型经典计算的范畴，尽管其中某些态存在量子叠加。因此，有朋友戏称其是“没有量子灵魂的”。

　　不过幸运的是，我们只需要想办法到达球面上这六个点外的某一点，那么就可以通过反复作用逼近任何一点了。例如，我们可以把这个点选成八面体对称轴与球面的交点：

　　人们通常选择绕z轴的π/4角度转动，并称之为π/8门。这个命名看起来有点古怪，只是历史原因而已。π/8门又被称为T门。于是我们的结论是，反复作用H,S,T门可以逼近Bloch球面上的任意态。

　　首先，单纯重复T门是不行的，因为π/4的8倍就变成了2π。我们需要把这些门组合出一个特殊的转动来，使得转角除以2π是无理数。为此，我们先类似于T门构建类似的T_x，也就是绕x轴的π/4转动：

　　接着，我们先后作用Tx和T，会得到一个奇怪的转动R_1。首先R_1的转轴并不在坐标轴上。其次，R_1的转角θ由下式决定：

　　不难证明θ是2π的无理数倍（不过我还没去细读证明过程）。于是R_1的反复作用可以逼近一个大圆上的所有点。

　　进一步定义R_2=HR_1H以改变转轴，反复作用R2得到的点可以密布另一个大圆。那么同时反复作用R1和R2呢？当然是近似得到整个Bloch球面。

　　这么做的代价是多少呢？也就是说，要以一定精度逼近一个任意的单比特门，需要大概多少个基础的H，S和T门呢？

　　假定我们需要的精度是ϵ。那么我们可以把圆分成1/ϵ份，必然有一份包含了需要的态。所以我们需要的基础门数目大概是Θ(1/ϵ)（Θ指的是相差常数因子的意义上等同）。同时考虑两个大圆只会让这个数目乘以一定的倍数，所以仍然是Θ(1/ϵ)。

　　以此类推，当我们的电路由m个任意单比特门组成时，如果我们仍然希望以精度ϵ去逼近它，需要的基础门的总数目大约是Θ(m^2/ϵ)，因为这时候单个门的精度需要达到ϵ/m。

　　如果从P与NP的角度来看，这个代价当然不算高。但是，Solovay与Kitaev告诉我们，可以大幅降低这一代价。他们用到的技术可以称为级联（concatenation）。

　　通过这样的方式，Solovay和Kitaev证明逼近任意单比特态只需要Θ(log^c(1/ϵ))个基础门，其中c≈4。而对于m个任意单比特门组成的电路，则只需要Θ(mlog^c(m/ϵ))个基础门。这只带来了对数级的额外代价，自然是完全可以接受的。

　　经典的逻辑电路基于布尔代数，而布尔代数是通过与、或、非运算定义的。相应地，所有的逻辑电路只需要这三种门就全都可以实现了。事实上，借助非门，与门和或门是可以互相替换的。这样一来，只需要与、非，或者或、非门就够了。人们甚至把它们各自组合在一起，构成与非门和或非门，并称它们为通用门。

　　那么，在量子电路中，我们还需要哪些两比特门，才能与基础的单比特门一起构成一组通用门集呢？当然，这里的通用是在近似的意义上说的。答案很简单，只需要一个就够了，那就是受控非门，CNOT。

　　单比特门可以借用Bloch球面来直观地定义，两比特门定义起来稍微麻烦一点，不过在物理上可以轻易解决这个问题。

　　所有门的定义都必须跟式（1）那样的态叠加相容。换句话说，我们可以利用态的叠加性将门的定义约束到经典比特态上。于是，对于这里的CNOT门我们只需要定义它的经典版本就可以了，如下图：

　　有了CNOT门，我们就可以声称：{H,S,T,CNOT}构成一组近似通用门集。也就是说，任何n比特门都可以通过它们的反复作用来近似地实现。

　　要证明这一点有点繁琐，我们只给一个定性的说明。一个任意n比特门包含两方面：在每个比特上的作用，以及比特之间的关联，或者说量子纠缠。利用CNOT门可以实现两比特之间的纠缠，而不断地在各个比特对之间作用CNOT门可以实现任意的n比特纠缠。一个简单的例子是三比特的Toffoli门，也叫控-控-非门，或者量子与门。它的一种实现方式是：

　　不过，通过这种方式来实现多体纠缠是非常低效的。我们可以简单地估算一下逼近一个任意n比特态所需要的的门数目。类似于Bloch球，n比特态可以用一个（2^{n+1}-1）维空间中的球面来表示：

　　如果想要以精度ϵ逼近球面上的点，我们需要用半径ϵ的圆盘去覆盖整个球面。在（2^{n+1}-1）维空间里，可以计算出这个覆盖需要的圆盘数是Θ(1/ϵ^{2^n} )。而要得到这么多的圆盘，我们需要大概Θ(2^n)那么多的门。这当然大大超出了我们的承受能力。

　　由此我们得出结论，绝大部分n比特门都是量子电路难以有效实现的，而我们在编程时应选择那些易于实现的。同时，这也引发了一个新的概念，也就是量子计算复杂度，以及相应的量子版本的P与NP问题。而这些结果和概念又会进一步体现在量子多体系统的性质和分类中，这里不再详述。

　　有朋友可能看出来了，在我们的近似通用门集{H,S,T,CNOT}里面，S其实是多余的，因为S=T^2。但人们仍然习惯保留S门，因为{H,S,CNOT}构成了一类非常特殊的电路，Clifford电路。

　　简单来说，这种电路会让每个量子比特都“等效地”处在某个坐标轴上，也就是准经典八面体的顶点上。正因为这一点，Clifford电路可以用（概率型）经典计算机有效仿真，这就是所谓Gottesman-Knill定理。

　　Clifford电路因为其特殊性，有着极为广泛的应用，我们之前曾经提及过一些，以后有机会再详细讨论。