量子计算与量子信息 - 计算

• 量子计算与量子信息

量子电路

• 量子计数

单量子比特操作

• 一个单量子比特是由两个复参数构成的向量 \(\mid ψ \rangle = a \mid 0 \rangle + b \mid 1 \rangle\), 满足 \(| a |^2 + | b |^2 = 1\). 量子比特上的操作必须保范数, 因此用 \(2 \times 2\) 酉矩阵描述. 泡利矩阵属于其中最重要的矩阵, 在这里再次列出它们不无益处:
  • \[X \equiv \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\]
  • \[Y \equiv \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}\]
  • \[Z \equiv \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\]
• 另外三个量子门在下文中很重要, 阿达玛门 (记为 \(H\)), 相位门 (记为 \(S\)) 和 \(π / 8\) 门 (记为 \(T\)):
  • \[H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\]
  • \[S = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix}\]
  • \[T = \begin{bmatrix} 1 & 0 \\ 0 & e^{iπ / 4} \end{bmatrix}\]
• 需要记住的几个有用的代数事实是 \(H = (X + Z) / √2\) 和 \(S = T^2\). 鉴于定义中出现的是 \(π / 4\), 读者可能会对 \(T\) 门被称为 \(π / 8\) 门感到疑惑. 该门在历史上常被称为 \(π / 8\) 门, 因为除了一个不重要的全局相位, \(T\) 等同于在其对角线上是 \(e^{± iπ / 8}\) 的门.
  • \[T = e^{iπ / 8} \begin{bmatrix} e^{-iπ / 8} & 0 \\ 0 & e^{iπ / 8} \end{bmatrix}\]
  • 尽管如此, 这个命名在某些方面还是不恰当的, 我们这里常将其称为 \(T\) 门.
• 回忆状态为 \(a \mid 0 \rangle + b \mid 1 \rangle\) 的单量子比特可视为单位球面上的一个点 \((θ, φ)\), 其中 \(a = \cos (θ / 2)\), \(b = e^{i φ} \sin (θ / 2)\), 鉴于全局相位不可观测, \(a\) 可取作实数, 这便是布洛赫球面表示, 向量 \((\cos φ \sin θ, \sin φ \sin θ, \cos θ)\) 称为布洛赫向量.
  • 为了更加直观, 我们将常使用这个表示.

• 泡利矩阵出现在指数中时产生了三类有用的酉矩阵, 即关于 \(\hat{x}\), \(\hat{y}\) 和 \(\hat{z}\) 的旋转算子, 由以下方程定义:
  • \[R_{x} (θ) \equiv e^{-i θ X / 2} = \cos \frac{θ}{2} I - i \sin \frac{θ}{2} X = \begin{bmatrix} \cos \frac{θ}{2} & -i \sin \frac{θ}{2} \\ -i \sin \frac{θ}{2} & \cos \frac{θ}{2} \end{bmatrix}\]
  • \[R_{y} (θ) \equiv e^{-i θ Y / 2} = \cos \frac{θ}{2} I - i \sin \frac{θ}{2} Y = \begin{bmatrix} \cos \frac{θ}{2} & - \sin \frac{θ}{2} \\ \sin \frac{θ}{2} & \cos \frac{θ}{2} \end{bmatrix}\]
  • \[R_{z} (θ) \equiv e^{-i θ Z / 2} = \cos \frac{θ}{2} I - i \sin \frac{θ}{2} Z = \begin{bmatrix} e^{-iθ / 2} & 0 \\ 0 & e^{iθ / 2} \end{bmatrix}\]
• 若 \(\hat{n} = (n_x, n_y, n_z)\) 是三维空间中一实单位向量, 那么我们通过定义一关于 \(\hat{n}\) 轴转角为 \(θ\) 的旋转来推广上述定义, 形式如下
  • \[R_{\hat{n}} (θ) \equiv e^{-i θ \hat{n} \cdot \overrightarrow{σ} / 2} = \cos (\frac{θ}{2}) I - i \sin (\frac{θ}{2}) (n_x X + n_y Y + n_z Z)\]
  • \(\overrightarrow{σ}\) 代表由泡利矩阵组成的三元向量 \((X, Y, Z)\).

单量子比特上的任意酉算子可以用:
旋转组合加量子比特上的全局相位以多种方式表示.

• 定理 (单量子比特的 Z-Y 分解) 假设 \(U\) 是单量子比特上的酉操作, 存在实数 \(α\), \(β\), \(γ\) 和 \(δ\) 使得
  • \[U = e^{iα} R_z (β) R_y (γ) R_z (δ)\]

