量子计算系列：

唠唠闲话

量子系列第三篇，介绍量子门与量子电路的基础知识，内容如下

单量子门与多量子门

实现方式

数据和运算是计算机的两个重要部分。

  1. 经典计算：数据单位为比特，取值0或1，由二极管的通电断电实现。
  2. 量子计算：数据单位为量子比特，取值为 Bloch 球面向量，无穷集；由偏振光子，自旋 12\frac{1}{2} 粒子等实现。
  3. 经典计算：运算用逻辑门，通过电路实现。
  4. 量子计算：运算用量子门，通过磁场等方式实现。

注记：

  • 量子门对应薛定谔方程的时间演化算子，是一个酉变换，但在量子电路中简化为常量矩阵，为理想模型。
  • 经典电路是现实意义的电路，电路图和实际连线方式有联系，运算在空间上连接
  • 量子电路只是运算过程的抽象，电路图与物理实现方式无关，运算在时间上连接

常见逻辑门有：与，或，非，与非，或非，异或，同或，电路符号如下

应用例子：通过“与门”和“异或门”，实现二进制数的一位数加法

延伸：计算机是如何运算的，用加法机介绍计算机的基本组成部件。

单量子门

n 量子比特的量子门为 2n2^n 阶酉矩阵，特别地，单量子门为 2 阶矩阵。常用的单量子门：

名称 符号 矩阵 狄拉克符号
I 门 I (1001)\begin{pmatrix} 1&0\\ 0&1\end{pmatrix} ∣0⟩⟨0∣+∣1⟩⟨1∣\vert 0\rangle\langle 0\vert+\vert 1\rangle\langle 1\vert
X 门 X, ⨁\bigoplus σx, (0110)\sigma_x,\ \begin{pmatrix} 0&1\\ 1&0\end{pmatrix} ∣1⟩⟨0∣+∣0⟩⟨1∣\vert 1\rangle\langle 0\vert+\vert 0\rangle\langle 1\vert
Y 门 Y iσy, (01−10)i\sigma_y,\ \begin{pmatrix} 0&1\\ -1&0\end{pmatrix} ∣0⟩⟨1∣−∣1⟩⟨0∣\vert 0\rangle\langle 1\vert-\vert 1\rangle\langle 0\vert
Z 门 Z σz, (100−1)\sigma_z,\ \begin{pmatrix} 1&0\\ 0&-1\end{pmatrix} ∣0⟩⟨0∣−∣1⟩⟨1∣\vert 0\rangle\langle 0\vert-\vert 1\rangle\langle 1\vert
Hadamard 门 H 12(111−1)\frac{1}{\sqrt{2}}\begin{pmatrix} 1&1\\ 1&-1\end{pmatrix} 12(∣0⟩+∣1⟩)⟨0∣\frac{1}{\sqrt 2}(\vert 0\rangle+\vert 1\rangle)\langle 0\vert + 12(∣0⟩−∣1⟩)⟨1∣\frac{1}{\sqrt 2}(\vert 0\rangle-\vert 1\rangle)\langle 1\vert

注记：

  • Y 门可以用 X 门和 Z 门生成（Y=ZX）
  • X 门也称为反门，非门(negation)
  • 狄拉克符号读法：∣像⟩⟨原像∣\vert 像\rangle\langle 原像\vert，比如 H 门的 (∣0⟩+∣1⟩)⟨0∣(\vert 0\rangle+\vert 1\rangle)\langle 0\vert 表示作用在 ∣0⟩\vert 0\rangle 上，得到纠缠态 (∣0⟩+∣1⟩)(\vert 0\rangle + \vert 1\rangle)

