• qubit
• 类似于传统计算机的比特，量子计算机也会使用一些物理量来表示【量子比特】，比如电子的自旋（向上/向下），或者光的偏振（垂直/水平）
• 使用表示量子 0，使用表示量子 1

• 内积(inner product)：
  • 类似于条件概率，意为：如果量子初始状态是，那么测量到的概率是多少
  • 其中被称为 bra，被称为 ket
  • 被称为 braket
• 叠加态(superposition of states)：
  • 众所周知量子态是可以叠加的，所以对于一个量子态，可以同时是或
  • 是的概率为，是的概率为。显然
• 张量积(tensor product)：
  • 张量积与内积的运算示例：
• 外积(outer product):
  • 物理意义：投影
    • 比如：求在上的投影

使用电路图描述量子运算。左边是输入的 n 个量子比特，右边是输出的 n 个量子比特，中间是量子逻辑门

类似于传统计算机的门电路，量子电路里面也有各种量子逻辑门(quantum logic gates)

可以看到，所有逻辑门的输入和输出量子比特个数相等，不像传统计算机，可以输入 N 个比特，输出 1 个比特。

量子电路是可逆的， 因为输入和输出一一对应，知道输出可以反推输入。

量子逻辑门里面很重要的一个门是 Hadamard 门， 可以用来创建叠加态的量子比特 ，比如 50% 概率是量子 0，50% 概率是量子 1

不可克隆原理 ：如果不读取/观测一个量子量，就无法复制这个量子量。

但是一旦读取/观测，量子态就会坍缩/被破坏。所以量子加密通信可以提供更高的安全性。

因为单个量子位有两个分量和，所以可以使用矩阵表示量子位。上面的数字(a)表示的分量，下面的数字(b)表示的分量。其中，并且 a/b 可以为负数。

如果要同时表示多个量子位的状态，需要使用张量积。

以两个量子位举例，会得到一个 4 行 1 列的矩阵，自上而下分别表示的分量，的分量，的分量，的分量。

量子逻辑门也可以使用矩阵的形式表示。进行逻辑运算的时候，量子逻辑门矩阵在乘法左侧

前文说过量子电路是可逆的，N 个输入与 N 个输出一一对应。因为量子逻辑门本质上是矩阵运算，而知道矩阵乘法的结果和其中一个因子，是可以算出来另一个因子的。

但是传统计算机中的逻辑门通常不是可逆的，比如 AND 门，两个输入对应一个输出。此时需要先把这种逻辑门转换为可逆的逻辑门

以 AND 门举例，传统计算机里面：

AND(0, 0) == 0;
AND(0, 1) == 0;
AND(1, 0) == 0;
AND(1, 1) == 1;

为了使输入和输出一一对应，构造如下函数：

function ReversibleAND(a, b, c) {
  return [a, b, XOR(AND(a, b), c)];
}

这样输入和输出就可以一一对应了，但是需要的比特数量增加了。其他函数可以类比此方案实现可逆化

Deutsch-Jozsa 算法

最简单的用来感受量子计算优势的算法

已知某个函数 f 的输入和输出都是 0 或者 1。如果f(0)=f(1)则称函数为 constant。如果f(0)!=f(1)则称函数为 balanced。现在有一个函数f要么是 constant 要么是 balanced，判断f是 balanced 还是 constant。

• 传统算法：调用两次f，判断是否相等
• 量子算法：只需要调用一次f

首先，如果函数f是 constant，它就不是可逆的，我们知道输出并不能反推出输入，所以要先把f转变为可逆函数

function ReversibleF(input, helper) {
  return [input, XOR(f(input), helper)];
}

使用 braket 来表示的话，ReversibleF 可以表示为：

使用矩阵表示的话（其中表示的分量）：

然后构造量子电路，图中就是可逆的，右边的三角形意为观测/坍缩：

其中表示经过某个门之后的整体状态。这个状态是所有量子位的张量积

所以我们可以计算出：

因为的输入是两个量子比特，我们可以直接把应用到上，从而计算出

根据不同的情况，有不同的值：

接下来我们需要对第一个量子位进行操作，从而得到。而是的反函数，所以我们可以轻易得出：

可以看出来，如果是 constant，那么第一个量子位测量出来一定是 0。如果是 balanced，那么第一个量子位测量出来一定是 1

• 量子计算为什么比传统计算快？
  • 可以看出，虽然只调用了一次f函数，但是这一次调用对 4 种可能的输入都进行了处理。我们只需要对输出进行精妙的转换，就能拿到我们想要的结果
• 解题思路
  • 首先把函数f转变为可逆函数。
  • 因为可逆函数有 4 种输入，所以我们使用了两个量子比特，通过叠加的方式（H 量子逻辑门）构建出了 4 种输入
  • 在得到输出之后，根据我们找到的规律，设计精妙的转换电路，把叠加的结果转换为确定的结果
• 推广：如果函数f不仅只有两种输入，而是n种，使用传统计算机需要算(n+1)/2次，量子计算机只需要算1次
• 量子计算机是并行计算/并行存储吗？
  • 是，但不完全是
  • 计算/存储的过程可以类比为并行
  • 观测的时候，会坍缩。所以量子位的数量决定了量子计算机的吞吐
  • 我们并不能拿到并行计算的所有结果，所以量子计算应该适用于大量输入、少量输出的场景，比如 reduce

量子计算机在线模拟器