下面这个奇妙的推论, 是构造受控多量子比特酉算子的关键.

• 推论 设 \(U\) 是作用在单量子比特上的一个酉门, 则单量子比特上存在酉算子 \(A\), \(B\), \(C\) 使得 \(ABC = I\) 且 \(U = e^{iα} AXBXC\), 其中 \(α\) 为某个全局相位因子.

明年 (2025), 该学习四元数, 李群, 李代数了~ 不过, 没有看见好的书籍.

• 回忆量子电路的基本特性:
  • 时间从左到右;
  • 线表示量子比特;
  • / 可以用来表示一束量子比特.
• 电路恒等
  • \[HXH = Z\]
  • \[HYH = -Y\]
  • \[HZH = X\]

受控操作

• 更一般地, 设 \(U\) 是任意单量子比特酉操作, 则受控 \(U\) 操作是两量子比特操作, 一个控制比特和一个目标比特, 若控制量子比特被置为一定值则 \(U\) 作用于目标比特上, 否则目标比特不变, 即 \(\mid c \rangle \mid t \rangle \rightarrow \mid c \rangle U^c \mid t \rangle\).

• Toffoli gate

• 熟知的 Toffoli 门是 \(C^2(U)\) 操作的一个重要特例, 即 \(C^2(X)\). 定义 \(V ≡ (1 - i)(I + iX) / 2\), 注意到 \(V^2 = X\).
  • 从经典的观点来看, 这是一个显著的结果; 仅用单比特和双比特经典可逆门对于实现 Toffoli 门, 或者更一般的通用计算, 都是不可行的.
  • 相反, 在量子情况下, 我们看到单量子比特和两量子比特可逆门足以实现 Toffoli 门, 最终将证明它们满足通用计算的要求.
• 任何酉算子都可以由阿达玛门, 相位门, 受控非门及 \(π/8\) 门以任意精度近似.

已知的受控门中, 如果控制比特设置为 1, 则目标量子比特改变.
当然, 1 没有什么特别之处, 考虑控制比特设置为 0 作为改变的条件是有用的.
例如, 假设我们希望实现一个两量子比特门, 其中第二 (目标)
量子比特翻转的条件是第一 (控制) 量子比特被设置为 0.

一般使用空心圆环表示对量子比特设置为 0,
而闭圆表示对量子比特设置为 1.

闭圆: 实心圆点

测量

延迟测量原理: 测量总是可以从量子电路的中间阶段移到电路末端;
如果测量结果在电路某个阶段使用, 那么经典条件运算可以用量子条件运算来代替.

延迟测量原理的结果是, 当被测量的量子比特是一个控制量子比特时, 测量与量子门交换.

隐含测量原理: 不失一般性,
可以假定在量子电路末端的任何未终止的量子线 (未被测量的量子比特) 都将被测量.

当考虑测量在量子电路中的作用时, 要记住测量作为量子世界和经典世界之间的界面,
通常被认为是不可逆操作, 它破坏了量子信息, 并用经典信息取代.
然而, 在某些精心设计的情况下, 这并不一定是真实的,
正如隐形传态和量子纠错所生动地说明的那样.
隐形传态和量子纠错的共同之处在于, 在任何情况下,
测量结果都没有揭示关于被测量子状态的任何信息.
事实上, 我们将看到这是测量的一个更一般的特征:
为了使测量是可逆的, 它必须不能揭露关于被测量的量子状态的任何信息!

通用量子门

• 设 \(U\) 作用于 \(d\) 维空间, 我们可以找到两级酉矩阵 \(U_1\), …, \(U_{d - 1}\) 使得矩阵 \(U_{d-1} U_{d-2} ... U_1 U\) 左上角项为 \(1\), 第一行和第一列的其余项均为零. 然后, 我们对矩阵 \(U_{d-1} U_{d-2} ... U_1 U\) 右下角的 \((d - 1) × (d - 1)\) 酉子矩阵重复这一过程, 最终可以将任意 \(d × d\) 酉矩阵写成
  • \[U = V_1 ... V_k\]
  • 其中矩阵 \(V_i\) 是两级酉矩阵, \(k ≤ (d - 1) + (d - 2) + ... + 1 = d (d - 1) / 2\).
