---

前言

量子算法是利用量子力学的特性巧妙地解决经典算法中的计算难题。它是将量子计算与量子信息理论融入到算法设计中。在这里，简单介绍一下量子计算基础。

---

一、量子计算基础

量子计算是以量子（微观粒子）结构与运动规律上的特性为基础发展而来具有巨大潜力的计算模式。对照于经典计算，量子计算的计算基础单元为量子比特。此外，还存在很多其它的与经典计算不同的性质，接下来我们将介绍部分量子计算中的一些基本性质。

1. 量子比特

经典计算机的运算与存储信息的基本单元是比特（bit），它的状态用0或者1来表示。而在量子计算机中运算与存储的基本单元为量子比特（qubit），它表示物理系统中某一时刻量子的状态，蕴藏着此时刻量子的所有信息。单个量子比特的状态通常由二维希尔伯特（Hilbert）空间的一组基态向量描述，这组基态一般表示为：

和

单量子比特可以由量子态$|0⟩$或量子态$|1⟩$表示，分别对应与经典比特0和1。更多地，单量子比特还可以处于量子态$|0⟩$和$|1⟩$的中间状态，称之为叠加态。二维Hilbert空间的量子比特状态可以表示为：

其中是$\alpha$和$\beta$是复数，并且满足$|\alpha {|}^2+|\beta {|}^2=1$。

2. 量子并行特性

量子并行性是量子计算一种重要的特性，它是指在相同的时间节点并在同一个量子线路上完成多个计算，即，利用同一个量子线路同时算出函数$f(x)$在不同$x$值处的函数值。
具体地说，假设计算定义域和值域都是单量子比特的函数$f(x):0,1\to 0,1$，利用经典计算则需要两次运算才会输出$f(x)$在0和1处的函数值。而在量子计算中，只需要利用量子电路进行一次计算就会同时得到$f(0)$和$f(1)$的值，这个过程就是量子并行性的表现。相对于经典利用多个电路，增加硬件的方法进行并行计算不同，量子计算是利用量子比特的叠加性，利用单个$f(x)$线路来同时计算出所有$x$的函数值。

二、量子基本门

量子线路是描述量子计算的通用语言，有效且有力地刻画出量子算法。如经典的计算机是将输入比特通过一系列逻辑门（Gate）构成的集成电路从而完成计算任务一样，量子计算机执行特定的计算任务也需要应用由单量子比特门（Single Qubit Gate）、多量子比特门以及量子测量（Quantum Measurement）组成的量子电路（Quantum Circuit）。本小节主要介绍常见的量子比特门以及量子测量，这些也是本文算法设计中常用的工具。

1. 单量子比特门

量子比特的运算操作与经典比特的逻辑门操作不同，量子计算操作是将量子态进行酉变换来处理包含在量子态中的信息。正如量子力学四个基本假设之二，一个封闭的量子系统的演化可以由酉变换来表示。其中，每一个酉变换就对应着一个量子门的应用，每个量子门用数学理论表示就是一个具有酉性的矩阵，即矩阵$U$满足$U{U}^{+}=I$（这里$U^{+}$称为$U$的复共轭转置，$I$为单位矩阵）。
单量子比特门是量子门中最为简单和基础的门电路，它只对一个量子比特进行酉操作，在数学上表现为一个2×2的酉矩阵。在下图中展示了一些量子计算中常见的单量子比特门，相应的线路符号表示以及它们的矩阵表示。

接下来，我们以$|0⟩$量子态在Hadamard门上酉变化为例，简单介绍一下量子门的操作。$|0⟩$态经过Hadamard门运算后的状态为：

其中，$|+⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$。

2. 多量子比特门

多量子比特门主要为受控门，它由多个控制位控制一个目标位构成。以$n（n\ge 2)$量子比特受控U门为例，它有$n-1$个控制位和1目标位，当$n-1$个控制位全部为$|1⟩$时，$U$才作用于目标量子位，线路如图所示。

控门中经常用到的主要有作为双量子比特门的受控非门（Controlled NOT Gate，以下简称为CNOT门）和三量子比特的Toffoli门。
CNOT门是双量子比特门，它有两个量子比特作为输入，一个称为控制比特，一个称为目标比特。CNOT门的线路表示和矩阵表示如图所示。

有当控制比特为$|1⟩$时，$X$门才会起作用，它的执行过程可以被描述为：

其中$c$表示控制比特，$t$表示目标比特，以及"⊕"表示异或操作。
Toffoli门是三量子比特门，作用在三个量子比特上。其中两个量子比特为控制位，余下一个量子比特为目标位。只有当两个控制比特都为$|1⟩$时，$X$门才会生效，作用在目标位上。它的操作过程可以由下式描述。

其中$c_1$和$c_2$表示控制比特，$t$表示目标比特。该门的线路和矩阵表示如图