量子算法的预备知识

Important

想要完全理解量子算法，还是得去阅读量子力学的内容，但在这里，主要讲解一些能够帮助快速入门量子算法的相关概念

在这里，我们抛去太理论的数学公式，仅仅只是从感性上介绍相关的概念

量子计算的物理基础

Cite

量子（Quantum）是物理学中的一个基本概念，指的是物理量的最小不可分割的基本单位，例如电子就属于量子。

量子本质上可以通过量子化进行得到，当我们对一个宏观物体进行无限细分后，直到不得不靠“几个原子”这种单位去描述物体的长度时，量子效应就出场了。薛定谔方程告诉人们，一定会遇到不可分割的最小单位，这种最小单位，统称为量子；这种现象，被称为量子化。

量子化的属性有很多种，但在此优先考虑一种——能量。经过长期探索得知，原子的光谱只会有几个峰值，而不是连续的谱线，这代表了原子内电子的能量只会出现几种情况，电子不可能具有几种情况之外的中间值，这就是能量的量子化。每一种能量，被称之为一个“能级”。

以一栋楼为例，在微观的世界里面，一栋楼的楼梯被拆掉了，这使得微观粒子要么在一楼，要么在二楼，仅存在于整数的楼层，但是，这不代表微观粒子就失去了上下楼的机会，这就是量子的第二个特性——跃迁。

当一个原子中的电子获得了来自原子外的能量时，它就有可能克服能级之间能量的差距，跳跃到另外一个态上面，并且这个电子也可以将自己的能量释放出来，跳跃到能量较低的能级上面。当然，能级本身是稳定的，不管怎么跃迁，电子的能量都只能处在这几个能级上，这是原则（能级的个数与原子序数相关）。

Example

例如高中化学中所学到的，在孤立的原子中，电子占据的原子轨道（如 s、p、d 轨道）具有特定的形状和能量，在发生化学反应形成化合物的过程中（即形成杂化轨道的过程中），会进行以下步骤：

• 在形成分子之前，原子中的一个或多个电子可能被激发到更高的能级，以便有更多的未成对电子参与成键。例如，碳原子在基态下有 2 个未成对的电子（$1s^{2}2s^{2}2p^2$），但在激发态下，一个 2s 电子可以被激发到 2p 轨道，形成 4 个未成对的电子（$1s^{2}2s^{1}2p^3$）。

量子叠加

如果仅仅是把能级建成大楼，然后把大楼的楼梯、电梯全拆掉（并且不追问原因）这件事情倒也不难理解，然而剩余部分，就无法用普通的现实去想象了。

量子叠加性是量子的第三个特性，这个性质来源于一个非常出名的思想实验：薛定谔的猫，这个故事非常简单：

Cite

把一只猫、一个装有毒气的玻璃烧瓶和一个有 50%几率衰变的原子。当盒子内的监控器侦测到衰变粒子时，就会打破烧瓶，杀死这只猫。

经过一小时以后，假若没有发生衰变事件，则猫仍旧存活；否则发生衰变，这套机构被触发，氰化氢挥发，导致猫随即死亡。用以描述整个事件的波函数竟然表达出了活猫与死猫各半纠合在一起的状态。显然这是反直觉的，但这种半死半活的叠加态在量子力学中确实存在。那么，作为宏观世界的我们，到底如何来判断猫是死了还是活着呢？

测量与坍塌

薛定谔宣称，不打开盒子，猫就处于生和死的“叠加态”，又称：“当我们打开盒子，经过了我们的观察，猫就会坍塌到一个确定的生或着死的唯一的状态上”。

这里提出量子的第四个特性：“测量和坍塌假设”。测量和坍塌对量子态的影响仍然是一个争议话题，所以用了“假设”。这个特性的描述如下：

Cite

对于一个叠加态而言，可以去测量它，测量的结果一定是这一组量子化之后的、确定的、分立的态中的一个。测量得到任意的态的概率是这个叠加态和测量态的内积的平方，测量之后，叠加态就会坍塌到这个确定的态之上。

