[学习]量子计算

最近学习入门量子计算，总结记录一些学习笔记。
需要亿一点点的线性代数知识。

一、量子比特

1.经典比特与量子比特

经典比特只有两种状态0和1，它们分别代表电路中高电平和低电平，准确来讲是可以用电路中的高低电平来表示。

量子比特也有 和两种状态，量子比特还有其特殊的叠加态。

其中是量子力学中的Dirac表示法，代表向量，与此同时则代表（PS：对于计算机科学家来说没有什么比非对称括号更糟糕的表示方法了。数学：我管你这那的）。学习到后面会发现这是一种十分优雅的表示。比如要表示列向量就可以写成。

而，其中表示共轭转置，与一般的转置不同。不过在实数域上这两者一致。

由此向量内积可以简写成。

而且称为bra，称为ket，合起来称为bra-ket。

量子比特可以使用向量表示，而向量可以通过线性组合的形式来表示。

比如某量子比特，要求，其中。

2.量子比特叠加态

在介绍叠加态之前需要了解一个线性代数概念：张量积。

很好理解，向量的张量积。

与之对应的还有矩阵张量积。特别的张量积幂态表示法 。

n个经典比特只能表示个状态，而且状态空间是离散的。而n个量子比特能表示维度的量子比特空间，状态是连续的。

例如使用两个量子比特，可以表示一个4维的量子比特空间。这个空间存在四个标准正交基向量。其中，如果写成向量形式就可以理解这个基向量的含义。

如果两个量子比特构成的状态可以写成张量积形式，称这个状态为乘积态。否则称之为叠加态。例如就是一个的叠加态，写成向量形式。

可以使用反证法证明这是一个叠加态。

假设存在两个单量子比特和，他们的张量积是。

令这两个单量子比特分别为和，可以得到。

从而知道、、、。

得到矛盾状态和。

因此原命题成立，是叠加态。

3.测量量子比特

量子比特叠加态过于复杂，不能直接得到结果，需要进行测量。

在线性代数中，测量某个向量在向量上的投影长度，使用公式。

在量子比特中也类似，测量量子比特在基准的投影长度（其实是测量概率）使用。

4.布洛赫球

这个东西挺难理解的。很多解释都是利用布洛赫球(bloch sphere)，介绍单量子比特门在做什么。

对于布洛赫球，只简单的提及对应布洛赫球轴正半轴，然后就恰好对应轴负半轴。然后立刻得到X门就是量子比特在布洛赫球上绕着轴旋转180°，Y门是绕着轴旋转180°。在这里X门旋转和矩阵向量计算结果能对应上；而Y门就始终无法理解到为什么会带一个相位（准确来说，相位对应轴正半轴方向，绕轴旋转为什么会引入轴正半轴方向的相位），比如，。

在此希望大佬解释。

先介绍一个概念，复平面。

复数，例如形式的复数，分为实数部分和虚数部分。要绘制复数的图像就需要分别绘制复数的两个部分，于是把普通二维平面坐标系轴当成实数轴，轴当作虚数轴。这样任意复数都可以在复平面上找到对应的点。

现在同样为复平面上的点增加一个约束性条件，要求。就很容易想到一个三角恒等式。于是令和，复数就可以表示为形式。

这时，欧拉公式及其推广式就派上用场。

发现二者恰好一致，可以使用一个变量表示二维方向信息。需要注意的是，只有方向信息，没有长度信息。

---

现在把和的位置在三维坐标空间中表示出来，注意平面用一个数字标记，所以第二个数字表示在轴上。更简单的说，表示在轴正半轴上与单位球的交点；表示单位球与平面的交线。图中红色一圈都表示，只是它们的相位略有不同，而相位不影响量子比特测量结果。

一般表示空间上球坐标，需要三个变量。比如下图球坐标表示为。前面提到用欧拉公式推广形式可以用一个变量表示方向信息，在这里合并的方向信息。

得到球面上量子比特，其中和。