• 假设 \(U\) 是 \(n\) 量子比特计算机上的两级酉矩阵, 特别地, 假设 \(U\) 在计算基矢态 \(\mid s \rangle\) 和 \(\mid t \rangle\) 所张成的空间上的作用是不平凡的, 其中 \(s = s_1 ... s_n\) 和 \(t = t_1 ... t_n\) 是 \(s\) 和 \(t\) 的二进制展开式. 令 \(\widetilde{U}\) 是 \(U\) 的非平凡 \(2 \times 2\) 酉子矩阵, \(\widetilde{U}\) 可视为单量子比特上的酉算子.
• 当前目标是构建一个由单量子比特门和受控非门组成的实现 \(U\) 的电路. 为此我们需要使用 Gray 码. 假设我们有不同的二进制数 \(s\) 和 \(t\), 一个连接 \(s\) 和 \(t\) 的 Gray 码是一组以 \(s\) 开始, 以 \(t\) 结尾的二进制数序列, 使得列表中的相邻数恰好有一位不同. 例如, \(s = 101001\), \(t = 110011\), 我们有 Gray 码
  • \[\begin{matrix} 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \end{matrix}\]
  • 设 \(g_1\) 到 \(g_m\) 是连接 \(s\) 和 \(t\) 的 Gray 码元素, 其中 \(g_1 = s\) 和 \(g_m = t\). 注意总是可以找到一个 Gray 码使得 \(m ≤ n + 1\), 因为 \(s\) 和 \(t\) 最多有 \(n\) 个位置不同.

• 实现量子电路 \(U\) 的基本思想是通过一系列门实现状态变化 \(\mid g_1 \rangle \to \mid g_2 \rangle \to ... \to \mid g_{m - 1} \rangle\), 然后执行受控 \(\widetilde{U}\) 运算, 其中目标量子比特位于 \(g_{m - 1}\) 和 \(g_m\) 不同的那一比特处, 然后还原第一阶段, 进行转化 \(\mid g_{m - 1} \rangle \to \mid g_{m - 2} \rangle \to ... \to \mid g_1 \rangle\), 以上每一步都可以使用本章前面的运算来很容易地实现, 最后结果即是 \(U\) 的一个实现.

• 我们看到实现两级酉操作 \(U\) 最多需要 \(2(n - 1)\) 次受控运算来交换 \(\mid g_1 \rangle\) 与 \(\mid g_{m - 1} \rangle\) 并还原, 每个受控运算都可以使用 \(O(n)\) 个单量子比特门和受控非门来实现; 受控 \(\widetilde{U}\) 运算也需要 \(O(n)\) 个门. 因此, 实现 \(U\) 操作需要 \(O(n^2)\) 个单量子比特门和受控非门.
  • 由前文可知, 在 \(2^n\) 维状态空间上任意作用在 \(n\) 量子比特上的酉矩阵可以写成 \(O(2^{2n}) = O(4^n)\) 个两级酉操作的乘积. 综上, 在 \(n\) 量子比特上的任意酉操作可以用包含 \(O(n^2 4^n)\) 个单量子比特门和受控非门的电路来实现.
  • 显然, 这种结构并没有提供非常有效的量子电路. 然而, 我们在后文会表明, 在需要指数数量的门才能实现酉操作的意义下, 该构造接近最优.

• 由于酉操作集合是连续的, 一个离散的门集合不能用来确切实现任意的酉操作. 然而离散集合可以用来逼近任意酉操作. 为了理解这是怎么工作的, 我们首先需要研究逼近酉操作是什么意思. 假设 \(U\) 和 \(V\) 是作用在相同状态空间上的两个酉操作, \(U\) 是我们希望实现的目标酉算子, \(V\) 是实际实现的酉算子. 我们定义当 \(V\) 代替 \(U\) 被实现时的误差
  • \[E(U, V) ≡ \max_{\mid ψ \rangle} \| (U - V) \mid ψ \rangle \|\]
  • 其中极大取遍状态空间上所有归一化的量子态 \(\mid ψ \rangle\).
  • 测量误差可以解释为: 如果 \(E(U, V)\) 很小, 则对任意的初始态 \(\mid ψ \rangle\), 在状态 \(V \mid ψ \rangle\) 上的任意测量将给出和在态 \(U \mid ψ \rangle\) 上近似的测量统计结果.
  • 具体地, 如果 \(M\) 是一个 POVM 测量中的 POVM 元, \(\mid ψ \rangle\) 是初始态, \(P_U\) 或 \(P_V\) 是 \(U\) 或 \(V\) 被作用后的结果概率, 则
  • \[\mid P_U - P_V \mid ≤ 2E (U, V)\]
  • 因此, 如果 \(E(U, V)\) 很小, 不管 \(U\) 还是 \(V\) 被作用, 测量结果出现的概率相似. 而且, 如果为了逼近某个门序列 \(U_1\), …, \(U_m\), 我们执行门序列 \(V_1\), …, \(V_m\), 则误差最多按线性增加,
  • \[E(U_m U_{m - 1} U_1, V_m V_{m - 1} ... V_1) ≤ \sum_{j = 1}^{m} E(U_j, V_j)\]
  • 逼近结果极其有用, 假设我们希望执行一个从 \(U_1\) 到 \(U_m\) 包含 \(m\) 个量子门的量子电路. 遗憾的是, 我们仅能通过门 \(V_j\) 逼近门 \(U_j\). 为了在逼近电路上不同测量结果的概率和正确概率相比偏差在 \(△ > 0\) 之内, 那么, 只需满足 \(E(U_j, V_j) ≤ △ / 2m\).
