参考用书：Kaye, Phillip, Raymond Laflamme, and Michele Mosca.An introduction to quantum computing. OUP Oxford, 2006.

3.1 量子电路模型（The Quantum Circuit Model）

• 一个典型的量子电路如下所示：

每一时刻，量子比特从左向右传播，经由矩形块表示的门进行处理并输出信号。小三角表示基于计算基（computational basis）的测量（measurement）。

3.2 量子门（Quantum Gates）

• 单量子比特门（1-Qubit Gates）：作用在一个二维量子系统上的任意酉算符。

• 泡利门（Pauli gates）： \sigma_{0}\equiv I\equiv\begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix},\sigma_{1}\equiv \sigma_{x}\equiv X\equiv\begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix},\\\sigma_{2}\equiv \sigma_{y}\equiv Y\equiv\begin{bmatrix} 0 & -i\\ i & 0 \end{bmatrix},\sigma_{3}\equiv \sigma_{z}\equiv Z\equiv\begin{bmatrix} 1 & 0\\ 0 & -1 \end{bmatrix}\\

• 对泡利门取幂（exponentiate），可以得到一类特殊的单量子比特门——旋转门（rotation gates）。它们与一个向量在布洛赫球 x-,y-,z- 三个轴坐标的变化相关。比如，NOT门将纯态 |0\rangle 旋转为 |1\rangle ，入股下图所示：

旋转门定义如下： R_{x}(\theta)\equiv\exp(\frac{-i\theta X}{2}),R_{y}(\theta)\equiv\exp(\frac{-i\theta Y}{2}),R_{z}(\theta)\equiv\exp(\frac{-i\theta Z}{2}) 。

• 如果矩阵 A 满足 A^{2}=I ，则 e^{iAx}=\cos(x)I+i\sin(x)A,x\in\mathbb{R}，则旋转门可以改写成： R_{x}(\theta)\equiv\exp(\frac{-i\theta X}{2})=\cos(\frac{\theta}{2})I-i\sin(\frac{\theta}{2})X\\ 。

• 旋转门也可以表示为矩阵的形式，例如： R_{x}(\theta)=\begin{bmatrix} \cos(\frac{\theta}{2}) & -i\sin(\frac{\theta}{2})\\ -i\sin(\frac{\theta}{2}) & \cos(\frac{\theta}{2}) \end{bmatrix}\\

• 假设 U 是一个单量子比特的酉门，那么存在实数 \alpha,\beta,\gamma,\delta 使得： U=e^{i\alpha}R_{z}(\beta)R_{y}(\gamma)R_{z}(\delta)\\

• 假设 U 是一个单量子比特的酉门， l,m 是任意布洛赫球的两个非并行的轴，那么存在实数 \alpha,\beta,\gamma,\delta 使得： U=e^{i\alpha}R_{l}(\beta)R_{m}(\gamma)R_{l}(\delta)\\

• 基于上述定理，有以下推论，即任意一个单量子比特的门都可以写成以下形式： U=e^{i\alpha}AXBXC ，A,B,C 都是酉算符并且满足 ABC=I 。

• 控制 U 门（\text{controlled-}U gate）。给定任意单量子比特门 U ，我们可以类似地定义控制 U 门，表示为 c\text{-}U 。这一个双量子比特门，它的操作如下： c\text{-}U| 0 \rangle| \psi \rangle=| 0 \rangle| \psi \rangle\\ c\text{-}U| 1 \rangle| \psi \rangle=| 1 \rangle U| \psi \rangle

• 给定一个实现了算符 U 的电路 C_{U} ，如果想要实现\text{controlled-}U，一个基本技巧是将 C_{U} 中的每一个门 G 都换成一个控制门 c\text{-}G ，如下图所示：

3.3 量子门的通用集合（Universal Sets of Quantum Gates）

• 在传统计算中我们可以把复杂的计算操作分解为一些更简单操作组成的序列。对于量子计算，我们也希望找到一些门的有限集合，来实现复杂的量子算符。

• 假设我们想要通过其他的酉变换 V 逼近一个想要的酉变换 U ，那么逼近误差定义为： E(U,V)\equiv \max_{|\psi\rangle}\Vert (U-V)|\psi\rangle \Vert\\ 当我们说一个算符 U 可以以任意的精度被逼近时，这表明给定阈值 \epsilon>0 ，我们可以实现一些酉变换 V 使得 E(U,V)<\epsilon 。特别地，有以下性质： E(U_{n}U_{n-1}\dots U_{1},V_{n}V_{n-1}\dots V_{1})\leq E(U_{n},V_{n})+\dots+E(U_{1},V_{1})\\

• 给定一个门集合，如果任意的 \text{n-qubit} 酉算符都能被该集合中门组成的电路逼近，则称该集合是通用的（universal）。

• 给定一个 \text{2-qubit} 门，如果对于以及积态（product state）输入 |\psi\rangle|\phi\rangle ，产生的输出不是积态，则称该门是纠缠门（entangling gate）。

• 一个由任意\text{2-qubit} 门和所有\text{1-qubit} 门组成的集合，是universal的。

• 给定一个门集合，如果任意一个\text{1-qubit} 酉门都可以被该集合中组成的量子电路近似，则称该集合对\text{1-qubit} 门是universal的。