---

这样做不够美观，尤其是表示的状态在图中占据了一系列位置。

增加一个变换，令从而使。在空间上可以想象成包包子过程，把整个上半球向下延展得到完整的球面。这样原本散布在平面上的就收束到轴负半轴上，得到布洛赫球。

• 定义域和。
• 和恰好落在轴正半轴和负半轴上。
• 原坐标系下互相正交的量子比特在布洛赫求坐标系下恰好相反。

二、量子比特门

1.酉矩阵

量子比特采用向量表示，对其进行运算需要引入矩阵。且经过运算后要保证量子比特的模长不变，这个矩阵需要满足一些特殊性质。

在实数域线性代数中，这种矩阵称为实正交矩阵，满足，其中表示阶单位矩阵。

量子比特的系数空间在复数域，对应的矩阵为酉矩阵(Unitary Matrix)，满足，其中表示共轭转置。实正交矩阵是酉矩阵的一个特例。

共轭转置：，虚数部分取反，实数部分不变，然后转置。

很显然，酉矩阵是可逆矩阵，且逆矩阵就是自身的共轭转置。量子计算和经典计算不同在于，量子计算操作是可逆的，而经典计算除非门外不可逆。

2.单量子比特门

懒得画图了，直接放一张找到的网图。

这里需要着重介绍门，常用于量子计算中制备叠加态。同时和这两种特别的表示法会在之后的样例中频繁见到。

另外。类似缩写也需要知道对应的展开形式。

除了以上介绍的常见量子比特门，还有一些带参数的如等，表示绕着轴旋转度，这个酉矩阵表示不唯一。学有余力可以尝试自行推导。我学完无力了。

如果无法理解Dirac表示法，不妨写成向量和矩阵形式，计算矩阵向量的乘积，可以更好理解。

3.多量子比特门

前面介绍都是基础的量子比特门，只能操作一个量子比特。通过矩阵张量积把两个的矩阵变成一个的矩阵，可以得到操作多量子的比特门。

例如双量子比特门就表示仅把第二个量子比特取反。可以代入观察计算结果。

---

控制非门，记作，对应矩阵为。作用是当控制比特为1时，另一个量子比特取反。

同样计算门作用在上的结果。

可以发现没有发生变化，而的第二个量子比特取反。

若将门换成门或者门可以得到对应的控制逻辑门。

---

量子比特门也具有通用性集合。类似于经典逻辑门中，可以用与非门得到其他任何逻辑门，此时与非门构成的集合是经典逻辑门最小通用性集合。

量子比特门的通用性集合，例如：

• {CNOT, 1-qubit比特门}
• {CNOT, H门, 相位门}
• {Toffoli门, H门}

这是很重要的性质，意味着你可以通过合适的组合方法，把基本比特门组合得到期望的比特门。

只要量子技术能制造的比特门覆盖任意通用性集合，就可以执行任意有限精度的量子计算。

门可以通过组合制造新门的特性为量子编译提供理论基础。原因是不同的量子技术制造的比特门在准确率、延迟上有差异，需要选择最适合当前量子技术的比特门实现量子算法。

三、量子算法

1.量子电路

量子算法依赖于量子电路实现。量子电路不像电路，更像是某种流水线。这个流水线按照一定顺序依次操作不同的量子比特，实现量子算法。

下图是包含三个量子比特的量子电路示意图。图中的门表示为控制比特，为被操纵比特。

最后测量特定的量子比特可以得到答案。

2.Deutsch-Jozsa量子算法(单比特版)

虽然这个量子算法没有解决实际问题，但还是介绍这个算法。因为算法简单，而且是首个证明量子计算的优越性的算法。

问题：假设有一个函数满足的映射关系，这个映射函数有可能是常函数，也有可能是对称函数（一半输出0，另一半输出1）。要求编写一个算法验证这个函数是常函数还是对称函数。

显然，经典计算机必须要验证次才能确定是否为常函数。对于量子计算机只需要次操作。