• 由于阿达玛门和 \(π / 8\) 门允许我们逼近任意的单量子比特酉算子, 进而我们可以逼近任意的 \(m\) 个门的量子电路. 给一个含有 \(m\) 个门的量子电路, 或者受控非门, 或者单量子比特酉门, 我们可以用阿达玛门, 受控非门和 \(π / 8\) 门逼近它 (后面我们将要发现相位门可以做容错的逼近, 但是对于当前通用性的讨论, 它们不是严格必需的).
  • 如果对于整个电路我们想要 \(ϵ\) 的逼近, 这可以通过上面的程序对每个单量子比特酉操作以 \(ϵ / m\) 逼近, 再用链不等式对整个电路以 \(ϵ\) 的逼近达到.

我们已经看到任意 n 量子比特上的酉变换可以从一个小的基本门集合构造.
这总能有效进行吗? 也就是, 给一个 n 量子比特的酉变换,
是否总存在一个关于 n 多项式尺寸的电路逼近 U?
这个问题的答案是否定的: 事实上, 大部分的酉变换只能非常低效地实现.
看到这点的一种方法是考虑下面的问题:
需要花费多少门来生成一个 n 量子比特的任意态?
一个简单的计算表明一般需要指数个; 这等于说存在酉操作需要指数多次操作来实现.

量子电路模型尽管简单和有吸引力, 记住可能的批评, 修改和扩展是有用的.
例如, 量子电路模型的状态空间和初始条件的基本假设一点也不清楚.
一切都是用有限维状态空间来表达的.
假设计算机的初始状态是计算基矢态也是不必要的,
或许用无限维的状态空间可以获取其他东西?
我们知道, 自然界中的许多系统"更偏好"处于高度纠缠态中,
是否可能利用这种偏好获得额外的计算能力?
或许有一些态比限制在计算基矢态上更容易做计算. 同样的,
在多量子比特基中有效地执行纠缠测量的能力可能与仅执行纠缠酉操作一样有用.
实际上, 利用这些测量来执行量子电路模型中难以解决的任务是可能的.

量子系统的模拟

• 量子系统模拟的关键挑战是必须求解指数个微分方程. 按照薛定谔方程, 对于一个量子比特的演化, 需要求解两个微分方程组成的系统; 对于两量子比特, 需要求解四个方程; 对于 \(n\) 量子比特系统, 需要求解 \(2^n\) 个方程.
  • 有时候, 可以通过逼近来简化有效方程的个数, 这样使得量子系统的经典模拟成为可能. 然而有许多有趣的量子系统目前不知道这样的逼近.

量子计算机可以有效地模拟没有有效经典模拟的量子系统.
从直觉上讲, 这是可能的,
原因与任何量子电路都可以用一组通用的量子门构造的原因大致相同.
此外, 正如存在无法有效近似的酉操作一样,
原则上可以想象具有哈密顿量的量子系统无法在量子计算机上有效模拟.
当然, 我们相信这样的系统实际上在自然界中是不能实现的,
否则我们就可以利用它们来完成量子电路模型之外的信息处理.

• 定理 (Trotter 公式) 令 \(A\), \(B\) 为厄米算子. 则对于任意的实数 \(t\),
  • \[\lim_{n \to ∞} (e^{iAt / n} e^{iBt / n})^n = e^{i(A + B)t}\]
  • 注意即使 \(A\) 和 \(B\) 不对易, 上式也是正确的. 更有趣的是, 也许, 它可以推广到对于某些半群的生成元 \(A\), \(B\) 成立, 它们对应于一般量子运算; 目前, 我们只考虑 \(A\) 和 \(B\) 是厄米矩阵的情况.
