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

• 量子计算与量子信息

量子电路

• 量子计数

单量子比特操作

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

测量

通用量子门

量子电路模型计算总结

量子系统的模拟

量子傅里叶变换及其应用

量子傅里叶变换

相位估计

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

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

量子搜索算法

量子搜索算法

作为量子模拟的量子搜索

量子计数

NP 完全问题解的加速

无结构数据库的量子搜索

搜索算法的最优性

黑盒算法的极限

量子计算机: 物理实现

这一章比较鸡肋~ 物理实现种类多样, 体系复杂, 对于非从业者, 意义不大. 且在可预见的未来存在很大变数! 估计成书之后, 已经有了不少进展~ 不过, 概略性的介绍其实也有意义, 概述基本理论. 所以这一章简单略读.

• 实现量子计算有 4 项基本要求:
  1. 量子比特表示,
  2. 可控酉变换,
  3. 初始量子比特态的制备,
  4. 最终量子比特态的测量.

量子计算的条件

• 量子比特是一些二能级系统, 作为量子计算机最简单的建造单元, 它们为成对的量子态提供了方便的标志和物理实现.
  • 因此, 比如自旋 \(3/2\) 粒子的 4 个态, \(\mid m = + 3/2 \rangle\), \(\mid m = + 1/2 \rangle\), \(\mid m = - 1/2 \rangle\), \(\mid m = - 3/2 \rangle\), 可以用来代表两个量子比特.
• 以计算作为目的, 要实现的关键是可访问态的集合应该是有限的. 沿一维直线运动粒子的位置 \(x\) 通常不适合作为计算态的集合, 尽管粒子可能处于量子态 \(\mid x \rangle\), 乃至叠加态 \(\sum_{x} c_x \mid x \rangle\).
  • 这是由于 \(x\) 处于概率上的连续区域, 且具有无限大小的希尔伯特空间, 因此无噪声时其信息容量也是无限的.
  • 比如说, 在完美世界中, 莎士比亚全集可以存储到无限位的二进制小数中 \(x = 0.010111011001...\) (并读出).
  • 这显然是不现实的, 现实是噪声的存在把可分态数目降为有限个.
• 实际上, 通常需要把某些对称性献给态空间的有限性, 以便把退相干降到最小.
  • 比如说, 一个自旋 \(1/2\) 粒子的希尔伯特空间由 \(\mid \uparrow \rangle\) 和 \(\mid \downarrow \rangle\) 两个态张成;
  • 自旋态不能处于此二维空间之外, 当被很好地孤立之后, 就成为一个近乎完美的量子比特.

量子计算机的实现

具体的量子计算机实现粗略的浏览了下~ 介绍的也比较概括.

• 量子谐振子
• F-P 腔
• Jaynes-Cummings model

• 偏振

• 一般来说, 对一个物理系统而言能完成一个酉变换 U 的充要条件很简单, 即为系统的时间演化算子 \(T = \exp(-i \mathbf{H} t)\), 由哈密顿量 H 来定义, 具有与 U 近乎相同的本征值谱.

也许最重要的, 是腔 QED 开启了对量子信息处理意义非凡的, 通向附加相互作用宝藏的大门.
我们也看到, 如何从量子信息的视角 -- 限定于单光子与单原子 -- 使我们能用最基本的腔
QED 相互作用 Jaynes-Cummings 哈密顿量, 构建出电磁波与物质相互作用的一些最基本的物理.

当离子具有自旋时, 它拥有磁矩, 就像是一个复合粒子, 其中有一些沿着环路运动的电流.
但是电子是基本粒子, 且已知组成原子核的夸克不会通过轨道运动产生自旋.
不仅如此, 一个粒子的自旋只能是整数或半整数.
不管怎样, 自旋是很真实的, 而且是日常物理学中的重要组分.

整数自旋粒子 -- 被称为玻色子 -- 包括光子.
它无静止质量, 某种程度上是特殊的, 只有自旋 ±1 的组分 (而没有零自旋),
对应于两个熟知的偏振正交态.

半整数自旋粒子, 被称为费米子, 包括电子, 质子和中子.
这些是 "自旋 1/2" 粒子, 它们的自旋分量要么是 +1/2 (自旋 "向上"),
要么是 -1/2 (自旋 "向下"). 当我们提到自旋, 通常是指自旋 1/2 粒子.

诸如位置和动量的连续变量, 以及其他无限的希尔伯特空间系统, 必须被人为地截断以便代表量子比特.
与它们不同, 自旋态为量子信息提供了一个良好的表示, 因为它们天然地存在有限的态空间.

当我们提到自旋, 通常是指自旋 \(1/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 | 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 | 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\) 连分式展开中的一个渐进分数.