我们对上面这部分内容只做了解即可，明白量子具有的几大性质，尤其是叠加与坍塌，一旦测量，量子会立刻坍缩到某一个状态上，而不再处于状态的叠加

量子计算的数学基础

态矢 (State Vector)

量子态可用线性代数中的向量来描述，在量子理论中，描述量子态的向量称为态矢，态矢分为左矢（bra）和右矢（ket），我们用狄拉克符号来表示：

$$\begin{array}{rl}|\psi ⟩& =[c_1,c_2,\dots ,c_n{]}^T\\ ⟨\psi |& =[c_1^{\ast },c_2^{\ast },\dots ,c_n^{\ast }]\end{array}$$

其中，矢态中的分量均为复数，且相同描述的左右矢，其互为转置共轭

考虑 $|\alpha ⟩=[a_1,\dots ,a_n{]}^T,|\beta ⟩=[b_1,\dots ,b_n{]}^T$，其内积与外积分别定义为：

$$\begin{array}{rl}⟨\alpha |\beta ⟩& =\sum _{i=1}^n{a}_i^{\ast }{b}_i\\ |\alpha ⟩⟨\beta |& =[a_i{b}_j^{\ast }{]}_{n\times n}\end{array}$$

两能级系统

Cite

对于微观量子而言，有一个决定粒子性质的最直接参量——能量。粒子的能量只会在几个分立的能级上面取值，限制取值的可能性种类为两种，这就构成了两能级系统。除了某些特殊的情况之外，这两个能级必定能找出来一个较低的，称之为基态(ground state)，记为  $|g⟩$ ；另一个能量较高的，称之为激发态(excited state)，记为  $|e⟩$

经典比特的取值为 1 或 0，由二极管的通电断电实现，量子比特的取值是二维复空间 ${\mathbb{C}}^2$ 上的单位向量，将其规定为：

$$\begin{array}{rl}|e⟩=|1⟩& =[1,0]\\ |g⟩=|0⟩& =[0,1]\end{array}$$

这样，任意一个量子比特 $|\psi ⟩$ 我们可以写为如下形式：

$$|\psi ⟩=\alpha |0⟩+\beta |1⟩$$

其中 $\alpha ,\beta \in \mathbb{C}$，且 $|\alpha {|}^2+|\beta {|}^2=1$，这里的 $|\alpha {|}^2,|\beta {|}^2$ 表示这个量子比特坍缩到 $|0⟩,|1⟩$ 的概率

显然，上面这个表达式我们可以知道，$|0⟩,|1⟩$ 是这个线性空间的一组标准基（也是正交的）

Info

物理上，实现基元 $|1⟩,|0⟩$ 有多种方案：

1. 电子的自旋：
   • $|0⟩=|\uparrow ⟩$ 为上旋
   • $|1⟩=|\downarrow ⟩$ 为下旋
2. 偏振光子
   • $|0⟩=|\updownarrow ⟩$ 竖直偏振的光子
   • $|1⟩=|\leftrightarrow ⟩$ 水平偏振的光子

几何表示

量子态 $|\psi ⟩$ 是复空间 ${\mathbb{C}}^2$ 中的向量，从实数域上看，${\mathbb{C}}^2$ 是个四维空间，我们很难想象。但借助 ${\mathbb{C}}^2$ 纯态与二维球面 ${\mathcal{S}}^2$ 的对应，我们可以用 Bloch 球面的几何性质理解 ${\mathbb{C}}^2$ 中纯态的几何性质

Important

这里的推导过程较为简单，考虑 $|\psi ⟩=\alpha ket0+\beta |1⟩$，由于 $\alpha ,\beta in\mathbb{C}$，由欧拉公式， 我们有：

$$|\psi ⟩=e^{i\delta }(\cos \theta |0⟩+\sin \theta e^{i\varphi }|1⟩)$$

其中 $e^{i\delta }$ 称作共同相位（global phase），因为对 $|0⟩,|1⟩$ 的影响都一样，无法从实验上测得，因此我们可以将其忽略，于是剩下的部分，我们就可以使用球面几何来描述，这就是布洛赫球