• (Theorem 4.3.5, page 70) 如果一个含有两个\text{1-qubit} 旋转门的集合 \mathcal{G}=\{ R_{l}(\beta),R_{m}(\gamma) \} 满足：1. l,m 是布洛赫球的非平行轴。2. \beta,\gamma\in[0,2\pi) 并且 \frac{\beta}{\pi},\frac{\gamma}{\pi} 是无理的（not rational）。则该集合对\text{1-qubit} 门是universal的。

• 哈达玛门（Hadamard gate） H ： H|0\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle),\\H|1\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\\，其矩阵表示为 H=\frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} ，并且 H=H^{-1} 。

• \frac{\pi}{8}\text{-phase} 门 T ： T|0\rangle=|0\rangle,T|1\rangle=e^{i\frac{\pi}{4}}|1\rangle\\ ，其矩阵表示为 T=\frac{1}{\sqrt{2}} \begin{bmatrix} e^{-i\frac{\pi}{8}} & 0\\ 0 & e^{i\frac{\pi}{8}} \end{bmatrix} 。

• 集合 G=\{HTHT,THTH\} ， \{H,T\} 对\text{1-qubit} 门是universal的。

• 根据前述定理，集合\{\text{CNOT},H,T\} 是一个universal的门集合。

3.4 近似酉变换的效率（Efficiency of Approximating Unitary Transformations）

• Solovay-Kitaev定理：如果 \mathcal{G} 是一个满足(Theorem 4.3.5, page 70) 的有限集，并且对于任意的 g\in\mathcal{G} ，它的逆 g^{-1} 都可以由 \mathcal{G} 中的门组成的序列实现，则任意\text{1-qubit} 门都可以用\mathcal{G}中 O(\log^{c}(\frac{1}{\epsilon})) 个门组成的电路逼近（误差至多为 \epsilon ），其中是一个正的常数。

3.5 基于量子电路的测量实现（Implementing Measurements with Quantum Circuits）

• 回顾一下测量公理（measurement postulate）：给定系统 A ， B=\{|\varphi_{i}\rangle\} 是一组状态空间 \mathcal{H}_{A} 的正交基，我们定义冯洛伊曼测量（Von Neumann measurement）如下： |\psi\rangle=\sum_{i}\alpha_{i}|\varphi_{i}\rangle,\\ 其以 |\alpha_{i}|^{2} 的概率输出标签 i 并将该系统留在状态 |i\rangle 。进一步地，给定一个来自双边状态空间 \mathcal{H}_{A}\bigotimes\mathcal{H}_{B} 的向量 |\psi\rangle=\sum_{i}\alpha_{i}|\varphi_{i}\rangle|\gamma_{i}\rangle ，其中 |\varphi_{i}\rangle 是正交的， |\gamma_{i}\rangle 的范数为1，则在系统A上进行冯洛伊曼测量将会以|\alpha_{i}|^{2} 的概率输出标签 i 并将该系统留在状态 |\varphi_{i}\rangle|\gamma_{i}\rangle。由于 \alpha_{i}=\langle\varphi_{i}||\psi\rangle=\langle\varphi_{i}|\psi\rangle ，因此 |\alpha_{i}|^{2}=\alpha_{i}^{*}\alpha_{i}=\langle\psi|\varphi_{i}\rangle\langle\varphi_{i}|\psi\rangle\\

• 下图所示的量子电路实现了关于基 \{|\phi_{j}\rangle\} 的冯洛伊曼测量：

首先使用酉变换 U 对原状态向量进行基变换，再基于计算基进行测量，最后再使用逆变换（反向运行量子电路，把其中每个门都换成对应的逆）得到留置状态。

• 贝尔基（Bell basis, also called EPR pairs）： |\beta_{00}\rangle=\frac{1}{\sqrt{2}}|00\rangle+\frac{1}{\sqrt{2}}|11\rangle,|\beta_{01}\rangle=\frac{1}{\sqrt{2}}|01\rangle+\frac{1}{\sqrt{2}}|10\rangle,\\ |\beta_{10}\rangle=\frac{1}{\sqrt{2}}|00\rangle-\frac{1}{\sqrt{2}}|11\rangle,|\beta_{11}\rangle=\frac{1}{\sqrt{2}}|01\rangle-\frac{1}{\sqrt{2}}|10\rangle\\

• 下图展示了将computational basis变换为贝尔基的量子电路：

• 对于量子计算，特别是量子错误校正（quantum error correction），实现通用的投影测量和非完备的冯诺依曼测量是很重要的。考虑一个基于分解 I=\sum_{i}P_{i}, \text{rank}(P_{i})=r_{i} 的投影测量，即 P_{i}=\sum_{j=1}^{r_{i}}|\psi_{i,j}\rangle\langle\psi_{i,j}| ，状态集合 \{|\psi_{i,j}\rangle\} 是希尔伯特空间的一组正交基，并且 N=\sum_{i}r_{i} 。给定电路 U_{P}:|\psi_{i,j}\rangle|0\rangle\rightarrow|\psi_{i,j}\rangle|j\rangle ，实现该电路的一种方法是基变换 U:|\psi_{i,j}\rangle\rightarrow|i,j\rangle ，复制 j 到辅助寄存器（ancilla register）中，然后再使用 U^{-1} 。