关于 Toffoli 门的分解

本篇汇报主要学习 Toffoli 门的分解的思想和方法。

引用文献

[1] Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., … & Weinfurter, H. (1995). Elementary gates for quantum computation. Physical review A, 52(5), 3457.

[2] DiVincenzo, D. P. (1998). Quantum gates and circuits. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969), 261-276.

[3] Sleator, T., & Weinfurter, H. (1995). Realizable universal quantum logic gates. Physical Review Letters, 74(20), 4087.

[4] Yu, N., Duan, R., & Ying, M. (2013). Five two-qubit gates are necessary for implementing the Toffoli gate. Physical Review A, 88(1), 010304.

引理

根据文献[1],对于一个矩阵 $W\in SU(2)$,一定存在 $A,B,C \in SU(2)$,使得 $A\sigma_x B\sigma_x C = W$,以及 $ABC = I$ 同时成立。文献 [1] 中给出了证明,作者使用旋转门构造了$A,B,C$ 三个矩阵:

$A=R_z(\alpha) R_y(\frac{\theta}{2})$

$B=R_y(-\frac{\theta}{2}) R_z(-\frac{\alpha+\beta}{2})$

$C=R_z(\frac{\beta-\alpha}{2})$

可以看出单量子比特的分解一共需要三个参数 $\alpha, \beta, \theta$,这定义了 Bloch 球上的一个任意的旋转。

双量子门的分解

我们先来看看文献 [1] 中介绍了对双量子比特门分解的方法,对于任意的 Controlled-U 操作,可以使用三个单量子比特门和两个CNOT门进行分解:

根据前面的引理,我们可以很容易对上述双量子比特门进行分解。而对于一些特殊的 $W$,分解方式可以有更多的简化。

当 $W$ 满足如下形式:

则可以这样分解:

又当 $W$ 满足如下形式:

则可以这样分解:

三量子比特门的分解

文献[1] 中直接给出了分解方法:

这其中$U,V$都为酉矩阵,并且满足 $V^2=U$。这个电路很容易分析,只要对两个控制比特分成四种情况讨论就很容易验证,但是电路的构造是很巧妙的,我们可以稍微逆向分析一下:

可以看出实际上,前两步的操作保证了 $q_1=0$ 的两种情况下,对 $q_3$ 的操作为单位操作,而第四步操作实际上是完成了剩下的 $q_1=1$ 时的情况。

有了这样的理论我们就可以轻松地将三比特门拆分为两比特门,那么接下来的事情就容易了,即使用上一节的只是,对 Controlled-$V$ 和 Controlled-$V^{\dagger}$ 进行分解就可以了。

由于我们的目标是 Toffoli 门,因此 $U = \sigma_x$,因为我们需要找到 $V$ 使得 $VV=\sigma_x$,设 $V=[a,b;c,d]$,则最终化简得到方程:

$a^2+b^2=0, 2ab=1, a=d, b=c$

可以求出 $a=d=-\frac{i+1}{2}$, $b=c=\frac{i-1}{2}$,因此矩阵可以写为:

$$V = \left( \begin{array}{ccc} -\frac{i+1}{2} & \frac{i-1}{2} \\ \frac{i-1}{2} & -\frac{i+1}{2}\end{array} \right)$$

可以验算 V 是酉矩阵,因此可以用如下通式表示:

可以解得,$\alpha=3\pi/2, \beta=\pi/2, \delta=5\pi/4, \theta=\pi/2$,因此可以使用旋转门和相位门来构造 $V$:

$$V=\Phi(\frac{5\pi}{4})R_z(\frac{3\pi}{2})R_y(\frac{\pi}{2})R_z(\frac{\pi}{2})$$

因此,根据第一节的只是,可以直接给出$A,B,C$的表达式:

$A=R_z(\frac{3\pi}{2})R_y(\frac{\pi}{4})$

$B=R_y(-\frac{\pi}{4})R_z(-\frac{2\pi}{2})$

$C=R_z(-\frac{\pi}{2})$

即满足 $ABC=I$,并且 $A\sigma_x B\sigma_x C= V$,因此总的效果如下:

可以看出这需要七个双量子比特门。

Toffoli 门的近似分解方法

文献 [1] 中也提到,Toffoli门有近似的分解方法:

其中 $A=R_y(\pi/4)$,这种方法会导致本征态 $|100\rangle$ 的相位被翻转。还有一种类似的方法:

这种分解由 Margolous 提出,其构造方法还没有去仔细研究,但是由于其只是一种近似,因此也还是有明显缺陷的。

一些其它方法

在文献[2]中给出了如下的分解方法

其中的操作为:

这种方法一共需要六个双量子比特门,较使用通用方法得到的结果要更好一些,分解的方法暂时还没有具体去研究。

目前最优的方法

目前最优的方法允许只使用5个双量子比特门即可实现,文献[3]中提及,而且较新的研究 [4] 还指出了五个双量子比特门是最少的限度,并证明了3个或4个都无法得到精确的解。文献 [4] 中介绍了 Deutsch gate,这是一种 Toffoli 门的推广,有如下形式:

这种门,貌似目前还没有被实现。这种方法首先定义了一种两比特的通用量子门:

然后使用这个门来定义构造了对于通用三量子比特门的分解方法:

这种方法只需要5个双量子比特门就可以实现。

Leave a Reply

Your email address will not be published. Required fields are marked *