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

• 量子计算与量子信息

为什么量子算法的突破如此艰难?
媒体上普遍解释量子计算的加速是由于指数级的并行处理,
这种理解没有触及量子计算的本质,
因为量子计算完全不同于计算机界耳熟能详的"并行处理".

在一个量子比特的状态里, 大自然隐藏了大量的"隐含信息",
量子算法必须利用量子界独特的干涉和纠缠特性.

经典的并行性是用多个电路同时计算 f(x),
而量子并行性是利用不同量子状态的叠加,
用单个 f(x) 电路同时计算多个 x 的函数值.

"纠缠"不是简单的并行, 而是我们在宏观世界从未接触过的新的"自然资源".
人类的直觉植根于经典世界, 如果只是借助于我们已有的知识和直觉来设计算法,
就跳不出经典思维的局限. 为设计好的量子算法, 需要部分地"关闭"经典直觉,
巧妙地利用量子效应去达到期望的算法目的.

用单个 f(x) 电路同时计算多个 x 的函数值.

Shor 教授采用不同寻常的思路, 将整数质因数分解重构为一个新问题:
确定一个序列的重复周期. 这本质上是一种傅里叶变换,
可以通过在量子比特的全集上使用全局运算找到这个序列.

上世纪 80 年代人们就知道量子计算机可以实现傅里叶变换,
但由于在量子计算机上, 振幅不能通过测量直接访问,
也没有有效的方法来制备傅里叶变换的初始态,
因此寻找量子傅里叶变换的应用希望渺茫.

Shor 教授找到了在不测量计算的情况下测量误差的巧妙办法,
用量子傅里叶变换解决了整数因子分解和离散对数问题.
量子计算将计算机科学推向物理学的最前沿, 如果没有对量子纠缠的深刻理解,
只在传统的并行处理上动脑筋, 就难以找到比传统算法更有效的量子算法.

学习与研究量子算法的另一个难点是, 传统算法已经研究了几十年,
各个领域都有大量成熟的算法, 如果我们设计的量子算法与已有的算法相比,
没有明显的优势, 就没有必要杀鸡用牛刀了.
尽管量子计算机的物理实现有较大进展, 但运行 Shor 算法破解 1024 位
RSA 的加密信息仍需要比当前量子计算机的规模扩大五个数量级,
错误率则要再降低两个数量级, 估计近十年内难以实现.

估计近十年内难以实现. 不用估计了, 十年已经过去了~

在有噪声的中尺度量子计算机上能有效运行哪些有重大科学和经济价值的量子算法,
是当前应优先考虑的研究方向.
在量子搜索, 量子组合优化, 量子机器学习, 量子游走,
变分量子算法等方向都有可能做出实用化的量子算法.
在未来的 10 到 15 年内,
量子计算机可能是与传统计算机互补的协处理器或加速器,
量子算法与传统算法的协同值得高度重视.

在未来的 10 到 15 年内. 时间已到, 尚未实现~

这种情况在 20 世纪七八十年代开始发生改变, 当时一些先驱者受到启发,
开始考虑计算机科学和信息论的一些基本问题是否可以应用于量子系统的研究.
相比将量子系统纯粹视为自然界中可以解释的现象,
他们将量子系统视为可以设计的系统.

这似乎是观念上的微小变化, 但意义是深远的.
量子世界不再仅仅是呈现出来的, 而是可以创造出来的.
其结果是一幅全新的景象, 不仅激发了人们对量子力学基本原理的兴趣,
还有融合了物理学, 计算机科学和信息论的许多新问题.

这些问题包括:
构建量子态所需的空间和时间的基本物理限制是什么?
实现给定的动态操作需要多少时间和空间?
是什么使量子系统难以通过传统的经典方法来理解和模拟?

还有融合了物理学, 计算机科学和信息论的许多新问题. 是啊! 精彩!

• 本书的约定
  • 向量空间假定是有限维的.
  • 除非另有说明, 对数以 2 为底.
  • 对于作为量子比特的两能级量子系统, 我们通常使用向量 \((1, 0)\) 标识状态 \(\mid 0 \rangle\), 类似地, 用 \((0, 1)\) 标识状态 \(\mid 1 \rangle\).
  • 我们还按照惯例定义泡利西格玛矩阵. 最重要的是, 我们约定泡利西格玛 \(z\) 矩阵是 \(σ_{z} \mid 0 \rangle = \mid 0 \rangle\) 和 \(σ_{z} \mid 1 \rangle = - \mid 1 \rangle\), 这与某些物理学家 (但通常不是计算机科学家或数学家) 直观上的期望相反.
  • 这种不和谐的根源是, 物理学家通常把 \(σ_z\) 的本征态 \(+1\) 作为所谓的”激发态”, 对于许多人来说, 把它等同于 \(\mid 1 \rangle\) 似乎是自然的, 而不是像本书一样等同于 \(\mid 0 \rangle\). 我们的选择是为了与线性代数中矩阵元素常用的下标保持一致, 因此把 \(σ_z\) 的第 1 列与 \(σ_z\) 在 \(\mid 0 \rangle\) 上的操作等同, 把第 2 列与在 \(\mid 1 \rangle\) 上的操作等同是自然的. 这一选择也被整个量子计算和量子信息学界所使用.
  • 除了泡利西格玛矩阵的常规符号 \(σ_x\), \(σ_y\), \(σ_z\), 对于这 3 个矩阵使用符号 \(σ_1\), \(σ_2\), \(σ_3\), 并将 \(σ_0\) 定义为 \(2 \times 2\) 的单位矩阵也会带来很多方便. 但最常见的情况是, 我们分别使用符号 \(I\), \(X\), \(Y\), \(Z\) 来代替 \(σ_0\), \(σ_1\), \(σ_2\), \(σ_3\).
  • 可观测量 \(M\) 的平均值一般写成 \(\langle M \rangle\).

Part 1 的各章均可单独阅读, 几乎没有顺序依赖~

简介与概述

什么是量子力学?
量子力学是一个数学框架或物理理论构建的规则集.

量子力学与像量子电动力学那样的特定物理理论的关系,
更像是计算机操作系统与特定应用软件的关系 --
操作系统设置某些基本参数和操作模式, 而应用软件则完成特定任务.

与 Scott Aaronson 的观点类似, 是量子计算领域的主流观点?

那么, 什么是量子力学?
尽管它由物理学家发现, 但它并不是一个像电磁学或广义相对论那样的物理学理论.

在通常的"科学层级"中
(最顶上是生物学, 之下是化学, 再下是物理学, 最底下是数学),
量子力学应该位于数学与物理学之间.

简单来说, 量子力学是操作系统, 其他物理学理论作为应用软件在其中运行
(广义相对论除外, 因为它尚未被成功移植到这个操作系统).
甚至有一个词用来描述将一个物理学理论移植到这个操作系统的过程 -- 量子化.

但是, 如果量子力学不是通常意义上的物理学
(如果它不关于物质, 能量, 波或粒子), 那它到底关于什么呢?
在我看来, 量子力学关于信息, 概率, 可观测量, 以及它们之间的关系.

-- Scott Aaronson, 量子计算公开课

量子力学关于信息, 概率, 可观测量, 以及它们之间的关系. 2024, 隔了数年, 终于有了不一样的理解~ 哈哈

摘录 Scott Aaronson 的观点于此~

量子比特

• 比特和量子比特之间的区别在于量子比特可以处于除 \(\mid 0 \rangle\) 或 \(\mid 1 \rangle\) 外的状态, 量子比特是状态的线性组合, 通常称为叠加态, 如:
  • \[\mid ψ \rangle = α \mid 0 \rangle + β \mid 1 \rangle\]
  • 其中 \(α\) 和 \(β\) 是复数, 尽管很多时候将它们视为实数也没有太大问题.
  • 换句话说, 量子比特的状态是二维复向量空间中的向量.
  • 特殊的 \(\mid 0 \rangle\) 和 \(\mid 1 \rangle\) 状态被称为计算基矢态, 是构成该向量空间的一组正交基.

计算基矢态, 还不如直接译为: 基态.

• 布洛赫球面
  • 密度矩阵

布洛赫球面: 复系数线性叠加, 全局相位 (不可测量), 相对相位. 重点是下文的纯态, 混合态, 密度矩阵相关部分~

它是使得单个量子比特可视化的有效方法,
也是量子计算和量子信息思想很好的测试平台.
本章后面要讲的单量子比特的许多操作都在布洛赫球面的框架中描绘.
不过切记这种直观想象有很大的局限,
因为尚不清楚如何将布洛赫球面简单推广到多量子比特的情形.

• 一个描述两量子比特的态向量可以表示为
  • \[\mid ψ \rangle = a_{00} \mid 00 \rangle + a_{01} \mid 01 \rangle + a_{10} \mid 10 \rangle + a_{11} \mid 11 \rangle\]
  • 类似于单量子比特, 测量到 \(x (= 00, 01, 10, 11)\) 的概率为 \(\mid a_x \mid ^2\), 测量后量子比特将变成 \(\mid x \rangle\).
  • 此时由归一化条件可得, 概率和满足 \(\sum_{x \in \{ 0, 1 \} ^2} \mid a_x \mid ^2 = 1\), 其中记号 \(\{ 0, 1 \} ^2\) 表示每个字符取 0 或 1 的长度为 2 的串.

量子计算

• 事实上, 表示单量子门的矩阵 \(\mathbf{U}\) 需要满足酉性条件, 即 \(\mathbf{U}^{\dagger} \mathbf{U} = \mathbf{I}\), 其中 \(\mathbf{U}^{\dagger}\) 是 \(\mathbf{U}\) 的共轭转置 (取 \(\mathbf{U}\) 的转置, 再取复共轭得到), \(\mathbf{I}\) 是 \(2 \times 2\) 的单位阵.
  • 例如, 很容易验证对于非门有 \(\mathbf{X}^{\dagger} \mathbf{X} = \mathbf{I}\).

令人惊奇的是, 这一酉性限制是量子门的唯一限制.
任何酉矩阵都可以定义一个有效的量子门, 一个有趣的推论是:
和经典世界只有一个非平凡的单比特门 -- 非门 -- 相比,
有很多非平凡的单量子比特门.