• 算法 (量子模拟)
• 输入: (1) \(H = \sum_{k} H_k\) 是一个作用 \(N\) 维系统上的哈密顿量算子, 其中 \(H_k\) 作用在一个不依赖 \(N\) 的子系统上, (2) 在 \(t = 0\) 时, 系统的初始状态为 \(\mid ψ(0) \rangle\), (3) 一个正的非零的精确度 \(δ\), (4) 状态演化需要的时间 \(t_f\).
• 输出: 状态 \(\mid \widetilde{ψ} (t_f) \rangle\) 使得 \(\mid \langle \widetilde{ψ} (t_f) \mid e^{-iH t_f} \mid ψ_0 \rangle \mid^2 ≥ 1 - δ\).
• 运行时间: \(O(\mbox{poly} (1 / δ))\) 次运算.
• 程序: 选择一个表示使得 \(n = \mbox{poly} (\log N)\) 量子比特态 \(\mid \widetilde{ψ} \rangle\) 逼近系统, 且 \(e^{-i H_k △t}\) 有有效的量子电路逼近. 选择一种逼近方法且 \(△t\) 使得期望的错误率是可以接受的 (且 \(j △t = t_f\) 是一个整数), 对于迭代步骤构造对应的量子电路 \(U_{△t}\) 且做:
  • (1) \(\mid \widetilde{ψ}_0 \rangle \gets mid ψ_0 \rangle\); \(j = 0\) 初始化态
  • (2) \(\to \mid \widetilde{ψ}_{j + 1} \rangle = U_{△t} \mid \widetilde{ψ}_j \rangle\) 迭代更新
  • (3) \(\to j = j + 1\); \(\mbox{goto } 2 \mbox{ until } j △t ≥ t_f\); 循环
  • (4) \(\to \mid \widetilde{ψ} (t_f) \rangle = \mid \widetilde{ψ}_j \rangle\) 最后的结果

量子模拟算法与经典方法非常相似, 但在根本上也有所不同.
量子算法的每一次迭代都必须完全用新的状态替换旧的状态;
如果不显著地改变算法, 就无法从中间步骤获得 (非平凡的) 信息,
因为状态是量子的.
此外, 必须巧妙地选择最终测量以提供所需的结果, 因为它会扰乱量子态.
当然, 量子模拟可以重复以获得统计数据, 但最好只重复算法最多多项式次.
可能是, 即使模拟可以有效地执行, 也没有办法有效地执行所需的测量.
还有一些哈密顿函数无法有效地模拟.
我们先前看到存在着量子计算机无法有效逼近的幺正变换.
因此, 并不是所有的哈密顿演化都可以在量子计算机上有效地模拟,
因为如果这是可能的, 那么所有的酉变换都可以有效地近似!

• 本章小结
  • 通用性: \(n\) 量子比特上的任意酉操作可以确切地由单量子比特酉操作和受控非运算来实现.
  • 离散集的通用性: 阿达玛门, 受控非门, 相位门和 \(π / 8\) 门在如下意义下是量子计算的通用门, 即任意 \(n\) 量子比特的酉操作可以由这些门组成的电路以任意精度 \(ϵ\) 逼近. 用 Toffoli 门替代 \(π / 8\) 门也可以得到一个通用门族.
  • 并不是所有的酉操作都可以被有效实现: 对任意的有限门集合, 存在 \(n\) 量子比特上的酉操作需要用 \(Ω(2^n \log(1 / ϵ) / \log(n))\) 个门以 \(ϵ\) 距离逼近.
  • 模拟: 令哈密顿量 \(H = \sum_{k} H_k\), 其中项数和为多项式个, \(H_k\) 的有效量子电路可以被构造, 则给了初始态 \(\mid ψ_0 \rangle\), 存在量子计算机可以有效模拟 \(e^{-iHt}\) 的演化, 逼近 \(\mid ψ(t) \rangle = e^{-iHt} \mid ψ_0 \rangle\).

量子傅里叶变换及其应用

相位估计

应用: 求阶与因子分解问题

量子傅里叶变换的一般应用

量子搜索算法

作为量子模拟的量子搜索

量子计数

NP 完全问题解的加速

无结构数据库的量子搜索

搜索算法的最优性

黑盒算法的极限

量子纠错