---

直接研究比特的问题比较困难，从开始，此时原问题就可以转化为求解是什么。显然当函数是常函数，那么异或得到0；否则得到1。

搭建对应的求解量子电路，这里出现了从未见过的U门，是数学推演得到。不过不需要关心，只需要知道这个门对于端没有影响，对端进行一个异或计算。

这里笔者就没有花时间学习这部分的内容，将来会补上的。将来！嗯对的。

接下来，按照的顺序解析每一步量子计算后的结果。

首先是，容易得到，表示量子比特和的张量积。

---

然后是状态，没什么需要说明的。

到这一步插一嘴，可以通过合理调整辅助量子比特，取得一个惊人的效果。这里令。此时。为方便表示令。

此时经过门计算：

而，这很好理解，对于端无影响，端变成，正如门上写的那样。那么。

合并两种情况可以得到，成功把函数编码到量子态的相位，这是U门配合输入在这里的作用。

---

端也取一个值，经过门后得到，在单比特版本Deutsch-Jozsa量子算法中，端取不影响最后结果，可以由读者自行证明。

那么，实际上是一次把两种可能的输入叠加在一起，这两种输入的可能性一致。

利用前面得到的结论可以得到：

提取公因式化简，

前面提到的值域为，如果把、和的状态表列出来，可以发现等价于。

0	0	1	0
0	1	-1	1
1	0	-1	1
1	1	1	0

于是成功把目标函数编码到量子比特的相位上。

---

现在，如果，那么；如果，那么。

合并为一个结果，得到：

一个重要观察，第一个量子比特的状态会因为的不同而不同。不过和的表示还是太抽象。对第一个量子比特使用门映射回原状态。

和。最后测量端量子比特在方向上的概率。

若测量得到的概率是0，那么成立；否则成立。

3.Deutsch-Jozsa量子算法(多比特版)

学会单比特的操作，接下来拓展到多个量子比特，比如这个问题需要的个量子比特。

现在端有个量子比特输入，为其赋初始值，端仍然只输入，U门也进行相应的改造，端支持个量子比特的输入。

用同样的方法依次推导状态。

---

首先是状态。

，这是向量张量积，此时是一个维度的向量。

。这里包含从0到所有可能的输入，量子计算神奇的地方在于，可以一次代入超级多的数据进行计算，从而取得无与伦比的加速。

的推导过程如下所示：

---

这里最后一步思维跨度有些大，不妨从2比特的初始情况开始思考。

假设，可以得到，如果把它写成向量形式进行计算，可以得到：

其中，表示属于由0，1构成长度为2的串。

---

推广到，更便于理解包含0到所有的输入。

以此类推，得到：

其中表示是由0，1构成的长度为3的串。

在量子比特一节中我们介绍过向量可以写成。

同样的写法转移到上可以得到：

这两个是等价的，是同一个公式的不同表示形式。

---

现在来推导和的状态。

已知，利用单比特时得到关于U门的结论得到。

至于。

---

如何求？还是需要回到状态和。

已知和，整合为一个公式。在此基础上进一步写成求和形式，其中表示与按比特位相乘后求和。如果分别用和代入式子并展开就可以得到原来的结果。

关于这个式子也有一个比特的推广：

关于这个推广式子的证明，学不懂。这里也不展开证明，总之和当前主题相关性不高。

代入这个式子处理：

---

此时的只是看上去很复杂，实际上最后只关心在方向的投影。

的向量均与正交，投影结果为0，可以直接舍弃这一个求和符号。而且。

最后得到在的概率为。如果是常函数，那么测量概率；否则成立，此刻与恰好相互抵消。

四、总结

对于Deutsch-Jozsa量子算法解决的问题。

经典计算至少需要计算个数字才能确定是常函数还是对称函数，对应的时间复杂度为。

而量子计算机一共执行次门和一次门，以及次测量就得到结果，对应的时间复杂度为。

量子计算取得远超经典计算的加速比。