二进制索引

  1. 矩阵索引从0记起，此时 ∣i⟩⟨j∣=ei,j\vert i\rangle\langle j\vert=e_{i,j} ，比如

    ∣0⟩⟨1∣=(10)(01)=(0100)=e0,1\begin{align*} \vert 0\rangle\langle 1\vert &=\begin{pmatrix}1\\ 0\end{pmatrix}\begin{pmatrix}0&1\end{pmatrix}\\ &=\begin{pmatrix}0&1\\ 0&0\end{pmatrix}=e_{0,1} \end{align*}

  2. 多量子比特系统中，将 01 序列写为二进制数

    ∣m⟩=∣i1⋯in⟩=(0 0⋯ 0 1(m) 0⋯0)twhere m=2n−1i1+⋯+2in−1+in, ik∈{0,1}\begin{align*} \vert m\rangle=&\vert i_1\cdots i_n\rangle\\ =&(0\ 0\cdots\ 0\ \overset{(m)}{1}\ 0\cdots 0)^t\\ where\ m=&2^{n-1}i_1+\cdots+2i_{n-1}+i_n,\ i_k\in\{0,1\} \end{align*}

  3. 写法与克罗克积的定义相容，比如

    ∣2⟩:=∣10⟩=∣1⟩⊗∣0⟩=(01)⊗(10)=(0010)\begin{align*} \vert 2\rangle:=&\vert 10\rangle=\vert 1\rangle\otimes\vert 0\rangle\\ =&\begin{pmatrix}0\\ 1\end{pmatrix}\otimes\begin{pmatrix}1\\ 0\end{pmatrix}=\begin{pmatrix}0\\0\\1\\0\end{pmatrix} \end{align*}

  4. 多量子门酉矩阵的第 mm 行描述对量子态 ∣i1⋯in⟩\vert i_1\cdots i_n\rangle 的作用结果，比如 Toffoli 门

    (1000000001000000001000000001000000001000000001000000000100000010)\left(\begin{array}{rrrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right)

    左乘效果为最后两行置换，对应 ∣6⟩=∣110⟩\vert 6\rangle=\vert 110\rangle 与 ∣7⟩=∣111⟩\vert 7\rangle=\vert 111\rangle 的置换。

多量子门

受控门

  1. 受控非门，亦称为 CNOT 门，CX 门，记号 UCNOTU_{CNOT}，矩阵形式：

    (1000010000010010)\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0 &0 \\ 0 & 0 & 0 &1 \\ 0 & 0 & 1 &0 \end{pmatrix}

    狄拉克记号：

    ∣0⟩⟨0∣⊗I+∣1⟩⟨1∣⊗X\vert 0\rangle\langle 0\vert\otimes I + \vert 1\rangle\langle 1\vert\otimes X

    UCNOTU_{CNOT} 中，第 1 个比特称为控制比特，保持不变；第 2 个比特称为目标比特，受第 1 个比特控制。电路图：

  2. 一般受控门的矩阵形式：

    (10001000U)\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & U \end{pmatrix}

    狄拉克记号：

    ∣0⟩⟨0∣⊗I+∣1⟩⟨1∣⊗U\vert 0\rangle\langle 0\vert\otimes I + \vert 1\rangle\langle 1\vert\otimes U

    电路图：

n 个比特的量子门为 2n2^n 阶矩阵，阶数随 n 指数增长；在表现量子门作用效果时，矩阵形式不方便。使用狄拉克符号，量子门有这几种常用写法：

  • 局部写法和整体写法

∣ψ1⟩⟨ψ2∣⊗∣φ1⟩⟨φ2∣=∣ψ1φ1⟩⟨ψ2φ2∣ \vert \psi_1\rangle\langle \psi_2\vert\otimes \vert \varphi_1\rangle\langle \varphi_2\vert= \vert \psi_1\varphi_1\rangle\langle \psi_2\varphi_2\vert

  • 映射形式，比如控制非门：

∣i,j⟩⟶UCNOT∣i,i⊕j⟩\vert i,j\rangle \overset{U_{CNOT}}{\longrightarrow}\vert i,i\oplus j\rangle

其中 ⊕\oplus 为 Z2\mathbb{Z}_2 上的加法。

  • 映射形式，比如 Hadamard 门：

∣i⟩⟶H12(∣0⟩+(−1)i∣1⟩)=12∑0≤i<2(−1)i∣i⟩\vert i\rangle\overset{H}{\longrightarrow} \frac{1}{\sqrt 2}\left(\vert 0\rangle+(-1)^i\vert 1\rangle\right)=\frac {1}{\sqrt {2}}\sum_{0\leq i<2}(-1)^i\vert i\rangle

通用量子门

  1. 单量子门与受控非门构成通用量子门，即通过二者的复合与张量，可以构造任意量子门。数学表述：

    ∀ U∈U(C2n), ∃ {Ui,j}⊆Universal Gates, s.t.U=(U1,1⊗⋯⊗U1,k1)⋯(Um,1⊗⋯⊗Um,km)\forall\ U\in U(\mathbb{C}^{2^n}),\ \exists\ \{U_{i,j}\}\subseteq Universal\ Gates,\ s.t.\\ U=(U_{1,1}\otimes\cdots\otimes U_{1,k_1})\cdots(U_{m,1}\otimes\cdots\otimes U_{m,k_m})

    证明繁琐，只需知晓：实现一般量子门的关键是控制非门和任意单量子门
  2. 举个例子，用控制非门和 HH 门，实现“颠倒”的控制非门：

其他量子门

这几个量子门经常会用到：

  1. Walsh-Hadamard 门，记号 WnW_n，狄拉克符号：

    Wn=(UH)⊗nW_n=(U_H)^{\otimes n}

    特别地，W1=UHW_1=U_H 为 Hadamard 门。
    映射形式：

    ∣α⟩=∣i1⋯in⟩↦⨂k=1n(∣0⟩+(−1)ik∣1⟩)=12n∑β∈{0,1}⊗n(−1)α⋅β∣β⟩\vert\alpha\rangle=\vert i_1\cdots i_n\rangle\mapsto\bigotimes_{k=1}^n(\vert 0\rangle+(-1)^{i_k}\vert 1\rangle)=\frac {1}{\sqrt {2^n}}\sum_{\beta\in\{0,1\}^{\otimes n}}(-1)^{\alpha \cdot \beta}\vert\beta\rangle

    其中 α⋅β\alpha \cdot \beta 为向量点积。
    特别地，WnW_n 门作用量子态 ∣0⟩⊗n\vert 0\rangle^{\otimes n} 上，得到 2n2^n 种状态的叠加

    ∑0≤i<2n12n∣i⟩\sum_{0\leq i< 2^n}\frac{1}{\sqrt{2^n}}\vert i\rangle

    注：Detusch Josza 算法就是借助 WnW_n 门产生叠加态，做并行计算

  2. UHU_H 和 UCNOTU_{CNOT} 组合，用于构造 Bell 态，产生纠缠粒子：

    ∣00⟩⟶H⊗I12(∣00⟩+∣10⟩)⟶UCNOT12(∣00⟩+∣11⟩)∣01⟩⟶H⊗I12(∣01⟩+∣11⟩)⟶UCNOT12(∣01⟩+∣10⟩)∣10⟩⟶H⊗I12(∣00⟩−∣10⟩)⟶UCNOT12(∣00⟩−∣11⟩)∣11⟩⟶H⊗I12(∣01⟩−∣11⟩)⟶UCNOT12(∣01⟩−∣10⟩)\begin{align*} \vert 00\rangle\overset{H\otimes I}{\longrightarrow}&\frac{1}{\sqrt 2}(\vert 00\rangle +\vert 10\rangle)\overset{U_{CNOT}}{\longrightarrow}\frac{1}{\sqrt 2}(\vert 00\rangle +\vert 11\rangle)\\ \vert 01\rangle\overset{H\otimes I}{\longrightarrow}&\frac{1}{\sqrt 2}(\vert 01\rangle +\vert 11\rangle)\overset{U_{CNOT}}{\longrightarrow}\frac{1}{\sqrt 2}(\vert 01\rangle +\vert 10\rangle)\\ \vert 10\rangle\overset{H\otimes I}{\longrightarrow}&\frac{1}{\sqrt 2}(\vert 00\rangle -\vert 10\rangle)\overset{U_{CNOT}}{\longrightarrow}\frac{1}{\sqrt 2}(\vert 00\rangle -\vert 11\rangle)\\ \vert 11\rangle\overset{H\otimes I}{\longrightarrow}&\frac{1}{\sqrt 2}(\vert 01\rangle -\vert 11\rangle)\overset{U_{CNOT}}{\longrightarrow}\frac{1}{\sqrt 2}(\vert 01\rangle -\vert 10\rangle)\\ \end{align*}

  3. 交换门，记号 USWAPU_{SWAP}，用于交换比特状态：

    电路图写成通用量子门形式：

    ∣i,j⟩⟶UCNOT∣i,i⊕j⟩⟶UCNOT′∣i⊕(i⊕j),i⊕j⟩=∣j,i⊕j⟩⟶UCNOT∣i,(i⊕j)⊕j⟩=∣j,i⟩\begin{align*} \vert i,j\rangle \overset{U_{CNOT}}{\longrightarrow} &\vert i,i\oplus j\rangle\\ \overset{U_{CNOT}'}{\longrightarrow} &\vert i\oplus(i\oplus j),i\oplus j\rangle=\vert j,i\oplus j\rangle\\ \overset{U_{CNOT}}{\longrightarrow} &\vert i,(i\oplus j)\oplus j\rangle=\vert j,i\rangle \end{align*}

  4. Toffoli 门，也称为 CCNOT 门，当两个控制比特取 ∣1⟩\vert 1\rangle 时，目标比特取反。Toffoli 门可用于构造经典电路，狄拉克符号：

    UCCNOT=∣0⟩⟨0∣⊗I⊗I+∣1⟩⟨1∣⊗UCNOT=(∣00⟩⟨00∣+∣01⟩⟨01∣+∣10⟩⟨10∣)⊗I+∣11⟩⟨11∣⊗X\begin{align*} U_{CCNOT}&=\vert 0\rangle\langle 0\vert\otimes I\otimes I + \vert 1\rangle\langle 1\vert\otimes U_{CNOT}\\ &=(\vert 00\rangle\langle 00\vert+\vert 01\rangle\langle 01\vert+\vert 10\rangle\langle 10\vert)\otimes I \\ &\quad+ \vert 11\rangle\langle 11\vert\otimes X \end{align*}

    由狄拉克符号，容易读取作用性质，两个等式对应两种视角
    映射形式：

    ∣i0,i1,i2⟩⟶UCCNOT∣i0,i1,i0i1⊕i2⟩\vert i_0,i_1,i_2\rangle\overset{U_{CCNOT}}{\longrightarrow}\vert i_0,i_1,i_0i_1\oplus i_2\rangle

    矩阵形式：

    (1000000001000000001000000001000000001000000001000000000100000010)\left(\begin{array}{rrrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right)

    矩阵只有后两列“非平凡”，表明 UCCNOTU_{CCNOT} 交换量子态 ∣110⟩,∣111⟩\vert 110\rangle,\vert 111\rangle，其他不变。
    电路图：

量子门记号和矩阵（wiki 百科）：

Toffoli 门与逻辑门

令量子电路中的状态 ∣0⟩\vert 0\rangle 和 ∣1⟩\vert 1\rangle 与经典电路的0-1 对应。用 Toffoli 门和 XX 门可以生成基本逻辑门的“与”，“或”和“非”，继而构造所有经典逻辑门。

  1. “非” 运算符为 ¬\neg，用 Toffoli 门实现：

    量子态变化过程：

    ∣1,1,x⟩⟶UCCNOT∣1,1,1⊕x⟩=∣1,1,¬x⟩\vert 1,1,x\rangle\overset{U_{CCNOT}}{\longrightarrow}\vert 1,1,1\oplus x\rangle=\vert 1,1,\neg x\rangle

  2. “与” 运算符为 ∧\wedge ，真值表：

    与门 0 1
    0 0 0
    1 0 1

    用 Toffoli 门实现：

    量子态变化过程：

    ∣x,y,0⟩⟶UCCNOT∣x,y,xy⟩=∣x,y,x∧y⟩\vert x,y,0\rangle\overset{U_{CCNOT}}{\longrightarrow}\vert x,y,xy\rangle=\vert x,y,x\wedge y\rangle

  3. “或” 运算符为 ∨\vee ，真值表

    或门 0 1
    0 0 1
    1 1 0

    用 Toffoli 门实现：

    量子态变化过程：

    ∣x,y,0⟩⟶X⊗X⊗I∣¬x,¬y,0⟩⟶UCCNOT∣¬x,¬y,(¬x)∧(¬y)⟩=∣¬x,¬y,¬(x∨y)⟩⟶I⊗I⊗X∣¬x,¬y,x∨y⟩\begin{align*} \vert x,y,0\rangle\overset{X\otimes X\otimes I}{\longrightarrow}&\vert \neg x,\neg y,0\rangle\\ \overset{U_{CCNOT}}{\longrightarrow}&\vert \neg x,\neg y,(\neg x)\wedge(\neg y)\rangle=\vert \neg x,\neg y,\neg (x\vee y)\rangle\\ \overset{I\otimes I\otimes X}{\longrightarrow}&\vert \neg x,\neg y,x\vee y\rangle\\ \end{align*}

Ps：“与非门”和“或非门”称为通用逻辑门，也可以生成所有经典逻辑门。

可逆计算

20 世纪中叶，人们发现计算机芯片的能耗会导致芯片发热，限制芯片集成度，进而影响计算机的运行速度。物理学家兰道尔发现，芯片能耗主要源于计算中的不可逆操作。
可逆计算（Reversible Computing），是一种计算模型，它的计算过程是可逆的。在这种计算模型中，使用的能量很低，熵的增加会最小化，换句话说，它几乎不会产生额外的热。

  1. 经典逻辑门多数是不可逆的，比如“与门”：

    ∧:{0,1}⊗2→{0,1}(0,0)↦0(0,1)↦0(1,0)↦0(1,1)↦1\begin{align*} \wedge:\{0,1\}^{\otimes 2}&\rightarrow \{0,1\}\\ (0,0) &\mapsto 0\\ (0,1) &\mapsto 0\\ (1,0) &\mapsto 0\\ (1,1) &\mapsto 1 \end{align*}

    当 x∧y=1x\wedge y=1 时，无法反推 (x,y)(x,y) 取值。
  2. 量子电路中，量子门为酉矩阵，为可逆矩阵，运算自然可逆。
  3. 前边用 Toffoli 门实现不可逆的“与门”时，保留了前两个比特的信息，从而使计算可逆。

不可克隆定理

不可克隆定理指出：未知的量子态 ∣ψ⟩\vert\psi\rangle 不可能通过酉变换复制信息。换言之，不存在满足如下形式的量子门，对任意 ∣ψ⟩\vert\psi\rangle 成立：

反证法，取正交的两个量子态 ∣ψ⟩,∣φ⟩\vert\psi\rangle,\vert\varphi\rangle，则：

U∣0,ψ⟩=∣ψ,ψ⟩U∣0,φ⟩=∣φ,φ⟩U∣0⟩12(∣ψ⟩+∣φ⟩)=12(U∣0,ψ⟩+U∣0,φ⟩)=12(∣ψ,ψ⟩+∣φ,φ⟩)(1)U∣0⟩12(∣ψ⟩+∣φ⟩)=12(∣ψ⟩+∣φ⟩)(∣ψ⟩+∣φ⟩)=12(∣ψ,ψ⟩+∣ψ,φ⟩+∣φ,ψ⟩+∣φ,φ⟩)(2)\begin{align*} U\vert 0,\psi\rangle &= \vert \psi,\psi\rangle\\ U\vert 0,\varphi\rangle &=\vert \varphi,\varphi\rangle\\ U\vert 0\rangle\frac{1}{\sqrt 2}(\vert\psi\rangle+\vert\varphi\rangle)&=\frac{1}{\sqrt 2}(U\vert 0,\psi\rangle+U\vert 0,\varphi\rangle)\\ &=\frac{1}{\sqrt 2}(\vert \psi,\psi\rangle+\vert \varphi,\varphi\rangle)&(1)\\ U\vert 0\rangle\frac{1}{\sqrt 2}(\vert\psi\rangle+\vert\varphi\rangle)&=\frac{1}{2}(\vert\psi\rangle+\vert\varphi\rangle)(\vert\psi\rangle+\vert\varphi\rangle)\\ &=\frac 12(\vert\psi,\psi\rangle+\vert\psi,\varphi\rangle+\vert\varphi,\psi\rangle+\vert\varphi,\varphi\rangle)&(2) \end{align*}

比较 (1),(2)(1),(2) 系数，导出矛盾。

注记：

  • 不可克隆定理指出：不存在酉变换，可以复制任意量子态的信息。
  • 如果未知量子态取值局限在 ∣0⟩\vert 0\rangle 和 ∣1⟩\vert 1\rangle，通过 CNOT 门就能复制。

    ∣i,0⟩⟶UCNOT∣i,i⊕0⟩=∣i,i⟩\vert i,0\rangle \overset{U_{CNOT}}{\longrightarrow}\vert i,i\oplus 0\rangle=\vert i,i\rangle

  • 类似还有“不可删除定理”，一种理解是：酉变换为可逆计算，因而信息不增不减。