• 假设我们将单量子比特 \(a \mid 0 \rangle + b \mid 1 \rangle\) 编码成 \(a \mid 000 \rangle + b \mid 111 \rangle\), 通常我们将这种编码方式表示为
  • \[\mid 0 \rangle \to \mid 0_L \rangle ≡ \mid 000 \rangle\]
  • \[\mid 1 \rangle \to \mid 1_L \rangle ≡ \mid 111 \rangle\]
  • 这里, 编码方案可以理解为将待编码量子比特中基矢态的叠加态, 替换成编码态的对应叠加态. 符号 \(\mid 0_L \rangle\) 和 \(\mid 1_L \rangle\) 分别表示这是逻辑比特 \(\mid 0 \rangle\) 和 \(\mid 1 \rangle\), 而不是物理比特 \(0\) 和 \(1\).
• 错误探测或者征状诊断: 我们通过一个测量来搞清楚, 如果有错误, 到底是哪个错误发生了. 测量的结果称为错误征状. 对于比特翻转信道, 有四种不同的错误征状, 对应四种不同的投影算子:
  • \(P_0 ≡ \mid 000 \rangle \langle 000 \mid + \mid 111 \rangle \langle 111 \mid\) 没有错误
  • \(P_1 ≡ \mid 100 \rangle \langle 100 \mid + \mid 011 \rangle \langle 011 \mid\) 量子比特 \(1\) 上发生比特翻转
  • \(P_2 ≡ \mid 010 \rangle \langle 010 \mid + \mid 101 \rangle \rangle 101 \mid\) 量子比特 \(2\) 上发生比特翻转
  • \(P_3 ≡ \mid 001 \rangle \langle 001 \mid + \mid 110 \rangle \langle 110 \mid\) 量子比特 \(3\) 上发生比特翻转
  • 例如, 假设比特翻转发生在第一个量子比特上, 则被影响的量子态成为 \(a \mid 100 \rangle + b \mid 011 \rangle\). 注意在这种情况下 \(\langle ψ \mid P_1 \mid ψ \rangle = 1\), 所以测量结果将确定为 \(1\).
  • 而且, 征状测量将不对量子态产生任何影响: 测量前后都是 \(a \mid 100 \rangle + b \mid 011 \rangle\).
  • 注意, 这里征状只包含何种错误发生的信息, 并不揭示 \(a\) 和 \(b\) 的任何信息, 因此, 并不包含被保护量子态的任何信息. 这是征状测量的一般性特征, 因为为了获取被保护量子态的具体信息, 一定要扰动它, 这不是我们希望看到的.
• 恢复: 我们使用错误诊断的结果来指示将使用何种操作来恢复原有信息. 例如, 如果错误征状是 \(1\), 表示第一个量子比特发生了翻转错误, 那我们再次将其翻转, 这样将完美恢复原有信息. 四个可能的错误征状和每种情形的恢复程序是:
  • \(0\) (没有错误), 什么也不做;
  • \(1\) (第一个量子比特翻转), 再次将第一个量子比特翻转;
  • \(2\) (第二个量子比特翻转), 再次将第二个量子比特翻转;
  • \(3\) (第三个量子比特翻转), 再次将第三个量子比特翻转.
  • 对错误征状的每一个值, 如果对应的错误确实发生了, 则很容易看到原有信息都被完美恢复.

Shor 编码

量子纠错理论

构造量子编码

稳定子编码

容错量子计算

附录

群论

• 隐藏子群问题

• 元素 \(g \in G\) 的阶是使得 \(g^r\) (\(g\) 自乘 \(r\) 次) 等于单位元 \(e\) 的最小正整数.
• 若 \(H\) 是 \(G\) 的子集, 且与 \(G\) 在相同乘法运算下构成群, 则称 \(H\) 是群 \(G\) 的子群.

• 拉格朗日定理 如果 \(H\) 是一个有限群 \(G\) 的子群, 那么 \(|H|\) 可以整除 \(|G|\).

• 如果 \(g_1\) 和 \(g_2\) 是 \(G\) 中的元素, 那么 \(g_2\) 关于 \(g_1\) 的共轭为元素 \(g_1^{-1} g_2 g_1\).
  • 若 \(H\) 是 \(G\) 的子群, 且 \(g^{-1} H g = H\) 对所有 \(g \in G\) 成立, 则称其为正规子群.
  • 群 \(G\) 中的元素 \(x\) 的共轭类 \(G_x\), 定义为 \(G_x ≡ \{ g^{-1} x g \mbox{ } | \mbox{ } g \in G \}\).

• 生成元