狄拉克符号	坐标轴方向	${\mathcal{S}}^2$坐标	($\theta ,\varphi$)	量子态
$|0⟩$	$z^{+}$	(0, 0, 1)	(0, 0)	$|0⟩=\left[\begin{array}{c}1\\ 0\end{array}\right]$
$|1⟩$	$z^{-}$	(0, 0, -1)	($\pi$, 0)	$|1⟩=\left[\begin{array}{c}0\\ 1\end{array}\right]$
$|+⟩$	$x^{+}$	(1, 0, 0)	($\frac{\pi }{2}$, 0)	$\frac{|0⟩+|1⟩}{\sqrt{2}}=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right]$
$|-⟩$	$x^{-}$	(-1, 0, 0)	($\frac{\pi }{2}$, $\pi$)	$\frac{|0⟩-|1⟩}{\sqrt{2}}=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -1\end{array}\right]$
$|i⟩$	$y^{+}$	(0, 1, 0)	($\frac{\pi }{2}$, $\frac{\pi }{2}$)	$\frac{|0⟩+i|1⟩}{\sqrt{2}}=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ i\end{array}\right]$
$-|i⟩$	$y^{-}$	(0, -1, 0)	($\frac{\pi }{2}$, $\frac{3\pi }{2}$)	$\frac{|0⟩-i|1⟩}{\sqrt{2}}=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -i\end{array}\right]$

可以发现，一个球面上的点 $|\psi ⟩$ 可以被写成三维坐标的形式，我们将其记为 $|\psi ⟩=({\sigma }_x,{\sigma }_y,{\sigma }_z)$

测量

Important

量子比特的信息不能直接获取，而是通过测量来获取量子比特的可观测的信息。可观测量在量子理论中由自伴算子来表征，自伴的有时也称厄密算子。量子理论中的可观测量与经典力学中的动力学量，如位置、动量和角动量等对应，而系统的其他特征，如质量或电荷，并不在可观测量的类别之中，它是作为参数被引入到系统的哈密顿量（Hamiltonian）。

可观测量是一个物理量，可以简单理解为一个厄密算子 $A$，一般与量子态 $|\psi ⟩$ 一起给出：

1. 对 $A$ 做谱分解 $A={\sum }_{i=1}^n{\lambda }_i|{\psi }_i⟩⟨{\psi }_i|$，得到正交基 $\{|{\psi }_i⟩{\}}_{i=1}^n$
2. 对 $|\psi ⟩$ 做正交分解 $|\psi ⟩={\sum }_{i=1}^n{c}_i|{\psi }_i⟩$，于是 $|\psi ⟩$ 为这 $n$ 个状态的叠加态

我们测量本质上是对可观测量进行测量，每次测量有以下规则：

算子 $A$ 的每次测量结果为特征值 ${\lambda }_i$ 中的一个，且得到 ${\lambda }_i$ 的概率为 $|c_i{|}^2$，测量后，量子态坍塌为 $|{\psi }_i⟩$

我们记 $⟨A⟩$ 表示可观测量 $A$ 的测量结果的期望值，可以证明 $⟨A⟩\equiv ⟨\psi |A|\psi ⟩$

Example

哈密顿量 $H$ 是一个可观测量，对应于系统的总能量。一如其他所有算符，哈密顿量的谱为测量系统总能是所有可能结果的集合

状态的演化

我们如何通过一个量子态来得到另一个量子态，换句话说，量子态之间是如何演化的？

这里，对于一个封闭的量子系统，其演化过程我们使用酉变换来描述，具体而言，在 $t_1$ 时刻系统处于量子态 $|{\psi }_1⟩$，经过一个和时间 $t_1,t_2$ 的酉变换 $U$，系统在 $t_2$ 时刻的状态为

$$|{\psi }_2⟩=U|{\psi }_1⟩$$

其中，酉变换 $U$ 是一个矩阵，并且满足 $U{U}^{†}=I$ （可以类比欧氏空间中的正交变换，酉变换就是复空间中的正交变换）