• 任何 \(2 \times 2\) 酉矩阵可以分解为
  • \[\mathbf{U} = e^{iα} \begin{bmatrix} e^{-iβ/2} & 0 \\ 0 & e^{iβ/2} \end{bmatrix} \begin{bmatrix} \cos \frac{γ}{2} & - \sin \frac{γ}{2} \\ \sin \frac{γ}{2} & \cos \frac{γ}{2} \end{bmatrix} \begin{bmatrix} e^{-iδ/2} & 0 \\ 0 & e^{iδ/2} \end{bmatrix}\]
  • 其中 \(α\), \(β\), \(γ\) 和 \(δ\) 都是实数.
  • 注意第二个矩阵仅是一次普通的旋转, 第一个和最后一个矩阵都可以理解为不同平面上的旋转.
  • 该分解可对任何单量子比特逻辑门的操作进行精确描述.

受控非门的描述如下:
如果控制量子比特被置为 0, 那么目标量子比特不变;
如果控制量子比特被置为 1, 那么目标量子比特翻转.

• 我们注意到受控非门可以看成一种拓展的异或门. 其他经典门, 如与非门和通常的异或门, 是否能在某种意义上以类似于量子非门表示经典非门的方式被视为酉门呢?
  • 事实上这是不可能的, 因为异或门和与非门本质上是不可逆的.
  • 例如, 给定异或门的输出 \(A \oplus B\), 不可能确定输入 \(A\) 和 \(B\); 异或门的不可逆性带来了信息的损失.
  • 另一方面, 酉量子门总是可逆的, 因为酉矩阵的逆仍然是酉矩阵, 所以量子门的逆总可以由另一个量子门表示.

理解如何在这种可逆和不可逆意义下做经典逻辑运算,
是懂得如何利用量子力学优势来进行计算的关键步骤.

当然, 除了受控非门, 还有许多其他有趣的量子门.
然而, 在某种意义下受控非门和单量子比特门是其他所有门的原型,
这是因为如下著名的通用性结果:
任何多量子比特逻辑门可以由受控非门和单量子门组成.

• 更一般地, 给定任意一组基 \(\mid a \rangle\) 和 \(\mid b \rangle\), 可以把任意态表示为这组基的线性组合的形式 \(α \mid a \rangle + β \mid b \rangle\).
  • 此外, 如果 \(\mid a \rangle\) 和 \(\mid b \rangle\) 是相互正交的, 那么可以相对基 \(\mid a \rangle\) 和 \(\mid b \rangle\) 进行测量, 以概率 \(\mid α \mid ^2\) 得到 \(a\), 而以概率 \(\mid β \mid ^2\) 得到 \(b\).
  • 为了满足概率限制 \(\mid α \mid ^2 + \mid β \mid ^2 = 1\), 正交性是必要的.
  • 类似地, 多量子比特系统相对于任意正交基的测量原则上也是可能的. 但这仅仅是在原则上是可能的, 并不意味着这样的测量是容易实现的.

一些经典电路的特征在量子电路中通常不会出现.

首先, 我们不允许环路, 即从量子电路的一部分反馈到另一部分;
我们称电路为非周期的.

其次, 经典电路允许连线汇合, 即扇入操作,
导致单线包含所有输入位的按位或.
显然这个操作不是可逆的, 因此也不是酉操作,
所以我们不允许量子电路中有扇入操作.

第三, 与上面相反的操作, 扇出操作,
即产生一个比特的多个拷贝在量子电路中也是不允许的.

• 假定我们想利用受控非门来复制未知态 \(\mid ψ \rangle = a \mid 0 \rangle + b \mid 1 \rangle\).
  • 两个输入量子比特可以写作
  • \[[ a \mid 0 \rangle + b \mid 1 \rangle ] \mid 0 \rangle = a \mid 00 \rangle + b \mid 10 \rangle\]
  • 受控非门的作用是当第一个量子比特是 1 时翻转第二个量子比特, 因此输出是
  • \(a \mid 00 \rangle + b \mid 11 \rangle\).
• 我们成功地复制了 \(\mid ψ \rangle\) 吗? 或者说, 我们制备了态 \(\mid ψ \rangle \mid ψ \rangle\) 吗?
  • 当 \(\mid ψ \rangle = \mid 0 \rangle\) 或 \(\mid ψ \rangle = \mid 1 \rangle\) 时, 该电路确实做到了;
  • 因为用量子电路复制经典信息如 \(\mid 0 \rangle\) 或 \(\mid 1 \rangle\) 是可能的.
• 然而对一般的量子态 \(\mid ψ \rangle\), 我们发现
  • \[\mid ψ \rangle \mid ψ \rangle = a^2 \mid 00 \rangle + ab \mid 01 \rangle + ab \mid 10 \rangle + b^2 \mid 11 \rangle\]
  • 与 \(a \mid 00 \rangle + b \mid 11 \rangle\) 相比, 我们发现除了 \(ab = 0\), 上述复制电路不能复制量子比特输入.
• 事实上要制备一个未知量子态的拷贝是不可能的.
  • 量子态不能被复制的这条性质被称为不可克隆定理, 是量子信息和经典信息的主要区别之一.

量子隐形传态是在发送方和接收方之间甚至没有量子通信信道连接的情况下,
进行量子态的传输.

• 量子隐形传态
  • 贝尔态

量子算法

• Deutsch-Jozsa 算法

众多量子算法其设计的本质都是精心选择函数和最终变换,
使得能高效地确定有用的全局信息 --
这些信息无法很快地在经典计算机上得到.

实验量子信息处理

• 施特恩-格拉赫实验

氢原子有一个质子和一个环绕的电子.
你可以把这个电子想象成质子周围的一点"电流".
该电流使原子具有磁场; 每个原子都有物理学家所说的"磁偶极矩".

我们自然地预期离开炉子的热原子的偶极子在每个方向上随机取向,
因此应当会出现原子连续分布,
看到原子从 Stern-Gerlach 装置的各个角度射出.
然而事实上看到的是原子从一组离散的角度出现.
物理学家通过假设原子的磁偶极矩是量子化的能够解释这一现象,
即, 磁偶极矩是一些基本量的离散倍.

这一观点提出后, 伟大的物理学家海森伯 (旧译作海森堡) 称其"勇敢",
因为它向自然界引入了一个全新的物理量.
除了由于电子的旋转运动引起的贡献,
它还假定电子的自旋对氢原子的磁偶极矩产生额外的贡献.

海森伯 (旧译作海森堡). 哈哈, 强迫症救星~

我们现在相信量子比特是描述电子自旋的最好模型.
更进一步, 我们相信量子比特模型
(以及它向更高维度的推广; 换句话说, 量子力学)
能够描述每个物理系统.

建立两个光子之间的有效相互作用, 本质上分两步工作:
第一个光子与原子相互作用, 而原子又与第二个光子相互作用,
从而导致两个光子之间的整体相互作用.

量子信息

1. 确定量子力学中的基本静态资源类.
   • 一个例子是量子比特, 另一个例子是经典比特;
   • 经典物理学是量子物理学的一个特例, 因此在经典信息理论中出现的基本静态资源在量子信息理论中具有重要意义也就不足为奇了.
   • 另一个基本静态资源类的例子是相距遥远的两方之间共享的贝尔态.
2. 确定量子力学中动力学过程的基本类.
   • 一个简单的例子是内存, 即在一段时间内存储量子态的能力.
   • 较不平凡的过程是两方 Alice 和 Bob 之间的量子信息传输; 复制 (或试图复制) 量子态, 以及保护量子信息处理免受噪声影响的过程.
3. 量化执行基本动态过程所需的资源折衷.
   • 例如, 使用嘈杂的通信信道在两方之间可靠地传输量子信息所需的最小资源是多少?

• 香农熵

香农的无噪声信道编码定理提供了一个很好的例子,
满足了前面列出的信息理论的目标.
确定了两个静态资源 (目标 1): 比特和信息源.
确定了两阶段动态过程 (目标 2): 压缩信息源, 然后解压缩以恢复信息源.
最后通过找到最优数据压缩方案确定消耗资源的量化标准 (目标 3).

香农的有噪声信道编码定理也实现了我们前面提到的信息理论的三个目标.
涉及两种类型的静态资源 (目标 1), 即信息源, 以及通过信道发送的比特.
涉及三个动态过程 (目标 2). 主要过程是信道中的噪声.
为了对抗这种噪声, 我们使用纠错码对状态执行编码和解码的双重过程.
对于固定噪声模型, 香农的定理告诉我们如果要实现可靠的信息传输,
最佳纠错方案必须引入多少冗余 (目标 3).

• 冯·诺依曼熵

这种非正交量子态的不可区分性是量子计算和量子信息的核心.
它是我们断言的本质, 即量子态包含无法通过测量获得的隐藏信息,
因此这些信息在量子算法和量子密码学中起着关键作用.
量子信息理论的核心问题之一是发展度量来量化非正交量子态的可区分度.

这一章部分内容可以分别后置到后面的不同章. 作为简介和概述而言, 内容稍多了些; 但又没有展开讲述. 略显鸡肋~

量子力学基础

线性代数

在我们看来, 认同量子力学公设的主要障碍不是公设本身,
而是为理解它们所需要的大量的线性代数概念.
再加上量子力学中被物理学家采用的不常用的狄拉克 (Dirac) 记号.

扯淡! 另, 数学预备知识, 补充推荐: 陶哲轩实分析的傅里叶级数一章; 科恩的量子力学卷二的附录: 傅立叶级数和傅立叶变换.

• 向量空间中向量的标准量子力学记号为 \(\mid ψ \rangle\)
  • \(ψ\) 是向量的标签 (任意的标签都是有效的, 尽管我们喜欢用像 \(ψ\) 和 \(φ\) 这样的简单标签).
  • 记号 \(\mid \cdot \rangle\) 用来表示其中的对象是向量.
