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

• 量子计算与量子信息

量子电路

量子计数

单量子比特操作

• 一个单量子比特是由两个复参数构成的向量 \(\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) / \sqrt{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\) 最后的结果

输出: 把 1 移到左侧, 两边乘以 -1, 则意思更清晰.

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

本章小结

• 通用性: \(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\).

量子纠错

• 假设我们将单量子比特 \(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 编码, 本质上是三量子比特相位翻转编码和比特翻转编码的一种结合. 我们首先将量子比特做相位翻转编码:
  • \(\mid 0 \rangle \to \mid +++ \rangle\), \(\mid 1 \rangle \to \mid --- \rangle\).
  • 接着, 我们再将每一个量子比特做比特翻转编码: \(\mid + \rangle\) 编码成 \((\mid 000 \rangle + \mid 111 \rangle) / \sqrt{2}\), \(\mid - \rangle\) 编码成 \((\mid 000 \rangle - \mid 111 \rangle) / \sqrt{2}\).
  • 结果, 我们得到一个如下的九量子比特编码:
  • \[\mid 0 \rangle \to \mid 0_L \rangle ≡ \frac{ (\mid 000 \rangle + \mid 111 \rangle) (\mid 000 \rangle + \mid 111 \rangle) (\mid 000 \rangle + \mid 111 \rangle) }{2 \sqrt{2}}\]
  • \[\mid 1 \rangle \to \mid 1_L \rangle ≡ \frac{ (\mid 000 \rangle - \mid 111 \rangle) (\mid 000 \rangle - \mid 111 \rangle) (\mid 000 \rangle - \mid 111 \rangle) }{2 \sqrt{2}}\]

发生在一个量子比特上的错误明显是连续的, 但我们只要能纠正其中的一个离散真子集,
那么一般性错误就可以被同样的步骤纠正!
量子错误的这种离散化是量子纠错能被成功实现的核心原因.
值得注意的是, 经典模拟系统的纠错没有类似的特征, 这是一个本质的区别.

通过纠正一系列离散的量子错误, 比如, 比特翻转, 相位翻转和比特相位联合翻转,
量子纠错码可以自动纠正一大类量子错误, 甚至是连续的错误.

如果噪声影响的不止是第一个量子比特怎么办?
我们可以用两个不同的想法考虑这个问题.
首先, 在许多情形中, 假设噪声独立地影响每个量子比特是一个很好的近似.
只要噪声在每个量子比特上作用的效果很小,
我们可以将噪声的整体效果分解为几种不同情形的总和:
没有量子比特发生错误, 一个量子比特发生错误, 两个量子比特发生错误, 等等.
其中, 相对其他项, 没有错误发生和只有一个量子比特发生错误占据统治地位.
因此, 只要能合理地纠正 0 阶项和 1 阶项, 即使不处理高阶项,
整体上也会对噪声的影响实现有效抑制.
当然, 有时候假设噪声独立地作用于每个量子比特上并不合理,
在这种情况下我们将使用另外一种思路:
使用能纠正不止一个量子比特错误的量子纠错码.
这些纠错码也可以用类似 Shor 编码的思路构造出来.

• 量子纠错码理论的基本想法就是自然推广 Shor 编码的思路. 通过一个酉变换, 量子态被编码成量子纠错码, 严格来说这是某个更大的希尔伯特空间的子空间 \(C\). 引入一个将量子态投影到编码空间 \(C\) 的投影算子是很有帮助的, 我们将其记为 \(P\). 对于三量子比特的比特翻转编码, \(P = \mid 000 \rangle \langle 000 \mid + \mid 111 \rangle \langle 111 \mid\).
  • 在噪声作用到编码后的量子态上之后, 我们通过征状测量去诊断所发生的是何种错误, 这称为错误诊断. 一旦错误被确定, 我们将进行恢复操作, 将量子系统恢复到原本的编码状态. 不同的错误诊断对应全空间不同的非形变, 正交子空间.
  • 这些子空间必须正交, 否则它们不能被征状测量精确地分辨开来. 并且, 这些子空间必须是原来编码空间的非形变版本, 这意味着在不同子空间中, 错误必须将正交的量子编码映射到正交的量子态上, 只有这样才能最终完全恢复被保护的量子态.

说明: 本文不区分 \(ε\) 和 \(\mathcal{E}\)

• 噪声的行为被一个量子操作 \(ε\) 描述, 以及整个纠错的过程等效于一个保迹的量子操作 \(\mathcal{R}\), 我们称之为量子纠错操作. 因此, 量子纠错操作将之前描述的错误探测和信息恢复两个阶段合二为一. 对于一个成功的纠错过程, 我们要求, 对支集位于编码空间 \(C\) 中的任意量子态 \(ρ\),
  • \[(\mathcal{R} ∘ ε) (ρ) \propto ρ\]
  • 也许有人会问, 为什么我们写作 \(\propto\), 而不是 \(=\). 如果 \(ε\) 是一个保迹量子操作, 那么对两边取迹我们就会发现, \(\propto\) 实际上就是 \(=\). 但是, 我们有时候也对非保迹的量子纠错操作 \(ε\) 感兴趣, 比如量子测量, 在这种情况下 \(\propto\) 是合适的.
  • 当然, 量子纠错操作 \(\mathcal{R}\) 必须以概率 \(1\) 完成, 这就是为什么我们要求 \(\mathcal{R}\) 是保迹的.

• 量子纠错条件就是这样一组方程, 它让我们能确认一个量子纠错码是否能够对抗一类特定的量子噪声 \(ε\). 我们将使用这个条件构造众多的量子纠错码, 以及研究量子纠错码的一些一般性特性.

• 定理 (量子纠错条件) \(C\) 是一组量子编码, \(P\) 是映射到 \(C\) 上的投影算子. 假设 \(ε\) 是一个算子元素 \(\{ E_i \}\) 描述的量子操作, 那么基于量子编码 \(C\), 存在一个能对抗 \(ε\) 描述的噪声的纠错操作 \(\mathcal{R}\) 的充要条件是
  • \(P E_{i}^{\dagger} E_j P = α_{ij}\) 对某个复元素的厄米矩阵 \(α\) 成立.
  • 我们将算子元素 \(\{ E_i \}\) 称为噪声 \(ε\) 导致的错误. 如果这样的 \(\mathcal{R}\) 存在, 我们说 \(\{ E_i \}\) 构成一组可纠正的错误.
• 定理 假设 \(C\) 是一个量子编码, \(\mathcal{R}\) 是量子纠错条件定理中所构造的纠错操作, 它被用来恢复操作元素 \(\{ E_i \}\) 所描述的噪声作用过程 \(ε\) 的影响. 假设 \(\mathcal{F}\) 是另一个量子操作, 且它的操作算子 \(\{ F_i \}\) 是 \(\{ E_i \}\) 的线性组合, 即 \(F_j = \sum_{i} m_{ji} E_i\), 这里 \(m_{ji}\) 构成一个复数矩阵.
  • 那么, \(\mathcal{R}\) 也能纠正噪声作用过程 \(\mathcal{F}\) 对编码 \(C\) 的影响.
• 上述结果让我们可以引入一种更强大的语言来描述量子纠错. 与其讨论编码 \(C\) 和纠错程序 \(\mathcal{R}\) 所能纠正的噪声作用过程 \(ε\) 的种类, 我们现在改为讨论可以纠正的噪声算子 \(\{ E_i \}\) (或者简单就说噪声).
  • 这意味着, 对这些算子来说, 量子纠错条件成立, 即
  • \[P E_i E_j^{\dagger} P = α_{ij} P\]
• 将上述两个定理结合起来, 可知对于一个任意的噪声作用过程 \(ε\), 只要其操作元素由这些噪声算子 \(\{ E_i \}\) 的线性组合构成, 那么 \(ε\) 就能被 \(\mathcal{R}\) 纠正!

总结一下, 我们已经知道, 量子噪声是可以离散化的,
所以为了对抗单量子比特上具有连续可能的错误,
只需要纠正一个离散集合的错误, 即四个泡利矩阵,
而且高维量子系统也有类似结论.
与经典模拟系统相比, 这是一个根本性的差别, 因为在经典模拟系统中,
原则上有无限种可能的错误征状, 因此实现纠错极其困难.
经典信息处理的数字化纠错则相当成功, 因为它只涉及有限种可能的错误征状.
所以, 我们体会到了一件惊人的事实, 量子纠错似乎跟经典数字化系统的纠错类似,
而与经典模拟系统的状况迥异.

量子纠错似乎跟经典数字化系统的纠错类似, 而与经典模拟系统的状况迥异.

简并纠错码的存在, 对量子纠错来说既是一个好消息, 也是一个坏消息.
坏消息是经典情形下行之有效的一些证明上下界的技术在量子情形下不再适用,
我们将在量子汉明界中看到这种例子;
好消息是简并编码似乎是量子编码中一个最有趣的现象.
某种意义上说, 相对经典情形这种现象让我们有机会将更多的信息打包进量子编码,
因为不同的错误不一定将编码空间映射到正交空间,
因此一个可能的结果是相对非简并编码, 简并编码可以更有效地存储量子信息.

• 假设一个量子编码将 \(k\) 个量子比特编码成 \(n\) 个量子比特, 而且它能纠正 \(t\) 个或者更少量子比特任意组合上的错误. 假设发生了 \(j\) 个错误, 这里 \(j ≤ t\), 则发生错误的位置有 \(\tbinom{n}{j}\) 种不同的可能组合.
  • 对应任何一种此类组合, 每个量子比特上的错误有三个可能: 泡利矩阵 \(X\), \(Y\), \(Z\), 于是, 有 \(3^j\) 种不同的错误可能. 因此, 发生在 \(t\) 个或者更少量子比特上不同错误的可能总数为
  • \[\sum_{j = 0}^{t} \binom{n}{j} 3^j\]
  • (注意 \(j = 0\) 对应没有错误发生的情况, 即错误 \(I\)).
  • 为了将 \(k\) 个量子比特以非简并的方式编码, 这些错误中的每一个都需要对应一个正交的 \(2^k\) 维子空间, 而且这些子空间都能嵌入到 \(n\) 个量子比特对应的 \(2^n\) 维状态空间中. 于是,
  • \[\sum_{j = 0}^{t} \binom{n}{j} 3^j 2^k ≤ 2^n\]
  • 这就是量子汉明界.

当然, 并不是所有的量子纠错码都是非简并的,
因此量子汉明界类似一个经验法则, 而不是一个量子编码存在性的严格界限.
(实际上, 在写作本书时, 还没有任何量子编码能违背量子汉明界, 即使允许简并发生.)

构造量子编码

• 一个将 \(k\) 比特信息编码到 \(n\) 比特编码空间上的线性码 \(C\) 由一个 \(n \times k\) 的产生矩阵 \(G\) 确定, 这些矩阵的元素是 \(Z_2\) 的元素, 也就是 1 和 0. 矩阵 \(G\) 将信息映射到对应的编码上来, 因此, \(k\) 比特的信息 \(x\) 被编码后就成为 \(Gx\), 这里, 信息 \(x\) 可以被看成一个列向量.
  • 值得注意的是, 本节中矩阵乘法运算, 以及其他代数运算, 都是取模为 2 的结果. 作为一个简单例子, 将一个比特映到三个比特的重复性编码, 可以由产生矩阵
  • \[G = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}\]
  • 确定, 这里 \(G\) 将可能的信息, 0 或者 1, 映射到它们对应的编码形式, \(G[0] = (0, 0, 0)\) 及 \(G[1] = (1, 1, 1)\). (注意 \((a, b, ..., z)\) 是列向量的标准记号). 如果一个编码用 \(n\) 个比特来编码 \(k\) 个比特的信息, 我们称之为一个 \([n, k]\) 编码; 上面的例子即为一个 \([3, 1]\) 编码.
  • 一个稍微复杂一些的例子是: 将一个两比特信息中的每一个比特用重复性编码来处理, 这样将得到一个 \([6, 2]\) 编码. 这里对应的产生矩阵是
  • \[G = \begin{bmatrix} 1 & 0 \\ 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \\ 0 & 1 \end{bmatrix}\]
  • 同时, 如同预期的一样, 我们可以看到,
  • \(G(0, 0) = (0, 0, 0, 0, 0, 0)\);
  • \(G(0, 1) = (0, 0, 0, 1, 1, 1)\);
  • \(G(1, 0) = (1, 1, 1, 0, 0, 0)\);
  • \(G(1, 1) = (1, 1, 1, 1, 1, 1)\).
  • 不难看出, 所有可能的码字都是 \(G\) 的列所张成的空间中的向量. 因此, 为了让所有的信息编码方式唯一, 我们需要 \(G\) 的列向量线性无关, 除此之外对 \(G\) 没有任何约束.