• 循环群 \(G\) 包含一个元素 \(a\), 使得任意元素 \(g \in G\) 能够表示为 \(a^n\), 其中 \(n\) 为某个整数.
  • \(a\) 称为 \(G\) 的生成元, 我们记 \(G = \langle a \rangle\).
  • 由 \(g \in G\) 生成的循环子群 \(H\) 是指由 \(\{ e, g, g^2, ..., g^{r-1} \}\) 构成的群, 其中 \(r\) 为 \(g\) 的阶. 即 \(H = \langle H \rangle\).
• 若 \(H\) 是 \(G\) 的一个子群, 由 \(g\) 所确定的 \(H\) 在 \(G\) 中的左陪集定义为集合 \(gH ≡ \{ gh \mbox{ } | \mbox{ } h \in H \}\).
  • 右陪集定义类似. 陪集是左陪集还是右陪集可以从上下文看出.
  • 对像 \(\mathbb{Z}_n\) 的群运算为加法的群, 习惯上把子群 \(H\) 对 \(g \in \mathbb{Z}_n\) 的陪集写成 \(g + H\) 的形式.
  • 陪集 \(gH\) 的一个特定的元素被称为该陪集的代表元.

• 令 \(M_n\) 表示 \(n \times n\) 复矩阵的集合. 那么一个矩阵群是 \(M_n\) 的集合, 它在矩阵乘法下满足群的性质. 我们记这类群的单位元为 \(I\). 一个群 \(G\) 的表示 \(ρ\) 定义为一个函数, 该函数将 \(G\) 映射到一个矩阵群, 且保持群的乘法运算.
  • 特别地, \(g \in G\) 被映射到 \(ρ(g) \in M_n\), 使得 \(g_1 g_2 = g_3\) 蕴含 \(ρ(g_1) ρ(g_2) = ρ(g_3)\).
  • 如果映射是多对一的, 则称之为同态; 如果是一对一的, 则称之为同构.

• 一个映射到 \(M_n\) 的表示 \(ρ\) 具有维数 \(d_n = n\). 我们定义的表示也称为矩阵表示, 还有更一般的表示, 但是对我们来说矩阵表示足够用了.

• 矩阵群
  • 表示
  • 特征
• 有限群上的傅立叶变换

最后 4 页的信息量蛮大~

数论

• 假设 \(n\) 是一个整数. 如果存在一个整数 \(k\), 使得 \(n = dk\), 我们就称整数 \(d\) 整除 \(n\) (写作 \(d \mid n\)). 当 \(d\) 不整除 (不是 \(n\) 的因子) \(n\) 时, 我们记作 \(d \nmid n\).
• 通常同余采用符号 “\(≡\)”, 即 \(2 ≡ 5 ≡ 8 ≡ 11\) \((mod \mbox{ } 3)\), 但本书中全部采用的是 “\(=\)” 符号.

符号约定

• 定理 (算术基本定理) 令 \(a\) 为任意大于 \(1\) 的整数. 那么 \(a\) 有素因子分解形式
  • \[a = p_{1}^{a_1} p_{2}^{a_2} ... p_{n}^{a_n}\]
  • 其中 \(p_1\), …, \(p_n\) 是不同的素数, \(a_1\), …, \(a_n\) 是正整数. 此外, 在不考虑因子的排列情况下这个分解是唯一的.
• 定理 (最大公约数的表示定理) 两个整数 \(a\) 和 \(b\) 的最大公约数是可以写成 \(ax + by\) 形式的最小正整数, 其中 \(x\) 和 \(y\) 是整数.

注: \(x\) 和 \(y\) 可取负值.

• 推论 假设 \(c\) 能同时整除 \(a\) 和 \(b\), 那么 \(c\) 也能整除 \(gcd(a, b)\).

• 一个数 \(a\) 什么时候在模运算中有一个乘法逆? 也就是说, 给定 \(a\) 和 \(n\), 什么时候存在 \(b\) 使得 \(a b = 1\) \((mod \mbox{ } n)\)?
  • 在模算术中寻找乘法逆, 与互质数的概念有关: 如果整数 \(a\) 和 \(b\) 的最大公约数是 \(1\), 则称为互质数.
  • 下面的推论利用互素性来刻画模算术中乘法逆的存在性.

• 推论 令 \(n\) 为大于 \(1\) 的整数. 当且仅当 \(gcd(a, n) = 1\) 时, \(a\) 和 \(n\) 互素.

• 定理 设 \(a\) 和 \(b\) 为整数, \(r\) 为 \(a\) 除以 \(b\) 的余数, 假设 \(r ≠ 0\), 则有
  • \(gcd(a, b) = gcd(b, r)\).