在量子计算中，各种形式的酉变换被称为量子门，例如最经典的泡利 X 门：

$${\sigma }_1\equiv {\sigma }_x\equiv X\equiv \left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$$

其作用在量子态上与经典比特门中的非门效果一致：

$$X|\psi ⟩=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}\alpha \\ \beta \end{array}\right]=\left[\begin{array}{c}\beta \\ \alpha \end{array}\right]$$

于是，$X|0⟩=|1⟩,X|1⟩=|0⟩$

Cite

量子态是随着时间改变的，纯态由波函数 $\psi (t)$ 来描述，随时间的变化规律遵从薛定谔方程：

$$i\hslash \frac{\partial |\psi ⟩}{\partial t}=(-\frac{{\hslash }^2}{2m}{\nabla }^2+V)|\psi ⟩=\hat{H}|\psi ⟩$$

其中 $\hat{H}$ 表示哈密顿算子（哈密顿量），当其随时间改变时，方程的解为：

$$\begin{array}{rl}|\psi (t)⟩& =\mathcal{T}\exp (\frac{-i}{\hslash }{\int }_0^t\hat{H}(t)dt)|\psi (0)⟩\\ & =U(t)|\psi (0)⟩\end{array}$$

其中，$\mathcal{T}$ 表示时间演化算符

多量子比特

上文中，我们只集中在单量子比特，对于存在两个及以上的量子比特系统，我们将其称为复合系统，我们首先介绍什么是张量积。

张量积是两个向量空间形成一个更大向量空间的运算。在量子力学中，量子的状态由希尔伯特空间中的单位向量来描述。

假设 $H_1,H_2$ 分别为 $n_1,n_2$ 维的希尔伯特空间，$H_1$ 与 $H_2$ 的张量积表示一个 $n_1\times n_2$ 维的希尔伯特空间，我们用 $H_1\otimes H_2$ 来表示 ，我们以一个例子来说明其运算规则：

$$\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\end{array}\right]\otimes \left[\begin{array}{cc}{b}_{11}& b_{12}\\ b_{21}& b_{22}\end{array}\right]=\left[\begin{array}{cccccccc}{b}_{11}& b_{12}& |& 2b_{11}& 2b_{12}& |& 3b_{11}& 3b_{12}\\ b_{21}& b_{22}& |& 2b_{21}& 2b_{22}& |& 3b_{21}& 3b_{22}\\ 4b_{11}& 4b_{12}& |& 5b_{11}& 5b_{12}& |& 6b_{11}& 6b_{12}\\ 4b_{21}& 4b_{22}& |& 5b_{21}& 5b_{22}& |& 6b_{21}& 6b_{22}\end{array}\right]$$

对于上文中的狄拉克符号（纯态单量子），我们将其表示为：

$$|\psi ⟩\otimes |\phi ⟩=|\psi \phi ⟩=\left[\begin{array}{c}{\alpha }_1{\beta }_1\\ {\alpha }_1{\beta }_2\\ {\alpha }_2{\beta }_1\\ {\alpha }_2{\beta }_2\end{array}\right]$$

量子计算原理

经典计算中，最基本的单元是比特，而最基本的控制模式是逻辑门，可以通过逻辑门的组合来达到控制电路的目的。类似地，处理量子比特的方式就是量子逻辑门，使用量子逻辑门，有意识的使量子态发生演化，所以量子逻辑门是构成量子算法的基础。

由状态的演化 中提到的，本质上我们需要求得的就是将酉变换的算子 $U(t)$ 线路化，常用的策略为 Problem-inspired ansatz

Problem-inspired ansatz

举一个简单的例子，我们假定，问题的哈密顿量为 $H$，目标是寻找这个哈密顿量的基态，我们将损失函数定义为：

$$\mathcal{C}(\theta )=⟨H⟩=⟨\psi (\theta )|H|\psi (\theta )⟩,|\psi (\theta )⟩=U(\theta )|{\psi }_0⟩$$

其中，$U(\theta )$ 为我们需要生成的量子线路