• 常见符号
  • \(\mid ψ \rangle\), 向量
  • \(\langle ψ \mid\), \(\mid ψ \rangle\) 的对偶向量
  • \(\langle φ \mid ψ \rangle\), 向量 \(\mid φ \rangle\) 和 \(\mid ψ \rangle\) 的内积
  • \(\mid φ \rangle \otimes \mid ψ \rangle\), \(\mid φ \rangle\) 和 \(\mid ψ \rangle\) 的张量积
  • \(\mid φ \rangle \mid ψ \rangle\), \(\mid φ \rangle\) 和 \(\mid ψ \rangle\) 张量积的缩写
  • \(\mathbf{A}^{\dagger}\), 矩阵 A 的厄米共轭或伴随, \(\mathbf{A}^{\dagger} = (\mathbf{A}^{T})^{*}\)
  • \[\begin{bmatrix} a & b \\ c & d \end{bmatrix}^{\dagger} = \begin{bmatrix} a^{*} & c^{*} \\ b^{*} & d^{*} \end{bmatrix}\]
  • \(\langle φ \mid \mathbf{A} \mid ψ \rangle\), \(\mid φ \rangle\) 和 \(\mathbf{A} \mid ψ \rangle\) 的内积
  • 等价的, \(\mathbf{A}^{\dagger} \mid φ \rangle\) 和 \(\mid ψ \rangle\) 的内积

最后一个, 注意顺序~

注: 符号 \(\mathbf{A}^{*}\) 在线性代数中通常表示共轭转置, 但在量子力学中, 仅仅表示共轭.

\(\mathbf{A}^{\dagger}\) 在量子力学中替代了 \(\mathbf{A}^{*}\) 在线性代数中的含义.

• 向量空间 V 和 W 之间的线性算子定义为对输入具有线性性质的映射 \(\mathbf{A}: \mathbf{V} \to \mathbf{W}\):
  • \[\mathbf{A} (\sum_{i} a_i \mid v_i \rangle) = \sum_i a_i \mathbf{A} (\mid v_i \rangle)\]
  • 通常将 \(\mathbf{A} (\mid v \rangle)\) 写成 \(\mathbf{A} \mid v \rangle\).
  • 当我们说定义在线性空间 V 上的线性算子 A 时, 意味着 A 是一个从 V 到 V 的线性算子.
• 在任意向量空间 V 上, 一个重要的线性算子是恒等算子 \(I_V\), 定义为对任意的向量 \(\mid v \rangle\), \(I_V (\mid v \rangle) = \mid v \rangle\).
  • 在不会出现混淆时, 我们丢弃下标 V 仅用 I 表示恒等算子.
• 另一个重要的线性算子是零算子, 用 \(\mathbf{0}\) 表示.
  • 零算子把所有的向量都映射为零向量, 即 \(\mathbf{0} \mid v \rangle = \mathbf{0}\).

很容易看出, 一旦线性算子在基上的行为确定, A 在所有输入上的行为也就确定了.

• 泡利矩阵
  • \[I \equiv \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\]
  • \[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}\]

• 假设 \(\mathbf{A} : \mathbf{V} \to \mathbf{W}\) 是向量空间 V 和 W 之间的线性算子. \(\mid v_1 \rangle\), …, \(\mid v_m \rangle\) 是 V 的一组基, \(\mid w_1 \rangle\), …, \(\mid w_n \rangle\) 是 W 的一组基.
  • 则对 1, …, m 中任意的 j 存在复数 \(A_{1j}\) 到 \(A_{nj}\), 使得
  • \[\mathbf{A} \mid v_j \rangle = \sum_{i} \mathbf{A}_{ij} \mid w_i \rangle\]
  • 我们称这个元素为 \(A_{ij}\) 的矩阵形成了算子 A 的一个矩阵表示. A 的矩阵表示完全等价于算子 A, 因而我们将交替使用矩阵和算子的概念.

需要注意的是, 为了建立矩阵和线性算子之间的联系,
我们需要为线性算子的输入和输出向量空间各指定一组输入和输出基矢态.

• 内积 \((\mid v \rangle, \mid w \rangle)\) 的标准量子力学记号是 \(\langle v \mid w \rangle\), 其中 \(\mid v \rangle\) 和 \(\mid w \rangle\) 是内积空间的向量, 记号 \(\langle v \mid\) 是向量 \(\mid v \rangle\) 的对偶向量;
  • 对偶是从内积空间 V 映射到复数 \(\mathbb{C}\) 的一个线性算子, 其中 \(\langle v \mid (\mid w \rangle) \equiv \langle v \mid w \rangle \equiv (\mid v \rangle, \mid w \rangle)\).
  • 对偶向量的矩阵表示就是一个行向量.
• 一个从 \(\mathbf{V} \times \mathbf{V}\) 到复数空间 \(\mathbb{C}\) 的函数 \((\cdot, \cdot)\), 如果满足下面的要求:
  • \((\cdot, \cdot)\) 对于第二个参数是线性的: \((\mid v \rangle, \sum_{i} \lambda_{i} \mid w_i \rangle) = \sum_i \lambda_{i} (\mid v \rangle, \mid w_i \rangle)\)
  • \[(\mid v \rangle, \mid w \rangle) = (\mid w \rangle, \mid v \rangle)^{*}\]
  • \((\mid v \rangle, \mid v \rangle) \ge 0\), 当且仅当 \(\mid v \rangle = \mathbf{0}\) 时等式成立.
• 则称函数 \((\cdot, \cdot)\) 是一个内积. 例如, \(\mathbb{C}^{n}\) 中的内积定义为
  • \[((y_{1}, ..., y_{n}), (z_{1}, ..., z_{n})) \equiv \sum_{i} y_{i}^{*} z_{i} = [y_{1}^{*}, ..., y_{n}^{*}] \begin{bmatrix} z_{1} \\ \vdots \\ z_{n} \end{bmatrix}\]
• 我们称定义了内积的向量空间为内积空间.

注: 内积的定义不同文献会有差异, 即取第一个变量的共轭, 还是第二个变量的共轭. 没有本质的区别, 计算结果共轭. 量子领域一般取本书的定义 (因为右矢的广泛出现, 所以更加便利). 参见: 点积, 内积空间. 另: 点积一般对应实数, 可视作内积的特例. (比较初级~)

关于对偶, 首先参看: 量子力学, 科恩, 卷一, Page 108 及相关章节 (主要在第二章: 量子力学的数学工具); 其次参看 对偶空间.

量子力学的讨论总是关系到希尔伯特空间.
在量子计算和量子信息中出现的有限维复向量空间中, 希尔伯特空间和内积空间完全相同.
从现在开始, 我们交替使用这两个术语, 较多用希尔伯特空间这个术语.
在无限维度, 希尔伯特空间满足内积空间之上和之外的技术限制, 我们不需要担心.

再次重申, 本书只讨论有限维~

• 简单来说, 正规化一个向量就是用该向量除以它的范数; 因此, 对任意的非零向量 \(\mid v \rangle\), \(\mid v \rangle / \| \mid v \rangle \|\) 是 \(\mid v \rangle\) 的正规化.
  • 对于一个向量集 \(\mid i \rangle\), 其中 \(i\) 是指标, 如果集合中的每一个向量都是单位向量, 而且不同的向量之间是正交的, 即 \(\langle i \mid j \rangle = \delta_{ij}\), 这里 \(i\), \(j\) 取自指标集, 那么称该向量集为标准正交的.

注: \(\delta_{ij}\) 是克罗内克函数. 原书并未特别说明~

• 格拉姆-施密特正交化

• 下面又是本书约定

从现在起, 当我们说一个线性算子的矩阵表示时,
意味着关于标准正交输入和输出基的矩阵表示.
我们还使用这样的约定:
如果线性算子的输入和输出空间相同,
那么输入和输出基相同, 除非另有说明.

标准正交基

• 根据这些约定, 希尔伯特空间的内积可以方便地用矩阵表示.
  • 只要向量的矩阵表示按同一组标准正交基给出, 两个向量的内积就等于向量矩阵表示的内积.
  • 我们也看到对偶向量 \(\langle v \mid\) 作为行向量有一个好的解释, 它的元素是向量 \(\mid v \rangle\) 的列向量表示中对应分量的复共轭.
