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

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

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

单量子比特可以由量子态 ∣ 0 ⟩ |0\rangle ∣0⟩或量子态 ∣ 1 ⟩ |1\rangle ∣1⟩表示，分别对应与经典比特0和1。更多地，单量子比特还可以处于量子态 ∣ 0 ⟩ |0\rangle ∣0⟩和 ∣ 1 ⟩ |1\rangle ∣1⟩的中间状态，称之为叠加态。二维Hilbert空间的量子比特状态可以表示为： 其中是 α α α和 β \beta β是复数，并且满足 ∣ α ∣ 2 + ∣ β ∣ 2 = 1 |α|^2+|\beta|^2=1 ∣α∣2+∣β∣2=1。

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

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

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

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

控门中经常用到的主要有作为双量子比特门的受控非门（Controlled NOT Gate，以下简称为CNOT门）和三量子比特的Toffoli门。 CNOT门是双量子比特门，它有两个量子比特作为输入，一个称为控制比特，一个称为目标比特。CNOT门的线路表示和矩阵表示如图所示。 有当控制比特为 ∣ 1 ⟩ |1\rangle ∣1⟩时， X X X门才会起作用，它的执行过程可以被描述为： 其中 c c c表示控制比特， t t t表示目标比特，以及"⊕"表示异或操作。 Toffoli门是三量子比特门，作用在三个量子比特上。其中两个量子比特为控制位，余下一个量子比特为目标位。只有当两个控制比特都为 ∣ 1 ⟩ |1\rangle ∣1⟩时， X X X门才会生效，作用在目标位上。它的操作过程可以由下式描述。 其中 c 1 c_1 c1​和 c 2 c_2 c2​表示控制比特， t t t表示目标比特。该门的线路和矩阵表示如图