关于线性码的产生矩阵定义方式,
一个吸引人的特征是我们希望编码的信息和如何编码之间显而易见的联系.
然而, 如何实施纠错其实不是十分容易能看出来.

• 理解线性码的纠错, 一个最容易的方式是为线性码引入一个叫作奇偶校验的等价替代形式. 在这种定义方式中, 一个 \([n, k]\) 编码被定义为 \(Z_2\) 上的所有 \(n\) 元向量 \(x\), 并且同时满足
  • \[Hx = 0\]
  • 这里, \(H\) 是一个 \((n - k) \times k\) 矩阵, 被称为奇偶校验矩阵, 它所有的元素都是 0 或者 1. 一个相等但更简洁的方式, 是将编码空间定义为 \(H\) 的核空间.
  • 编码 \(k\) 个比特需要 \(2^k\) 个码字, 因此 \(H\) 的核空间必须至少是 \(k\) 维, 因此我们要求 \(H\) 的行向量线性无关.
• 为了从奇偶校验矩阵到产生矩阵, 选取张成 \(H\) 核空间的 \(k\) 个线性无关列向量 \(y_1\), …, \(y_k\), 然后将 \(G\) 的列向量设成 \(y_1\), …, \(y_k\). 为了从产生矩阵到奇偶校验矩阵, 选取与 \(G\) 的列向量都正交的 \(n - k\) 个线性无关向量 \(y_1\), …, \(y_{n - k}\), 然后将 \(H\) 的行设置为 \(y_1^T\), …, \(y_{n - k}^T\).
  • (这里, 正交是指内积对 2 取模结果为 0).