• 有一种表示线性算子的有用方式, 充分地利用了内积, 称为外积表示. 假设 \(\mid v \rangle\) 是内积空间 V 的一个向量, \(\mid w \rangle\) 是内积空间 W 的一个向量.
  • 定义 \(\mid w \rangle \langle v \mid\) 为从 V 到 W 的一个线性算子, 其作用为
  • \[(\mid w \rangle \langle v \mid)(\mid v' \rangle) \equiv \mid w \rangle \langle v \mid v' \rangle = \langle v \mid v' \rangle \mid w \rangle\]

注: 叉积, 外积, 张量积. 叉积没啥要说的; 外积可视作张量积的特例, 或者说张量积是外积的推广.

量子领域称张量积多一些, 而且上文刚刚出现过张量积.

• 这个方程与我们的记号约定完美吻合, 表达式 \(\mid w \rangle \langle v \mid v' \rangle\) 可能含有以下两种含义之一:
  • 我们用它表示算子 \(\mid w \rangle \langle v \mid\) 作用在 \(\mid v' \rangle\) 上的结果,
  • 也可以解释为 \(\mid w \rangle\) 被一个复数 \(\langle v \mid v' \rangle\) 相乘.

我们选择的定义使得这两种潜在意思是一致的,
事实上我们通过后者定义了前者!

推荐阅读: 科恩, 卷一, 第二章, B 态空间, 线性算符

• 柯西-施瓦茨不等式

• 外积记号的有用性可以从标准正交向量满足的完备性关系中看清楚. 令 \(\mid i \rangle\) 为向量空间 \(\mathbf{V}\) 的任意一组标准正交基, 那么任意向量 \(\mid v \rangle\) 可以写为 \(\mid v \rangle = \sum_{i} v_i \mid i \rangle\), \(v_i\) 是一组复数.
  • 注意到 \(\langle i \mid v \rangle = v_i\), 因此
  • \[(\sum_{i} \mid i \rangle \langle i \mid) \mid v \rangle = \sum_{i} \mid i \rangle \langle i \mid v \rangle = \sum_{i} v_i \mid i \rangle = \mid v \rangle\]
  • 由于最后的等式对于任意的 \(\mid v \rangle\) 成立, 这等于说
  • \[\sum_{i} \mid i \rangle \langle i \mid = \mathbf{I}\]
• 这个等式就是著名的完备性关系. 完备性关系的一个应用是用外积的记号给出任意算子的表示方式. 假设 \(\mathbf{A}: \mathbf{V} \to \mathbf{W}\) 是一个线性算子, \(\mid v_i \rangle\) 是 \(\mathbf{V}\) 的一组标准正交基, \(\mid w_i \rangle\) 是 \(\mathbf{W}\) 的一组标准正交基.
  • 运用两次完备性关系, 可以得到
  • \[\begin{align} \mathbf{A} & = \mathbf{I}_{W} \mathbf{A} \mathbf{I}_{V} \\ & = \sum_{ij} \mid w_j \rangle \langle w_j \mid A \mid v_i \rangle \langle v_i \mid \\ & = \sum_{ij} \langle w_j \mid A \mid v_i \rangle \mid w_j \rangle \langle v_i \mid \\ \end{align}\]
• 这是 \(\mathbf{A}\) 的外积表示. 从这个方程我们还看到, \(\mathbf{A}\) 的第 \(i\) 列第 \(j\) 行的矩阵元素为 \(\langle w_j \mid \mathbf{A} \mid v_i \rangle\), 与输入基 \(\mid v_i \rangle\) 和输出基 \(\mid w_j \rangle\) 有关.

• 特征值和特征向量
  • 本征函数
• 算子 A 与特征值 v 对应的特征空间 (本征空间) 是以 v 为特征值的向量的集合.
  • 它是 A 作用的向量空间的子空间.
  • 当特征空间高于一维时, 我们说它是退化的.

退化. 应译为: 简并

• 假设 A 是希尔伯特空间 V 上的任意一个线性算子. 事实上在 V 上存在一个唯一的线性算子 \(\mathbf{A}^{\dagger}\), 满足对所有的向量 \(\mid v \rangle, \mid w \rangle \in \mathbf{V}\) 都有
  • \[(\mid v \rangle, \mathbf{A} \mid w \rangle) = (\mathbf{A}^{\dagger} \mid v \rangle, \mid w \rangle)\]
  • 这个线性算子称为 \(\mathbf{A}\) 算子的伴随或厄米共轭.
• 根据定义易知 \((\mathbf{AB})^{\dagger} = \mathbf{B}^{\dagger} \mathbf{A}^{\dagger}\).
  • 一般地, 如果 \(\mid v \rangle\) 是一个向量, 那么我们定义 \(\mathbf{v}^{\dagger} \equiv \langle v \mid\).
  • 根据这个定义不难看出 \((\mathbf{A} \mid v \rangle)^{\dagger} = \langle v \mid \mathbf{A}^{\dagger}\).

• 如果算子 A 的伴随矩阵还是 A, 那么称算子 A 为厄米的或自伴算子. 有一类重要的厄米算子是投影.
  • 假设 W 是 d 维向量空间 V 的一个 k 维向量子空间. (注: W, k; V, d)
  • 根据格拉姆-施密特方法可以构造出一组 V 的标准正交基 \(\mid 1 \rangle\), …, \(\mid d \rangle\), 使得 \(\mid 1 \rangle\), …, \(\mid k \rangle\) 是 W 的一组标准正交基.
  • 根据定义, \(\mathbf{P} \equiv \sum_{i=1}^{k} \mid i \rangle \langle i \mid\) 是在子空间 W 上的投影.
  • 很容易验证这个定义不依赖于 W 中的正交基 \(\mid 1 \rangle\), …, \(\mid k \rangle\) 的选取.
  • 根据定义可知, 对任意的向量 \(\mid v \rangle\), \(\mid v \rangle \langle v \mid\) 是厄米的, 因此 P 是厄米的, \(\mathbf{P}^{\dagger} = \mathbf{P}\).

自伴, 厄米

关于投影算符, 科恩, 卷一, 第二章, B 态空间, 线性算符. 引出的一气呵成~

• 我们通常将”向量空间” P 称为投影算子 P 到向量空间投影的简写.
  • P 的正交补是算子 \(\mathbf{Q} \equiv \mathbf{I} - \mathbf{P}\).
  • 不难发现, Q 是由 \(\mid k + 1 \rangle\), …, \(\mid d \rangle\) 张成的向量空间上的投影, 它也被称为 P 的 正交补, 记为 Q.

• 如果 \(\mathbf{A}^{\dagger} \mathbf{A} = \mathbf{A} \mathbf{A}^{\dagger}\), 那么称算子 A 为正规的.
  • 显然, 如果一个算子是厄米的, 那么它一定是正规的.
  • 对于正规算子, 有一个很有名的表示定理, 叫做谱分解.
  • 它表明如果一个算子是正规的, 当且仅当它可对角化.

正规: 厄米, 酉, 均为正规; 均可对角化.

• 如果一个矩阵 U 满足 \(\mathbf{U}^{\dagger} \mathbf{U} = \mathbf{I}\), 那么称它是酉的. 类似地, 如果一个算子 U 满足 \(\mathbf{U}^{\dagger} \mathbf{U} = \mathbf{I}\), 那么称它是酉的.
  • 很容易验证一个算子是酉的当且仅当它的每一个矩阵表示都是酉的.
  • 酉算子也满足 \(\mathbf{U} \mathbf{U}^{\dagger} = \mathbf{I}\), 因此 U 是正规的并且可以谱分解.
  • 从几何的角度来看, 酉算子是很重要的, 因为它保持向量的内积不变.

酉: 即, 幺正

• 对任意的酉算子 U 都有如下的优雅外积表示. 设 \(\mid v_i \rangle\) 是任意一组标准正交基. 定义 \(\mid w_i \rangle ≡ \mathbf{U} \mid v_i \rangle\), 因为酉算子保持内积不变, 所以 \(\mid w_i \rangle\) 也是一组标准正交基.
  • 注意到 \(\mathbf{U} = \sum_{i} \mid w_i \rangle \langle v_i \mid\).
  • 反之, 如果 \(\mid v_i \rangle\) 和 \(\mid w_i \rangle\) 是两组标准正交基, 那么很容易验证算子 \(\mathbf{U} \equiv \sum_{i} \mid w_i \rangle \langle v_i \mid\) 是酉算子.
• 厄米算子有一个特殊子类极其重要, 它就是正算子. 正 (也即半正定) 算子 A 定义为, 对任意的向量 \(\mid v \rangle\) 都有 \((\mid v \rangle, \mathbf{A} \mid v \rangle)\) 是一个非负实数.
  • 如果对所有的 \(\mid v \rangle ≠ \mathbf{0}\), \((\mid v \rangle, \mathbf{A} \mid v \rangle)\) 都严格大于 0, 则称 A 为正定的.

• 谱分解定理 向量空间 V 上的任意正规算子 M 在 V 的某组标准正交基下是可对角化的.
  • 反之, 任意可对角化的算子都是正规的.
• 按外积表示, 这意味着 M 能够写成 \(\mathbf{M} = \sum_{i} λ_i \mid i \rangle \langle i \mid\). 其中 \(λ_i\) 是 M 的特征值, \(\mid i \rangle\) 是 V 中的一组标准正交基, 并且每个 \(\mid i \rangle\) 是 M 的特征值 \(λ_i\) 对应的特征向量.
  • 从投影算子的角度来看, \(\mathbf{M} = \sum_{i} λ_i P_i\), 其中 \(λ_i\) 还是表示 M 的特征值, \(P_i\) 是 M 在 \(λ_i\) 的本征空间里的投影.
  • 这些投影算子满足完备性关系 \(\sum_{i} P_i = \mathbf{I}\) 和正交性关系 \(P_i P_j = δ_{ij} P_i\).

这一章节比格里菲斯有诚意的多了~

• 设 \(V\) 和 \(W\) 分别是 \(m\) 维和 \(n\) 维的向量空间. 方便起见, 我们设 \(V\) 和 \(W\) 都是希尔伯特空间.
  • 那么 \(V \otimes W\) 是一个 \(mn\) 维的向量空间.
  • \(V \otimes W\) 里的元素是 \(V\) 空间中的元素 \(\mid v \rangle\) 和 \(W\) 空间中的元素 \(\mid w \rangle\) 的张量积 \(\mid v \rangle \otimes \mid w \rangle\) 的线性组合.
  • 特别地, 如果 \(\mid i \rangle\) 和 \(\mid j \rangle\) 是空间 \(V\) 和 \(W\) 中的标准正交基, 那么 \(\mid i \rangle \otimes \mid j \rangle\) 是 \(V \otimes W\) 的一组基.
  • 我们常用缩写符号 \(\mid v \rangle \mid w \rangle\), \(\mid v, w \rangle\), 甚至 \(\mid vw \rangle\) 表示张量积 \(\mid v \rangle \otimes \mid w \rangle\).

同样, 科恩, 卷一, 第二章, 有更详细的补充~

注意符号约定!

• 根据定义, 张量积满足以下基本性质:
  • 对任意的标量 \(z\), \(V\) 中元素 \(\mid v \rangle\) 和 \(W\) 中元素 \(\mid w \rangle\), 有 \(z (\mid v \rangle \otimes \mid w \rangle) = (z \mid v \rangle) \otimes \mid w \rangle = \mid v \rangle \otimes (z \mid w \rangle)\)
  • 对 \(V\) 中的任意向量 \(\mid v_1 \rangle\) 和 \(\mid v_2 \rangle\), 以及 \(W\) 中任意向量 \(\mid w \rangle\), 有 \((\mid v_1 \rangle + \mid v_2 \rangle) \otimes \mid w \rangle = \mid v_1 \rangle \otimes \mid w \rangle + \mid v_2 \rangle \otimes \mid w \rangle\)
  • 对 \(V\) 中任意向量 \(\mid v \rangle\) 和 \(W\) 中任意向量 \(\mid w_1 \rangle\), \(\mid w_2 \rangle\), 有 \(\mid v \rangle \otimes (\mid w_1 \rangle + \mid w_2 \rangle) = \mid v \rangle \otimes \mid w_1 \rangle + \mid v \rangle \otimes \mid w_2 \rangle\)
• \(V \otimes W\) 空间上的线性算子类型有哪些? 假设 \(\mid v \rangle\) 和 \(\mid w \rangle\) 分别是 \(V\) 和 \(W\) 中的向量, \(A\) 和 \(B\) 分别是 \(V\) 和 \(W\) 中的线性算子.
  • 那么我们可以根据以下等式来定义 \(V \otimes W\) 上的线性算子 \(A \otimes B\):
  • \[(A \otimes B) (\mid v \rangle \otimes \mid w \rangle) \equiv A \mid v \rangle \otimes B \mid w \rangle\]
  • 为确保 \(A \otimes B\) 的线性, \(A \otimes B\) 的定义可以很自然地扩展到 \(V \otimes W\) 上的所有元素, 也就是
  • \[(A \otimes B) (\sum_{i} a_i \mid v_i \rangle \otimes \mid w_i \rangle) \equiv \sum_{i} a_i A \mid v_i \rangle \otimes B \mid w_i \rangle\]

• 有很多重要的函数可以通过算子和矩阵来定义. 一般来说, 给定一个从复数域映射到复数域的函数 \(f\), 就可以根据下面的步骤定义正规矩阵 (或者是其子类, 例如厄米矩阵) 上的相应矩阵函数.
  • 设 \(A = \sum_{a} a \mid a \rangle \langle a \mid\) 是正规算子 \(A\) 的一个谱分解.
  • 定义 \(f(A) ≡ \sum_{a} f(a) \mid a \rangle \langle a \mid\).
  • 易知 \(f(A)\) 是唯一定义的.
• 这个过程可用于一些情况, 例如定义一个正算子的平方根, 正定算子的对数, 或者正规算子的指数.
  • 例如: \(\exp(\theta Z) = \begin{bmatrix} e^{\theta} & 0 \\ 0 & e^{- \theta} \end{bmatrix}\)
  • 其中 \(\mid 0 \rangle\) 和 \(\mid 1 \rangle\) 是 \(Z\) 的特征向量.

注: \(Z\) 是泡利矩阵.

• 另外一个重要的矩阵函数是矩阵的迹. \(A\) 的迹定义为其对角元素的和:
  • \[tr(A) ≡ \sum_{i} A_{ii}\]
  • 很容易看到迹是循环的, \(tr(AB) = tr(BA)\),
  • 也是线性的, \(tr(A + B) = tr(A) + tr(B)\), \(tr(zA) = z \mbox{ } tr(A)\),
  • 其中 \(A\) 和 \(B\) 是任意的矩阵, \(z\) 是一个复数.
• 进一步, 由循环性可知, 矩阵的迹在酉相似变换 \(A \rightarrow UAU^{\dagger}\) 下是不变的, 因为 \(tr(UAU^{\dagger}) = tr(U^{\dagger}UA) = tr(A)\).
  • 根据这个结果, 可以定义算子 \(A\) 的迹为 \(A\) 的任意矩阵表示的迹.
  • 迹在酉相似变换下的不变性确保了算子的迹是定义良好的.

• 两个算子 A 和 B 的对易式定义为
  • \[[ A, B ] ≡ AB - BA\]
  • 如果 \([ A, B ] = 0\), 也就是 \(AB = BA\), 那么我们说 A 和 B 是对易的.
• 类似地, 两个算子 A 和 B 的反对易式定义为
  • \[\{ A, B \} = AB + BA\]
  • 如果 \(\{ A, B \} = 0\), 我们说 A 和 B 是反对易的.
• 事实上, 算子对的很多重要性质都可以从其对易式和反对易式推导出来. 也许最有用的关系是对易式与厄米算子 A 和 B 可同时对角化之间的联系, 即可以写成
  • \(A = \sum_{i} a_i \mid i \rangle \langle i \mid\),
  • \(B = \sum_{i} b_i \mid i \rangle \langle i \mid\),
  • 其中 \(\mid i \rangle\) 是 A 和 B 的公共特征向量构成的标准正交集.

同样, 科恩, 卷一, 第二章

• 可同时对角化定理 假设 A 和 B 是厄米算子. 那么 \([ A, B ] = 0\) 成立, 当且仅当存在一组标准正交基使得 A 和 B 可同时对角化.
  • 我们说这种情况下 A 和 B 是可同时对角化的.

• 极式分解 设 A 是向量空间 V 上一个线性算子. 那么存在酉算子 U 和正算子 J, K 使得
  • \[A = UJ = KU\]
  • 其中 \(J ≡ \sqrt{A^{\dagger} A}\), \(K ≡ \sqrt{A A^{\dagger}}\), 并且 J 和 K 是唯一满足这些等式的正算子.
  • 而且, 如果 A 是可逆的, 那么 U 是唯一的.
  • 我们称表达式 \(A = UJ\) 是 A 的左极式分解, \(A = KU\) 是 A 的右极式分解.
  • 通常, 我们会省略掉左和右, 而用极式分解来表示两个表达式, 根据上下文来推断究竟是哪一个.
• 奇异值分解 设 A 是一个方阵. 那么存在酉矩阵 U 和 V, 以及非负对角阵 D, 使得
  • \[A = UDV\]
  • D 的对角元素称为 A 的奇异值.

量子力学的假设

这一章节不如: 科恩, 卷一, 第三章, 量子力学的假定!

• 公设 1: 任意一个孤立的量子系统都与一个称为系统状态空间的复内积向量空间 (也就是希尔伯特空间) 相联系.
  • 系统完全由状态向量来描述, 它是系统状态空间里的一个单位向量.

任意一个孤立的量子系统. 原文是: 任意一个孤立的物理系统.

• 公设 2: 封闭量子系统的演化可用酉变换来描述. 也就是说, 系统在 \(t_1\) 时所处的状态 \(\mid ψ \rangle\) 和在 \(t_2\) 时所处的状态 \(\mid ψ' \rangle\) 是通过一个仅与时间 \(t_1\) 和 \(t_2\) 有关的酉算子 \(\mathbf{U}\) 联系起来的.
  • \[\mid ψ' \rangle = \mathbf{U} \mid ψ \rangle\]
  • 正如量子力学不会告诉我们一个特定量子系统中的状态空间或者量子态一样, 它也不会告诉我们哪个酉算子 \(\mathbf{U}\) 描述了现实世界的量子动力学. 量子力学仅仅告诉我们封闭量子系统可以这么描述.
  • 一个很明显的问题是: 自然选择什么样的酉算子? 在单量子比特的情况下, 所有的酉算子都能够在实际的系统中实现.

酉算子

• 公设 2’: 封闭量子系统中态的演化由薛定谔方程描述
  • \[i \hbar \frac{d \mid ψ \rangle}{dt} = \mathbf{H} \mid ψ \rangle\]
  • 在这个方程中, \(\hbar\) 是一个物理常数, 被称为约化普朗克常数. 它的精确值对我们来说不重要. 实践中, 经常把因子 \(\hbar\) 放入 \(\mathbf{H}\) 中, 置 \(\hbar = 1\).
  • \(\mathbf{H}\) 是一个称为封闭系统哈密顿量的固定厄米算子.

注: 原文普朗克常数, 改为了约化普朗克常数~

• 因为哈密顿量是一个厄米算子, 所以它有谱分解
  • \[H = \sum_{E} E \mid E \rangle \langle E \mid\]
  • 其中它的特征值为 \(E\) 并且相应的特征向量为 \(\mid E \rangle\), 状态 \(\mid E \rangle\) 一般被称为能量本征态, 有时也被称为稳态, \(E\) 是状态 \(\mid E \rangle\) 的能量.
  • 最低的能量称为系统的基态能量, 相应的能量本征态 (或本征空间) 称为基态.
  • 状态 \(\mid E \rangle\) 有时称为稳态, 原因是它们随时间变化的仅仅是一个数值因子,
  • \[\mid E \rangle \rightarrow \exp(-iEt / \hbar) \mid E \rangle\]

• 公设 2' 中的哈密顿量的动力学描述和公设 2 中的酉算子描述之间有什么联系? 答案在于薛定谔方程的解, 很容易验证:
  • \[\mid ψ (t_2) \rangle = \exp [ \frac{-iH (t_2 - t_1)}{\hbar} ] \mid ψ (t_1) \rangle = U(t_1, t_2) \mid ψ (t_1) \rangle\]
  • 其中定义 \(U(t_1, t_2) \equiv \exp [ \frac{-iH (t_2 - t_1)}{\hbar} ]\)
• 这个算子是酉的, 而且, 任意的酉算子 \(U\) 都可以写成 \(U = \exp(iK)\) 的形式, 其中 \(K\) 是某个厄米算子.
  • 因此, 在用酉算子的离散时间动力学描述和用哈密顿量的连续时间动力学描述之间存在一一对应关系.

演化 (酉) 算子可以表示为: 测量 (厄米) 算子的级数和? 然后, \(i\) 的存在引入某种对称性?

再一次, 科恩, 卷一, 第三章. 虽然本章节不如科恩, 但是两者都值得阅读, 形式上互有补益!

• 公设 3: 量子测量由一组测量算子 \(\{ M_m \}\) 描述. 这些算子作用在被测系统的状态空间上. 指标 \(m\) 表示在实验中可能出现的测量结果.
  • 如果在测量前量子系统的最新状态是 \(\mid ψ \rangle\), 那么测量结果是 \(m\) 的概率为
  • \[p(m) = \langle ψ \mid M_{m}^{\dagger} M_{m} \mid ψ \rangle\]
  • 并且测量之后系统的状态为 \(\frac{M_{m} \mid ψ \rangle} {\sqrt{\langle ψ \mid M_{m}^{\dagger} M_{m} \mid ψ \rangle}}\)

不同书籍的措辞和公式会有细微差异, 但本质上一回事. 个人会以科恩的量子力学作为标准. 同时, 个人觉得串联所有公设的核心是谱分解~

• 测量算子满足完备性方程:
  • \[\sum_{m} M_{m}^{\dagger} M_{m} = I\]
  • 完备性方程表达了概率加起来是 1 的事实:
  • \[1 = \sum_{m} p(m) = \sum_{m} \langle ψ \mid M_{m}^{\dagger} M_{m} \mid ψ \rangle\]
  • 这个方程对所有的 \(\mid ψ \rangle\) 都成立, 并且等价于完备性方程. 然而, 直接检验完备性方程要容易得多, 这也是它出现在公设叙述中的原因.

• 量子测量

• 投影测量: 一个投影测量由被观测系统状态空间上的一个可观测量 \(M\) 来描述, \(M\) 是一个厄米算子. 这个可观测量有谱分解
  • \[M = \sum_{m} m P_m\]
  • 其中 \(P_m\) 是到 \(M\) 的特征值为 \(m\) 的本征空间上的投影. 测量的可能结果对应于可观测量的特征值 \(m\).

简并 vs 非简并 (细节参看: 科恩)

• 当测量状态为 \(\mid ψ \rangle\) 时, 得到结果为 \(m\) 的概率是
  • \[p (m) = \langle ψ | P_m | ψ \rangle\]
  • 给定测量结果 \(m\), 测量后量子状态立即变成 \(\frac{P_m \mid ψ \rangle}{\sqrt{p(m)}}\)
  • 投影测量可以理解为公设 3 的特例.

区别: 测量的结果 (特征值) vs 测量后的态 (本征态)

区别: 测量算子 (组), 测量算子 (组) 的完备性, 可观测量 (算子) 的谱分解, 可观测量 (算子) 的投影 (算子). 翻译用词有点纠结, 不过也不影响理解~

关于: 投影测量 vs 测量公设 (公设 3). 本书先介绍测量公设, 再介绍投影测量. 相对的, 格里菲斯直接就是介绍投影测量. 当然, 科恩的介绍最是行云流水, 特别是, 卷一, Page 219. 在公式的形式上, 也最是优雅工整!

• 设公设 3 中的测量算子除了满足完备性关系 \(\sum_{m} M_{m}^{\dagger} M_{m} = I\), 也满足 \(M_m\) 是正交投影算子这个条件.
  • 即, \(M_m\) 是厄米的, 并且 \(M_m M_{m'} = δ_{m, m'} M_m\).
  • 有了这些附加的限制, 公设 3 就变成了刚刚定义的投影测量.

• 这里强调一下关于测量的两个广泛使用的说法.
  • 人们通常列一组满足关系 \(\sum_{m} P_m = I\) 和 \(P_m P_{m'} = δ_{mm'} P_m\) 的正交投影算子 \(P_m\) 而不是给出一个描述投影算子的可观测量. 这种做法的相应观测量为 \(M = \sum_{m} m P_m\).
  • 另外一个广泛使用的术语 “在基 \(\mid m \rangle\) 下测量”, 其中 \(\mid m \rangle\) 是一组标准正交基. 它仅仅是指在投影算子 \(P_m = \mid m \rangle \langle m \mid\) 下的投影测量.
• 假设在状态为 \(\mid ψ \rangle\) 的量子系统中执行由测量算子 \(M_m\) 描述的测量. 则得到结果 \(m\) 的概率由 \(p(m) = \langle ψ \mid M_{m}^{\dagger} M_{m} \mid ψ \rangle\) 给出.
  • 假设我们定义 \(E_m \equiv M_{m}^{\dagger} M_{m}\)
  • 根据公设 3 和初等线性代数, \(E_m\) 是一个满足 \(\sum_{m} E_m = I\) 和 \(p(m) = \langle ψ \mid E_m \mid ψ \rangle\) 的正算子.
  • 因此, 算子 \(E_m\) 的集合足以确定不同测量结果的概率.
  • 算子 \(E_m\) 被称为与测量相关联的 POVM 元素. 完整的集合 \(\{ E_m \}\) 称为一个 POVM.

POVM vs PVM, 类同于: 混合态 vs 纯态.

• 上面提到, POVM 算子是半正定的并且满足 \(\sum_{m} E_m = I\). 设 \(\{ E_m \}\) 是任意满足 \(\sum_{m} E_m = I\) 的正算子集合. 我们将证明存在一组测量算子 \(M_m\) 来定义由 POVM \(\{ E_m \}\) 描述的测量.
  • 定义 \(M_m \equiv \sqrt{E_m}\), 我们将看到 \(\sum_{m} M_{m}^{\dagger} M_{m} = \sum_{m} E_m = I\).
  • 因此集合 \(\{ M_m \}\) 描述了使用 POVM \(\{ E_m \}\) 的测量.
• 由于这个原因, 将 POVM 定义为满足如下条件的算子集合 \(\{ E_m \}\) 是很方便的:
  • (a) 每个算子 \(E_m\) 都是半正定的;
  • (b) 满足完备性关系 \(\sum_{m} E_m = I\), 它表达了概率和为 1 的事实.
  • 为了完成 POVM 的描述, 我们再次注意到, 给定 POVM \(\{ E_m \}\), 得到结果 \(m\) 的概率为 \(p(m) = \langle ψ \mid E_m \mid ψ \rangle\).

投影测量, 属于第一部分 (本文) 重点之一 (1/3)!

相对相位因子与全局相位因子的区别在于, 相对相位的相位因子可能因振幅而异.
这就使得相对相位不同于全局相位, 它是依赖基的选择的. 因此, 在某个基下,
仅相对相位不同的状态会在测量统计中产生物理上可观测的差异,
而不能像我们对仅差全局相位因子状态那样把这些态视为物理等价.

• 公设 4: 复合量子系统的状态空间是分量子系统的状态空间的张量积. 此外, 如果系统编号为 1 到 n, 且系统 i 的状态被制备为 \(\mid ψ_i \rangle\), 则整个系统的联合状态是 \(\mid ψ_1 \rangle \otimes \mid ψ_2 \rangle \otimes ... \otimes \mid ψ_n \rangle\).
  • 在文献中会遇到各种不同的复合系统符号. 这种多样化的部分原因是, 不同的符号更适合于不同的应用, 并且有时引入一些专门的符号是很方便的.
  • 在上下文不明确时, 可以用一个下标符号表示不同系统上的状态和运算符. 例如, 在包含三个量子比特的系统中, 用 \(X_2\) 表示作用在第二个量子比特上的泡利算子 \(σ_x\).

注: 原文状态被准备为, 改为了状态被制备为.

复合量子系统, 原文复合物理系统; 分量子系统, 原文分物理系统.

公设 1 通过指定如何描述一个孤立量子系统的状态来设定量子力学的研究范畴.
公设 2 告诉我们封闭量子系统的动态演化是由薛定谔方程, 也就是酉演化来描述.
公设 3 告诉我们如何通过规定测量的描述从量子系统中提取信息.
公设 4 告诉我们如何把不同量子系统的状态空间相结合来描述复合系统.

应用: 超密编码

• 超密编码

密度算子

我们用状态向量的语言建立了量子力学,
另外一种描述是使用称为密度算子或密度矩阵的工具.
这个替代方案与状态向量方法在数学上是等价的,
但它在量子力学中的一些常见的场景下提供了一种更方便的语言.

• 密度算子语言为描述状态不完全已知的量子系统提供了一种方便的方法. 更准确地说, 假设一个量子系统以概率 \(p_i\) 处于多个状态 \(\mid ψ_i \rangle\) 之一, 其中 \(i\) 是一个指标, 我们将把 \(\{ p_i, \mid ψ_i \rangle \}\) 称为一个纯态系综.
  • 系统的密度算子定义为
  • \[ρ \equiv \sum_{i} p_i \mid ψ_i \rangle \langle ψ_i \mid\]
  • 密度算子通常称为密度矩阵, 我们将交替使用这两个术语.
  • 事实证明, 量子力学的所有公设都可以用密度算子的语言来重新表述.
• 然而在此之前, 再引入一些语言和一个关于密度算子的事实对我们是有帮助的. 首先是语言. 量子系统具有精确已知状态 \(\mid ψ \rangle\) 称为处于纯态. 这种情况下, 密度算子就是 \(ρ = \mid ψ \rangle \langle ψ \mid\). 否则, \(ρ\) 处于混合态, 它是指处于 \(ρ\) 的系综中不同纯态的混合.
• 判断状态是纯态还是混合态的一个简单判据: 纯态满足 \(tr(ρ^2) = 1\), 而混合态满足 \(tr(ρ^2) < 1\).
  • 关于这些名词要注意的是: 有时人们用术语混合态统称纯态和混合量子态. 这种用法的起源似乎蕴含着作者不必假设状态是纯的.
  • 另外, 术语纯态常用于指状态向量 \(\mid ψ \rangle\), 以区别于密度算子 \(ρ\).

关于: 纯态满足 \(tr(ρ^2) = 1\). 其实可以拆解为两部分: \(ρ^2 = ρ\) 和 \(Tr(ρ) = 1\).

• 最后, 设想量子状态以概率 \(p_i\) 处于状态 \(ρ_i\). 不难发现系统可以用密度矩阵 \(\sum_{i} p_i ρ_i\) 来描述. 关于这一点的证明如下:
  • 设 \(ρ_i\) 来自某个纯态的系综 \(\{ p_{ij}, \mid ψ_{ij} \rangle \}\) (注意 \(i\) 是固定的), 于是处于状态 \(\mid ψ_{ij} \rangle\) 的概率是 \(p_i p_{ij}\), 因此系统的密度矩阵是
  • \[\begin{align} ρ & = \sum_{i, j} p_i p_{ij} \mid ψ_{ij} \rangle \langle ψ_{ij} \mid \\ & = \sum_{i} p_i ρ_i \end{align}\]
  • 其中用了定义 \(ρ_i = \sum_{j} p_{ij} \mid ψ_{ij} \rangle \langle ψ_{ij} \mid\), 称 \(ρ\) 为具有概率 \(p_i\) 的状态 \(ρ_i\) 的混合.
  • 这个混合的概念在如量子噪声问题的分析中反复出现, 其中噪声的影响为我们对量子状态的认识引入了不确定性.

• (密度算子的特征) 算子 \(ρ\) 是与某个系综 \(\{ p_i, \mid ψ_i \rangle \}\) 相关的密度算子, 当且仅当它满足下列条件:
  • (迹条件) \(ρ\) 的迹等于 \(1\);
  • (半正定条件) \(ρ\) 是一个半正定算子.
• 反过来, 设 \(ρ\) 是满足迹和半正定条件的任意算子. 由于 \(ρ\) 是半正定的, 它一定有谱分解
  • \[ρ = \sum_{j} λ_j \mid j \rangle \langle j \mid\]
  • 其中向量组 \(\mid j \rangle\) 是正交的, 而 \(λ_j\) 是实数, 为 \(ρ\) 的非负特征值.
  • 从迹条件可知 \(\sum_{j} λ_j = 1\). 因此, 一个以概率 \(λ_j\) 处于状态 \(\mid j \rangle\) 的系统将具有密度算子 \(ρ\), 即系综 \(\{ λ_j, \mid j \rangle \}\) 是产生密度算子 \(ρ\) 的状态组的一个系综.
• 这个定理提供了密度算子本身固有的一个刻画: 我们可以定义一个密度算子为迹等于 \(1\) 的半正定算子 \(ρ\).
  • 这个定义允许我们在密度算子图景中重新表述量子力学的公设.

原文图画, 改为了图景

为了便于参考, 我们在此给出所有重新表述的公设:

• 公设 1: 任意孤立量子系统与该系统的状态空间相关联, 它是一个带内积的复向量空间 (即希尔伯特空间). 系统由作用在状态空间上的密度算子完全描述, 这是一个迹为 \(1\) 的半正定算子 \(ρ\).
  • 如果量子系统以概率 \(p_i\) 处于状态 \(ρ_i\), 则系统的密度算子为 \(\sum_{i} p_i ρ_i\).

任意孤立量子系统: 原文任意孤立物理系统

• 公设 2: 封闭量子系统的演化由一个酉变换描述, 即系统在时刻 \(t_1\) 的状态 \(ρ\) 和时刻 \(t_2\) 的状态 \(ρ'\) 由一个仅依赖于时间 \(t_1\) 和 \(t_2\) 的酉算子 \(U\) 联系:
  • \[ρ' = U ρ U^{\dagger}\]
• 公设 3: 量子测量由一组测量算子 \(\{ M_m \}\) 描述, 这些算子作用在被测系统的状态空间上, 指标 \(m\) 指实验中可能出现的测量结果.
  • 如果量子系统在测量前的最后状态是 \(ρ\), 则得到结果 \(m\) 的概率由
  • \[p (m) = tr( M_m^{\dagger} M_m ρ)\]
  • 给出, 并且测量后的系统状态为
  • \[\frac{M_m ρ M_m^{\dagger}}{tr(M_m^{\dagger} M_m ρ)}\]
  • 测量算子满足完备性方程:
  • \[\sum_{m} M_m^{\dagger} M_m = I\]
• 公设 4: 复合量子系统的状态空间是分量子系统状态空间的张量积. 而且, 如果有系统 1 到 n, 其中系统 i 处于状态 \(ρ_i\), 则全系统的联合状态是 \(ρ_1 \otimes ρ_2 \otimes ... \otimes ρ_n\).

复合量子系统, 原文复合物理系统; 分量子系统, 原文分物理系统.

当然, 这些量子力学基本公设用密度算子做的重新表述,
在数学上与用状态向量做的描述是等价的.

然而, 作为一种认识量子力学的方式, 密度算子方法确实有两个应用较为突出:
对状态未知的量子系统的描述, 和对复合系统的子系统的描述.

一般地,
密度矩阵的特征向量和特征值仅表示可能产生一个特定密度矩阵的许多系综中的一个,
没有理由表明哪个系统是特殊的.

• 为了方便给出答案, 我们使用未归一化到单位长度的向量 \(\mid \tilde{ψ}_i \rangle\). 设集合 \(\{ \mid \tilde{ψ}_i \rangle \}\) 生成算子 \(ρ ≡ \sum_{i} \mid \tilde{ψ}_i \rangle \langle \tilde{ψ}_i \mid\), 于是, 与普通的密度算子系综的关联由式子 \(\mid \tilde{ψ}_i \rangle = \sqrt{p_i} \mid {ψ}_i \rangle\) 表示.
  • 两组向量 \(\mid \tilde{ψ}_i \rangle\) 和 \(\mid \tilde{φ}_j \rangle\) 何时生成同一算子 \(ρ\)?
• 定理 (密度矩阵系综中的酉自由度) 向量组 \(\mid \tilde{ψ}_i \rangle\) 和 \(\mid \tilde{φ}_j \rangle\) 生成相同的密度矩阵, 当且仅当
  • \[\mid \tilde{ψ}_i \rangle = \sum_{j} u_{ij} \mid \tilde{φ}_j \rangle\]
  • 其中 \(u_{ij}\) 是一个带指标 \(i\) 和 \(j\) 的复酉矩阵, 并且我们在向量集合 \(\mid \tilde{ψ}_i \rangle\) 和 \(\mid \tilde{φ}_j \rangle\) 中向量较少的一个里面补充若干 0 向量, 以使两个集合的向量个数相等.
• 作为这个定理的一个结论, 注意到 \(ρ = \sum_{i} p_i \mid {ψ}_i \rangle \langle {ψ}_i \mid = \sum_{j} q_j \mid {φ}_j \rangle \langle {φ}_j \mid\) 对归一化状态集 \(\mid {ψ}_i \rangle\), \(\mid {φ}_j \rangle\) 与概率分布 \(p_i\) 和 \(q_j\) 成立, 当且仅当
  • \[\sqrt{p_i} \mid {ψ}_i \rangle = \sum_{j} u_{ij} \sqrt{q_j} \mid {φ}_j \rangle\]
  • 对于某个酉矩阵 \(u_{ij}\) 成立, 其中我们可能要向较小的系综增加零概率的项以使两个系综有相同的大小.
  • 因此, 定理刻画了产生一个给定的密度矩阵 \(ρ\) 的系综 \(\{ p_i, \mid {ψ}_i \rangle \}\) 所包含的自由度.

密度算子, 属于第一部分 (本文) 重点之二 (2/3)!

Bloch vector

• 假设有物理系统 \(A\) 和 \(B\), 其状态由密度算子 \(ρ^{AB}\) 描述. 对于系统 \(A\), 约化密度算子定义为
  • \[ρ^A ≡ tr_B (ρ^{AB})\]
  • 其中 \(tr_B\) 是一个算子映射, 称为在系统 \(B\) 上的偏迹.
• 偏迹定义为
  • \[tr_B ( \mid a_1 \rangle \langle a_2 \mid \otimes \mid b_1 \rangle \langle b_2 \mid ) ≡ \mid a_1 \rangle \langle a_2 \mid tr(\mid b_1 \rangle \langle b_2 \mid)\]
  • 其中 \(\mid a_1 \rangle\) 和 \(\mid a_2 \rangle\) 是状态空间 \(A\) 中的任意向量, \(\mid b_1 \rangle\) 和 \(\mid b_2 \rangle\) 是状态空间 \(B\) 中的任意向量.
  • 等式右边的迹运算是系统 \(B\) 上的普通迹运算, 因此 \(tr(\mid b_1 \rangle \langle b_2 \mid) = \langle b_2 \mid b_1 \rangle\).
  • 我们仅在 \(AB\) 的一个特殊的算子类上定义了偏迹运算, 为完成偏迹的定义, 需要附加偏迹对输入是线性算子的要求.

一个系统的联合状态可以被完全知道,
而某个子系统却处于混合态,
这是量子纠缠的另一个特征.

原书例题用到一个公式, 但貌似并未特别说明过: \(\mid φ χ \rangle \langle φ χ \mid = \mid φ \rangle \langle φ \mid \otimes \mid χ \rangle \langle χ \mid\)

施密特分解与纯化

• 定理 (施密特分解) 设 \(\mid ψ \rangle\) 是复合系统 \(AB\) 的一个纯态, 则存在系统 \(A\) 的标准正交基 \(\mid i_A \rangle\) 和系统 \(B\) 的标准正交基 \(\mid i_B \rangle\), 使得
  • \[\mid ψ \rangle = \sum_{i} λ_i \mid i_A \rangle \mid i_B \rangle\]
  • 其中 \(λ_i\) 是满足 \(\sum_{i} λ_i^2 = 1\) 的非负实数, 称为施密特系数.
• 这个结果非常有用. 为了解其用途, 请考虑以下结论:
  • 令 \(\mid ψ \rangle\) 为复合系统 \(AB\) 的纯态, 然后通过施密特分解得到 \(ρ^A = \sum_{i} λ_i^2 \mid i_A \rangle \langle i_A \mid\) 和 \(ρ^B = \sum_{i} λ_i^2 \mid i_B \rangle \langle i_B \mid\), 因此, \(ρ^A\) 和 \(ρ^B\) 的特征值是相同的, 即对于这两种密度算子的特征值均为 \(λ_i^2\).
  • 量子系统的许多重要性质完全由系统的约化密度算子的本征值决定, 所以对于复合系统的纯态, 两个系统的这些性质将相同.

施密特分解与纯化, 属于第一部分 (本文) 重点之二 (3/3)!

• 基 \(\mid i_A \rangle\) 和 \(\mid i_B \rangle\) 分别称为 \(A\) 和 \(B\) 的施密特基, 并且非零 \(λ_i\) 的个数称为态 \(\mid ψ \rangle\) 的施密特数. 施密特数是复合量子系统的一个重要性质, 它在某种意义上量化了系统 \(A\) 和 \(B\) 之间的纠缠量.
  • 为了解这个概念, 请考虑以下明显但重要的性质: 施密特数在系统 \(A\) 或 \(B\) 的单独酉变换下保持不变.
  • 为看清这一点, 注意到如果 \(\sum_{i} λ_i \mid i_A \rangle \mid i_B \rangle\) 是 \(\mid ψ \rangle\) 的施密特分解, 那么 \(\sum_{i} λ_i (U \mid i_A \rangle) \mid i_B \rangle\) 是 \(U \mid ψ \rangle\) 的施密特分解, 其中 \(U\) 是单独作用在系统 \(A\) 上的酉算子. 这种代数不变性使施密特数成为一个非常有用的工具.

• 第二项与量子计算和量子信息相关的技术是纯化. 假设给定量子系统 \(A\) 的状态 \(ρ^A\), 我们可以引入另一个系统 \(R\), 定义联合系统 \(AR\) 上的纯态 \(\mid AR \rangle\), 使得 \(ρ^A = tr_{R} (\mid AR \rangle \langle AR \mid)\).
  • 也就是说, 当我们单独看系统 \(A\) 时, 纯态 \(\mid AR \rangle\) 约化为 \(ρ^A\).
  • 这是一个纯粹的数学过程, 称为纯化, 它允许我们将纯态和混合态联系起来. 因此, 我们称系统 \(R\) 为参考系统: 它是一个虚构的系统, 没有直接的物理意义.
• 为了证明任何状态都可以进行纯化, 我们解释了如何为 \(ρ^A\) 构造一个系统 \(R\) 和纯化 \(\mid AR \rangle\). 假设 \(ρ^A\) 有标准正交分解 \(ρ^A = \sum_{i} p_i \mid i^A \rangle \langle i^A \mid\).
  • 为对 \(ρ^A\) 进行纯化, 我们引入和系统 \(A\) 有相同维数且有标准正交基 \(\mid i^R \rangle\) 的系统 \(R\), 并且为复合系统定义纯态
  • \[\mid AR \rangle \equiv \sum_{i} \sqrt{p_i} \mid i^A \rangle \mid i^R \rangle\]
• 我们现在计算系统 \(A\) 对应于状态 \(\mid AR \rangle\) 的约化密度算子:
  • \[\begin{align} tr_{R} (\mid AR \rangle \langle AR \mid) & = \sum_{ij} \sqrt{p_i p_j} \mid i^A \rangle \langle j^A \mid tr(\mid i^R \rangle \langle j^R \mid) \\ & = \sum_{ij} \sqrt{p_i p_j} \mid i^A \rangle \langle j^A \mid δ_{ij} \\ & = \sum_{i} p_i \mid i^A \rangle \langle i^A \mid \\ & = ρ^A \end{align}\]
  • 因此 \(\mid AR \rangle\) 是 \(ρ^A\) 的纯化.
• 注意施密特分解与纯化的密切关系: 纯化一个系统 \(A\) 的混合态所用的过程是定义一个纯态, 它相对系统 \(A\) 的施密特基恰好将混合态对角化, 施密特系数是被纯化的密度算子的特征值的平方根.

EPR 和贝尔不等式

• EPR

• 贝尔不等式

• 物理性质 \(P_Q\), \(P_R\), \(P_S\), \(P_T\) 有与观测无关的值 \(Q\), \(R\), \(S\), \(T\) 的假设.
  • 这有时被称为实在性假设.
• Alice 在做她的测量并不影响 Bob 的测量结果的假设.
  • 这有时被称为定域性假设.
• 这两个假设合称为定域实在性假设. 当然直观上, 它们是关于世界如何运行的合理的假设, 并且符合我们的日常经验.
  • 但是贝尔不等式表明, 这些假设中至少有一个是不正确的.

定域实在性: 只有两者兼备才有意义, 所以, 别提了~

计算机科学简介

标题不好, 可以改为: 计算理论简介.

令人惊讶的是, 事实证明, 只要人们能够使计算可逆,
执行计算所需的能量消耗可以几乎为零.

计算模型

图灵机的讲述, 简单清晰~

除了其固有的价值之外, 不可判断性预示着计算机科学,
以及量子计算和量子信息中一个备受关注的话题:
易于解决的问题与难以解决的问题之间的区别.
不可判定性提供了难以解决的问题的终极例子 --
它们是如此之难, 以至于实际上不可能解决.

这一部分的相关内容, 更推荐阅读: 量子计算公开课.

• 通用图灵机
• 电路复杂性

直观上, 一致电路族是可以由某个合理的算法生成的电路族.
可以证明, 一致电路族可计算的函数类与图灵机可计算的函数类完全相同.
由于这种一致性的限制,
图灵机计算模型中的结论通常可以直接翻译为电路计算模型的结论, 反之亦然.
之后我们对量子电路计算模型中的一致性问题给予了类似的关注.

计算问题的分析

• 强丘奇-图灵论题: 任何计算模型都可以在概率型图灵机上进行模拟, 且最多只需要增加多项式量级的基本运算次数.

当然, 对量子计算机感兴趣的主要原因之一是,
他们通过高效求解一个被认为在所有经典计算机上
(包括概率型图灵机) 难解的问题,
对强丘奇-图灵论题提出了质疑!
尽管如此, 理解和欣赏强丘奇-图灵论题,
在寻找独立于模型之外的计算复杂性理论中所扮演的角色仍然是有用的.

由于两个原因让量子计算和量子信息的研究人员对 NPI 中的问题很感兴趣.
首先, 人们希望找到快速量子算法来解决不在 P 中的问题.
其次, 许多人怀疑量子计算机不能有效地解决 NP 中的所有问题,
特别是 NP 完全问题.
因此, 关注 NPI 类是一件很自然的事情.
实际上, 已经发现了一种用于整数素因子分解的快速量子算法,
这促使人们寻找快速量子算法来解决其他疑似在 NPI 中的问题.

• BPP 复杂度
  • BQP 复杂度
  • 切诺夫界

不幸的是, 目前还不知道 PSPACE 是否包含不在 P 中的问题!
这是一个非常值得注意的现状 --
很显然拥有无限时间和多项式空间资源的图灵机应该比仅具有多项式时间的机器更强大.
然而, 尽管人们付出了相当大的努力, 这一点从未被证明.

稍后我们将看到, 在量子计算机上多项式时间内可解的问题类是 PSPACE 的一个子集,
因此证明在量子计算机上有效解决的问题在经典计算机上无法有效解决将证明 P ≠ PSPACE,
从而解决了计算机科学的一个重大悬而未决的问题.

从乐观的角度来说, 量子计算的思想可能有助于证明 P ≠ PSPACE.
悲观地说, 人们可能会得出结论,
要想严格证明量子计算机可以用来有效地解决在经典计算机上难以解决的问题还需要很长的时间.
更悲观的是, 有可能 P = PSPACE, 在这种情况下量子计算机相比经典计算机没有任何优势!
然而, 极少 (如果有的话) 计算复杂性专家认为 P = PSPACE.

• 给更多的时间和空间会增强计算能力吗? 对每种情形答案都是肯定的.
  • 严格来说, 时间层次定理表明 \(TIME(f(n))\) 是 \(TIME(f(n) \log^2 (f(n)))\) 的真子集.
  • 类似的, 空间层次定理表明 \(SPACE(f(n))\) 是 \(SPACE(f(n) \log(f(n)))\) 的真子集.
  • 这里 \(SPACE(f(n))\) 是指包含所有可以用 \(O(f(n))\) 空间来判定的语言的复杂性类.
  • 层次定理在复杂性类的等价性类方面有很多有趣的应用.
• 我们知道 \(L \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP\)
  • 不幸的是, 尽管每个包含关系都被相信是严格的, 但没有一个能被证明.
  • 不过, 时间层次定理指出 P 是 EXP 的严格真子集, 空间层次定理指出 L 被 PSPACE 严格包含!
  • 故我们可以得出结论, 式中至少存在一个严格包含关系, 虽然我们不知道是哪一个.
• 时间层次定理
• 空间层次定理

• 兰道尔原理 (第一种形式): 假设一台计算机擦除了 1 比特的信息, 那么耗散到整个环境中的能量至少是 \(k_B T \ln 2\), 其中 \(k_B\) 是玻尔兹曼常数, \(T\) 是电脑工作环境的温度.
• 兰道尔原理 (第二种形式): 假设一台计算机擦除了 1 比特的信息, 那么整个环境的熵至少增加了 \(k_B \ln 2\), 其中 \(k_B\) 是玻尔兹曼常数.

如果所有计算都可以可逆地完成,
则兰道尔原理意味着计算机消耗的能量没有下限,
因为在可逆计算期间根本不会擦除任何比特.
当然, 某些其他物理原理可能规定在计算过程中耗散能量;
幸运的是, 事实并非如此.

但是有可能在不删除任何信息的情况下执行通用计算吗?

物理学家可以在这个问题上作弊,
预先直接看到这个问题的答案必然是肯定的,
因为我们目前对物理定律的理解是它们从根本上是可逆的.
也就是说, 如果我们知道闭合物理系统的最终状态,
那么物理定律会使我们可以计算出系统的初始状态.

如果我们认为这些定律是正确的, 那么我们必能得出结论:
在像与门和或门这样的不可逆逻辑门中, 必然隐藏着一些潜在的可逆计算性.
但这隐藏的可逆性在哪里, 我们可以用它来构建显式的可逆计算机吗?

• Fredkin gate
• Toffoli gate

• 我们可以从可逆计算的研究中得出什么结论? 有三个关键的想法.
  • 首先, 可逆性源于保持追踪每一比特的信息; 只有在信息丢失或删除时才会发生不可逆的结果.
  • 其次, 通过可逆地进行计算, 我们消除了计算期间的能量消耗. 原则上, 所有计算都可以用零能耗完成.
  • 第三, 可以有效地完成可逆计算, 而不产生其值取决于计算输入的无用比特. 也就是说, 如果存在计算函数 \(f\) 的不可逆电路, 则通过具有功能 \((x, y) \to (x, y \oplus f(x))\) 的可逆电路能够有效地模拟该电路.

这些结果对物理学, 计算机科学以及量子计算和量子信息的影响是什么?
从一位关心散热性的物理学家或硬件工程师的角度来看,
好消息是, 原则上可以通过使计算可逆而使其无能量消耗,
尽管实际上维持系统的稳定性需要耗散能量以免受噪声干扰.

在更为基础的层面上,
可逆计算的思想也导致了基础物理学中一个有着百年历史的问题的解决,
这就是著名的麦克斯韦妖问题.
从计算机科学家的角度来看, 可逆计算验证了计算模型中不可逆元素的作用,
例如图灵机 (因为是否使用它们所得到的模型是多项式等价的).

此外, 由于物理世界从根本上是可逆的, 人们可以争辩说,
基于可逆计算模型的复杂性类比基于不可逆模型的复杂性类更自然,
从量子计算和量子信息的角度来看, 可逆计算非常重要.
为了利用量子计算的全部功能,
量子计算中的任何经典子程序必须可逆地执行,
而且不能产生依赖于经典输入的冗余比特.

关于计算科学的观点

对麦克斯韦妖悖论的解决基于如下事实, 为了确定分子的速度,
恶魔必须对在两个分区之间移动的分子进行测量.
测量结果必须存储在恶魔的存储器中, 而任何存储都是有限的,
恶魔最终必须开始从其存储中擦除信息, 以便为新的测量结果留出空间.

根据兰道尔的理论, 这种擦除信息的行为增加了
恶魔 -- 气缸 -- 环境
这一组合系统的总熵.

事实上, 一个完整的分析表明, 根据兰道尔原理,
组合系统因这种擦除信息的行为所增加的熵,
不少于组合系统因恶魔的行为而减少的熵,
从而确保了整个系统遵循热力学第二定律.

这一章真希望 Scott Aaronson 能够出一本专著

• 作者推荐的一些资料
  • Karp’s 21 NP-complete problems
  • 结构复杂性理论
  • 兰道尔原理

结: 2024 年 6 月