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

• 量子计算与量子信息

量子电路

• 量子计数

单量子比特操作

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

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

• 本章小结
  • 通用性: \(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 编码, 本质上是三量子比特相位翻转编码和比特翻转编码的一种结合. 我们首先将量子比特做相位翻转编码:
  • \(\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\) 的行向量线性无关.

稳定子编码

容错量子计算

• 本章小结
  • 量子纠错码: 一个 \([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)\) 量级.
  • 阈值定理: 假设单个量子门上的噪声低于某个常数阈值, 并且满足某些物理上合理的假设, 则可以可靠地实现任意长的量子计算, 并且为了确保可靠性, 多出的代价跟电路的规模比起来很小.

附录

群论

• 隐藏子群问题

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