内积对 2 取模结果为 0

• 奇偶校验矩阵使得错误探测和信息恢复的过程非常清晰. 假设我们将信息 \(x\) 编码成 \(y = Gx\), 但是因为噪声, 码字 \(y\) 产生了错误 \(e\), 使得被影响后的码字成为 \(y' = y + e\). (注意, 这里的加法是对 2 取模.) 因为对所有码字有 \(Hy = 0\), 我们得到 \(Hy' = He\), 我们将 \(Hy'\) 称为错误征状, 它扮演了类似量子纠错中错误征状的角色.
  • 并且, 由于 \(Hy' = He\), 错误征状包含错误发生状况的信息, 因此有希望据此恢复出原本的信息 \(y\).
  • 为了证实这一点, 我们假设没有错误或只有一个错误发生. 如果没有错误, 则对应的错误征状是 \(Hy' = 0\); 如果在第 \(j\) 个比特发生了一个错误, 则错误征状是 \(H e_j\), 这里 \(e_j\) 是第 \(j\) 个元素为 1 的单位向量.
  • 因此, 如果假设错误发生在至多一个比特上, 则可以通过计算错误征状 \(Hy'\), 再与不同可能的 \(H e_j\) 对比, 来确定需要修正的比特的位置并最终恢复原有信息.
• 纠错码的全局特点也可以使用汉明距离来理解. 我们将一个编码的距离定义为任意两个码字之间的最小距离, 即
  • \[d(C) ≡ \min_{x, y \in C, x ≠ y} d(x, y)\]
  • 注意, 我们有 \(d(x, y) = \mbox{wt} (x + y)\). 因为编码是线性的, 如果 \(x\) 和 \(y\) 是码字, 则 \(x + y\) 也是, 于是
  • \[d(C) = \min_{x \in C, x ≠ 0} \mbox{wt} (x)\]
  • 记 \(d ≡ d(C)\), 我们说 \(C\) 是一个 \([n, k, d]\) 编码. 距离这个概念的重要性在于, 一个距离为 \(2t + 1\) 的编码, 最多可以纠正 \(t\) 个比特上的错误. 如果错误少于 \(t\) 个, 则我们可以将噪声干扰后的编码信息 \(y'\) 解码为满足 \(d(y, y') ≤ t\) 的唯一码字 \(y\).

wt: 汉明重量

线性编码的 Gilbert-Varshamov 界限

• 作为对回顾经典纠错码的一个总结, 我们介绍对偶构造的想法, 这是一个重要的纠错码构造方法. 假设 \(C\) 是一个 \([n, k]\) 编码, 产生矩阵是 \(G\), 奇偶校验矩阵是 \(H\). 那么, 我们可以用产生矩阵 \(G^T\) 和奇偶校验矩阵 \(H^T\) 构造另一个编码 \(C^{⊥}\), 称为 \(C\) 的对偶.
  • 等价地, \(C\) 的对偶由那些与 \(C\) 的所有码字都正交的码字 \(y\) 构成. 一个编码如果满足 \(C \subseteq C^{⊥}\), 则称它是弱自对偶的; 如果满足 \(C = C^{⊥}\), 则称它是严格对偶的.
  • 一个非常值得注意的事实是, 经典线性码的对偶构造方法, 在量子纠错码中也会自然出现, 而且是一类称为 CSS 编码的重要纠错码的关键所在.

CSS 编码是更广泛的稳定子编码的一类重要子集.

• 假设 \(C_1\) 和 \(C_2\) 分别是 \([n, k_1]\) 和 \([n, k_2]\) 的经典线性码, 并且 \(C_2 \subset C_1\), \(C_1\) 和 \(C_2^{⊥}\) 都纠正 \(t\) 个错误. 我们现在来定义一个指标为 \([n, k_1 - k_2]\) 的量子编码 \(\mbox{CSS} (C_1, C_2)\), 称为 \(C_1\) 在 \(C_2\) 上的 CSS 编码, 它能纠正 \(t\) 个量子比特上的错误.
  • 假设 \(x \in C_1\) 是 \(C_1\) 编码中的任意码字, 那么定义量子态 \(\mid x + C_2 \rangle\) 如下:
  • \[\mid x + C_2 \rangle ≡ \frac{1}{\sqrt{\mid C_2 \mid}} \sum_{y \in C_2} \mid x + y \rangle\]
  • 这里 \(+\) 是模 2 的逐位加法. 假设 \(x'\) 是 \(C_1\) 的元素, 而且 \(x - x' \in C_2\), 则容易得知 \(\mid x + C_2 \rangle = \mid x' + C_2 \rangle\). 因此, \(\mid x + C_2 \rangle\) 只依赖于 \(x\) 所在的 \(C_1 / C_2\) 的陪集, 这解释了为何我们使用陪集符号 \(\mid x + C_2 \rangle\).
  • 并且, 如果 \(x\) 和 \(x'\) 属于不同的 \(C_2\) 陪集, 那么没有 \(y, y' \in C_2\) 使 \(x + y = x' + y'\) 成立, 因此, \(\mid x + C_2 \rangle\) 和 \(\mid x' + C_2 \rangle\) 是正交态.
  • 量子编码 \(\mbox{CSS} (C_1, C_2)\) 就定义为对所有状态 \(\mid x + C_2 \rangle\) 所张成的向量空间, 这里 \(x\) 取遍 \(C_1\) 所有值, \(C_2\) 在 \(C_1\) 中所有陪集的数量为 \(\mid C_1 \mid / \mid C_2 \mid\), 因此 \(\mbox{CSS} (C_1, C_2)\) 的维数为 \(\mid C_1 \mid / \mid C_2 \mid = 2^{k_1 - k_2}\), 所以 \(\mbox{CSS} (C_1, C_2)\) 是一个 \([n, k_1 - k_2]\) 量子编码.
• 总结一下, 假设 \(C_1\) 和 \(C_2\) 分别是 \([n, k_1]\) 和 \([n, k_2]\) 的经典线性编码, \(C_2 \subset C_1\), 而且 \(C_1\) 和 \(C_2^{⊥}\) 都能纠正至多 \(t\) 个错误, 那么 \(\mbox{CSS} (C_1, C_2)\) 是一个能纠正最多 \(t\) 个量子比特上任意错误的 \([n, k_1 - k_2]\) 量子纠错码.
  • 并且, 对应的错误探测和纠正步骤, 只需要应用数量是编码大小的常数倍数的阿达玛门和受控非门. 其实编码和解码也可以用编码大小常数倍数的操作完成, 但我们暂时不再详述.

Steane code

稳定子编码

• 稳定子形式的核心想法可以用一个例子来描述. 考虑两个量子比特的 EPR 对
  • \[\mid φ \rangle = \frac{\mid 00 \rangle + \mid 11 \rangle}{\sqrt{2}}\]
  • 不难验证, 这个量子态满足 \(X_1 X_2 \mid φ \rangle = \mid φ \rangle\) 和 \(Z_1 Z_2 \mid φ \rangle = \mid φ \rangle\), 因此我们说, 状态 \(\mid φ \rangle\) 被 \(X_1 X_2\) 和 \(Z_1 Z_2\) 稳定.
  • 实际上一个不太明显的事实是, 状态 \(\mid φ \rangle\) 是被这两个算子稳定的唯一量子态 (不考虑全局变量带来的差别).

稳定子形式的基本思想就是, 对于许多量子态,
用稳定它们的算子来描述经常比直接描述状态本身更加方便.

• 稳定子形式具有如此威力的关键, 是对群论的巧妙运用. 我们关心的群主要是 \(n\) 量子比特上的泡利群. 对单量子比特而言, 泡利群由连同系数 \(±1\), \(±i\) 在内的所有泡利矩阵组成:
  • \[G_1 ≡ \{ ±I, ±iI, ±X, ±iX, ±Y, ±iY, ±Z, ±iZ \}\]
  • 上述集合在矩阵乘法运算下构成一个群. 对于一般情况, 即 \(n\) 量子比特上的泡利群, 由所有泡利矩阵的 \(n\) 次张量乘积构成, 并且同样包含所有可能的系数 \(±1\), \(±i\).

• 我们现在给出稳定子更精确的定义. 假设 \(S\) 是 \(G_n\) 的一个子群, 将 \(V_S\) 定义为被 \(S\) 所有元素稳定的 \(n\) 量子比特状态的集合. 于是, 由于 \(V_S\) 的每个元素在 \(S\) 中元素的作用下保持稳定, \(V_S\) 是被 \(S\) 稳定的向量空间, \(S\) 则被称作空间 \(V_S\) 的稳定子.

• 使用生成元的一个巨大好处是它提供了一个非常简洁的方式来描述群. 实际上, 一个大小为 \(|G|\) 的群, 可以由一组至多包含 \(\log (|G|)\) 个生成子组成的集合生成. 并且, 为了验证一个特定的向量被一个群 \(S\) 稳定, 我们只需要验证它被生成元稳定, 因为如果这是正确的, 生成元的乘积自然也会稳定这个向量, 因而这是一种极端方便的群表示方法.
  • (我们用来表示群生成子的符号 \(\langle ... \rangle\) 可能会跟表示可观测量平均值的符号混淆, 但实际上根据上下文应该不难区分具体的含义.)
• 为了让被稳定的子空间 \(V_S\) 是非平凡的, \(S\) 必须满足什么条件呢? 两个容易被看出的必要条件是:
  • (a) \(S\) 的元素彼此对易,
  • (b) \(-I\) 不在 \(S\) 中.
  • 实际上, 这两个条件对 \(V_S\) 非平凡来说也是充分的.
• 实际上, 我们需要这些生成子 \(g_1\), …, \(g_l\) 都是互相独立的, 这意味着去掉任何一个生成子, 剩下的生成子能生成的群是严格小的, 即
  • \[\langle g_1, ..., g_{i - 1}, g_{i + 1}, ..., g_l \rangle ≠ \langle g_1, ..., g_l \rangle\]

就我们目前的理解来说, 决定一组生成子是否独立是一个非常耗费时间的过程.
幸运的是, 用被称为校验矩阵的想法, 有一个很简单的办法完成这个任务.
如此称呼这个方法的原因是, 它在稳定子编码中起到的作用,
与奇偶校验矩阵在经典线性编码中起到的作用类似.

• 假设 \(S = \langle g_1, ..., g_l \rangle\), 有一个极有用的用校验矩阵来描述生成子的方法. 这是一个 \(l \times 2n\) 的矩阵, 它的行对应着生成元 \(g_1\), …, \(g_l\), 矩阵左手边的 1 意味着生成子包含 \(X\) 操作, 右手边的 1 意味着生成子包含 \(Z\) 操作, 而两边都有 1 则表示生成子中有 \(Y\) 操作. 更具体地, 第 \(i\) 行是如下构造出来的.
  • 如果 \(g_i\) 的第 \(j\) 个量子比特上是 \(I\), 则第 \(j\) 和第 \(n + j\) 列元素是 0;
  • 如果第 \(j\) 个量子比特上是 \(X\), 则第 \(j\) 和第 \(n + j\) 列元素分别是 1 和 0;
  • 如果第 \(j\) 个量子比特上是 \(Z\), 则第 \(j\) 和第 \(n + j\) 列元素分别是 0 和 1;
  • 如果第 \(j\) 个量子比特上是 \(Y\), 则第 \(j\) 和第 \(n + j\) 列元素都是 1.
• 校验矩阵不包含任何关于生成子前系数的信息, 但它包含许多其他的有用信息. 为此, 我们用 \(r(g)\) 来代表泡利群中一个任意元素的 \(2n\) 维行向量描述. 假设我们定义一个如下的 \(2n \times 2n\) 矩阵 \(Λ\):
  • \[Λ = \begin{bmatrix} 0 & I \\ I & 0 \end{bmatrix}\]
  • 这里对角线外 \(I\) 是 \(n \times n\) 的. 那么, 不难看出, 泡利群的两个元素 \(g\) 和 \(g'\) 对易当且仅当 \(r(g) Λ r(g')^T = 0\).
  • 实际上, 形式 \(x Λ y^T\) 定义了 \(x\) 和 \(y\) 之间一种扭曲的内积, 给出了 \(x\) 和 \(y\) 对应的泡利群元素是否对易的信息.

• 命题 假设 \(S = \langle g_1 , ..., g_l \rangle\) 由 \(l\) 个独立的生成子生成, 而且 \(-I \notin S\). 在 \(1\), …, \(l\) 中挑出一个固定的 \(i\), 则 \(G_n\) 中存在一个元素 \(g\) 使得对所有 \(j ≠ i\) 都有 \(g g_j g^{\dagger} = g_j\) 和 \(g g_i g^{\dagger} = -g_i\) 成立.

• 在结束对稳定子形式基本特征的讨论之前, 我们来确认之前提到的一个论断, 即如果 \(S\) 是被一组独立, 互相对易的生成子生成, 并且 \(-I \notin S\), 则 \(V_S\) 是非平凡的. 实际上, 如果总共有 \(l = n - k\) 个生成子, 则一个合理的想法是 \(V_S\) 是 \(2^k\) 维的.
  • 因为直观上看, 每多出一个生成子, 则 \(V_S\) 的维数就会被乘以 \(1/2\), 其根据是泡利矩阵乘积的特征值是 \(+1\), \(-1\), 而它们将希尔伯特空间拆分成两个维度相同的子空间.
• 命题 令 \(S = \langle g_1, ..., g_l \rangle\) 是被 \(n - k\) 个独立, 互相对易的 \(G_n\) 元素生成, 而且 \(-I \notin S\).
  • 则 \(V_S\) 是 \(2^k\) 维向量空间.

• 在后面关于稳定子形式的所有讨论中, 我们总是假设稳定子由独立, 相互对易的生成子描述, 而且 \(-I \notin S\).

• 假设我们在一个被群 \(S\) 稳定的向量空间 \(V_S\) 上作用一个酉变换 \(U\), 则对 \(S\) 的任意元素 \(g\), 都有
  • \[U \mid ψ \rangle = U g \mid ψ \rangle = U g U^{\dagger} + U \mid ψ \rangle\]
  • 因此, 状态 \(U \mid ψ \rangle\) 被 \(U g U^{\dagger}\) 稳定, 于是我们可知向量空间 \(U V_S\) 被群 \(U S U^{\dagger} ≡ \{ U g U^{\dagger} \mid g \in S \}\) 稳定. 而且, 如果 \(g_1\), …, \(g_l\) 生成 \(S\), 则 \(U g_1 U^{\dagger}\), …, \(U g_l U^{\dagger}\) 生成 \(U S U^{\dagger}\). 所以, 为了计算稳定子的变化, 我们只需要计算对其生成子的影响.
• 这种方法描述动态过程的一个巨大优势就是, 对于某些特别的变换 \(U\), 生成子的变换呈现特别漂亮的形式. 例如, 假设我们对一个单量子比特作用一个阿达玛门. 注意我们有
  • \(H X H^{\dagger} = Z\); \(H Y H^{\dagger} = -Y\); \(H Z H^{\dagger} = X\)
  • 于是, 一个被 \(Z\) 稳定的量子态 \(\mid 0 \rangle\), 在被作用一个阿达玛门之后, 将被 \(X\) 稳定 (\(\mid + \rangle\)).
• 有一些关于阿达玛门, 相位门和泡利门的有用共关系:

• 共轭作用下一些常见操作对泡利群元素的变换. 受控非门中量子比特 1 是控制, 量子比特 2 是数据.

• 实际上, 对于一个任意的酉变换, 如果它将 \(G_n\) 中的元素变换到 \(G_n\) 中另外一个元素, 则这个西变换可以由阿达玛门, 相位门和受控非门构成. 根据定义, 满足 \(U G_n U^{\dagger} = G_n\) 的 \(U\) 的集合被称为 \(G_n\) 的规范子, 记作 \(N(G_n)\).
  • 所以, 我们实际上是在说, \(G_n\) 的规范子可以由阿达玛门, 相位门和受控非门构成, 因此, 阿达玛门, 相位门和受控非门经常也被称为规范子逻辑门.
• 定理 假设 \(U\) 是一个 \(n\) 量子比特上的西变换, 而且如果 \(g \in G_n\), 则有 \(U g U^{\dagger} \in G_n\).
  • 那么 \(U\) 可以由 \(O(n^2)\) 个阿达玛门, 相位门和受控非门, 外加一个可能的全局相位构成.
• 假设我们需要完成 \(g \in G_n\) 描述的测量 (如前所述, \(g\) 是一个厄米算子, 可以当作可观测量). 为了方便, 我们可以不失一般性地假设 \(g\) 是一个泡利矩阵的乘积, 并且没有前置系数 \(-1\) 或 \(±i\). 假设系统的状态是 \(\mid ψ \rangle\), 且有稳定子 \(\langle g_1, ..., g_n \rangle\). 那么在测量的作用下, 量子态的稳定子如何变化呢? 总共有两个可能性:
  • (1) \(g\) 和稳定子的所有生成子对易.
  • (2) \(g\) 和稳定子的一个或多个生成元反对易. 比如, 假设稳定子有生成子 \(g_1\), …, \(g_n\), \(g\) 和 \(g_1\) 反对易, 那么不失一般性我们可以假设 \(g\) 和 \(g_2\), …, \(g_n\) 对易. 这是因为, 如果 \(g\) 和这些元素中的某个不对易, 比如 \(g_2\), 则可知 \(g\) 和 \(g_1 g_2\) 对易, 然后我们将生成子列表中的 \(g_2\) 用 \(g_1 g_2\) 替代.
• 在上面第一种情形中, 根据下面的论述, \(g\) 或 \(-g\) 是稳定子的一个元素. 实际上, 对于每一个稳定子的生成元, 有 \(g_j g \mid ψ \rangle = g g_j \mid ψ \rangle = g \mid ψ \rangle\), 于是 \(g \mid ψ \rangle\) 在 \(V_S\) 中, 即它是 \(\mid ψ \rangle\) 乘以一个系数. 因为 \(g^2 = I\), 我们有 \(g \mid ψ \rangle = ± \mid ψ \rangle\), 所以 \(g\) 或 \(-g\) 在稳定子中.
  • 假设 \(g\) 是稳定子 (\(-g\) 的情形可以类似讨论), 则 \(g \mid ψ \rangle = \mid ψ \rangle\), 所以测量 \(g\) 将以概率 1 获得测量结果 \(+1\), 而且并不影响量子态本身, 所以稳定子保持不变.
• 在第二种情形中, 当 \(g\) 与 \(g_1\) 反对易, 跟其他生成子对易的时候会怎么样呢? 注意到 \(g\) 有特征值 \(±1\), 所以对应测量结果 \(±1\) 的投影算子分别为 \((I ± g) / 2\), 测量概率则为
  • \[p(+1) = tr(\frac{I + g}{2} \mid ψ \rangle \langle ψ \mid)\]
  • \[p(-1) = tr (\frac{I - g}{2} \mid ψ \rangle \langle ψ \mid)\]
• 基于事实 \(g_1 \mid ψ \rangle = \mid ψ \rangle\) 和 \(g g_1 = - g_1 g\), 我们有
  • \[\begin{align} p(+1) & = tr ( \frac{I + g}{2} g_1 \mid ψ \rangle \langle ψ \mid ) \\ & = tr ( g_1 \frac{I - g}{2} \mid ψ \rangle \langle ψ \mid ) \\ \end{align}\]
• 由求迹运算的循环特性, 我们可以将 \(g_1\) 放在求迹运算的右边并且根据 \(g_1 = g_1^{\dagger}\) 将它吸收进 \(\langle ψ \mid\), 得到
  • \[p(+1) = tr (\frac{I - g}{2} \mid ψ \rangle \langle ψ \mid) = p(-1)\]
  • 因为 \(p(+1) + p(-1) = 1\), 可知 \(p(+1) = p(-1) = 1/2\). 假设测量所得结果为 \(+1\), 则系统的新状态为 \(\mid ψ^+ \rangle ≡ (I + g) \mid ψ \rangle / √2\), 对应的稳定子为 \(\langle g, g_2, ..., g_n \rangle\). 类似地, 如果测量结果为 \(-1\), 则对应的稳定子为 \(\langle -g, g_2, ..., g_n \rangle\).

• 定理 (Gottesman-Knill 定理) 假设量子计算中只涉及以下操作: 计算基下的状态制备, 阿达玛门, 相位门, 受控非门, 泡利门, 与泡利群中可观测量对应的测量 (计算基下测量是其中的特殊形式), 以及基于量子测量结果的经典控制, 则这种量子计算可以被经典计算机有效模拟.

• 基本的想法非常简单: 对于 \(G_n\) 的一个子群 \(S\), 如果 \(-I\) 不在 \(S\) 中, 并且 \(S\) 有 \(n - k\) 个独立, 互相对易的生成子, \(S = \langle g_1, ..., g_{n - k} \rangle\), 则一个 \([n, k]\) 稳定子编码定义为被 \(S\) 稳定的子空间 \(V_S\), 记作 \(C(S)\).
  • 编码 \(C(S)\) 的逻辑基矢态是什么呢? 原则上, 给定稳定子 \(S\) 的 \(n - k\) 个生成子, 我们可以选取 \(C(S)\) 编码中任意一组规模为 \(2^k\) 的标准正交基作为逻辑计算基矢态. 但实际上, 我们可以用一些更有意义的方式系统地选取, 其中的一种如下所示.
  • 首先, 我们选择算子 \(\bar{Z}_1\), …, \(\bar{Z}_k \in G_n\) 使得 \(g_1\), …, \(g_{n - k}\), \(\bar{Z}_1\), …, \(\bar{Z}_k\) 形成一个独立, 互相对易的集合, 这里 \(\bar{Z}_j\) 算子起到第 \(j\) 个逻辑量子比特上的逻辑泡利算子 \(Z\) 的作用. 因此, 逻辑计算基矢态 \(\mid x_1, ..., x_k \rangle_L\) 被定义为稳定子为
  • \[\langle g_1, ..., g_{n - k}, (-1)^{x_1} \bar{Z}_1, ..., (-1)^{x_k} \bar{Z}_k \rangle\]
  • 的量子态. 类似地, 我们将 \(\bar{X}_j\) 定义为共轭操作下, 将 \(\bar{Z}_j\) 变成 \(-\bar{Z}_j\), 同时在其他 \(\bar{Z}_i\) 和 \(g_i\) 上保持不变的泡利算子的乘积.
  • 于是, \(\bar{X}_j\) 类似于第 \(j\) 个逻辑量子比特上的量子非门, 而且算子 \(\bar{X}_j\) 满足 \(\bar{X}_j g_k \bar{X}_j^{\dagger} = g_k\), 因此与稳定子的所有生成子对易. 同时, 不难验证, \(\bar{X}_j\) 除了和 \(\bar{Z}_j\) 反对易, 还与剩下的所有 \(\bar{Z}_i\) 对易.
• 假设 \(C(S)\) 是一个稳定子编码, 并且被噪声 \(E \in G_n\) 影响. 当 \(E\) 和所有的稳定子元素反对易时, 会发生什么呢? 在这种情况下, \(E\) 将把编码空间变换到一个正交空间中来, 所以这种错误可以通过合适的投影测量探测出来 (可能也能纠正). 如果 \(E\) 在 \(S\) 中, 则 “错误” \(E\) 根本不改变编码空间中任何态, 因此不必担心它的影响.
  • 所以, 真正的危险来自下面的情形, 就是 \(E\) 与 \(S\) 的所有元素对易, 但 \(E\) 并不在 \(S\) 中, 也就是对所有 \(g \in S\) 都有 \(Eg = gE\). 满足对所有 \(g \in S\), 都有 \(Eg = gE\) 成立的 \(E\) 的全体集合, 被称为 \(S\) 在 \(G_n\) 里的中心子, 记作 \(Z(S)\).
  • 实际上, 对于我们关心的稳定子群 \(S\) 来说, 中心子实际上与一个我们更熟悉的群相同, 即 \(S\) 的规范子, 记作 \(N(S)\). \(S\) 的规范子是对所有 \(g \in S\) 都有 \(E g E^{\dagger} \in S\) 成立的所有 \(E \in G_n\) 的全体集合.

容错量子计算

本章小结

• 量子纠错码: 一个 \([n, k, d]\) 量子纠错码用 \(n\) 个物理量子比特编码 \(k\) 个逻辑量子比特, 并且距离为 \(d\).
• 量子纠错条件: \(C\) 为一个量子纠错码, \(P\) 是映射到 \(C\) 上的投影算子. 该纠错码能纠正错误集 \(\{ E_i \}\) 当且仅当 \(P E_i^{\dagger} E_j P = α_{ij} P\) 对某个复数构成的厄米矩阵 \(α\) 成立.
• 稳定子编码: 令 \(S\) 是稳定子编码 \(C(S)\) 的稳定子, \(\{ E_j \}\) 是一组噪声, 它们是泡利群元素, 而且对所有的 \(j\) 和 \(k\) 有 \(E_j^{\dagger} E_k \notin N(S) - S\) 成立. 那么对 \(C(S)\) 来说, \(\{ E_j \}\) 是一组可纠正噪声.
• 容错量子计算: 编码量子态上的一组通用逻辑操作, 可以按下面的要求实现出来, 即如果所有逻辑门的错误概率是 \(p\), 编码数据中的等效错误概率将是 \(O(p^2)\) 量级.
• 阈值定理: 假设单个量子门上的噪声低于某个常数阈值, 并且满足某些物理上合理的假设, 则可以可靠地实现任意长的量子计算, 并且为了确保可靠性, 多出的代价跟电路的规模比起来很小.

量子傅里叶变换及其应用

相位估计

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

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

量子搜索算法

作为量子模拟的量子搜索

量子计数

NP 完全问题解的加速

无结构数据库的量子搜索

搜索算法的最优性

黑盒算法的极限

附录

群论

隐藏子群问题

• 元素 \(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 定理