• 假设 \(a\) 是 \(n\) 的互素数, 我们希望找到 \(a^{-1}\) 模 \(n\). 为此, 由欧几里得算法及 \(a\) 和 \(n\) 的互素性可得到满足下式的整数 \(x\) 和 \(y\):
  • \[ax + ny = 1\]
  • 注意到 \(ax = (1 - ny) = 1\) \((mod \mbox{ } n)\),
  • 即, \(x\) 是模 \(n\) 后 \(a\) 的乘法逆.
  • 此外, 该算法的计算效率很高, 只需要 \(O(L^3)\) 步, 其中 \(L\) 是 \(n\) 的比特长度.

• 中国剩余定理

• 引理 假设 \(p\) 是素数, \(k\) 是一个 \(1\) 到 \(p - 1\) 之间的整数. 则 \(p\) 能整除 \(\tbinom{p}{k}\).

• 定理 (费马小定理) 假设 \(p\) 是一个素数, \(a\) 是任意整数. 如果 \(a\) 不能被 \(p\) 整除, 那么 \(a^{p - 1} = 1\) \((mod \mbox{ } p)\).

• 欧拉定理 (欧拉-费马小定理)

因数分解 -> 求阶问题

• 假设 \(N\) 是一个正整数, 并且 \(x\) 与 \(N\) 互质, 其中 \(1 ≤ x < N\), 那么 \(x\) 模 \(N\) 的阶被定义为满足 \(x^r = 1\) \((mod \mbox{ } N)\) 的最小正整数 \(r\).
  • 求阶问题的目标是在给定 \(x\) 与 \(N\) 的条件下, 确定 \(r\).

• 从因数分解到求阶问题的归约过程主要分为两个基础步骤.
  • 第一步是证明如果可以找到方程 \(x^2 = 1\) \((mod \mbox{ } N)\) 的一个非平凡解 \(x ≠ ±1\) \((mod \mbox{ } N)\), 那么我们就能够计算出 \(N\) 的一个因数.
  • 第二步则是证明随机挑选一个与 \(N\) 互质的数 \(y\), 它就有很大可能具有偶数阶 \(r\), 并且满足 \(y^{r / 2} ≠ ±1\) \((mod \mbox{ } N)\), 那么 \(x ≡ y^{r / 2}\) \((mod \mbox{ } N)\) 就是 \(x^2 = 1\) \((mod \mbox{ } N)\) 的一个解.

• 定理 假设 \(N\) 是一个 \(L\) 比特长的合数, \(x\) 是方程 \(x^2 = 1\) \((mod \mbox{ } N)\) 的一个非平凡解, 其中 \(1 ≤ x ≤ N\), 即 \(x ≠ 1\) \((mod \mbox{ } N)\) 且 \(x ≠ -1\) \((mod \mbox{ } N)\).
  • 那么 \(gcd(x - 1, N)\) 与 \(gcd(x + 1, N)\) 中至少有一个是 \(N\) 的非平凡因子, 且可以在 \(O(L^3)\) 次操作内被计算出来.

• 连分数

• 定理 假设 \(x\) 是一个大于等于一的有理数. 那么 \(x\) 存在一个连分式表示 \(x = [ a_0, ..., a_N ]\), 这一表示可以通过连分式算法构造.

• 上述定理是对 \(x ≥ 1\) 而言的; 但是在实际应用中放松 \(a_0\) 必须为正的约束并允许其为任意整数是非常方便的, 这就使 \(x ≥ 1\) 的约束变得很多余.
  • 特别地, 如同在量子算法的应用中出现的情况那样, 如果令 \(x\) 取值为从 0 到 1, 那么在连分式展开中就有 \(a_0 = 0\).
• 连分式算法提供了一种明确的方法来得到一个给定有理数的连分式展开, 其中唯一可能不明确的地方出现在最后一步; 因为我们可以使用两种方法来划分一个整数, 或者令 \(a_n = a_n\), 或者令 \(a_n = (a_n - 1) + 1/1\), 这就给出了两种可行的连分式展开.
  • 这种不明确性实际上是很有用的, 因为它允许我们可以根据需要不失一般性地假设: 一个给定有理数的连分式展开有奇数或偶数个渐进分数.
• 定理 令 \(x\) 是一个有理数, 并且假设 \(p/q\) 也是一个有理数且满足
  • \[| \frac{p}{q} - x | ≤ \frac{1}{2 q^2}\]
  • 那么 \(p / q\) 是 \(x\) 连分式展开中的一个渐进分数.

Solovay-Kitaev 定理

• Solovay-Kitaev 定理