Quantum Computing for Computer Scientists

面向计算机科学家的量子计算 本次讲座摒弃了深奥的物理学隐喻，而是借助状态机、基向量以及可逆酉矩阵，为量子计算构建了严谨的理论基础。在从数学角度阐明量子比特、叠加态以及量子门的工作机制后，演讲者详细阐述了多伊奇（Deutsch）预言机问题如何通过相位反冲与干涉仅凭单次查询实现量子加速。讲座进一步延伸至多量子比特纠缠、贝尔定理以及量子隐形传态的机理，同时解释了纠错扩展所面临的瓶颈。最后，讲座以Q#端到端运行多伊奇算法的演示收尾，并展示了来自IBM物理稀释制冷机处理器的实测数据。 量子计算是通过线性代数进行形式化建模的，它将量子比特建模为归一化的二维状态向量，其叠加态可通过可逆酉门进行变换。 (4:23) 多伊奇预言机问题为量子加速提供了基础证明，经典计算需要两次查询，而该算法仅需单次查询即可评估黑盒函数是常数还是变量。 (33:09) 量子纠缠允许超光速的瞬时非局域协同，而贝尔定理和因果律则确保超光速通信在严格意义上仍是不可能的。 (61:45) 实际的容错需要大量的硬件冗余，据估计构建单个可靠、经过纠错的逻辑量子比特需要100到200个物理量子比特。 (74:45)

Presenting quantum computing through the lens of theoretical computer science rather than physics, the speaker frames quantum machines as linear-algebraic state machines governed by reversible operations. Under this framework, quantum algorithms achieve computational advantages through superposition and phase interference, though their physical realization remains constrained by hardware noise and substantial error-correction overhead. State Machine Foundations and Reversible Logic (4:23) Classical digital logic maps directly to two-dimensional basis vectors, where state 0 is represented as [1, 0]ᵀ and state 1 as [0, 1]ᵀ. Qubits generalize these basis states into column vectors [a, b]ᵀ subject to the normalization constraint a² + b² = 1, representing probability amplitudes that collapse upon measurement. Multi-qubit systems scale exponentially through the tensor product, requiring a 2ⁿ-dimensional vector to describe an n-qubit register. Single-qubit transformations can be visualized geometrically as rotations and reflections along the unit circle, where classical basis states sit at coordinates (1, 0) and (0, 1). Unlike conventional computing, quantum operations must be strictly unitary, reversible, and self-inverting. Irreversible classical operations like bit erasure overwrite data and dissipate energy at or above the theoretical thermodynamic Landauer limit. Quantum circuits preserve state information through invertible matrices such as the Hadamard gate, which creates uniform superpositions, and the Controlled-NOT (CNOT) gate, which flips a target qubit conditionally without altering the control qubit in classical settings. Algorithmic Speedups Through Phase Kickback (33:09) The speaker uses the Deutsch oracle problem—classifying an unknown single-bit function as constant or variable (balanced)—to demonstrate a concrete quantum speedup. While a classical deterministic algorithm strictly requires two queries to evaluate both inputs, the quantum Deutsch algorithm resolves the function type in a single query. Because constant functions map distinct inputs to identical outputs, quantum implementations must introduce an auxiliary ancilla wire to preserve information and maintain physical reversibility. Rather than evaluating all inputs simultaneously in parallel, the algorithm relies on quantum interference. By preparing both the input and ancilla qubits in superposition using Hadamard gates, the CNOT gate causes a counterintuitive 'phase kickback' where the control qubit flips phase while the target qubit remains unchanged. This phase distinction allows a final Hadamard transformation to deterministically output |01⟩ for variable functions and |11⟩ for constant functions. The speaker notes that this foundational concept generalized into the Deutsch–Jozsa algorithm and inspired Peter Shor's algorithm for polynomial-time integer factorization. Entanglement Mechanics and the No-Cloning Theorem (57:57) Entanglement occurs when a composite multi-qubit state vector cannot be mathematically factored back into isolated, individual qubit tensor products. In the Bell state [1/√2, 0, 0, 1/√2]ᵀ—synthesized using only a Hadamard gate followed by a CNOT gate—measuring one qubit instantaneously collapses the second qubit across arbitrary distances. Citing John Bell's theorem, the speaker emphasizes that this behavior cannot be explained by pre-coordinated local hidden variables; quantum particles exist in genuine superpositions until observed. The speaker stresses a strict distinction between physical coordination and communication: entangled collapses cannot transmit arbitrary messages faster than light, leaving relativistic causality intact. Furthermore, the no-cloning theorem proves that unknown quantum states cannot be duplicated. Quantum teleportation circumvents this by transferring a state destructively—effectively cutting and pasting rather than copying—which requires transmitting two classical bits over conventional channels at sub-luminal speeds to complete the state reconstruction. Decoherence Barriers and Physical Overhead (74:45) Simulating an N-qubit quantum system on a classical computer requires tracking 2ᴺ complex amplitudes, creating an exponential memory bottleneck. In physical systems, however, quantum states are exceptionally fragile and vulnerable to environmental noise. While theoretical error-correction models establish a minimum of five physical qubits per fault-tolerant logical qubit, the speaker notes that practical implementations are estimated to require between 100 and 200 physical qubits for each stable logical qubit. During a cloud execution on IBM's five-qubit processor, the speaker demonstrated entanglement by reading out dominant |00⟩ and |11⟩ measurement distributions alongside residual error states caused by thermal noise and imperfect gate fidelity. Highlighting skepticism from mathematician Gil Kalai, the speaker notes the unresolved theoretical concern that environmental noise might compound exponentially with register size, potentially preventing physical quantum systems from scaling into practical computational supremacy. The presentation demystifies quantum computing by treating it as an accessible extension of linear algebra and state-machine theory rather than an incomprehensible physical paradox. Nonetheless, the speaker cautions that whether gate-model quantum computers can successfully overcome exponential noise scaling and error-correction overheads to outperform modern classical optimization remains an unresolved question facing the industry.

微软研究院在本次讲座中指出，计算机科学家无需深究物理细节，仅凭线性代数与状态机模型即可理解量子计算；其计算优势源于相干态干涉、相位回冲与可逆逻辑，而非对所有数值的并行穷举。 基于线性代数的状态机与可逆计算约束 (4:23) 量子计算在门模型下可以被形式化为经典计算在线性代数框架下的拓展。经典比特被映射为二维基向量（0 对应 $[1, 0]^T$，1 对应 $[0, 1]^T$），单比特操作对应矩阵乘法。量子计算要求所有逻辑操作必须完全可逆且自逆（即满足 $A \cdot A = I$），这排除了如常数-0 或常数-1 这种会抹除状态信息的不可逆操作。演讲者引用兰道尔极限（Landauer limit）指出，不可逆操作会伴随能量耗散，而可逆计算在理论上具有规避热力学耗散下限的潜力。 量子比特（qubit）则泛化为满足归一化条件 $a^2 + b^2 = 1$ 的向量 $[a, b]^T$。当比特处于叠加态时，其概率幅平方对应测量坍缩至对应经典基态的概率。对于多比特系统，系统状态由各子空间经张量积（$\otimes$）构成，$n$ 个量子比特的系统状态向量维度呈指数级扩张至 $2^n$。在此模型中，CNOT 门作为受控翻转的基本可逆构建块，展现了与经典可逆逻辑相似但更丰富的代数特性。 相位回冲与多项式加速的核心机制 (33:09) 公众常误以为量子计算机能够“同时计算所有数值”，演讲者强调这一观点存在偏差：任何测量行为都会使量子态瞬间坍缩为单一经典值，仅凭一次测量无法提取超过单比特的信息熵。量子算法的核心优势在于利用幺正变换（如阿达马门 $H$）建立均等叠加态，通过量子相位差异（例如 $1/\sqrt{2}$ 与 $-1/\sqrt{2}$ 虽概率均为 50%，但在量子内部具有不同相位）引起干涉，最终实现确定性输出。 在戴奇神谕（Deutsch oracle）问题中，算法需判断黑盒函数属于常数函数还是平衡函数。由于量子黑盒必须维持幺正性与可逆性，系统引入了辅助比特线构成双比特架构。当辅助比特被初始化为 $|-\rangle$ 态时，执行恒等函数的 CNOT 门会引发“相位回冲”（Phase Kickback），反向改变控制比特的相位，使得整个函数类型的判断仅需单次查询即可完成，而经典计算则严格需要两次查询。这一机制经由 Simon 周期性问题延伸，奠定了肖尔算法（Shor's algorithm）在多项式时间内分解大整数的基础。 纠缠的代数本质与量子通信边界 (57:57) 在多比特系统中，当复合态向量无法因式分解为单比特张量积时，系统即处于量子纠缠态（如贝尔态 $[1/\sqrt{2}, 0, 0, 1/\sqrt{2}]^T$）。演讲者通过代数矛盾证明了该状态的不可拆分性。在物理实现上，仅需将一个处于叠加态的比特作为控制端、连同基态比特输入 CNOT 门即可制备纠缠对。根据贝尔定理，隐变量理论已被推翻，纠缠粒子并非事先约定好测量结果，而是在被测瞬间发生全系统坍缩。 演讲者特别厘清了超光速协调与超光速通信的界限：纠缠虽然展现出瞬时关联，但无法单独用来传递任何预定的信息或打破因果律。根据不可克隆定理，未知量子态不能被直接复制，仅能被“剪切并粘贴”。在量子隐形传态协议中，发送方必须通过经典信道传输 2 个经典比特协助接收方完成旋转校正，因此信息传递的速度仍受光速严格限制。 指数噪声瓶颈与工程实现的现实挑战 (74:45) 经典计算机在模拟量子计算机时面临指数级内存瓶颈，原因在于无法将纠缠态拆解为独立分量，必须全程维护规模为 $2^N$ 的复数概率幅。然而在物理构建层面，量子系统极度脆弱，外界微弱扰动即可引发退相干。演讲者指出，理论上构建一个容错逻辑量子比特至少需要 5 个物理比特，而在实际工程中预计需要 100 至 200 个物理比特进行冗余纠错；因此业界宣称的数十个无纠错物理比特并不能直接转化为有效算力。 讲座引述了数学家吉尔·卡莱（Gil Kalai）的怀疑论观点：环境噪声和错误率可能随纠缠规模呈指数级增长，使物理可扩展的量子计算机在理论上不可行。在 IBM 5 比特量子云平台的实时测试中，尽管纠缠态实验数据在 $|00\rangle$ 与 $|11\rangle$ 呈现显著峰值，但依然存在因门保真度缺陷与热噪声引起的错误读数。量子计算是否能够跨越这一潜在的指数级噪声壁垒，仍是未来工程实践必须面对的根本考验。 量子计算的核心逻辑能够完全建立在严谨的线性代数与可逆逻辑门体系之上，为理解复杂量子算法提供了清晰路径。然而，其实用化前景依然受制于高昂的量子纠错开销以及不可避免的环境噪声扩展挑战，物理可扩展量子机能否最终实现仍是一个待解的重大命题。

## Background 本内容由微软研究院（Microsoft Research）于 2018 年 5 月 14 日发布在 YouTube 平台上。视频简介表明，本场讲座旨在摒弃模糊的科普隐喻，纯粹从计算机科学与初等线性代数的视角，深入剖析量子比特、叠加态、量子逻辑门以及量子计算机超越经典计算的核心机制，并包含多伊奇神谕问题的 Q# 实现与真实量子计算机的纠缠实验演示。 ## TL;DR 讲座首先以状态机和矩阵向量乘法为切入点，将经典比特运算自然延展至量子比特、叠加态与阿达马门等酉变换操作。随后，讲座通过解决著名的多伊奇神谕（Deutsch Oracle）问题，直观证明了量子计算如何仅凭单次查询击败经典系统的两次查询，展示了相位反冲与对称性调控的威力。最后，主讲人剖析了量子纠缠的不可因式分解本质与量子隐形传态协议，并结合微软 Q# 语言模拟与 IBM 云端真实量子计算机实测，客观探讨了量子噪声与工程实现面临的严峻挑战。 ## Atmosphere & style 整场讲座洋溢着极客式的幽默、坦诚与严谨，主讲人完全摒弃了玄虚的物理黑话，以“闭嘴，计算吧”的极简数学态度引领听众剥离神秘感。现场互动频繁且充满张力，听众对因果律、状态坍缩和拓扑抗噪的犀利追问引发了多次思想交锋。从黑板式的几何推导到云端调度稀释制冷机的真机实测，整个过程既有拆解前沿算理的智力快感，又带有面对物理现实噪声与工程不确定性时的清醒与敬畏。 ## Bulletin - [04:23](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=263s) 量子计算的核心数学可以用初等线性代数完全建模：量子比特由满足概率幅模平方和为 1 的向量表示，量子逻辑门则对应纯可逆且通常自反的酉矩阵变换。 - [33:09](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1989s) 多伊奇神谕（Deutsch Oracle）问题展示了量子计算超越经典计算的最简范例：通过制备叠加态与利用相位反冲效应，量子计算机仅需 1 次黑盒查询即可判定布尔函数的常数或平衡属性，而经典算法至少需要 2 次。 - [58:00](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=3480s) 量子纠缠在数学上定义为复合乘积态无法分解为各子系统单比特向量的张量积；它只支持瞬时“超光速协同”，由于单方测量结果纯粹随机，严格禁止超光速通信传递有效信息。 - [01:14:45](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4485s) 经典计算机模拟量子计算会遭遇指数级内存瓶颈（存储 N 个纠缠量子比特需 2^N 维向量）；而在物理工程端，为了对冲噪声并获得 1 个高质量逻辑量子比特，往往需要 100 到 200 个物理量子比特进行纠错冗余。 ## Key takeaways - [00:04](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4s) 量子门模型计算完全可以剥离复杂的波粒二象性物理隐喻，抽象为计算机科学家熟悉的确定性矩阵变换与离散状态机模型。 - [01:11](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=71s) 量子计算的核心应用主要集中在三大领域：破解大数质因数分解的 Shor 算法、提供根号级加速的 Grover 无序搜索，以及对分子动力学和固氮作用等物理生化系统的指数级模拟加速。 - [09:38](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=578s) 量子逻辑门必须满足严格的可逆计算（Reversible Computing）与酉变换要求，大多数门（如非门、阿达马门）还具有应用两次即复原的自反性（self-inverse）。 - [10:43](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=643s) 多比特系统的复合状态通过张量积（Tensor Product）构建，N 个经典或量子比特的状态空间维度随比特数呈 2^N 指数级膨胀。 - [23:27](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1407s) 阿达马门（Hadamard Gate）能够将确定基态推入等权重的量子叠加态，并在算法末期逆向施加，将计算结果完好无损地拉出叠加态以实现高确定性的经典测量。 - [35:42](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=2142s) 为了在可逆量子系统中运行不可逆的经典布尔函数，必须采用双导线黑盒（Oracle）设计，引入辅助比特通过异或写入函数输出，从而保证整个变换矩阵可逆。 - [50:27](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=3027s) 在多伊奇算法中，受控非门（CNOT）在特定的叠加态输入下会触发反直觉的“相位反冲”（Phase Kickback）效应，导致辅助目标比特保持不变，而输入控制比特的状态发生翻转。 - [58:00](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=3480s) 贝尔态（Bell State）在数学上具有不可因式分解性，证明了处于纠缠态的量子比特并不具备各自独立的物理数值，其取值唯有联合测量才有意义。 - [01:01:45](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=3705s) 约翰·贝尔打破了局域隐变量理论，证实微观粒子并非在测量前就暗中确定了数值；但纠缠测量产生的关联纯属真随机数，因果律依然成立，无法用于超光速传递有效信息。 - [01:08:26](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4106s) 不可克隆原理（No-Cloning Theorem）禁止对未知量子态执行复制操作，量子态的转移只能是“剪切并粘贴”式的量子隐形传态，且该协议必须依赖经典信道传输 2 个经典比特以完成重构。 - [01:17:35](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4655s) 量子计算的工程实现面临严峻的噪声屏障，部分怀疑论学者（如 Gil Kalai）认为物理噪声可能随纠缠规模呈指数级激增，这构成了拓扑与超导路线能否真正迈向容错量子计算的生死考验。 - [01:27:06](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=5226s) IBM 云端真实量子计算机运行贝尔态的实验数据表明，绝大多数测量结果严格聚集在 |00⟩ 与 |11⟩，而少量的杂散状态则直观印证了物理硬件上门操作误差与环境噪声的存在。 ## Detailed walkthrough ### [00:04](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4s) 面向计算机科学家的量子计算：摆脱物理神话 主讲人首先向听众致意“情人节快乐”，并半开玩笑地称量子计算为“所有学科中最浪漫的一门”。这场讲座专门面向计算机科学家展开，因此完全剥离了晦涩的物理学内容——现场不会讨论双缝干涉实验（Double-Slit Experiment）或测不准原理（Uncertainty Principle）。主讲人指出，本次讲座的核心是引入一个大家会觉得非常直观的计算模型——状态机（state machine）。随后，他们将在这个模型上运行量子算法，证明其在性能上超越经典计算模型，最后以包含微软量子编程语言 Q# 的实际运行演示来结束。 当前讲座聚焦于“量子门计算模型”（Gate Quantum Computation Model），它的运行形式与经典计算模型极其相似：拥有类似比特的载体，将它们输入逻辑门并施加变换。主讲人补充说明，业界还有另一种被 D-Wave 等公司采用的“量子退火模型”（Quantum Annealing Model），这与本次讲座讲解的模型有所不同，虽然学界有人认为两者可能在计算能力上等价，但目前尚未有明确结论。 ```mermaid flowchart LR accTitle: Quantum Computing Models accDescr: Gate model compared to quantum annealing model discussed in the talk subgraph GateModel["门量子计算模型 (本次讲座核心)"] A["量子比特 (Qubits)"] --> B["量子逻辑门 (Gates)"] --> C["状态变换输出"] end subgraph AnnealingModel["量子退火模型 (D-Wave)"] D["量子退火"] -. "能力是否等价存疑".- GateModel end ``` ### [01:11](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=71s) 为什么学习量子计算：三大驱动力与数学的本质 主讲人给出了三条学习量子计算的关键理由： 1. **量子霸权（Quantum Supremacy）近在眼前**：谷歌已宣布预期在当年实现量子霸权，即在真实量子计算机上运行实际问题，其实际运行速度超越经典计算机。如果实现，未来 5 到 10 年内程序员就可能需要用量子计算机处理极其棘手的问题。微软、谷歌、英特尔、IBM 等科技巨头正在对此投入数十亿美元。 2. **激动人心的实际应用场景**： - **Shor 算法**：这一论文问世时轰动了全球，证明量子计算机具有切实的经济冲击力，“我们能够分解 RSA，破坏我们的全球金融体系，这非常酷”（“We could factor RSA, and undermine our global financial system, which is pretty cool.”）。 - **无序列表搜索（Grover 算法）**：经典计算机遍历无序列表需要检查每一个元素，复杂度为 $O(N)$；而量子计算机仅需 $\sqrt{N}$ 次查询即可完成搜索。 - **量子力学系统模拟的指数级加速**：主讲人认为这是改变世界概率最高的方向，能够极大加速分子相互作用模拟、药物设计以及生物学研究，比如微软在宣传中经常提及的生物“固氮作用”（Nitrogen Fixation）模拟。 3. **智力上的极大吸引力与突破直觉**：主讲人坦言这才是驱动他本人的根本动力。对多数资深工程师而言，面对任何经典数字或机械系统，脑海中都能大致推测出其运行原理；但量子计算机为何能超越经典计算，完全超出了日常经验的直觉范围。 主讲人上升到哲学层面解释道：人类日常的非正式语言是在纯粹的经典世界中发展出来的，根本无法准确描述量子世界。这就是为什么所有关于量子力学科普文章中的隐喻和类比读起来都似是而非甚至带有误导性。想要真正理解量子力学，唯一的途径是掌握它的新语言——数学。主讲人引用了物理学家戴维·默明（David Mermin）针对量子力学研究的名言：“闭嘴，计算吧”（“Shut up and calculate”）。当研究生们靠在椅背上迷茫地追问“这到底意味着什么”时，唯一的准则就是相信数学，只有数学才不会把人带偏。 ```mermaid flowchart TD accTitle: Applications of Quantum Computing accDescr: Three main practical applications of quantum computing mentioned in the lecture App["量子计算核心应用"] App --> Alg1["Shor 算法: 破解 RSA 密码体系"] App --> Alg2["无序搜索: 时间复杂度从 O(N) 降至 O(sqrt(N))"] App --> Alg3["物理与生化模拟: 药物设计与固氮作用模拟 (指数级加速)"] ``` ### [04:23](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=263s) 讲座大纲与向量表示法 主讲人梳理了接下来的内容规划： - 使用初等线性代数（矩阵、向量、矩阵乘法）来表示计算过程； - 将这一数学工具推广至量子比特（Qubit）、叠加态（Superposition）以及量子逻辑门； - 运用这些工具解决量子计算机优于经典计算机的最简单范例——多伊奇神谕问题（Deutsch Oracle Problem）； - 作为额外拓展，顺带讲解极易理解的量子纠缠（Quantum Entanglement）与量子隐形传态（Teleportation），并展示 Q# 代码与实时演示。 随后，主讲人引入了代表经典比特 0 和 1 的两个基础二维列向量： - 状态 $0$ 表示为 $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ - 状态 $1$ 表示为 $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$ 这种状态也可以使用狄拉克符号（Dirac Vector Notation，即右矢 ket 记号）写成 $|0\rangle$ 和 $|1\rangle$。若难以记忆，可以将其类比为一个从索引 0 开始计数的数组：第 0 个索引位置为 1 则代表数值 0，第 1 个索引位置为 1 则代表数值 1。 - 状态 0 对应向量：$\begin{bmatrix} 1 \\ 0 \end{bmatrix} \iff |0\rangle$（第 0 项为 1） - 状态 1 对应向量：$\begin{bmatrix} 0 \\ 1 \end{bmatrix} \iff |1\rangle$（第 1 项为 1） ### [05:51](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=351s) 矩阵乘法回顾与单比特逻辑运算 主讲人快速复习了线性代数第一课的内容：矩阵乘向量时，取矩阵的水平行翻转后与向量元素逐项相乘再相加。例如一个 $2 \times 2$ 矩阵乘二维向量： $$\begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} ax + by \\ cx + dy \end{bmatrix}$$ 同样规则适用于 $3 \times 3$ 矩阵与三维向量的运算。主讲人特别提到了单位矩阵（Identity Matrix），其主对角线上全是 1，其余全为 0，任何向量与其相乘都保持原样，通常用符号 $I$ 或数字 $1$ 表示。主讲人分享了一个实用法则：后续用到的大量矩阵长得很像单位矩阵，主要由 0 和 1 构成；例如若一个矩阵相对于单位矩阵颠倒了中间两行，那么它对任何相乘对象产生的作用就是对调中间两行。 主讲人随后向现场观众提问：“有人能告诉我单比特上的四种操作是什么吗？一共有四种。”（“Can anyone tell me what are the four operations on one bit? There's four of them.”）观众席起初给出了 AND、OR、XOR 等双比特门，随后修正为正确的四种单比特操作： 1. **恒等操作（Identity）**：$f(x) = x$ 2. **取反操作（Negation / NOT）**：$f(x) = \neg x$ 3. **常数 0（Constant-0）**：恒输出 0 4. **常数 1（Constant-1）**：恒输出 1 这些操作完全可以用矩阵乘法表示： - 恒等矩阵 $\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$：作用于 $|0\rangle$ 仍为 $|0\rangle$，作用于 $|1\rangle$ 仍为 $|1\rangle$。 - 非门（Negation）矩阵 $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$：将 $|0\rangle$ 翻转为 $|1\rangle$，将 $|1\rangle$ 翻转为 $|0\rangle$。 - 常数 0 矩阵 $\begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}$ 与常数 1 矩阵 $\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}$：分别强制将输入映射为 $|0\rangle$ 或 $|1\rangle$。 | 操作名称 | 函数表达式 | 矩阵表示 | 输入 $|0\rangle$ 输出 | 输入 $|1\rangle$ 输出 | |:--- |:--- |:--- |:--- |:--- | | **恒等 (Identity)** | $f(x) = x$ | $\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$ | $|0\rangle$ | $|1\rangle$ | | **取反 (Negation)** | $f(x) = \neg x$ | $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ | $|1\rangle$ | $|0\rangle$ | | **常数 0 (Constant-0)** | $f(x) = 0$ | $\begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}$ | $|0\rangle$ | $|0\rangle$ | | **常数 1 (Constant-1)** | $f(x) = 1$ | $\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}$ | $|1\rangle$ | $|1\rangle$ | ### [08:49](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=529s) 可逆计算（Reversible Computing） 主讲人引出“可逆计算”（Reversible Computing）的概念，提到流行科幻小说《促进绝快》（*Accelerando*）中也探讨过这一术语。可逆计算的定义非常直观：“基本上意味着，如果我告诉你我执行的操作以及该操作的输出，只要该操作是可逆的，你总能反推出该操作的输入”（“basically it means that if I tell you the operation I did and the output of that operation, you can always tell the input of that operation, if the operation's reversible.”）。 直观上来看，只是在重新排列或置换比特的操作是可逆的；而那些擦除比特并覆盖它们的操作则是不可逆的。在前述单比特操作中： - **恒等与取反是可逆的**：若非门输出为 1，则输入必然是 0； - **常数 0 与常数 1 是不可逆的**：若常数 1 操作输出为 1，无法得知原本输入是 0 还是 1，因为该操作在执行过程中擦除了原有信息。 ### [09:38](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=578s) 可逆计算与冯·诺依曼-兰道尔极限 量子计算的一个关键特征在于：量子计算机仅使用可逆操作（reversible operations）。演讲者指出，在此前讨论的单比特经典逻辑门中，真正被量子计算关心的只有非门（negation），虽然恒等门（identity）也是可逆的，但它等同于“什么都不做”。量子计算机还有一个更加严格的特性：它们所使用的操作实际上全部是其自身的逆（self-inverse）。这意味着操作不仅可逆，只要连续施加两次，就能直接恢复原本的输入值。 ```mermaid flowchart LR accTitle: 自反可逆操作示意图 accDescr: 展示一个输入值在连续应用两次相同操作后变回初始状态的过程 subgraph S1["自反操作 (Self-Inverse)"] direction LR A["输入状态"] -->|"门操作 U"| B["中间状态"] B -->|"再次应用门操作 U"| C["恢复输入状态"] end ``` 演讲者随后聊起一段带有“科普色彩”的物理背景：理论物理中存在一个名为“冯·诺依曼-兰道尔极限”（Von Neumann-Landauer Limit）的概念。该极限定义了物理学家所计算出的、进行一次最简单不可逆计算所必然消耗的最小能量下限。如果计算过程是不可逆的，信息擦除就必定伴随能量耗散；而可逆计算在理论上打破了这道物理屏障，未来可能使能耗跨越这一理论极限。演讲者幽默地调侃道：“目前现有的处理器能耗是冯·诺依曼-兰道尔极限的数百万倍，但谁知道五千年后会变成什么样呢？” - 量子计算门操作的核心原则：纯可逆（reversible）且自反（self-inverse，$U^2 = I$）。 - 不可逆擦除信息会导致发热与能耗，而纯可逆计算在理论上具有零最小热耗散的潜力。 ### [10:43](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=643s) 张量积与多经典比特的向量表示 为了用线性代数同时表示多个比特，需要引入线性代数中一种基础工具：张量积（tensor product，符号为 $\otimes$）。当对两个向量进行张量积运算时，直观上的操作方式是：将第二个向量完整地“平铺”（tile）到第一个向量的每一个元素旁，再分别进行标量乘法。例如两维向量 $(x_0, x_1)^T$ 与 $(y_0, y_1)^T$ 的张量积，展开后会变成一个四维向量 $(x_0 y_0, x_0 y_1, x_1 y_0, x_1 y_1)^T$。当应用于三个向量时，维数会进一步扩展为一个巨大的数组。如果输入向量均只包含经典值 0 和 1，最终张量积生成的长向量中，将有且仅有一个位置是 1，其余全为 0。 ```mermaid flowchart TD accTitle: 两个二维向量的张量积展开 accDescr: 展示第一向量元素与第二向量组合生成四维长向量的过程 subgraph Input["输入向量"] direction LR V1["[ x₀, x₁ ]ᵀ"] V2["[ y₀, y₁ ]ᵀ"] end subgraph Tiling["展开平铺"] direction TB T1["x₀ × [ y₀, y₁ ]ᵀ = [ x₀y₀, x₀y₁ ]ᵀ"] T2["x₁ × [ y₀, y₁ ]ᵀ = [ x₁y₀, x₁y₁ ]ᵀ"] end subgraph Result["合成积状态 (Product State)"] R["[ x₀y₀, x₀y₁, x₁y₀, x₁y₁ ]ᵀ"] end V1 --> Tiling V2 --> Tiling Tiling --> Result ``` 在表示多比特经典系统时，复合状态由各单比特向量的张量积构成，被称为“积状态”（product state）： - 状态 $|00\rangle = |0\rangle \otimes |0\rangle = (1, 0)^T \otimes (1, 0)^T = (1, 0, 0, 0)^T$（索引 0 处为 1） - 状态 $|01\rangle = |0\rangle \otimes |1\rangle = (1, 0)^T \otimes (0, 1)^T = (0, 1, 0, 0)^T$（索引 1 处为 1） - 状态 $|10\rangle = |1\rangle \otimes |0\rangle = (0, 1)^T \otimes (1, 0)^T = (0, 0, 1, 0)^T$（索引 2 处为 1） - 状态 $|11\rangle = |1\rangle \otimes |1\rangle = (0, 1)^T \otimes (0, 1)^T = (0, 0, 0, 1)^T$（索引 3 处为 1） 通过观察可以发现，比特串所表示的二进制整数值，正好对应长向量中非零元 1 的数组索引下标（例如二进制 100 等于十进制 4，其在三比特状态向量的第 4 项为 1）。对于 $n$ 个比特的系统，其积状态向量的维度为 $2^n$。演讲者特别提醒大家留心这一数学性质：“在此处，我们透过这个指数项，隐约听到了量子计算潜能的轻声低语，不过先记住这点，我们稍后还会回到这里。” | 比特状态 | 二进制值 | 十进制索引 | 向量形式 | |:--- |:--- |:--- |:--- | | $|00\rangle$ | 00 | 0 | $[1, 0, 0, 0]^T$ | | $|01\rangle$ | 01 | 1 | $[0, 1, 0, 0]^T$ | | $|10\rangle$ | 10 | 2 | $[0, 0, 1, 0]^T$ | | $|11\rangle$ | 11 | 3 | $[0, 0, 0, 1]^T$ | ### [13:06](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=786s) 受控非门（CNOT）及其矩阵代数推导 为了在多比特系统上实现逻辑运算，演讲者引出了可逆计算与量子计算中至关重要的基本逻辑门——CNOT门（Conditional NOT，受控非门）。CNOT 作用于一对比特之上，其中一个比特被指定为“控制比特”（control bit），另一个为“目标比特”（target bit）。其运作语义非常直观：控制比特始终保持不变；若控制比特为 1，则翻转目标比特；若控制比特为 0，则目标比特保持原样不变。以最高有效位为控制比特、最低有效位为目标比特的约定下： - $|00\rangle \rightarrow |00\rangle$ - $|01\rangle \rightarrow |01\rangle$ - $|10\rangle \rightarrow |11\rangle$ - $|11\rangle \rightarrow |10\rangle$ 从矩阵形式上看，CNOT 对应的 $4 \times 4$ 矩阵形式极其简洁：它其实就是将四阶单位矩阵（Identity Matrix）的最后两行进行了对调交换： $$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$ 现场推导展示了将该矩阵乘在状态向量上的过程：当输入为 $|10\rangle = (0, 0, 1, 0)^T$ 时，矩阵相乘将原本第 3 行与第 4 行的值对调，输出变为 $(0, 0, 0, 1)^T$，因子分解还原为单比特形式正好是 $|11\rangle$；同理，作用于 $|11\rangle = (0, 0, 0, 1)^T$ 时输出变为 $(0, 0, 1, 0)^T$，分解后为 $|10\rangle$。此时台下有听众提问：“这种分解对于更大的向量总是可行或实用的吗？”演讲者回答道：“实用是实用的，但并不总是可能，这正是我们后面讲到量子纠缠时要深入探讨的内容，提得很好。” 演讲者将 CNOT 比作经典集成电路里的与非门（NAND）：经典 CPU 的一切逻辑功能几乎都基于 NAND 构建，而 CNOT 则是可逆计算的基石。但他随即严谨地指出：CNOT 门本身并不是通用的（universal），单独依靠它无法拼凑出任意复杂的逻辑函数；要构建通用可逆逻辑，还需要结合诸如托佛利门（Toffoli gate）等三比特门。 ### [17:18](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1038s) 量子比特、叠加态与测量坍缩 在全面回顾了经典计算的线性代数表达后，演讲者带领听众正式跨入量子领域：“现在我们迈出这一步，量子比特（qubit）。”出乎大家意料的是，其实整场演讲从一开始就在使用量子比特，因为经典比特（cbit）不过是量子比特的一种特例。一般情况下，量子比特用一个二维复数向量 $(a, b)^T$ 表示，但在本次讲座中为了保持简明，全部限定为实数。该向量满足归一化约束条件： $$a^2 + b^2 = 1$$ 此约束自然包容经典比特：对于 $(1, 0)^T$，有 $1^2 + 0^2 = 1$；对于 $(0, 1)^T$，有 $0^2 + 1^2 = 1$。此外还可以取各种满足平方和为 1 的数值组合： - 经典基态：$(1, 0)^T$ 与 $(0, 1)^T$ - 均等分配状态：$(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})^T$，因为 $(\frac{1}{\sqrt{2}})^2 + (\frac{1}{\sqrt{2}})^2 = \frac{1}{2} + \frac{1}{2} = 1$ - 几何角度状态：$(\frac{1}{2}, \frac{\sqrt{3}}{2})^T$，因为 $(\frac{1}{2})^2 + (\frac{\sqrt{3}}{2})^2 = \frac{1}{4} + \frac{3}{4} = 1$ - 引入负振幅的状态：如 $(-1, 0)^T$ 或 $(\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}})^T$，由于负数平方为正数，完全符合模长守恒。 ```mermaid flowchart TD accTitle: 量子态叠加与测量坍缩过程 accDescr: 量子比特在叠加态下保持连续概率幅，一经测量即以概率坍缩为经典比特 subgraph Superposition["叠加态 (|ψ⟩ = a|0⟩ + b|1⟩)"] Q["状态向量: [ a, b ]ᵀ (约束: a² + b² = 1)"] end subgraph Measure["测量通道 (Measurement Gate)"] M{"观察 / 测量"} end subgraph Collapse["经典坍缩结果"] direction LR C0["状态 |0⟩ (经典0)\n概率 = a²"] C1["状态 |1⟩ (经典1)\n概率 = b²"] end Q --> M M -->|"概率 a²"| C0 M -->|"概率 b²"| C1 ``` 这意味着量子比特的值并非非 0 即 1，而是可以同时处于 0 和 1 的状态，这被称为“叠加态”（superposition）。演讲者打趣说，大众科普里常提的“薛定谔的猫既死又活”，本质上就是对这个概念的一种科普化表达。处于叠加态的量子比特允许系统在某种意义上同时对 0 和 1 进行运算，这构成了量子加速能力的源头。 当在量子算法末尾试图读取运算结果时，系统必须经过测量（measurement）。一经测量，量子比特就会发生坍缩（collapse）： - 状态向量 $(a, b)^T$ 坍缩为 0 的概率为 $a^2$ - 坍缩为 1 的概率为 $b^2$ 例如对于 $(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})^T$，坍缩为 0 的概率是 $(\frac{1}{\sqrt{2}})^2 = \frac{1}{2}$，坍缩为 1 的概率也是 $\frac{1}{2}$，其物理效果就像抛一枚完全公平的硬币。而经典比特向量 $(1, 0)^T$ 在测量时，坍缩到 0 的概率是 $1^2 = 100\%$，坍缩到 1 的概率为 0，这与经典确定性系统完全吻合。 ### [20:01](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1201s) 物理直觉：光子偏振与量子比特塌缩 为了让台下的听众对抽象的量子比特（qbit）建立直观认知，讲师借用了日常生活中常见的“偏光太阳镜”作为物理类比。讲师解释道，偏振本身其实就是一种量子现象：光子可以呈现横向或纵向的偏振方向，而偏光太阳镜的镜片格栅只允许特定偏振方向的光穿透。如果把某一个方向的偏振看作状态 0，垂直方向的偏振看作状态 1，那么“叠加态”（superposition）就意味着光子在穿过格栅前实际上同时兼具两种偏振可能，直到它撞上偏振格栅——格栅的拦截与通过就是一种“测量”动作，此时它便瞬间塌缩（collapse）为确定的 0 或 1。 不过讲师随即补充道，这仅仅是一个帮助理解的物理隐喻。在实际工程中，科学家发现光子由于极易与外界发生相互作用而发生塌缩，实际上并不是理想的量子比特制造载体。讲师向全场确认大家是否理解了这种由测量引发的塌缩概率机制，在得到全场默许后，讲解迅速推进到多量子比特系统。 ### [21:18](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1278s) 多量子比特与张量积：维持单位平方和 多量子比特的数学表示方式与经典比特完全一致，都是通过张量积（tensor product / Kronecker product）连接。张量积运算能够完美维持“概率幅平方和等于 1”（$a^2 + b^2 = 1$）这一基本恒等式约束。讲师以两个完全均匀的“抛硬币”量子比特（各自处于 50% 塌缩为 0、50% 塌缩为 1 的状态，对应向量为 $\begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \end{bmatrix}$）相乘为例，两者的张量积生成了一个 4 维列向量，其中每一个元素的值均为 $\frac{1}{2}$。由于 $(\frac{1}{2})^2 = \frac{1}{4}$，四个位置的概率平方相加正好等于 1： $$\frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} = 1$$ 这意味着一旦对这两个量子比特进行联合测量，塌缩到经典状态 $(0, 0)$、$(0, 1)$、$(1, 0)$ 和 $(1, 1)$ 的概率各为 25%。 在问答环节，有听众举手提出疑问：“测量之后，向量里是不是只会剩下一个 1，而不可能出现两个 1？”讲师明确肯定了这一判断：“There could not two ones because that would actually violate our $a^2 + b^2 = 1$ constraint.” 讲师解释说，测量完成之后，这个四维向量中只会在某一特定位置保留一个 1，其余全为 0，随后便可以将其分解为具体的两个经典比特。另一位听众追问这个长向量的塌缩过程是否针对整体生效，讲师表示完全正确：测量联合量子比特时，整个积态（product state）向量会瞬间塌缩，其每个条目记录的就是在该位置读出 1、其他位置全为 0 的塌缩概率。这种全局状态表示在后续遇到无法因式分解的纠缠态时将显得尤为关键。 ```mermaid flowchart LR accTitle: Two Qubit Tensor Product and Measurement Collapse accDescr: Flow showing two superposition qubits combined by tensor product into a 4-vector and collapsed by measurement. subgraph Inputs["单量子比特输入"] Q1["Qubit 1: [1/√2, 1/√2]ᵀ"] Q2["Qubit 2: [1/√2, 1/√2]ᵀ"] end subgraph Tensor["复合状态"] TP["张量积运算 ⊗"] V4["4维状态向量: [1/2, 1/2, 1/2, 1/2]ᵀ<br/>(00, 01, 10, 11 各占 1/4 概率)"] end subgraph Output["测量操作"] M["测量 / 塌缩"] Res["单一确定状态: 仅含一个 1<br/>如 [0, 1, 0, 0]ᵀ 对应 |01⟩"] end Q1 --> TP Q2 --> TP TP --> V4 V4 --> M M --> Res ``` ### [23:27](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1407s) 量子门操作与核心的阿达马门（Hadamard Gate） 有了量子比特，接下来的核心问题是如何操纵它们。讲师指出，前面学过的经典矩阵算子在量子世界中完全适用。例如对于一个有 25% 概率塌缩为 0、75% 概率塌缩为 1 的量子比特，用非门（bit flip operator，即泡利 X 门）对其进行变换后，它塌缩为 0 的概率变成了 75%，塌缩为 1 的概率则变成了 25%。量子门本质上是科学家研发的一种物理装置，能够“轻柔地干预量子比特，既改变其量子态（概率幅），又不会剧烈到使其发生塌缩”。 随后，讲师引入了量子计算中最具代表性且最重要的矩阵——阿达马门（Hadamard Gate）。阿达马门的作用是把处于确定状态的经典量子比特（0 或 1）转化为均匀的 50/50 抛硬币叠加态。其矩阵定义如下： $$H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$ - 将 $H$ 作用于状态 $|0\rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ 时，得到 $\begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \end{bmatrix}$； - 将 $H$ 作用于状态 $|1\rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$ 时，得到 $\begin{bmatrix} 1/\sqrt{2} \\ -1/\sqrt{2} \end{bmatrix}$。 讲师随即抛出小测验：“为什么阿达马矩阵右下角的元素必须是负号？”在听众尝试回答后，讲师道破了底细：量子操作必须具备可逆性（unitary/reversible）。如果右下角不是负号，那么 0 和 1 输入经过运算后会映射到完全相同的结果，从而丧失可逆性。 ### [25:39](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1539s) 叠加态的本质与“符号”携带的信息 一位听众针对“叠加态”的概念要求进一步厘清。讲师借此机会向全场严正澄清了一个极其普遍的认识误区：“And I want to be really clear about something here. This doesn't mean the qubit is secretly zero or secretly one, and we don't know. It means it's actually in both at the same time, this is just quantum weirdness.” 讲师强调，在微观物理层面上，物理量在被测量之前本身就处于一种不确定的客观共存状态，而非经典视角下“实际上有个固定值只是我们还没揭晓”。 听众接着提出锐利的质疑：由 0 演变而来的 $\begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \end{bmatrix}$ 与由 1 演变而来的 $\begin{bmatrix} 1/\sqrt{2} \\ -1/\sqrt{2} \end{bmatrix}$，在测量时塌缩到 0 或 1 的概率同样都是 50%，既然测量表现毫无差异，这两者在概念上是否等同？听众甚至打趣提问：“那它是不是某种程度上‘记着’自己曾经是 1？” 讲师解释道，从经典宏观测量的视角来看，两者确实表现相同，均呈现五五开的塌缩几率；但如果停留在量子计算领域内，那个负号（相位信息）只要没有遭到测量破坏，就会被完整保留下来，并对后续的矩阵运算产生决定性的干涉影响。两者在量子世界中是截然不同的两种量子态，拥有不同的计算属性，不能混为一谈。 ### [27:23](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1643s) 逆操作退出叠加态：确定性量子计算范式 紧接着，讲师展示了阿达马门另一个极其关键且震撼的数学性质：阿达马门自身就是其逆矩阵（$H = H^{-1}$）。如果对处于正负叠加态的向量再次施加阿达马门： - $H \begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$（精确变回状态 0） - $H \begin{bmatrix} 1/\sqrt{2} \\ -1/\sqrt{2} \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$（精确变回状态 1） 这一性质揭示了一种极其优美而强大的量子算法范式：我们可以从明确的经典数据（0 或 1）出发，通过阿达马门将其推入量子叠加态，在叠加态的宽广空间中并行执行复杂的矩阵变换；如果算法设计足够精妙，最终我们可以再次使用阿达马门将系统“完好无损地拉出叠加态”，使其在不依赖概率猜度的情况下，以 100% 的确定性塌缩或直接恢复为唯一的正确答案。 讲师坦承并非所有算法都能实现百分百的确定性输出，比如著名的秀尔算法（Shor's algorithm）最终给出正确答案的概率大约只有 50%，需要多次运行，但在本次讲座接下来要讲的具体问题（Deutsch 算法）中，这种确定性是可以完美做到的。 有听众举手发问：“能不能演示一下简单的运算，比如在量子计算机里做 2 + 2 怎么转进量子态再转回来？”讲师幽默而坦率地打碎了这一幻想，指出量子计算机并非擅长所有任务：“There are certain problems where computers are better than classical. Addition is not one of them. It works the exact same way in both.” 讲师补充说明，所有经典计算确实都可以在量子计算机上运行（只需把取值严格限制在 0 和 1 即可），但这么做毫无意义，完全是杀鸡用牛刀，量子计算机的真正价值在于挖掘叠加态带来的额外计算维度。 ### [29:18](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1758s) 单位圆与状态机视角 讲座随后将量子操作抽象为软件工程师最熟悉的“状态机”（State Machine）模型，借由高中的平面直角坐标系与单位圆（Unit Circle）进行可视化呈现。讲师引导听众把二维向量的顶部数值视为 X 轴坐标，底部数值视为 Y 轴坐标： | 状态向量 | 坐标 $(x, y)$ | 几何位置 | |:--- |:--- |:--- | | $|0\rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ | $(1, 0)$ | X 轴正半轴上的交点 | | $|1\rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$ | $(0, 1)$ | Y 轴正半轴上的交点 | | $|-\rangle = \begin{bmatrix} 0 \\ -1 \end{bmatrix}$ | $(0, -1)$ | Y 轴负半轴上的交点 | | 均匀叠加态 $\begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \end{bmatrix}$ | $(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})$ | 第一象限 45 度对角线上 | | 带相位叠加态 $\begin{bmatrix} 1/\sqrt{2} \\ -1/\sqrt{2} \end{bmatrix}$ | $(\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}})$ | 第四象限 315 度对角线上 | 在单位圆模型下，经典比特翻转门（非门）的矩阵几何意义就是在坐标系中执行翻转与沿轴轮换：它将 $(1, 0)$ 映射至 $(0, 1)$，反之亦然。然而，讲师指出了一个极为有趣的现象：当经典翻转门作用在均匀叠加态 $(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})$ 上时，由于其 X 坐标与 Y 坐标完全相等，翻转后状态根本没有发生变化；而在带有不同符号的叠加态上，矩阵变换则会在单位圆上产生横跨象限的特定转移，这一几何特性正是后续构造量子加速算法的关键杠杆。 ### [30:33](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1833s) 单位圆上的状态机与量子线路记号 “I should mention here that if we were using complex numbers, this would actually be a sphere.” 讲者首先对几何表示进行了说明：尽管完整的量子计算基于复数，在几何上对应的是三维的布洛赫球面（Bloch sphere），但在本讲座中，坚持使用实数构成的单位圆（unit circle）就足够阐明核心机制，同时也避免了三维复数球面的直观理解困难。讲者风趣地补充道，只要有需要，这个额外的维度随时可用，以使计算变得更加强大。 随后，讲者带领大家回顾了比特翻转门（$X$ 门）和阿达马门（$H$ 门）在单位圆上的对称变换效果。$H$ 门将状态在基态与叠加态之间转换（如从 $|0\rangle$ 到 $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$，从 $|1\rangle$ 到 $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$）。此时，整个几何系统变成了一个直观、优雅的状态机，计算可以通过在单位圆上“跳跃”来完成，而不需要每一步都手动计算繁琐的矩阵乘法。 讲者在此引入了量子线路记号（quantum circuit notation）：量子比特（qubit）沿着水平导线穿过一个个方框算符。例如，从向量 $[1, 0]^T$ 出发，依次通过 $X$ 门、$H$ 门、$X$ 门、$H$ 门、$X$ 门，量子状态就在单位圆上连续跳转，最终穿过圆环到达 $[0, 1]^T$。因为所有这些量子操作都是可逆的，所以该路径也能原路逆向返回。讲者总结道，这和经典计算中的有限状态机没有本质差别，只是伴随着测量坍缩等奇特的量子力学规则。 - 实数模型限制在单位圆二维平面，完整的复数系统对应布洛赫球面（Bloch sphere）。 - 量子线路中算符沿时间线排列，水平线代表量子比特传输，方框代表门操作（$X$ 为比特翻转，$H$ 为阿达马门）。 - 基础概念复习：经典比特（Cbit）是量子比特（Qbit）的特例；量子比特满足概率归一化条件 $a^2 + b^2 = 1$；多量子比特系统由单量子比特通过张量积（tensor product）组合而成。 --- ### [33:09](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=1989s) 德伊奇神谕（Deutsch Oracle）问题与经典局限 “We learn that Cbits are just a special case of Qbits, and Qbits are two vectors of complex numbers such that a squared plus b squared equals one.” 讲者在梳理了所有必备基础后，正式切入核心主题：展示量子计算机超越经典计算机的最简案例——德伊奇神谕（Deutsch oracle）问题。该问题最初由物理学家戴维·德伊奇（David Deutsch）在1985年前后提出。 讲者打了个生动的比方：假设有人在你的门前放了一个神秘包裹，里面是一个封装好的黑盒（black box）。盒子里实现了一个作用在单比特上的函数 $f(x)$。对于单比特输入，总共只可能存在 4 种函数：常数 0（恒输出 0）、常数 1（恒输出 1）、恒等函数（Identity，输出与输入相同）以及求反函数（Negation / Bit-flip，翻转输入）。黑盒有输入引线和输出引线，但不允许拆开窥探内部线路。 讲者向台下抛出提问：“如果要在经典计算机上明确判断黑盒里究竟是这 4 个函数中的哪一个，需要查询几次？”听众立刻回答是两次：先输入 0 观察输出，再输入 1 观察输出。讲者接着问：“那在量子计算机上需要几次？”现场有人猜测是一次，讲者笑着纠正：“你猜错了，还是两次！”讲者借此澄清了大众对量子计算的典型误解：量子计算机并不是真正意义上把所有结果并发算完并全部拿到，因为最终的测量会导致叠加态坍缩为一个确定的经典比特；单比特信息最多只能区分两种状态，要精准确定 4 个函数之一，在信息论上至少需要两个比特，因此量子计算机也必须查询两次。 然而，如果改变提问方式，量子计算机的优势就立刻显现了：我们不要求精确知道是哪个函数，而只关心该函数是“常数函数”（Constant：恒 0 或恒 1）还是“平衡/变化函数”（Variable：恒等或取反）。在经典计算机上，这仍然严格需要查询两次——若第一次输入 0 得到 0，无法确定是恒 0 函数还是恒等函数，对称地，输入 1 同样无法一次定夺。听众这次自信地回答量子计算机只需要“一次”，讲者给予了肯定：利用叠加态的神奇特性，量子计算机仅需单次查询就能无误区分常数与变化，从而在性能上无可争议地胜过了经典计算机。 --- ### [35:42](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=2142s) 可逆性难题与双引线“黑盒重构”机制 “This is actually a really common problem in quantum computation. You really often have to deal with non-reversible functions if you have to write them in an irreversible way, and the hack we do is this.” 讲者指出了将德伊奇问题搬上量子系统时遇到的最大物理与数学阻碍：量子计算的演化矩阵必须是可逆（酉变换）的，但常数函数（丢弃输入信息全部映射为 0 或 1）是完全不可逆的。 为了在可逆计算系统中实现不可逆逻辑，量子计算领域采用了一种普遍的工程手法（hack）：引入辅助输出量子比特，将黑盒从单线重构成双线系统。黑盒包含两条线路：一条是输入线（Input），另一条是辅助输出线（Output，预先初始化为 $|0\rangle$）。系统计算函数值 $f(x)$ 后，将其异或/写到输出线上，而原本的输入量子比特在穿过黑盒后保持不变（$x \to x$）。 ```mermaid flowchart LR accTitle: Oracle Rewiring Architecture accDescr: Diagram showing how a single-wire black box is rewired into a reversible two-wire quantum oracle. subgraph Original["不可逆黑盒 (单导线)"] direction LR In1["输入 x"] --> BB1["不可逆计算 f(x)"] --> Out1["输出 f(x)"] end subgraph Rewired["可逆量子黑盒 (双导线结构)"] direction LR In2["输入线 |x⟩"] --> BB2["酉变换 Oracle (U_f)"] --> Pass2["保持原样 |x⟩"] Out2["辅助输出线 |0⟩"] --> BB2 --> Res2["写入计算结果 |0 ⊕ f(x)⟩"] end ``` 这个设计引发了现场听众密集的困惑与热烈追问： - 有听众坦言“我没听懂（I didn't get it）”，讲者停下来反复厘清：原本是一进一出的盒子，现在强行改成两进两出的黑盒，输入线负责接收计算目标，内部完成函数计算后将结果作用在另一根线上。 - 另一位听众质疑：既然输入线穿过去没有变，为什么辅助线必须强制输入 $|0\rangle$？是不是因为不需要用到它的初始值？讲者明确回答：这并不是“无关输入（don't care pin）”，线路的矩阵构造和相位回冲严格依赖于这根辅助输出线输入时处于 $|0\rangle$ 基态。 - 还有听众对命名产生疑惑：“为什么一条进入盒子的线会被标注为输出线（Output wire）？”讲者承认这种行业叫法确实有点别扭，之所以称其为输出线，是因为我们真正关注的运算结果值最终会落在它身上，而输入线的输出端通常保持原值不变。 - 现场一位听众接着构想了串联架构的场景：“如果把两个黑盒串联起来，第一级的计算结果是否会作为下一级的输入？”讲者赞赏这一提问非常敏锐，指出这涉及量子线路中级联操作与并行处理的设计差异。 ### [40:19](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=2419s) 可逆计算的困境与双线黑盒模型的引入 讲座在此进入了整个分享中概念最艰深的部分。讲者和听众就黑盒（Black Box）的内部机制以及数据流转展开了细致的讨论。有听众提出疑问：是否应该将右上角输出的 $f(x)$ 作为下一个阶段的输入？讲者给予了充分肯定，并借此抛出了一个关键伏笔：虽然黑盒的标准设定假设用于承载结果的比特输入为 $0$，但为了榨取更多信息，我们完全可以“打破这一假设”（break that assumption），故意送入非零状态。针对听众对于后续阶段复用输入的设想，讲者坦言：“这绝对可以，事实上，尽管黑盒假定这个输入值是零，但我们可以打破这个假设，玩点巧妙的手段。” ```mermaid flowchart LR accTitle: Two-wire reversible black box model accDescr: Diagram showing the two-wire reversible computation setup where input x remains unchanged and output wire receives f of x via XOR. subgraph BlackBox["量子可逆黑盒 (Oracle)"] direction TB subgraph Wires["量子线路"] direction LR InX["输入比特 |x⟩"] --> OutX["保持不变 |x⟩"] InY["辅助/输出比特 |0⟩"] --> OutY["函数计算 |0 ⊕ f(x)⟩"] end end ``` 面对现场观众表现出的困惑，讲者多次给全场打预防针：“我发誓，这是整场演讲中在概念上最困难的部分。如果有任何人觉得理解困难，请一定要告诉我。”为了彻底讲清原理，讲者退回到底层，逐一剖析经典布尔函数在量子计算机中必须面对的物理与数学限制——**可逆性（Reversibility）**。 在经典计算中，常数函数（如恒为 $0$）会丢弃输入信息，但在量子物理中，根据酉变换（Unitary transformation）的性质，所有计算必须是可逆的。讲者举例说明： - 如果尝试用单根导线实现“恒为 $0$”的操作，必须使用将所有状态映射为零的矩阵 $\begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}$。 - 但该矩阵不是酉矩阵，不可逆，因此“在量子计算机中这不是一个合法的算符，因为它不可逆……物理现实根本不允许我们制造出具备这种功能的设备”。 - 所有的数学表述并非刻意复杂化，而是因为它们精确对应了物理量子系统的语义与行为。 为了在满足可逆性的前提下实现非可逆逻辑，必须引入**双线模型（Two-wire model）**：一条线承载实际输入比特 $x$（并在计算后原样输出），另一条线作为辅助/输出比特（可称为“工作比特与备用比特”，Compute and Spare bit）。通过将 $f(x)$ 异或到辅助比特上，整个黑盒在数学上表现为一个 $4 \times 4$ 的可逆酉矩阵，从而在保证信息不丢失的前提下实现了任意经典函数。 --- ### [44:39](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=2679s) 四种经典布尔函数的量子线路实现 厘清了可逆性的要求后，讲者带领大家逐个推导布尔域 $f: \{0, 1\} \to \{0, 1\}$ 上的全部四种函数在双导线黑盒内部的具体线路结构。假设辅助线（输出端）的初值输入为 $|0\rangle$： 1. **常数零函数（Constant-0, $f(x) = 0$）**： - 输入 $x$ 保持不变输出；输出端目标值为 $0$。由于假设送入的就是 $0$，因此辅助线不做任何改动。 - 线路内部表现为两根平行的直线导线，没有任何量子门（完全空白）。 2. **常数一函数（Constant-1, $f(x) = 1$）**： - 不管输入 $x$ 是什么，输出端都必须变为 $1$。 - 实现方式极其简单：在辅助导线上放置一个 Pauli-X 门（非门/比特翻转门）。$|0\rangle$ 经过 X 门翻转后直接变成 $|1\rangle$。由于 X 门本身自伴且可逆（$X = X^{-1}$），这一操作完全符合量子物理法则。 3. **恒等函数（Identity, $f(x) = x$）**： - 输出端的值必须与输入端 $x$ 完全一致（输入 $0$ 输出 $0$，输入 $1$ 输出 $1$）。 - 此时引入了**受控非门（CNOT gate）**。将主输入线设为控制比特（Control bit），辅助输出线设为目标比特（Target bit）。当输入为 $0$ 时，目标比特保持 $|0\rangle$；当输入为 $1$ 时，控制端触发目标比特翻转为 $|1\rangle$。 4. **取反函数（Negation, $f(x) = \text{NOT } x$）**： - 讲者向观众提问如何构建取反操作。有观众建议“将控制比特硬编码设为 1”或“使用两个 CNOT 门”。 - 讲者澄清了最直接的解法：在 CNOT 门之后，于输出端再挂接一个 X 门。前半部分先完成恒等复制，后半部分对输出比特执行一次翻转，得到 $\neg x$。 | 函数类型 | 函数类别 | 线路实现方式 | |:--- |:--- |:--- | | **Constant-0** ($f(x)=0$) | 常数函数 (Constant) | 双线直通，无任何量子门（Blank） | | **Constant-1** ($f(x)=1$) | 常数函数 (Constant) | 辅助/输出导线上串联一个单比特 **X 门** | | **Identity** ($f(x)=x$) | 平衡函数 (Variable/Balanced) | 以输入线为控制、输出线为目标的 **CNOT 门** | | **Negation** ($f(x)=\neg x$) | 平衡函数 (Variable/Balanced) | **CNOT 门** 后在输出线上串联一个 **X 门** | --- ### [47:08](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=2828s) 破解 Deutsch 问题：单次查询算法的设计框架 在明确了四种黑盒内部结构后，讲者正式揭晓如何在量子计算机上以**仅仅一次黑盒查询**（Single Query）判定该函数是“常数函数”（Constant，输出全相同）还是“可变/平衡函数”（Variable，输出不相同）。在经典世界中，由于存在两种常数和两种平衡函数，必须查询两次才能下定论；但在量子算法中，只需巧妙打破常规。 整个算法流程由“前处理（Preprocessing）”、“黑盒评估（Oracle Evaluation）”和“后处理与测量（Post-processing & Measurement）”三部分构成： ```mermaid flowchart LR accTitle: Deutsch Algorithm Circuit Architecture accDescr: Quantum circuit diagram for the Deutsch algorithm showing initialization, Hadamard gates, Oracle call, and final measurement. subgraph Pre["前处理 (Preprocessing)"] direction TB Q0_in["|0⟩"] --> X0["X 门"] --> H0["H 门"] Q1_in["|0⟩"] --> X1["X 门"] --> H1["H 门"] end subgraph Oracle["黑盒查询 (Oracle)"] direction TB H0 --> Uf["U_f 内部黑盒"] H1 --> Uf end subgraph Post["后处理与测量"] direction TB Uf --> H0_out["H 门"] --> M0["测量端 (高位 MSB)"] Uf --> H1_out["H 门"] --> M1["测量端 (低位 LSB)"] end ``` 讲者对该算法做出了确定性的断言：“我在此断言，并马上向大家证明：如果黑盒函数是常数函数，系统在测量后的状态必然是 $|11\rangle$；如果黑盒函数是可变函数，测量后的状态必然是 $|01\rangle$。”通过这一机制，算法无需关心具体是四个函数中的哪一个，仅凭一次调用即可通过最高有效位（MSB）是 $0$ 还是 $1$ 彻底区分出函数性质。 前处理的具体状态轨迹在单位圆（Unit Circle）上表现得非常直观： - 两个量子比特均从 $|0\rangle$（即向量 $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$）开始。 - 经过 X 门翻转，状态移至 $|1\rangle$（即向量 $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$）。 - 再通过 Hadamard 门变换，状态被压入均衡叠加态：$\frac{1}{\sqrt{2}}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle$。在二维平面直角坐标系中，这对应于落在第四象限单位圆上的点 $\left(\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}}\right)$。 --- ### [48:31](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=2911s) 常数函数的状态演变与测量验证 讲者紧接着用几何与代数视角检验两种常数函数在上述算法下的最终结果。 1. **针对 Constant-0 函数的演算**： - 处于叠加态 $\left(\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}}\right)$ 的两比特穿过黑盒。由于 Constant-0 的线路内部完全为空，两比特状态没有任何变化，依然停留在第四象限。 - 离开黑盒后进入后处理阶段，两比特分别再次通过一个 Hadamard 门。 - 由于 Hadamard 变换是其自身的逆矩阵（$H = H^{-1}$），它直接将落在第四象限的状态向量翻转回垂直正方向的 $|1\rangle$ 态（即 $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$）。 - 最终进行测量，两个比特 $100\%$ 塌缩到 $|1\rangle$，测得状态为 $|11\rangle$。 2. **针对 Constant-1 函数的演算**： - 辅助/输出线在黑盒内部经历了一个 X 门。在状态圆上，X 门的操作等价于将第四象限的点沿着原点或对角轴反射到第二象限的 $\left(-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right)$。 - 随后经过后处理阶段的 Hadamard 门，该向量被映射到负 $Y$ 轴方向，即状态向量处于 $\begin{bmatrix} 0 \\ -1 \end{bmatrix}$。 - 有听众在此提问：“我就是没搞懂，为什么最后算出来会是 1-1？”讲者耐心拆解了概率计算：在量子力学中，测得某一状态的概率是其概率振幅的模平方。对于状态向量 $\begin{bmatrix} 0 \\ -1 \end{bmatrix}$ 而言，测得 $|1\rangle$ 的概率是 $(-1)^2 = 1$（即 $100\%$ 的概率坍缩到 $1$）。因此，高位是 $1$，低位也是 $1$，系统的最终测量输出依然是稳定确凿的 $|11\rangle$。 讲者兴奋地向观众宣布：“至此我们在两种常数函数上全部验证成功，两战全胜（Two for two）！” --- ### [50:27](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=3027s) 平衡函数初探与相位反冲奇象（Phase Kickback） 进入到平衡函数（以恒等函数 Identity 为例）的分析时，量子力学中最反直觉、最迷人的特性开始显现。Identity 函数由一个 CNOT 门构成，其中输入比特作为控制位，辅助比特作为目标位。 在经典电路的常识中，控制比特仅仅起到“开闭条件”的作用，其自身绝对不应该被目标端修改。然而，在讲者的单位圆投影与状态追踪图上，出现了一个令全场震惊的异象： - 辅助比特（目标比特）的状态穿过黑盒后**纹丝不动**。 - 反而是作为控制端的输入比特，其状态向量从第四象限直接被拉到了第一象限的 $\left(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right)$。 - 随后，该输入比特经过后处理的 Hadamard 门变换后，并没有像常数函数那样落到 $|1\rangle$，而是精准落到了基态 $|0\rangle$（即 $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$）。 - 最终对两比特进行测量，得到的结果恰恰就是预言的 $|01\rangle$。 面对听众的惊讶，讲者直言：“这显得非常怪异，主要有两个原因：其一是 CNOT 门按理说应该保持控制比特不变，但在这里，控制比特却成了唯一发生改变的东西。”讲者安抚台下不要恐慌，这一控制端与目标端“角色颠倒”的奇特现象正是量子计算中著名的**相位反冲（Phase Kickback）**效应。讲者随后切入严密的矩阵与向量乘法，从数学本源开始推导这一 $4 \times 4$ 算符作用在直积态 $\begin{bmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{bmatrix} \otimes \begin{bmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{bmatrix}$ 上的奇妙物理过程。 ### [51:29](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=3089s) 变量函数与多伊奇预言机全验证 在处理变量函数（包含 CNOT 门）时，两个量子比特的初始输入向量分别为 $\begin{bmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{bmatrix}$ 与 $\begin{bmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{bmatrix}$。将它们做张量积（Tensor Product）后，提取出系数 $\frac{1}{2}$，得到联合状态向量 $\frac{1}{2} \begin{bmatrix} 1 \\ -1 \\ -1 \\ 1 \end{bmatrix}$。应用 CNOT 门的变换矩阵后，底层两个状态分量发生翻转，向量转变为 $\frac{1}{2} \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix}$。此时将该联合向量重新因式分解回独立的单比特状态，会发现最低有效位（输出比特）依然保持为 $\begin{bmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{bmatrix}$ 不变；而输入控制比特则从最初的 $\begin{bmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{bmatrix}$ 变成了 $\begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix}$。这种门的作用虽然受限于可视化工具难以平滑呈现状态跃迁，但数学证明明确指出了这种矢量的改变，测量结果严格遵循预测给出了 $01$。 最后一种情况是否定函数（先经过 CNOT 门，紧接着接一个比特翻转门 NOT）。系统向量在酉圆上完成变换，再经过 Hadamard 门后处理，最终的测量值同样锁定为 $01$。至此，预言机所涵盖的四种函数全部验证完毕：两个常数函数测量得到 $00$，两个变量函数测量得到 $01$。主讲人兴奋地宣布：“Single query, outperformed classical computation, pretty nuts, right?”（单次查询就击败了经典计算，相当疯狂，对吧？）量子计算仅凭一次黑盒调用便解决了经典计算机至少需要查询两次才能判定的问题。 ```mermaid flowchart LR accTitle: Deutsch Algorithm State Transformation accDescr: Flowchart illustrating the state transformations for constant and variable functions in Deutsch's algorithm. subgraph Input["输入初始化"] Q["|0> 与 |1>"] --> H["Hadamard 变换"] end subgraph Oracle["多伊奇预言机黑盒"] H --> F1["常数函数: 无 CNOT / 仅 NOT"] H --> F2["变量函数: 含 CNOT / CNOT + NOT"] end subgraph Measure["后处理与测量"] F1 --> P1["测量结果: 00 (常数)"] F2 --> P2["测量结果: 01 (变量/平衡)"] end ``` ### [53:23](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=3203s) 核心直觉：对称性中和与算法演进历史 从直觉层面来看，多伊奇算法之所以能够战胜经典计算机，核心在于同类内部差异被“中和”，而类间差异被“放大”。常数 0 与常数 1 之间、恒等与取反之间，唯一的类内差异仅是一个否定门（NOT gate）；但在特定的叠加态下，否定门的作用被抵消，其影响力被最小化。相反，变量函数与常数函数之间的本质差异是是否存在 CNOT 门，通过叠加态的设计，CNOT 门对相位的影响被显著放大。这正是量子计算的强大之处：通过构建特定的叠加态，计算者能够人为调控各种逻辑门所施加的作用。 尽管这个单比特的多伊奇问题看起来极其人工合成（Contrived），但它拉开了一系列量子飞跃的序幕： 1. **多伊奇-乔萨算法（Deutsch-Jozsa Algorithm）**：1990 年代推广至 $n$ 位输入，函数要么是常数函数（全部映射到同个值），要么是平衡函数（输出 0 和 1 各占一半）。经典计算在最差情况下需要尝试 $2^{n-1} + 1$ 次，而量子计算依然仅需单次查询，达成了真正的指数级加速。 2. **西蒙周期性问题（Simon's Problem）**：在预言机黑盒模型中寻找函数的隐藏周期，为后续算法奠定了框架。 3. **肖尔算法（Shor's Algorithm）**：彼得·肖尔（Peter Shor）借鉴了寻找周期的思想，并断言：“We can use this to factor large integers.”（我们可以用它来分解大整数。）大数质因数分解算法的提出彻底引爆了密码学界与整个量子计算领域。 现场观众随即提问：微软官网上曾有文章宣称“量子计算机能将运行几十亿年的程序缩短到一周内完成”，是否指的就是这种加速？主讲人确认了这一点，指出如果一个问题输入规模达到 80 位，在经典计算机上尝试 $2^{80}$ 种组合确实需要花费数十亿年，而在量子计算机上可能只需极短的时间。针对观众关于“判定函数是否具备某项性质在现实中有何价值”的疑问，主讲人解释道，正如理论计算机科学中判定问题往往与求解问题等价，肖尔算法正是通过构造判定整数是否存在某种周期结构，进而实现了高效的大数分解。 ### [58:00](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=3480s) 无法因式分解的数学真相：量子纠缠 在梳理完经典计算的线性代数建模、量子比特、叠加态、Hadamard 门以及多伊奇预言机后，演讲进入了进阶主题：量子纠缠（Quantum Entanglement）与量子隐形传态（Quantum Teleportation）。 ```mermaid flowchart TD accTitle: Bell State Generation Circuit accDescr: Circuit showing the Hadamard gate and CNOT gate creating a Bell entangled state. Q0["|0> (控制比特)"] --> H["Hadamard 门"] --> CNOT_Ctrl["CNOT 控制端"] Q1["|0> (目标比特)"] ----------------------> CNOT_Tgt["CNOT 目标端"] CNOT_Ctrl --> BellOut["纠缠态: 1/√2 (|00> + |11>)"] CNOT_Tgt --> BellOut ``` 许多科普文章习惯用糟糕的隐喻来解释纠缠，而用严密的线性代数能够揭示纠缠的真实面貌：**当一个复合系统的乘积态（Product State）无法因式分解为各个单比特状态的张量积时，这些量子比特便处于纠缠态。** 考虑著名的贝尔态（Bell State）向量： $$\begin{bmatrix} \frac{1}{\sqrt{2}} \\ 0 \\ 0 \\ \frac{1}{\sqrt{2}} \end{bmatrix}$$ 若假设它可以被分解为两个单比特 $\begin{bmatrix} A \\ B \end{bmatrix} \otimes \begin{bmatrix} C \\ D \end{bmatrix}$，则必须同时满足方程组： - $A \times C = \frac{1}{\sqrt{2}}$ - $A \times D = 0$ - $B \times C = 0$ - $B \times D = \frac{1}{\sqrt{2}}$ 由 $A \times D = 0$ 可知 $A$ 或 $D$ 必有一者为 0。但若 $A = 0$，则 $A \times C = 0$，与第一式矛盾；若 $D = 0$，则 $B \times D = 0$，与第四式矛盾。因此该方程组无解。主讲人指出：“They have no individual value, their value only make sense together, they're called entangled.”（它们没有各自独立的数值，它们的数值只有结合在一起才有意义，这被称为纠缠。）物理上，测量该系统有 50% 的概率塌缩为 $|00\rangle$，50% 的概率塌缩为 $|11\rangle$，两个量子比特呈现出高度协同。而在硬件中制备纠缠极其简单：仅需将两个初始为 $|00\rangle$ 的比特中的最高有效位送入 Hadamard 门，再将其作为控制位接入 CNOT 门即可。 - **超远距离验证**：中国在墨子号量子科学实验卫星项目中，成功实现了地球与太空轨道卫星之间的量子纠缠分发，在巨大空间尺度上验证了两端测量结果的一致性。 - **超越光速的协同塌缩**：2013 年的一项实验中，研究人员将纠缠的量子比特相隔遥远距离，借助原子钟实现纳秒级的高精度同步测量。两处测量的时间差极短，光信号往返所需的时间比该测量间隔慢了上万倍。数据表明纠缠塌缩绝非依靠电磁辐射或经典信号传递，它在测量发生的瞬间即刻协同完成。 ### [01:01:45](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=3705s) 隐变量理论的破灭与“协同而非通信” 讲者指出，面对量子纠缠，人们最直观的反应往往是：“纠缠发生时，两个量子比特只是提前商量好了之后要怎么做而已，对吧？”但这种常识直觉在物理学上被称为“隐变量理论”（Hidden Variable Theory）。这与单个处于叠加态的量子比特相同：它并不是暗地里已经是 $0$ 或暗地里已经是 $1$，而是二者兼具。讲者提到，虽然本讲座不会推导具体数学证明，但物理学家约翰·贝尔（John Bell）已经通过严谨论证指出，如果隐变量理论成立，将会导致极度诡异且自相矛盾的推论，因此该理论是站不住脚的。宇宙的实际运作机制就是如此：纠缠粒子之间能够以超越光速的方式协调一致。 这立刻引出了爱因斯坦一生中最感焦虑的问题：难道光速作为宇宙速度极限的法则被打破了吗？局域性（locality）难道真的失效了？讲者强调，这里存在一个至关重要的限定条件：“超光速协同是可以的，但超光速通信绝对不行；信息是无法被超光速传递的。”讲者举例说明：如果将两个量子比特纠缠，两人各持一个并分别前往宇宙两端，当一方观测并坍缩自己的量子比特时，唯一能知道的只是对方的量子比特也同时发生了坍缩，且对方测量时会看到相同的结果。但在这一过程中，没有任何有效信息能够从一端传递到另一端。因此，超光速协同（Coordination）是被允许的，而超光速通信（Communication）绝不可能发生。 ```mermaid flowchart LR accTitle: 超光速协同与通信的区别 accDescr: 展示纠缠量子比特在宇宙两端观测时只能共享关联随机数，而无法超光速传递有效信息。 subgraph AliceEnd["观测端 A（爱丽丝）"] A["纠缠量子比特 A"] -->|"测量坍缩"| M1["获得随机结果 (0 或 1)"] end subgraph BobEnd["观测端 B（鲍勃）"] B["纠缠量子比特 B"] -->|"瞬时协同坍缩"| M2["获得相同测量结果 (0 或 1)"] end A -.->|"瞬时超光速关联（无信息载荷）"| B M1 x-.-x|"无法传递任意数据（因果律保持成立）"| M2 ``` - 约翰·贝尔（John Bell）证明了局域隐变量理论不可能解释量子力学的预测，否定了“粒子提前决定好状态”的假设。 - 讲者直白地揭示了人类语言描述量子现象的局限性：“除了数学本身，我试图向你们描述的任何东西从根本上来说都是谎言（Anything I try and tell you is fundamentally a lie, except for the math）。” --- ### [01:03:50](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=3830s) 测量判定、因果律与纠缠现场辩论 现场观众随即就测量与坍缩机制展开了一系列深入追问。一名观众提问：如果测量了一个量子比特，是否意味着另一个量子比特立刻坍缩？讲者确认：“是的，当你测量其中一个时，它会瞬间使另一个坍缩。”随后另一位观众敏锐地指出，如果量子比特坍缩了，远端是否可以通过某种量子计算手段探查出它“是否已经处于坍缩态”，从而利用坍缩作为一种超光速同步信号？讲者断然否定了这一设想：任何试图探查量子比特是否处于叠加态的操作本身，都会直接导致其坍缩。 当观众追问背后是否有直观解释时，台下有人打趣搬出了物理学界的著名格言：“闭嘴，老老实实计算去吧（Shut up and calculate）！”讲者笑称这确实是个绝佳的避风港。讲者鼓励大家拿纸笔自行演算，便会发现根本设计不出任何操作序列能在不破坏态的前提下探测到坍缩的先验发生。针对观众“这是否破坏了因果律”的困惑，讲者重申这绝不违反因果律：因为通信的严格定义是一方持有特定比特（$0$ 或 $1$）并能将其传给另一方。而在纠缠测量中，双方所做的仅仅是以超光速方式共同生成了一组完全一致的“真随机数”，没有一方能够通过自己的测量动作把任何有效控制信号输入到对方的参考系中以改变那里的因果链。 - 观众试图利用量子线路探测态的坍缩历史，但在量子力学中，探测与坍缩无法解耦。 - “超光速协同”不破坏相对论因果律，因为任何单方的测量结果在本地看来都是纯粹均匀的随机分布，不携带任何远程发送者编码的信息。 --- ### [01:07:20](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4040s) EPR 佯谬的反转：从质疑工具到物理现实 现场观众提问：“如果纠缠不能用于传递信息，那量子纠缠的实际应用价值究竟是什么？”讲者表示这正好引出了接下来的量子隐形传态主题，但在展开之前，他分享了一则物理学史上的著名轶事。 人们常听到的“鬼魅般的超距作用（spooky action at a distance）”正是爱因斯坦用来讽刺量子力学的用语。爱因斯坦、波多尔斯基（Podolsky）和罗森（Rosen）三位物理学家提出了著名的 EPR 佯谬（EPR paradox）。他们最初推导出量子力学公式必然会导致纠缠态这种超距效应，以此论证说：“这显然极其荒谬，因此量子力学本身肯定是有缺陷的垃圾理论。”然而历史充满了戏剧性，后来的实际物理实验（例如 2013 年等一系列远距离粒子纠缠验证实验）无情地证明宇宙的底层构造确实就是如此不可思议——局域实在性确实被打破了。讲者感叹道：“EPR 佯谬最初被设计出来是为了让量子力学声名狼藉，结果却成了揭示宇宙真正运行方式的核心理论，这真是一段绝妙的历史。” - 爱因斯坦、波多尔斯基和罗森（EPR）提出纠缠现象本意是证伪量子力学的完备性。 - 现代物理实验已彻底证实局域实在性的破缺，反向确立了量子纠缠作为物理现实的基石地位。 --- ### [01:08:26](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4106s) 概率验证与量子隐形传态、不可克隆原理引入 在进入下一主题前，一名观众对单次测量的概率基础提出了认识论层面的哲学质疑：如果单次测量只能看到一个确定的结果（比如坍缩为 $1$），凭什么反向断定它坍缩为 $0$ 的概率也是有效的？讲者解释称，科学验证依赖于将实验重复成千上万次，从而在统计图表上清晰地观察到双端量子比特坍缩为 $00$ 或 $11$ 各占 50% 的对称分布；随后讲者更向观众保证，稍后会在一台真实的量子计算机上现场运行这段纠缠程序供大家亲眼见证。 紧接着，讲者正式切入量子纠缠的重大核心应用——量子隐形传态（Quantum Teleportation）。讲者吐槽道，大家平时在科普文章中看到的解释基本都是“彻头彻尾的垃圾，完全不知所云（complete trash, made no sense at all）”，但掌握了线性代数与纠缠机制后，其底层逻辑将变得极其清晰。量子隐形传态的本质，是借助一对纠缠量子比特作为“量子桥梁”，将一个任意的、未知的未知量子比特状态跨越时空完整传输到另一个位置。在展开线路细节之前，讲者特意强调了量子信息领域一道不可动摇的物理铁律——不可克隆原理（No-Cloning Theorem）：“你可以转移量子比特状态，可以把它剪切并粘贴过去，但你绝对不能复制它；你无法对一个量子比特状态执行复制和粘贴，你永远无法克隆它。” - **量子隐形传态定义**：利用纠缠对作为信道，将未知的任意单量子比特量子态从一处无损传递到另一处。 - **不可克隆原理（No-Cloning Theorem）**：量子态只支持“剪切-粘贴”（状态转移），绝对禁止“复制-粘贴”（克隆未知量子态）。 ### [01:11:05](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4265s) 量子隐形传态协议与经典通信限制 演讲者接着阐述了不可克隆定理（No-Cloning Theorem），指出要证明这一物理定律其实相当简单——只需证明任何此类克隆操作在数学上都不是可逆矩阵或自反的（即不是其自身的逆），但他在此不会展开严谨推导。随后，演讲者指出了量子隐形传态中至关重要的一点：尽管隐形传态利用了纠缠态这种看起来超光速的物理现象，但整个协议本身绝对无法实现超光速通信。因为隐形传态的成立，要求发送方必须通过经典信道传输两个经典比特。 演讲者用通俗的比喻解释道：“所以，如果我要把我的量子比特隐形传态给你，除了我们之间要拥有一对纠缠的量子比特外，我还必须向你发送两个比特的信息。”（“So, if I'm teleporting my qubit to you in addition, to us having an entangled qubit pair, I also have to send you two bits of information and we'll show why that is in the next slide.”）这意味着无论纠缠效应多么瞬时发生，信息的完整重构仍然被经典光速所限制。 ```mermaid flowchart TD accTitle: Quantum Teleportation Protocol accDescr: Circuit flow illustrating quantum teleportation between Alice and Bob using an EPR pair and two classical bits. subgraph Pre["纠缠源准备"] EPR["制备纠缠对 (EPR 对)<br/>Qubit A 与 Qubit B 处于纠缠态"] end subgraph Alice["Alice 端操作"] T["待传态 |ψ⟩ (Qubit T)"] BellEntangle["将 Qubit T 与 Qubit A 进行 CNOT 纠缠"] HGate["Qubit T 穿过 Hadamard 门"] Measure["测量 Qubit T 与 Qubit A<br/>坍缩为 2 个经典比特"] T --> BellEntangle EPR --> BellEntangle BellEntangle --> HGate HGate --> Measure end subgraph Classic["经典信道"] Bits["传输 2 个经典比特 (无法超光速)"] Measure --> Bits end subgraph Bob["Bob 端重构"] Recv["接收经典比特并校正 Qubit B:<br/>根据测量结果选择性应用 X 门 / Z 门"] Target["完美还原态 |ψ⟩"] Bits --> Recv EPR --> Recv Recv --> Target end ``` ### [01:11:44](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4304s) 隐形传态电路图与 EPR 对的“预配”消耗 演讲者调出完整的隐形传态电路图。待传输的量子比特记为 $T$（其状态为任意未知的通用量子态 $|\phi\rangle$），另外有两个初始状态皆为 $|0\rangle$ 的量子比特 $A$ 和 $B$。电路首先对 $A$ 和 $B$ 执行纠缠操作（Hadamard 门加 CNOT 门），随后将纠缠对拆分开：$A$ 留在 Alice 手中，$B$ 则交给 Bob。此时 Alice 和 Bob 各持有一个纠缠体系的一半。紧接着，Alice 将自己手中待传输的量子比特 $T$ 与其持有的量子比特 $A$ 进行纠缠，构建出一个不可因式分解的三量子比特联合纠缠系统，并将其中的量子比特 $T$ 送入 Hadamard 门。 随后，Alice 对手中所持有的两个量子比特执行测量，使量子态坍缩并输出两个经典比特。Alice 把这两个经典比特发给 Bob： - 第一个经典比特的测量结果决定 Bob 是否需要对其持有的量子比特 $B$ 实施 $X$ 门（即比特翻转门，Bit-Flip Gate）； - 第二个经典比特的测量结果则控制 Bob 是否需要实施 $Z$ 门（即相位翻转门，Phase-Flip Gate）。 演讲者展示了 $Z$ 门的矩阵表达，并指出若两个比特都是 0，Bob 就什么门都不用做。完成这套操作后，Bob 手里的量子比特便会神奇地转变成 Alice 原本要传输的量子态。 针对现场可能出现的疑惑——“既然本来就要给 Bob 一个量子比特，Alice 为什么不直接把量子比特寄给 Bob 呢？”演讲者给出了极为形象的工业化思路：通信双方完全可以在前期一次性预先纠缠数十亿个量子比特（称为 EPR 对半体，EPR Halves），然后通过传统物流邮寄或者铺设光纤，分别存放在 Alice 和 Bob 的大型仓库中。未来每当 Alice 想要向 Bob 发送一个未知量子比特时，只需在本地消耗掉一个预存的 EPR 对并打通两比特经典通信。“在那个时刻，那个 EPR 对就已经坍缩了，无法再次使用，它是一种不可再生资源。”（“And at that point, that EPR pair has been collapsed can no longer be used so it's non-renewable resource.”） ### [01:14:45](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4485s) 经典模拟的指数爆炸与物理实现的工程瓶颈 在进入下一步之前，演讲者特别强调了量子计算模拟的本质障碍。外界经常听说用经典计算机模拟量子计算会遭遇指数级减速或指数级内存暴增，其根本原因正在于量子纠缠：一旦两个量子比特发生纠缠，经典计算机就无法再将它们当作两个独立的二维向量存储，而必须在内存中完整维护包含所有基底的张量积（Product State）。“所以，如果 $N$ 个量子比特纠缠在一起，你就必须在内存中保留一个大小为 $2^N$ 的向量。这就是为什么在经典计算机上模拟量子计算机需要指数级的内存。”（“So, if N qubit with become entangled you have to keep a vector of size two to the N you have to keep in memory. And that is why, it takes exponential memory to simulate a quantum computer on a classical computer.”） 随后演讲者梳理了后续学习路径与推荐读物： - **进阶算法**：将单比特扩展至多比特维度的 Deutsch-Jozsa 算法、求解函数隐藏周期的 Simon 周期性问题、破译 RSA 的 Shor 算法、无序搜索加速的 Grover 算法以及相对简单的量子密钥分发（Quantum Cryptographic Key Exchange）。 - **量子纠错（Quantum Error Correction）**：由于微观量子系统极度脆弱，一束宇宙射线扫过都可能破坏运算，必须依赖高冗余纠错。理论上仅需 5 个物理量子比特即可纠错保护出 1 个逻辑量子比特；但在现实工程中，为了达到接近 100% 确定性的高质量逻辑比特，往往需要动用 100 到 200 个物理量子比特去纠错抵消噪声。“所以这必须牢记在心，当我们看到 Google 发布 30 个量子比特的计算机时，其意义或许并没有我们想象的那么大。我们可能最终只能做出两到三个真正高质量的逻辑量子比特。”（“When we see Google's coming out with a 30 qubit computer that maybe doesn't mean as much as we'd hope. We've made only guys like two or three really high-quality qubits.”） - **教材推荐**：首推与本次讲座同名的书籍《Quantum Computing for Computer Scientists》；其次提到了 David Mermin 撰写的教材，演讲者笑称其是一部“绞肉机式的教科书”（meat grinder of a textbook），推导跳步严重且以纯粹的符号操作为主，缺少具体的向量与矩阵展示；另外还有微软图书馆藏的《Quantum Computing: A Gentle Introduction》以及微软量子开发套件（Microsoft Quantum Development Kit）官方文档。 ### [01:17:35](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4655s) 对量子计算实现的怀疑论：Gil Kalai 的噪声假说 在进入实际代码演示之前，演讲者客观地引入了学术界内部对量子计算可行性的反思。他提到近期《Quanta Magazine》上刊登的一篇关于以色列数学家吉尔·卡莱（Gil Kalai）的专访。卡莱坚持认为在物理现实中根本不可能造出真正可用的通用量子计算机。 卡莱的核心论点简化后在于：量子系统内部的噪声并不随规模呈线性增加，而是随着纠缠量子比特数量的增长而呈指数级飙升。如果物理噪声以指数级爆发，运算过程就会不可避免地在执行中途频繁坍缩，大规模纠错码机制也将彻底失效。演讲者流露出坦率的担忧与无奈：“所以，如果这种情况真的发生了，我会非常伤心。我会觉得连整个宇宙都在和我作对。如果我们无法实现量子计算的红利，那真的是一种宇宙级别的遗憾。但无论如何，你无法跟宇宙的客观规律争辩。”（“And so, I'll be very sad if this happened. I'd feel like the universe is against me. It'd be really, it'd be very sad if we could not realize the benefits of Quantum Computing, like cosmetically sad. But anyway, you can't argue with the universe and yeah you can read that article for some skepticism.”） ### [01:18:40](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4720s) Q# 编程演示与 IBM Quantum Experience 实机介绍 演讲者切换屏幕进行实操演示，首先展示了基于 F# 语法风格的微软 Q# 语言所编写的 Deutsch Oracle（多伊奇神谕）问题实现： - 核心判定函数命名为 `IsBlackBoxConstant`，该函数接收一个黑盒操作并返回一个布尔值（`Bool`），用于判断黑盒函数是常数函数还是平衡函数。 - 内部流程严格遵循课件算法：通过语言原语分配两个量子比特并分别命名为输入与输出，全部初始化清零；预处理阶段翻转输出比特并让二者均穿过 Hadamard 门；送入给定的黑盒进行评估；输出再次穿过 Hadamard 门并测量。若测量结果为 1，则断言该黑盒为常数（Constant）。 - 演讲者在代码中定义了四种经典黑盒测试用例： - `ConstantZero`：完全不做任何操作； - `ConstantOne`：对输出比特执行翻转操作； - `Identity`：将输入作为控制位、输出作为目标位执行 CNOT 门； - `Negation`：执行相应的反转判定逻辑。 - 运行驱动程序（Classical Driver）后，控制台在量子模拟器上依次打印出判别结果： - `IsConstantZero`：`True` - `ConstantOne`：`True` - `Identity`：`False` - `Negation`：`False` 程序准确无误地运行完毕，演讲者欣慰地总结道，他们亲手编写了 Deutsch Oracle 并成功在真实模拟器上得到了验证。紧接着，演讲者切换到当天的压轴环节——IBM Quantum Experience 网页界面，准备在由 IBM 实际搭建的真实物理量子计算机云平台上运行纠缠实验。 ### [01:20:49](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4849s) 云端真机演示：在 IBM 量子计算机上构建纠缠电路 讲师在现场打开了 IBM 的云端量子计算平台（IBM Q Experience），展示如何直接在网页界面上拖拽量子逻辑门来编写量子电路。这台机器虽然只有 5 个量子比特（Qubit），但允许全世界的研究者和开发者将编写好的量子线路直接发送给真实的物理量子计算机执行。讲师计划在现场观众面前实时演示量子纠缠（Bell 态）的生成。按照纠缠电路的设计步骤，首先需要在一个量子比特上放置一个阿达马门（Hadamard Gate），随后需要连接受控非门（CNOT Gate）。但在实际操作中，量子计算机的物理布线存在拓扑约束，两个比特之间如果缺乏直接的物理耦合就无法施加 CNOT 门。讲师尝试了几种连线组合，终于成功在两个物理相邻的比特间建立了 CNOT 连接。 在完成逻辑门配置后，讲师提醒道，千万不能忘记放置两个测量门（Measurement Gates），分别对纠缠后的两个量子比特进行采样读取。按照理论预期，测量结果应该绝大多数集中在 $|00\rangle$ 和 $|11\rangle$。虽然系统支持直接读取先前的缓存结果，但讲师为了现场效果决定发起一次全新的实时任务执行。他生动地向大家描绘正在后台发生的一幕：“你们可以想象一下，此时此刻在 IBM 研究实验室深处，置身于运行温度仅略高于绝对零度的稀释制冷机中，真实的量子比特正在被纠缠并测量数千次，只为了给我们带来一点视觉体验，这真的很酷。”由于云端排队，系统显示任务处于挂起（Pending）状态，需要等待数分钟才能返回数据。 ```mermaid flowchart LR accTitle: Bell State Circuit on Real Hardware accDescr: 量子纠缠电路从初始化、门操作到云端制冷机硬件执行的流程图。 subgraph Circuit ["量子电路配置"] Q0["|0⟩ (比特 0)"] --> H["Hadamard 门 (H)"] Q1["|0⟩ (比特 1)"] --> CNOT_T["CNOT 目标端"] H --> CNOT_C["CNOT 控制端"] end subgraph Execution ["云端真机执行"] CNOT_C --> M0["测量比特 0"] CNOT_T --> M1["测量比特 1"] M0 & M1 --> Cloud["IBM 稀释制冷机\n(接近绝对零度)"] Cloud --> Results["输出统计结果\n(|00⟩ 与 |11⟩ 占主导)"] end ``` ### [01:22:56](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4976s) 观众问答：量子卫星、激光传输与拓扑量子计算的噪声挑战 在等待 IBM 真机返回结果的间隙，讲师回答了现场观众的一连串提问。有观众提到之前讲过的空间卫星纠缠实验，好奇人类目前是否已经掌握了长时间存储量子比特的技术，因为直觉上纠缠态极易衰退退相干。讲师对此予以澄清：人类目前在长效量子存储方面依然非常吃力，量子比特的寿命相当短暂；中国发射的“墨子号”量子科学实验卫星并不是把量子比特长时间装在卫星里，而是利用地面发射的激光将 EPR 纠缠对中的一半光子实时射向太空，随后再利用这半个纠缠对完成了地面到卫星的量子隐形传态（Quantum Teleportation）。 另一位观众随后抛出了更犀利的技术难题：最近有数学家（指 Gil Kalai 等学者）发表论文指出，量子系统中的噪声增长速度可能呈指数级上升，那么拓扑量子计算机（Topological Quantum Computer）是否能抵抗这种噪声？讲师客观分析表示，任何架构的量子计算机都会遭遇噪声困扰；尽管微软所押注的拓扑量子计算在抗噪性能上理论上优于 IBM 的超导路线，但如果底层物理真的存在某种指数级噪声屏障，拓扑体系同样无法幸免。讲师坦言这一现状让人感到忐忑，并做出展望：“因此，未来几年对于量子计算来说真的是决定生死的关键时期，因为我们现在开始具备能力去建造触碰到这一指数限制（如果它真的存在的话）的计算机了。”他补充道，如果像 Google 这样的机构在短期内无法成功演示“量子霸权”（Quantum Supremacy），整个领域的信心可能会受到很大冲击。 - 空间量子通信并非依赖脆弱的静态量子存储，而是通过空间激光链路高速传输纠缠光子实现隐形传态。 - 拓扑量子计算凭借非阿贝尔任意子的辫子拓扑特性提供硬件级容错保护，但在极端规模下依然面临指数级噪声假设的检验。 - 业界正处于从几十量子比特向可验证“量子霸权”冲刺的临界点，相关工程验证将直接检验量子计算理论在物理世界的可行性。 ### [01:24:56](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=5096s) D-Wave 量子退火争议与实际优化应用 现场话题随后延伸到了商业量子设备与不同技术路线上。有观众询问 Google 到底将量子理论用于哪些具体领域，以及加拿大公司 D-Wave 的机器到底是怎么回事。讲师解释道，很多人对 D-Wave 持有争议，甚至外界有声音怀疑他们“非常像骗子、并不是真正的量子计算”，但更准确的技术界定是：D-Wave 采用的是完全不同的计算范式——量子退火（Quantum Annealing）。它并不是通用的门模型量子计算机，而是专门用于求解组合优化问题。 讲师透露，自己的经理目前就在使用 D-Wave 的模拟器研究网络路由（Network Routing）等图论问题。在量子退火模型下，可以将网络拓扑图映射为物理系统的能量曲面，使求解网络中的最低能耗路径等价于寻找图上的最低成本路径（类似于开放式最短路径优先 OSPF）。针对观众提出的“传统计算机是否比 D-Wave 跑得更快”的疑问，讲师表示两者的表现目前可能处在旗鼓相当的水平；特别是在近年来机器学习蓬勃发展的驱动下，经典数值优化算法（如在高维曲面上寻找极值点的方法）取得了极大的进展，通用经典优化与专用量子退火之间的胜负依然是一个处于激烈竞争中的研究课题。 ### [01:27:06](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=5226s) 实验结果解读与总结：量子纠缠的真实存在 由于云端真机的队列执行依然在等待中，讲师为了不耽误时间，切换界面调出了此前在同一线路上预先运行并缓存的真实实验数据集。结果柱状图直观地展示了物理实测的数据分布：虽然该批次测试使用的具体量子比特编号与刚刚拖拽的略有不同，但输出统计中 $|00\rangle$ 和 $|11\rangle$ 占据了压倒性的绝大多数比例。同时，图表中也能清晰地看到有极少量处于中间态的 $|01\rangle$ 和 $|10\rangle$ 分布。讲师指出，这些非预期的状态正是物理系统存在门误差与测量噪声的铁证，表明系统无法像理想数学模型那样百分之百完美运作，但这种压倒性的相关性已经确凿无疑地证明了纠缠态在物理硬件上的真实存在。 在全场讲座的尾声，讲师总结道，量子计算的核心并不神秘，其底层逻辑完全可以通过基础的线性代数与矩阵运算来理解。他真诚地对全场听众表示：“这并不是什么疯狂天才才能涉足的科学，这是非常亲民、易于理解的科学。”讲师希望大家在听完这场抛开虚幻科普隐喻的报告后，能够消除对量子概念的困惑，建立起清晰严谨的计算机科学视角，并在未来继续探索这一前沿领域。整个分享在全场热烈的掌声中正式落下帷幕。 ## Notable quotes > [01:08:26](https://www.youtube.com/watch?v=F_Riqjdh2oM&t=4106s) 你可以转移量子比特状态，可以把它剪切并粘贴过去，但你绝对不能复制它；你无法对一个量子比特状态执行复制和粘贴，你永远无法克隆它。 ## Mentioned Microsoft Research, Q#, Microsoft Quantum Development Kit, D-Wave, Google, Intel, IBM, IBM Quantum Experience, David Mermin, David Deutsch, Peter Shor, Gil Kalai, John Bell, Albert Einstein, Boris Podolsky, Nathan Rosen, EPR paradox, Shor's Algorithm, Grover's Algorithm, Deutsch-Jozsa Algorithm, Simon's Problem, 墨子号量子科学实验卫星, Accelerando, Quanta Magazine, Quantum Computing for Computer Scientists, Quantum Computing: A Gentle Introduction ## Video description This talk discards hand-wavy pop-science metaphors and answers a simple question: from a computer science perspective, how can a quantum computer outperform a classical computer? Attendees will learn the following: - Representing computation with basic linear algebra (matrices and vectors) - The computational workings of qbits, superposition, and quantum logic gates - Solving the Deutsch oracle problem: the simplest problem where a quantum computer outperforms classical methods - Bonus topics: quantum entanglement and teleportation The talk concludes with a live demonstration of quantum entanglement on a real-world quantum computer, and a demo of the Deutsch oracle problem implemented in Q# with the Microsoft Quantum Development Kit. This talk assumes no prerequisite knowledge, although comfort with basic linear algebra (matrices, vectors, matrix multiplication) will ease understanding. See more at https://www.microsoft.com/en-us/research/video/quantum-computing-computer-scientists/ [Source](https://www.youtube.com/watch?v=F_Riqjdh2oM)

[68:26] 你可以转移量子比特状态，可以把它剪切并粘贴过去，但你绝对不能复制它；你无法对一个量子比特状态执行复制和粘贴，你永远无法克隆它。

[68:26] Speaker: Anything I try and tell you is fundamentally a lie, except for the math. [68:26] Speaker: You can transfer qubit states so you can cut and paste them, but you cannot copy them, you cannot copy and paste a qubit state, you cannot clone it.

[0:04] >> Welcome to Quantum Computing for Computer Scientists. [0:08] Happy Valentine's Day. [0:10] We will learn about this most romantic of [0:12] all subjects, Quantum Computing. [0:14] This is a talk aimed at Computer Scientists. [0:18] We will not go over very much, [0:19] if any, physics during this talk. [0:21] We won't go like for the Double-Slit [0:22] Experiment or Uncertainty Principle. [0:23] We're not learning about any of that. [0:26] We're going to cover the Computation Model [0:28] which you'll all be finding, [0:30] fairly intuitive I think, is a state machine. [0:32] And we will run a Quantum Algorithm on it, [0:35] show that it outperforms a classical Computation Model, [0:38] and then we'll end with some demos, [0:40] including a running program [0:42] in Q-sharp, Microsoft's quantum language. [0:45] This is the Gate Quantum Computation Model. [0:47] It looks a lot like the classical [0:49] Computation Model where you have bits, [0:50] and you send them through the logic gates, [0:52] and transformations are applied to them. [0:53] There's another Computation Model called [0:57] the Quantum Annealing Model [0:59] which is used by D-Wave, if you've heard of that. [1:01] That's something different from what [1:04] we'll be going over but [1:05] people think they might be equivalent. [1:07] The jury is still out on that. [1:08] Anyway, I'm sure you'll have a great time. [1:11] So, I'm sure all of you have [1:13] your reasons for being here but here are [1:15] three reasons I've come up with if you need some [1:18] additional convincing [1:19] why you should learn Quantum Computing. [1:21] The first is that quantum supremacy is [1:23] expected this year, this very year. [1:25] Quantum supremacy means we have [1:28] a real problem running on [1:30] a real quantum computer which in real-time, [1:32] runs faster than the same problem [1:33] on a classical computer. [1:34] So, Google has announced [1:36] they think they'll do it this year. [1:37] If they do, it's a really big thing. [1:39] So, it might be in your future. Who knows? [1:41] Five, 10 years, we could all be running [1:44] some really tricky problems on quantum computers. [1:47] So, we have lots of large companies, [1:49] Microsoft, Google, Intel, IBM, [1:51] they're all investing billions of dollars [1:52] in quantum computer developments. [1:54] There are lots of really exciting applications. [1:57] This is the one that everyone's [1:58] heard about, Shor's algorithm. [1:59] When this paper came out, it lit the world on fire. [2:02] People were like, "Wow, quantum computers could [2:03] actually have real economic impact." [2:05] We could factor RSA, [2:08] and undermine our global financial system, [2:10] which is pretty cool. [2:11] Here's one that programmers will I [2:13] think appreciate which is [2:15] we can search an unordered list in square root N time. [2:18] So, you think for an unordered list, [2:19] you have to check every element. That's ON. [2:21] You can just get a nice speed-up, [2:23] just square root n queries on a quantum computer, [2:25] which is pretty, pretty nifty, generally useful. [2:28] And here's the one which, I think, [2:29] probably is the best probability of changing the world. [2:32] Sorry, Programmers scroll and [2:34] search probably won't [inaudible] too much. [2:36] Which is, we might be able to have [2:38] an exponential speed-up in [2:39] simulating quantum mechanical systems. [2:41] So, things like drug design, [2:45] if you simulate like biological molecules [2:47] interacting, things like that, [2:49] it could massively speed [2:50] up a lot of our biological research, [2:52] and everyone talks about nitrogen fixation for this. [2:56] That's like part of the main Microsoft sales pitch. [2:59] But this is the one [3:00] that actually motivated me, the bottom one, [3:02] which it's, I think, [3:03] from talking to couple of you before the presentation, [3:05] we can also motivate you. [3:06] It's intellectually interesting, and it's [3:09] interesting because it's just [3:10] kind of outside my intuition. [3:12] Like I think all of us, at this point in our careers, [3:14] can basically look at any digital or mechanical system, [3:17] and have like a ballpark idea of how it works, right? [3:20] But if you look at a quantum computer, [3:21] like how can a quantum computer [3:23] outperform classical computation? [3:24] It doesn't make any sense. [3:25] Like there's no way [3:26] I could even start to guess how it would work. [3:28] And so, I really wanted to learn it. [3:31] And I think there's a reason for this, and this is [3:32] kind of getting a bit philosophical. [3:34] But our language, [3:36] our informal language that we use [3:38] developed in very classical world. [3:39] It is simply not equipped to deal with the quantum world, [3:43] and this is why any pop science article [3:44] you've read on quantum phenomena, [3:47] it doesn't really ring true. [3:49] All the metaphors, they don't really make [3:51] sense because we're trying to [3:53] express it in this language which [3:54] is developed in the classical world. [3:55] We need to learn [3:56] a new language which is the language of mathematics, [3:59] and that is the only thing which will actually let us [4:01] understand quantum mechanics is [4:02] to learn it mathematically. [4:04] All metaphors and analogies will lead you astray. [4:06] There's a famous quote here by a physicist [4:09] named David Mermin which is "Shut up and calculate", [4:13] with regard to quantum mechanics. [4:15] So, some grad students, [4:16] maybe they lean back in their chair and [4:17] they're like, "Oh, what does this all mean?" [4:18] Shut up and calculate. Just trust the math. [4:20] Math is the only thing which will not lead you astray. [4:23] Okay, here's how this presentation will break down. [4:26] First, we're going to learn how to [4:29] represent computation using super basic linear algebra, [4:31] matrices, vectors, matrix multiplication. [4:34] Then we will generalize that to learn about Qubits, [4:38] superposition, and quantum logic gates. [4:40] And finally, we will use all those tools we've developed [4:44] to go over the simplest problem [4:46] where quantum computer outperforms a classical computer. [4:48] This is called the Deutsche Oracle problem. [4:50] I mean, there are a bunch of problems, [4:50] but this is the simplest. [4:52] And finally, it'll be almost negligent to let you get out [4:57] of here without learning about Quantum Entanglement and [4:59] Teleportation just because with the tools we'll develop, [5:01] they're so easy to understand. [5:02] So, I'll have bonus topics, [5:04] and then we'll have some demos. [5:05] All right, let's get to it. [5:07] You'll become very, very familiar with these two vectors. [5:12] This is how we represent a 0 and a 1, [5:15] the two values of one bit in classical terms. [5:18] So, the top one, [5:20] it's just 1 over 0, and the bottom one is just 0 over 1. [5:24] You can also write them in that [5:25] weird angle bracket thing. [5:27] That's called Dirac Vector Notation. [5:30] So, you have a zero in there. That means [5:31] this is the value of that vector. [5:33] If you have trouble remembering this, [5:35] just think of it like an array indexed from 0, [5:39] and so, there's a [5:41] 1 in the 0th index, that means it's a zero. [5:43] There's a 1 in the first index, that means it's a 1. [5:46] Okay, everyone's fine with this? [5:48] You'll be very familiar with this by [5:49] the end of the presentation. [5:51] We're going to go over [5:54] matrix multiplication really quickly. [5:58] So, the way to [6:01] think about matrix multiplication, [6:03] just to review for you. [6:03] Most of you will have gone over this in your [6:05] Linear Algebra courses the first or second day. [6:08] So, if we have a matrix multiplied by a vector, [6:10] you kind of take this horizontal row, [6:12] and then flip it, and multiply it [6:14] point-wise with these vector values. [6:18] So, a times x, b times [6:19] y, and that's how you get the top one. [6:20] And you do the same thing in the bottom row. [6:22] C times x, d times y, [6:23] and you get a two vector. [6:25] The same thing happens with three-by-three matrix. [6:28] A times x, b times y, [6:31] c times z, and you get this matrix. [6:33] This vector, you can also multiply matrices together. [6:37] We won't really be doing much of that. [6:39] And there's a very special matrix called [6:42] the Identity Matrix which has zeros everywhere, [6:47] except for ones along the main diagonal, [6:49] and anything multiplied by the Identity Matrix is itself. [6:53] It's just like multiplying by 1. [6:54] In fact, usually, you refer to [6:55] the Identity Matrix by the symbol 1. [6:58] Now thankfully, for simplicity, [7:00] a lot of the matrices we'll be [7:01] using look a lot like this. [7:02] They're mostly 0s with just some 1s, [7:04] and you can notice, it's a nice rule of thumb, [7:06] that relative to the identity matrix, [7:08] this matrix has the middle two rows flipped, okay? [7:12] And that's actually the action it [7:14] has on anything it multiplies. [7:16] So, it flips the middle two rows. [7:18] It's a nice sort of rule of thumb [7:20] to remember how matrix multiplication works. [7:24] Does anyone have any trouble with this? [7:25] Because you really need to know [7:27] this in order to go ahead. [7:29] You got to know it. Okay, great. [7:32] Operations are actually, I'd like to make this a quiz. [7:35] Can anyone tell me what are [7:37] the four operations on one bit? There's four of them. [7:43] >>One bit. [7:45] >>One bit. [7:46] >>AND, OR, exclusive-or. [7:47] >> That's around two bits. [7:50] >>Not identity. [7:51] >>Identity not. [7:52] >>Set to 0, set to 1. [7:53] >>Set 0, set 1. There we go. [7:55] Good. Yes. So, we have identity, [7:57] just f of x equals x. [8:00] Negation fx equals not [8:02] x. Constant-0, it's always set to 0. [8:04] Constant-1, it's always set to 1. [8:05] You can see with a diagram how it kind of looks, okay? [8:09] And we can write these as matrices. [8:12] So, the identity is just the Identity Matrix. [8:16] This, remember, is our symbol for zero. [8:19] Identity multiplied by 0 is 0. [8:21] Identity multiplied by 1 is 1. [8:22] Here's negation. You flip it from 0 to 1, and 1 to 0. [8:28] Same thing for constant-0, constant-1. [8:31] So, I hope I've convinced you we can [8:33] represent very simple functions at least, [8:35] with matrices multiplied by our 0 and 1 vectors, okay? [8:41] And remember these four functions [8:44] because I will quiz you later on them. [8:45] They'll come back up. So, let's [8:49] talk about Reversible Computing. [8:50] Reversible Computing is a neat sort of buzzword. [8:52] It if you've read the popular sci-fi book Accelerando, [8:55] it talks about Reversible Computing, [8:58] and basically it means that if I tell you [9:00] the operation I did and the output of that operation, [9:03] you can always tell the input of that operation, [9:06] if the operation's reversible. [9:08] So intuitively, operations that just shuffle bits around, [9:13] like permute them, they are reversible. [9:15] But operations that erase [9:16] bits and then overwrite them are not reversible. [9:18] And in our previous slide, [9:21] identity and negation are both [9:23] reversible because I say the output is one, [9:26] and I put it through the negation gate. [9:28] That means the input was zero. You can always tell that. [9:30] But if I say the output was 1, [9:32] and I put it through the constant-1 operation, [9:34] you can't tell what the input was. [9:35] It's not reversible. It erases information. [9:38] And the nice thing about Quantum Computing, [9:40] which you're going to remember, [9:41] is that one of [9:43] the computers only use reversible operations. [9:45] Those are the only ones we care about. [9:47] So, the only operation we [9:48] actually care about on this slide is really negation. [9:50] Like also identity but it's the same as doing nothing. [9:53] A further fun fact about chronic computers is [9:58] they actually only use [10:00] operations which are their own inverses. [10:02] So, not only are they reversible but if you apply them [10:04] twice you'll just get back the same input value. [10:07] And we're going to go in a little, [10:09] this is kind of like going into pop science but whatever. [10:12] There's something called the Von Neumann Vander Limit, [10:16] which is the smallest amount of [10:18] energy physicists have calculated [10:21] is necessary for the simplest possible calculation, [10:24] which raises is non-reversible. [10:27] And reversible computing might [10:29] eventually lead us go beyond that limit, [10:31] more efficient than that theoretical limit. [10:34] Now, currently, processors needs [10:36] millions of times more energy [10:37] than the Von Neumann Vander Limit but, [10:39] you know, 5,000 years from now, who knows? [10:41] Pretty nifty. All right. [10:43] This is something you probably did not go over in [10:46] linear algebra but don't worry it's still pretty simple. [10:49] It's called the tensor product. [10:50] So if you have the tensor product of two vectors, [10:54] it's kind of like you take the second vector and you [10:57] tile it for each element in the first vector. [11:00] So, X0 gets its own copy and X1 gets its own copy. [11:04] And then, you multiply it out so you get eventually X0, [11:07] Y0, X0, Y1, et cetera. [11:10] It's maybe easier to look at this with real numbers. [11:14] Here we have one times three, [11:16] one times four, two times three, [11:18] and two times four to get this. [11:21] Here's how it looks like with three vectors. [11:25] You get this like giant array. [11:27] Don't worry about it too much. [11:28] And I'd like to point out [11:30] that if we use R0 and one values [11:32] you end up with a vector [11:35] which has a one in only a single position. [11:37] Okay. Does anyone have [11:39] any real trouble with this concept? [11:40] If I gave you two vectors you could [11:42] probably calculate the tensor product. [11:44] It's not entirely difficult. All right. [11:47] But, the final point animate leads [11:49] into how do we represent multiple classical bits? [11:53] And we represent them by their tensor product. [11:55] So, 00 remember we tensor, this is a zero symbol. [11:59] 0 tensor with 0 is this, [12:01] product state, we call it, [12:03] 01 is this product state 10 is this product state, [12:07] like 0 times 1, 0, [12:10] 0 time 0, 0, 1 time 1, 1. [12:13] One times 0, 0. Okay. And 11 [12:16] is this product state and similar [12:18] to just a single bit you can think of [12:20] this is an index in this vector array. [12:23] So, this is 0. There's a one [12:25] at the zero position. This is one. [12:27] There's value with the first position [12:30] coming from zero and, [12:32] this is two value of the second position, [12:33] three value of the third position. [12:35] This is the only time I will tenser [12:38] three bits together thankfully, because they us humus. [12:41] They grow exponentially in size but it works for this. [12:44] So, four is 100 you have 01234 is where the one bit is. [12:50] Okay. Yeah. So, we call this the product state. [12:52] We can always factor it out into [12:54] its individual states and [12:58] the product state of n bits [12:59] is a vector of size of two to the n. Here, [13:01] we see a sort of whisper [13:02] of the power of quantum computing in [13:03] this exponential term but [13:05] hold that thought, we'll get back to it. [13:06] So, we're going to learn a very important operation, [13:12] very fundamental to [13:13] reversible computing and quantum computing [13:14] is called CNOT or conditional not. [13:16] It operates on a pair of bits. [13:18] You designate one bit, [13:20] the control, bit the other bit is the target bit. [13:22] So, the control bit if it's one it flips the target bit. [13:26] If it's zero it leaves the target bit [13:27] alone and the control bit is always left alone. [13:30] So, if we have the most significant bit [13:33] of a 2-bit system as control, [13:34] the least significant bit is target, [13:36] then 00 since this is the most significant bit, [13:41] it's the target bit, and just goes to 00, 01 goes to 01. [13:44] Now, 10, since the control bit is [13:47] one maps to 11 because it flips the other bit, [13:50] and 11 since it again flips, [13:53] the target bit goes to 10. [13:56] And this matrix, you can actually kind of write it, [13:59] you see there's a sort of correspondence [14:01] here we flip the bottom two rows, [14:03] which is the identity matrix, [14:04] and this I claim [14:06] which I will show in the next couple slides, [14:07] will change our product states [14:10] according to the semantics of CNOT. [14:12] So, does everyone get the semantics here? [14:14] We have a control bit and a target bit, [14:15] control bit one, we flipped the other bit. Pretty good? [14:19] Now, this is a lot of math [14:21] but don't panic we're gonna go over step-by-step. [14:24] If we apply the CNOT gate to 10, [14:27] remember that this is the control bits one, [14:30] so we're going to flip the other bits, [14:30] so we expect it to go to 11. [14:32] Now, let's expand this out just step-by-step. [14:34] So,10 corresponds to this tensor product. [14:37] This is the matrix from the previous slide [14:40] and we're applying it to our product state. [14:42] Remember, it's just going to flip [14:43] the bottom two rows so we get to this product state, [14:46] which when we factor it out, [14:48] indeed gets us 11. [14:51] Now, let's do it with 11, same thing, [14:55] we have our familiar matrix, [14:57] multiply by this product state, [14:58] we go to here, which we factor into 10. [15:00] So, I hope I've convinced you at this point that we [15:04] can use matrices to represent [15:06] more interesting logical operations than just a bit flip. [15:09] Has anyone eventually, yes? [15:11] >> Is that factoring always [15:13] possible or practical for larger vectors? [15:15] >> It is practical, yes. [15:19] Not always possible, [15:21] which we'll get into [15:23] that when we get into quantum entanglement, [15:24] basically, but good question. [15:28] So, this is fine for everyone? [15:33] Nobody's lost in the gigantic equations here? [15:36] Okay. We're gonna go over 10 then, or sorry, 00. [15:40] So, the control bit 0 [15:41] that means we're going to leave [15:42] the other bit alone, right? [15:43] And we see that indeed [15:46] this is what we do and same with for 01. [15:49] Okay. So, everyone, well, [15:53] maybe familiar with how classical computers [15:55] are like real CPU's [15:56] there they're all built on the, sort of, [15:57] NAND gate, like everything is fundamentally built on NAND [16:00] and CNOT is kind of [16:02] the analogous NAND for reversible computing. [16:05] It's like a really basic thing that is used to build [16:08] up larger and more complicated logical statements. [16:11] So, I'm sure if I gave you a task, [16:13] like build some more complicated [16:15] logical formula with CNOT, [16:17] you'd probably be able to do it at this point, [16:18] you just like stick them all together [16:19] and eventually comes out. [16:22] I will note that it's not actually universal. [16:25] You can't make every logical function with the CNOT gate. [16:27] You need something called a Toffoli Gate, [16:29] but we won't see that in this presentation. [16:33] And we've learned everything we need to know about how to [16:36] use linear algebra to represent classical computation, [16:40] and we can now go on to quantum computing. [16:42] So, to recap, we [16:43] learned that we can represent classical bits [16:45] in vector form is 10 for 0 and 01 for 1. [16:48] We can represent operations on bits [16:51] by multiplications on their bit vectors. [16:54] We know that quantum computers only use [16:56] reversible operations and in [16:58] fact the operations are their own [16:59] inverses and multibit states, [17:01] we write is the tensor product of our single bit states. [17:04] Finally, learned about CNOT which is [17:07] a very fundamental gate [17:09] in reversible computing and quantum computing. [17:12] So, everyone's following along so far? [17:15] This is pretty simple, right? And it's not that bad. [17:18] Okay. Let's make the jump, qbits. [17:22] And I will surprise you, we've been learned [17:24] using qbits all along actually. [17:27] The cbits are just special cases of qbits. [17:32] And we represent the qbit in general [17:33] by a vector of two elements a, [17:35] b where a and b are complex numbers. [17:38] Don't worry. We'll only use [17:40] real numbers for this presentation. [17:41] We're keeping it simple. [17:42] Only using real numbers. And we have [17:44] the constraint that a squared plus b squared is one. [17:48] So, (1,0) and (0,1) fit this definition because [17:50] one squared plus zero squared is [17:52] one and zero squared plus one squared is one, right? [17:55] Now, here are some example qbit values. [17:58] This is one with which you'll become very familiar. [18:01] It is one over root two, one over root two. [18:03] Can anyone tell me what one over root two squared is? [18:06] >> One half. [18:07] >> One half exactly. [18:08] one half plus one half is one. So, this is a qbit. [18:11] What about one half and root three over two? [18:14] What's one half squared? One quarter. [18:16] So, one quarter plus three quarters is one. [18:19] Here's an interesting thing. [18:21] We can actually use negative numbers [18:22] now because the negative number [18:23] squared is a positive number. [18:24] So, negative one squared is one. [18:26] One plus zero is one. And the same thing here, [18:28] it's just the same as this first matrix, [18:30] but one of the values is negative. Pretty neat. [18:34] Not bad so far, right? [18:37] Okay, but you might say this is kind of like [18:40] saying that a qbit has a value which is not zero or one, [18:44] but actually both zero and one at the same time. [18:47] This is called superposition. [18:49] Everyone's probably heard of [18:50] the Schrodinger's cat being both alive and dead. [18:53] That's just like a pop science [18:55] the way of articulating this concept sort of. [18:58] And the interesting thing [19:00] about a qbit being in superposition, [19:02] it means we can kind of, [19:04] I want to really qualify this kind of compute with [19:07] the values of both zero and one at the same time, [19:10] which again is the sort of [19:11] whisper of some quantum speedup power. [19:14] Okay? Now, how this works is, [19:17] when we measure this qbit, [19:19] it collapses to our familiar values [19:22] of zero and one with some probability. [19:25] And this is what we usually do at the end of [19:27] a quantum computation to get the final result. [19:29] We send it through the measurement gate, [19:30] we see what the result is. [19:32] So, how the probability works is, [19:35] if you have a value (a, b), [19:36] it collapses to zero with probability [19:38] a squared mand one with probability b squared. [19:41] So, if we look at [19:44] our familiar qbit from previous slide, one over root two, [19:46] one over root two, it has [19:48] a one half chance of collapsing to zero, [19:50] and one half chance of collapsing into one. [19:52] It's like a coin-flip. Now, if [19:54] we just measure our classical qbit, [19:56] our classical cbits the (1,0) [19:59] has a 100 percent chance of collapsing to zero, [20:01] and (0, 1) has a 100 percent chance collapse into one. [20:04] So, it's sort of item put in that way. [20:07] And I found it useful here to [20:10] give people sort of physical [20:11] intuition about what we're doing, [20:12] what bit is or a qbit is. [20:15] If you've heard of polarization, [20:17] you've probably bought fancy sunglasses, [20:19] says that they're polarized. [20:20] So, polarization is actually sort of quantum phenomenon. [20:23] You can be polarized like this way or this way, [20:26] and your glasses will only be polarized a certain [20:29] way so only let light [20:31] polarized in this way through basically. [20:33] It turns out that qbits, [20:35] you can think of this, yeah, [20:38] a photon being polarized this way is a zero, [20:40] and photon being polarized this way is a one. [20:42] Superposition means it's actually like both, right? [20:45] So, it could actually go through both gradients. [20:48] And then if you measure it, [20:49] and a way to measure it is just to [20:50] fire it through grating and see whether it goes through, [20:53] then you can collapse it to zero or one. [20:55] So, that's our intuition [20:57] pinning this to a physical concept. [21:00] Of course, modern, we [21:01] found that photons actually make very, [21:02] very poor qbits, they tend to collapse to easily. [21:05] So, we don't use those, but you can maybe think of that. [21:08] Does anyone have any confusion here, really, [21:11] about how this measurement [21:13] process collapse probability works? [21:16] Okay, great. [21:18] We will learn about multiple qbits. [21:20] The same is multiple cbits. [21:22] We represent them by the tensor product. [21:24] Why is it doing that? [21:27] Okay, hold on, laser pointer. [21:34] Okay, there we go. Nope, that's not. [21:38] Okay. So, if we have two qbits, and we multiply them, [21:43] the sum of squares identity actually is maintained. [21:49] And so, if we consider [21:51] our perfectly balanced 50 percent coin-flip qbit. [21:54] And we tensor with another coin-flip qbit, [21:57] we get this four vector with [21:59] one half in every single column, [22:01] and one half squared is of course, one-quarter. [22:03] So, one-quarter plus one-quarter [22:05] plus one-quarter plus one-quarter is one. [22:06] This maintains the property. [22:08] And the way to read this is [22:10] when you measure these two qbits, [22:12] it has a one-quarter chance of collapsing to (0, [22:14] 0), (0, 1), (1, 0), and (1,1). [22:16] This is sort of the probability of when you measure it, [22:20] finding a one there, [22:22] and zero everywhere else. [22:23] So, we could find, [22:25] it's a one-quarter probability of finding one in [22:27] this position and all zeroes everywhere else. [22:29] Does that make sense for multiple qbits? [22:32] Okay great. [22:34] You guys are just trucking along and no problem. [22:36] Should be super easy. Yes? [22:38] >> I have a question. [22:39] >> Absolutely. [22:40] >> So, there's only going to be one, [22:43] one left in the vector? [22:45] >> Yes. [22:45] >> There couldn't be two ones? [22:47] >> There could not two ones [22:48] because that would actually violate [22:49] our a squared plus b squared equals one constraint. [22:52] >> Okay. [22:52] >> But yeah, after measurement there'll only be one, [22:56] one here in this in four vector, [22:59] which we can then factor into two bits actually. [23:01] Okay. Yes? [23:03] >> You also find collapsing for that longer vector? [23:06] >> Yeah, yeah. [23:08] So, if you measure these two qbits at once, [23:11] you can think of this product state vector is collapsing. [23:15] And then that's just the probability of [23:18] finding a one here and a zero everywhere else. [23:20] It'll become useful in the future when we can't [23:23] actually factor out the product state, but that's anyway. [23:27] Okay. How about operations on qbits? [23:30] We have these qbits, how do we actually manipulate them? [23:32] The same way we do with the classical bits. [23:34] And all the matrix operators we've [23:37] learned also work with qbits. [23:39] So, for example, negation. [23:42] If we have our qbit that has [23:43] a 25 percent chance of collapsing to zero, [23:45] 75 percent chance collapse into one, [23:47] if we run it through the bit flip operator, [23:49] now it has a 75 percent chance of collapse into zero, [23:51] and 25 percent chance of collapse into one. [23:53] So, we can manipulate these probabilities actually [23:55] called amplitudes with gates. [23:57] And you can think of gates, [23:59] they correspond to some device scientists have created [24:02] which is like manipulate the qbits with a gentle touch. [24:05] Not enough to collapse them, [24:06] but enough to change their state. [24:08] So, pretty neat. [24:11] And there are also a couple important matrix operators, [24:15] which we haven't learned yet because they only [24:16] really make sense in the quantum context. [24:18] Okay, all right. We're good. [24:23] Then the most important one is the Hadamard gate. [24:26] And what it does is, it takes a zero or one qbit, [24:30] and it takes it to the coin-flip state [24:32] where it's in exactly equal superposition. [24:35] The matrix looks like this. [24:36] It as one over root two in [24:38] every single entry except [24:39] for a negative in the bottom right corner. [24:41] So, if you multiply that by this, [24:43] you get one over root two, one over root two. [24:45] If you multiply this by one, [24:47] we get one over root two, negative one over two. [24:49] Pretty neat. So, this is how we [24:50] actually get into superposition. [24:52] We use the Hadamard device, [24:53] which scientists have developed, [24:56] and we can make much use of. [25:00] So, quiz time. [25:03] Can anyone tell me why we need a negative one in [25:05] the bottom right corner? [25:07] Why do we need a negative sign here? [25:11] >> It's like a matrix on bigger provision. [25:20] I don't know exactly why, [25:23] but it is too big. [25:24] >> Well, the answer basically has to be reversible. [25:29] So, if we didn't have this negative number here, [25:31] then both zero and one would map to the same value, [25:33] and it would not be reversible. [25:34] So, we need this negative sign. Yes, correct. Okay. [25:39] >> Question. [25:40] >> Yes? [25:41] >> Review of superposition, [25:43] what does that mean exactly? [25:45] >> Superposition, yeah. [25:46] So, superposition means that a qbit is [25:49] in both states zero and one at the same time. [25:52] >> Okay. [25:53] >> And I want to be really clear about something here. [25:56] This doesn't mean the qbit is secretly [25:58] zero or secretly one, and we don't know. [26:00] It means it's actually in both at the same time, [26:03] this is just quantum weirdness. [26:06] This is just like what happens at the very, [26:08] very small level of our world, [26:09] which is that things don't have [26:10] definite values until we measure them. [26:13] >> Here you have (0, [26:15] 1) in superposition is one over root two, [26:18] one over root two. [26:19] And one and superposition one over root two minus one. [26:23] >> Yes. [26:23] >> So, we seem to have [26:24] different values but they're [26:27] representing conceptually the same thing. [26:30] >> Right. So, this [26:32] comes down to the distinction [26:35] between the quantum and classical world,. [26:36] Which is that from the classical perspective, [26:39] these two qbits are the same. [26:40] Both have 50 percent probability [26:42] of collapsing to zero or one. [26:43] But, if we stay within the quantum realm, [26:46] this sign information is [26:48] preserved as long as we don't measure it, [26:50] and it can affect our computations. [26:52] >> So, it's got a 50-50 chance, [26:56] but it has a sense that it used to be a one? [27:00] >> Has a sense that it used to be one? [27:03] Not really, it just ends up in this state, [27:06] which is different within [27:07] the quantum realm than this state. [27:09] These are two different states. [27:10] >> Okay. [27:11] >> Yes. [27:11] >> Both for the 50-50 chance. [27:13] >> Yes, exactly. Both when you [27:14] measure it and convert it into [27:15] the classical world come down with a 50-50 chance. [27:18] Yes. But they are different, [27:20] and they have different computational properties. [27:23] Okay. Now, I'm going to show you something [27:25] really cool about the Hadamard gate, [27:28] which actually takes us out of [27:30] superposition into the classical bits. [27:33] This should be unsurprising. [27:34] Everything is its own inverse, right? [27:36] If we just apply the Hadamard gate to our value here, [27:41] our coin-flip value, we get zero. [27:43] And for this one, we get one. [27:45] So, this suggests to us a quantum computation structure. [27:51] We can start with our classical bit values. [27:53] We put them into superposition, [27:55] do a bunch of quantum stuff to them, [27:56] and at the end if we're clever, [27:58] we can transition them to zero or one [28:00] so that our whole computation was deterministic. [28:03] Pretty neat, right? Okay. Now, I [28:07] should say that not all algorithms work this way. [28:09] There are algorithms like Shor's algorithm, [28:11] which only gives the right answer [28:12] of 50 percent of the time. [28:13] You can't be clever and [28:15] always get the right answers, just not doable. [28:18] But the one, the problem we will look at does [28:20] give this deterministic property. [28:23] So, does anyone have trouble with this concept? [28:28] We transition out of superposition [28:30] without measurement, pretty interesting. [28:31] >> Can you go over this transition from [28:33] a classical computation to [28:36] quantum and then converting it back? [28:38] >> Yes. [28:38] >> That's correct. Let's say two plus two, [28:40] how would that look like in? [28:42] >> How-? [28:43] >> Just the simplest type of math. [28:46] >> The simplest type of math. [28:48] What we're going to go over that basically, [28:50] we're going to go over a problem. [28:52] There are certain problems where computers [28:55] are better than classical. Addition is not one of them. [28:59] It works the exact same way in both. [29:02] It should also be said that all classical computation [29:05] can be done on a quantum computer, [29:07] all you do is just restrict [29:08] all the values to zero and one, [29:09] and it works, but it's [29:11] kind of a waste because you can also use [29:13] all the extra values that we found. [29:18] Okay, and we've actually [29:20] sort of define a state machine here, [29:22] which I am sure many of you will appreciate [29:23] if you're software engineers or computer scientists. [29:26] This is the unit circle which [29:30] many of you will remember from [29:31] high school trigonometry, right? [29:33] It's a circle of radius one around the origin. [29:36] Here's the X axis, [29:39] this is the Y axis. [29:40] You can think of the top value is the value of [29:45] the x-value and the bottom one is the y-value [29:47] so our zero value is at position one, [29:51] zero which is along the X axis. [29:53] Our one value is position zero, [29:54] one which is along the Y axis. [29:56] And this is the bit flip operator, [29:58] it defines transitions around this unit circle. [30:02] So zero goes to one, one goes to zero, [30:05] zero negative one goes to negative one, [30:08] zero which when you collapse them, [30:10] this is zero, this is one, and vice versa. [30:13] And if we look at the [30:15] superposition values, here's something interesting. [30:18] The bit flip operator [30:20] really kind of has no effect on them. [30:22] For this one, if you flip it upside down [30:24] it's stays itself same with this over here. [30:27] This one's kind of interesting and that it transitions [30:30] you all the way across the unit circle [30:31] and we'll make use of that. [30:33] But yeah, this is pretty much [30:36] the full action of the bit [30:37] flip operator on the unit circle. [30:39] I should mention here that if we [30:40] were using complex numbers, [30:41] this would actually be a sphere. [30:43] Much more difficult to sort of intuitively graphically [30:47] represent so we're sticking with [30:48] real numbers, they suit us just fine. [30:51] But it's nice to know that additional dimension is always [30:54] available to us if we want to [30:55] make our computation even more powerful. [30:56] And then here's the action of the Hadamard gate, [30:58] which we saw in the past couple slides. [31:00] It takes us from zero to one over two, [31:02] one over two, one, two, [31:04] one over two negative one over two, [31:05] and kind of symmetrically, [31:07] it also works in this way over here. [31:09] So, we have a nice state machine that we've developed and [31:12] now we can start running things on the state machine. [31:14] Very nice intuitive sort of representation, [31:15] you don't need to do matrix multiplication all the time. [31:18] Everyone kind of gets this? [31:21] Okay, great. So here's [31:24] an example of something we [31:25] could run through the state machine. [31:27] Here, I'm introducing something called [31:29] quantum circuit notation. [31:31] You can think of the cubit traveling along [31:33] this line has these operations applied to it, [31:36] is it goes through the boxes. [31:37] So X is bit flip, [31:39] H is Haddamard, and then so we go a bit flip, [31:41] Haddamard, and bit flip, Haddamard, [31:42] bit flip and if we start out here, [31:45] we go bit flip, Haddamard, [31:48] bit flip, Haddamard, bit flip. [31:50] So we start off at one, [31:51] zero and get to zero, [31:53] one, we got to cross the circle. [31:54] And note, this is reversible so we can [31:56] also go this way and get back. [31:58] So this is kind of how we'll [32:00] be doing all of our computations like this basically, [32:06] just hopping around the unit circle. [32:09] It's pretty simple, pretty intuitive, right? [32:10] It's just a state machine. [32:12] We use this in classical computing all the time. [32:15] Just has a bit of weird rules with [32:17] the claps and whatever but don't worry. [32:19] Okay, now we have everything we [32:22] need to learn the simplest problem [32:23] where a quantum computer [32:24] outperforms a classical computer. [32:26] We learn that Cbits are just a special case of Qbits, [32:28] and Qbits are two vectors of [32:30] complex numbers such that [32:31] a squared plus b squared equals one. [32:33] Within the Qbits is going to be in superposition, [32:35] they're probabilistically collapsed [32:37] to Cbits by measurement. [32:38] Multi-Qbits systems we learned are tensor products of [32:41] single Qbit systems same as with Cbits. [32:43] Matrices, again, represent operations on Qbits, [32:47] and we learn about the Hadamard gate, [32:48] very important which takes [32:49] our zero and one bits to superposition and back. [32:52] And finally, we learned [32:54] that we can think of Qbits in their operations is [32:56] forming the state machine on the unit circle or [32:58] unit sphere if we're using complex numbers. [33:00] It's actually called the bloch sphere, [33:01] if you want to look that up for the full complex numbers, [33:06] but unit circle, just fine for us. [33:09] Okay, so we're gonna [33:12] learn about something called the Deutsch oracle. [33:14] This is originally proposed by David Deutsch in, [33:18] was it like 83 or something like that? [33:21] And the problem is this. [33:22] Imagine I show up at [33:23] your doorstep and I give you a package, [33:25] the package is just this black box, [33:27] it's just horribly present. [33:29] It's a black box which has a function on one bit. [33:32] There's one of those four functions [33:33] on one bit, do you remember what those are? [33:34] I said I would ask you about them. Set zero, [33:39] set one, identity, indication. [33:40] Exactly. So one of those four functions, [33:42] I don't tell you which one is inside this black box. [33:45] There's a wire going in and a wire going out so you can [33:47] send in values see where it goes out, [33:49] but you can actually look inside the black box, okay? [33:53] So how many queries [33:56] on a classical computer would it take to figure out [33:58] which function is inside the black box? Two, exactly. [34:03] You send in zero, see what comes out, [34:05] you send in one, see what comes out. [34:07] So that will uniquely identify which function it is. [34:10] Now, how many queries do you think it [34:11] takes on a quantum computer. [34:13] You're wrong, it's two. [34:16] I say this to illustrate an important point, [34:21] which is quantum computers, [34:22] they don't really compute with all value simultaneously. [34:26] At the end of the day, you collapse [34:28] your Qbit to a single bit of information, [34:30] and a single bit of information is not enough to [34:32] uniquely identify one of four functions, right? [34:35] You need two bits at least So [34:37] this actually takes two queries on a quantum computer. [34:40] Well I'm not too exciting so far. [34:42] Now, what if instead [34:45] of not wanting to know which function it is, [34:47] we just want to know whether the function [34:48] is constant or variable. [34:50] The constant functions are, [34:51] constant zero, constant one, [34:52] they're always mapped to 0, always mapped to one. [34:54] The variable functions our identity and negation. [34:57] So how many queries would this [35:00] take on a classical computer? [35:01] >> Two. [35:03] >> Two. You put in zero, [35:06] if you get zero you don't know whether [35:07] it's identity or constant zero. [35:09] If you get one, you don't know whether it's bit [35:10] flip or constant one, [35:12] symmetrically with one, so it always takes [35:14] two queries on a classical computer. [35:16] Even though there are two categories, [35:18] so really we only need a single bit [35:20] of information to tell us which category it's in. [35:22] But how many queries [35:25] do you think it takes on a quantum computer? [35:27] I kind of burned you last time so maybe you're a bit shy. [35:30] >>I'm going for a one. [35:31] One, you are correct. [35:33] We can do this in a single query on a quantum computer. [35:36] We can tell whether its constants or variable. [35:38] This like undeniably outperforms [35:40] a classical computer and we're going to learn how. [35:42] Okay, we do with the magic of superposition. [35:46] But first we have to define [35:48] which each of those four functions [35:51] look like on a quantum computer. [35:52] We have an instant obvious problem [35:54] with the constant functions. [35:55] Can anyone tell me what it is? [35:56] >> Not reversible. [35:57] >> They're not reversible, [35:59] how are we going to write [36:00] these non-reversible functions on a reversible computer? [36:03] This is actually a really common [36:04] problem in quantum computation. [36:06] You really often have to deal with [36:08] non-reversible functions if you [36:09] have to write them in an irreversible way, [36:11] and the hack we do is this. [36:13] So originally we had this, right. [36:15] We add an input and an output, [36:16] a single wire going through. [36:17] And we just imagine that you put in [36:20] the value and you get the function [36:21] applied to that value, right? [36:23] But the hack that you always do on quantum computers [36:25] is you add an additional output Qbit. [36:28] So you actually have two Qbits. [36:30] We have to rewire our black box. [36:32] So you have your input Qbit, which is unchanged, [36:34] and then the value of the function on the input [36:36] Qbit is written to the output Qbit. [36:39] Does everyone kind of get this. [36:42] I think this the thing that people have [36:43] the most trouble with, this is necessity. [36:46] The reason we have to do this, [36:47] is so we can write non-reversible [36:49] functions in a reversible way. [36:50] And the way you do that is to [36:53] have a separate input and output qubit. [36:56] So when you see larger quantum computations, [36:59] instead of having all the bits [37:01] go in and have transformations [37:02] applied to them and then being measured. [37:03] You usually have a separate set of output bits, [37:06] so the input bits go in, [37:08] they have their value sort of written to the output bits, [37:10] and you measure the output bits. [37:11] This is a very standard way of doing quantum computation. [37:16] So does anyone have any trouble with this? [37:18] This is a very difficult concept. So, yes? [37:19] >> I didn't get it. [37:21] >> Okay. [37:24] So, do you understand this model basically, [37:26] this is what we have now, okay? [37:28] So we need to rewire it [37:30] so there are two wires going through the box now. [37:35] And one of those wires we call the input wire, [37:38] one of those wires we call the output wire. [37:40] We assume the output wires just [37:42] initialize to zero,right? It's always zero. [37:44] Now our input wire is what we actually give our input in. [37:47] Like it'd be like zero or one or whatever value [37:49] you want to give input to the function. [37:51] So, it goes to the box, it's just unchanged. [37:54] We don't touch the value of the input wire, [37:57] but we calculate the function in here, [38:00] on this input and then we write [38:02] its value to the output wire, okay? [38:07] >> Black box? [38:08] >> Yes, we are rewiring the black box. [38:12] We have to rewire the black box in [38:13] order for the black box to really work. [38:15] So the black box I gave you has to be rewired. Yes. [38:18] >> Did you use the first input, [38:21] which is the output of zero? [38:22] >> Did I use the first input? [38:25] >> Yeah, because one of them was kind of identity, right? [38:28] You put the X out, and then it was the F or X. [38:31] >> One of them was X and the other was [38:34] >> You need the X out. [38:38] >> Say we only have this, [38:41] right? This is the old way of doing it. [38:42] We can't have a non-reversible function in here, right? [38:47] For it to be on the quantum field. [38:48] >> No, that I get, right? [38:49] >> Okay, yes. [38:49] >> Because when that thing is on the right side, [38:51] you have two going in, two going out. [38:53] >> Yes, two going in, two going out, yes. [38:54] >> I get why two going out. [38:56] >> Yes. [38:56] >> I don't get why we have that zero is also going in, [38:59] It doesn't seem that you're actually using [39:01] it to produce any of the others. [39:03] >> You're correct, it's just we need. [39:05] >> Symmetry? [39:07] >> Not really symmetry, [39:09] it's just like how we would write the quantum circuit, [39:12] we would need two qubits in general. [39:15] So, you're correct that [39:18] this algorithm value isn't really used. [39:19] >> Is it like we don't care a pen off? [39:22] >> No, we do want it to be zero because the way [39:26] that we write the circuit assumes that [39:28] this value coming in is always zero. Yes. [39:31] >> Why is it ingoing output wire called output. [39:35] >> What? [39:36] Yeah. So, this is kind of weird that [39:39] the output of the input is called input. [39:42] But, we basically only really look at this value here, [39:46] is the basic idea. [39:48] This is like the real output. [39:49] The input will always be unchanged. [39:52] >> Question. So if I have [39:53] multis two black boxes in series, [39:57] the upper input which you have labeled Alvap. [40:03] >> That's smart, that's a good one. [40:05] >> And the second stage would be the F of [40:08] X output of the first stage? [40:10] >> Okay, so you're saying if you had [40:13] these in series rather than sort of in [40:15] parallel to what we're doing is that what you'resaying? [40:17] >> Yeah I want to do two operations [40:19] one and then another one. [40:21] And the black box is doing some operation. [40:25] >> The black box is doing some operation. [40:27] You can have as many operations as you want [40:29] in here inside this black box basically. [40:31] >> True, but I'm trying to [40:33] conceptually understand whether I [40:36] would take the F of X is the output upper right. [40:39] And that will be the input. [40:41] >> The input, the next one. [40:43] >> Absolutely and in fact I [40:45] said that this black-box assumes this value is zero, [40:48] this isn't maybe throw in a bit much of you, [40:49] but actually we can break that assumption and send it [40:53] some other value which maybe [40:55] will get us more information [40:56] which is in fact what we'll be doing. [40:58] So, the working of black box [41:01] assumes that the output input is zero, [41:05] but we can break that assumption and be tricky. [41:07] >> My way of thinking was I didn't [41:09] have any other value for the first stage, [41:12] but for subsequent inputs I do have one. [41:16] So I could use it if I want? [41:17] >> Yeah you could, yeah and you [41:19] might get some interesting values which actually well. [41:21] Okay I swear, this is [41:23] the most difficult part [41:24] conceptually of this entire presentation. [41:26] So if anyone has any trouble with it please let me know. [41:29] Ask any questions you can spend [41:30] as longer time on this as we want. Yes [41:32] >> As we go ahead, is there [41:34] some additional clarifications because I didn't get it. [41:37] >> Okay. Well we'll go over all each of [41:40] the four functions in this way, so maybe that will help. [41:43] So, for example, constant zero, here's how it would look. [41:48] X goes in, X goes out it's unchanged. [41:51] Now, the output is always going to be zero, right? [41:54] That's just what the constant zero does. [41:56] So we always want this value [41:58] in the upper right to be zero. [42:00] If we assume zero goes in, [42:01] this is our circuit diagram, [42:03] neither of the two wires make any modifications, right? [42:07] It's a straight wire. [42:10] Does that sort of makes sense? [42:13] We will see the next slide, [42:15] what about for constant one? [42:17] We want one to go out here, right? [42:20] This is our function output value. [42:23] And we assume zero is the input here. [42:24] All we do is we do a bit flip right here, [42:28] and that gets us the semantics we want. [42:31] Is anyone having any trouble with this so far? [42:34] I swear this is the most difficult part. [42:37] So if you get this you're golden. Yeah. [42:39] >> So these labels output, input, [42:42] would you call them something [42:43] like computations and its spare? [42:44] >> Sure yeah, you could. [42:47] You can call it the compute and the spare fit. [42:49] Yeah, that also works.They might reduce [42:52] some confusion about there being [42:54] an open output and input output. [42:57] >>Why is it called output? [43:00] >> Why is it called output? [43:03] We call this the upper qubit because it's [43:04] just the place that we write the output of the function. [43:09] But we could call it like compute [43:13] and spare or something like that, like he suggested. [43:15] Like this would be the spare sort of bit that we [43:18] write the function number 2. Yes [43:21] >> We need this to do a reversible computation, [43:23] right why is this? [43:26] >> Reversible? [43:27] >> Can we compare the reversibility of [43:29] this likewise the right one reversible one? [43:31] >> Absolutely, okay. [43:32] So let's consider this one right here, right? [43:37] We have our black box with [43:40] a single wire and [43:42] say we want to do the bit flip operator. [43:44] So, that would just be. [43:46] Sorry not with bit flip operator, [43:48] a bit flip operator is reversible. [43:49] So we want to do the constant zero operator. [43:53] We always want to map this to zero. [43:54] So you need some operation right [43:56] here, that would map this to zero. [43:58] But it'll be the matrix [44:01] 1100 but this is [44:04] not a valid operator in a quantum computer, [44:07] because it's not reversible. [44:09] So, does that kinda makes sense? [44:12] It's just we can't construct a device which does this. [44:14] It's just not permitted by physical reality. [44:17] All this math and stuff I'm showing you, [44:19] it's not like special it's just, [44:20] we found that it corresponds to [44:23] the semantics and workings of a quantum system, [44:25] and so it's a nice way to reason about it basically. [44:29] Okay. Of course if we [44:32] want to write constant zero here with [44:36] their two inputs are [44:40] the two wire model it would just be blank, right? [44:44] Or if we want to do this is [44:49] constant one always maps to [44:51] one we saw that this has an X gate here. [44:54] And this is reversible, right? [44:57] Okay. So we managed to write [45:00] a non-reversible function in a reversible way. [45:01] If you've got this congratulations, [45:04] this is the trickiest part. [45:05] It took me awhile to figure out why we needed to [45:07] do this staring at the textbook. [45:08] Does anyone have any confusion here? [45:11] Okay. So remember constants zero is just blank. [45:16] Constant one has a single X gate. Yes. [45:19] >> There's a point you always end up with [45:20] a four by four reversible matrix [45:22] by doing this in black box? [45:25] >> Yes. Black box is always a four by [45:27] four reversible matrix applied to [45:28] a product state, you're correct. [45:30] Although we will be not going [45:32] into the math in that way we'll just be using [45:33] the state machine to look at it, [45:36] but the math is very easy for you to do it yourself. [45:39] Okay. So let's look at identity this is a bit more [45:42] complicated this is the CNOT gate, okay? [45:46] Where this is the control, and this is the target. [45:51] So we'll end up with, [45:53] so input again is unchanged. [45:55] We want output we assume it zero we [45:57] want to end up with a value X, right? [45:59] So if zero is sent in here, [46:02] then this is the control bit, [46:04] so the target bit is just left unchanged, [46:06] right? So zero comes out. [46:08] If one is here, one is sent in, [46:10] and the control bits one so we flip thright? [46:14] Is bit, and we end up with one. [46:16] Does this make sense? This is kind of [46:19] tricky it is a big step up in complexity of our circuit, [46:21] but everyone's fine with this? [46:23] Wow okay. Can anyone guess how will do negation? [46:31] >> You can hardset the control bit to one. [46:35] >> How can we hardset control bit to one? [46:39] >> Two controlled NOTS. They're. [46:41] >> Not two controlled NOTS, [46:45] we just have an X gate there. [46:49] So, up to here it's equivalent to identity, right? [46:52] And then we just [46:53] flip the output bit and then we got NOT X. [46:57] So, those are the four circuit values. [47:00] Okay. Everyone's good so far? [47:05] Everyone knows how we write our four functions? [47:08] Are you ready to see how we solve [47:11] it on a quantum computer? We use this. [47:14] So, we're going to break the assumption [47:16] that this value goes into the black-box as zero. [47:20] We put, first, we initialize [47:22] both in putting up a qubits to zero. [47:25] We bit flip them so now they're both one. [47:28] We put them through the Hadamard gate to put them into [47:31] equal superposition then we send them into the black-box. [47:34] One of those four circuits is applied. [47:37] Then we do the post-processing, [47:38] we send them through the Hadamard gate again [47:40] and we measure them. This is measurement. [47:42] And I claim, and I will show it to you that if [47:46] the black-box function is constant [47:47] the system will be in state one-one after measurement. [47:50] Like this will have value one, this will have value one. [47:53] We're using input as the most significant bit by the way. [47:55] And if the black-box function is [47:58] variable and the system [47:59] will be in state zero-one after measurements. [48:01] So this will be zero, this will be one. [48:03] And we will know whether the function is constant or [48:05] variable in a single query. [48:07] Pretty nifty, right? I'm going to show you how it's done. [48:10] First the preprocessing. [48:13] Remember, we start with zero then [48:15] we'd been flipped both in the Hadamard gate both. [48:17] So we start here, bit flip takes us up to here, [48:21] Hadamard gate down here. [48:22] So this is the value that is sent into the black-box. [48:25] Just remember it's in [48:26] the bottom right on the unit circle. [48:27] This is the value right before we send [48:29] it through one of those four circuits. [48:31] Okay? Now, let's look at how we do constant-0. [48:35] So constant-0 remember, it's just blank on [48:37] both and the post-processing is a single Hadamard gate. [48:41] So since no gates are applied they stay in [48:43] this bottom right value, [48:46] and since the Hadamard gate is [48:48] applied as part of the post-processing, [48:50] we flipped back up here. [48:52] When we measure this, this is one-one. [48:55] Remember I said the value would be [48:57] one-one if it were a constant function. [48:59] So we're one for one, okay? [49:02] Seem okay so far? All right. [49:05] Let's add a bit flip [49:08] because we're going to go over constant-one now. [49:10] So this is the other constant function. [49:12] Now remember, if we do a bit flip in [49:16] this state we flip across the unit circle over here, [49:21] and the Hadamard gate [49:24] then takes us down to here, zero and negative one. [49:27] When we measure it we again get one-one. [49:31] Okay? So we're two for two. [49:34] Not bad, right? Okay. Things get a bit more complicated. [49:37] Does anyone have any trouble with this so far? [49:39] And then, yes? [49:40] >> I just didn't get like why it turns out to one-one? [49:47] >> Why it works out to one-one? [49:48] >> Yes. [49:48] >>That's a good question. Okay. So we're up here, right? [49:51] If we measure this then what value do we [49:54] get? This is just one. [49:56] Remember, this is the value of the one bit. [50:00] So if you measure one, we get one. [50:02] Yes. Now down here, [50:04] if we measure this we also get [50:07] one because negative one squared is one. [50:09] So is 100% probability of collapsing to one. [50:13] And so, we can say this is one-one. [50:17] This is like the most significant bit [50:18] and this is the least significant bit. [50:20] So we end up with one-one. [50:22] Does that answer your question? [50:23] >> Yeah. [50:23] >> Okay. Great. All right. [50:27] Let's go on to something more complicated, which is CNOT. [50:31] This is going to get a bit weird [50:32] but this is how we do identity remember? [50:34] The input bit is the control bit, [50:36] the output bit is the target bit. [50:38] And don't panic, [50:41] I'm going to show you why this is on the next slide. [50:43] But the action of CNOT is to take [50:46] our input qubit up to here. [50:49] That's the green line. This is weird for two reasons. [50:53] One is that the CNOT [50:55] is supposed to leave the control bit unchanged. [50:57] Right? But here this is the only thing that control bit, [50:59] like the qubit it's the only thing that's changed. [51:02] And, this sort of action is a bit odd, [51:04] but don't worry I'm going to show you the math, [51:06] the reason why this works on the next slide. [51:08] But just for now, [51:10] so we flip from here up to here, [51:12] and then when we do the Hadamard gate [51:15] to post-process we end up in state zero. [51:18] So zero-one, pretty neat. [51:22] Okay, here's how the math works. [51:23] We're applying the CNOT gate [51:26] to the state one over root two, [51:28] negative one over root two, [51:29] and one over a two, negative one over root two, right? [51:32] When we tensor these together, [51:33] we get this ridiculous matrix which I'm going to [51:35] factor out one-half, just to make it readable. [51:38] So, we have the matrix one, [51:39] or a spectra is at 1-1-1,1. [51:41] Right? Now, we remember [51:44] this familiar matrix from the CNOT slide. [51:46] When we apply this matrix to this vector we get this. [51:51] Right? We flip the bottom two rows. [51:53] Now, when we factor this, [51:56] remember the products that we can [51:58] factor it into the individual state, [52:00] we get this tensor product. [52:02] If you ignore everything in the middle and just [52:04] compare our start values to our end values, [52:07] this is the output or least significant bit. [52:11] This is unchanged. [52:13] Right? This is still one 1/2 -1/2. [52:15] The input bit which started out as [52:17] 1/2 -1/2 ends up as 1/ 2 1 over root two. [52:21] This is just the action of the gate. [52:23] So this is kind of a limitation of [52:25] our visualizer that we can't really show [52:27] the state transition but I hope I've [52:30] convinced you that this arrow is in fact what happens. [52:33] Does anyone have any questions about this? [52:36] Okay so we're three for three right. [52:39] I said the measure value would be zero-one, [52:44] if it were a variable function and [52:47] indeed it is as I said. [52:49] So for three-three.Three for three. [52:50] Let's go over the very last one which is negation. [52:54] It's a CNOT and then a bit flip. [52:57] Right? Let's see how that works. [52:59] Again we have this arrow. [53:01] Taking us up to here and [53:03] the bit flip takes us across the unit circle [53:05] and we do the Hadamard [53:06] post-processing to get us down to here. [53:09] When we measure these, we get zero-one. [53:12] Four for four, huh? [53:15] Single query, outperformed [53:16] classical computation, pretty nuts, right? [53:19] Pretty nuts. Okay, so we did it. [53:23] We now, we have outperformed classical computing. [53:26] Classical computing is in the dust. [53:27] It's done, it's dead. [53:28] So we might think like, [53:30] yeah I see how the math works and what's the intuition? [53:32] I'm going to tell you the intuition. [53:34] The intuition is the difference [53:37] within the categories was a single negation gate. [53:41] So if we go back to here, [53:46] so we have constant zero and constant one. [53:50] The only difference between them is [53:51] a single negation gate. [53:52] When you apply negation gate in a superposed state, [53:56] it doesn't really have any effect. [53:58] Right? So we kind of [53:59] neutralize the effect of the negation gate. [54:02] So we neutralize the difference within [54:04] the categories and then we magnify [54:07] the difference between the categories which is that [54:10] the variable functions have a CNOT [54:11] and the constant functions do not. [54:13] So we magnify the effect of [54:14] the CNOT and minimize the effect of the negation. [54:18] And that's a powerful thing about [54:21] quantum computing which is that you can change [54:25] the action of various logic gates [54:28] by putting yourself in [54:29] superposition in different sorts of states and stuff. [54:32] So that's pretty neat. And this problem [54:35] you may say like, "Okay well yeah. [54:37] Great. Whatever." It's really contrived. [54:39] When do I ever do this in real life? [54:41] That's a good question and it was [54:44] contrived back when it was announced, [54:47] I think was 1993, but then a generalized version of [54:51] this function was found [54:53] which it takes n bits as input, not a single bit. [54:56] And the n bits either all map to the same value, sorry, [55:00] like that's two to the n possible values, [55:02] they all map to the same value [55:03] or they equally map to zero or one. [55:06] They're constant or balanced it's called. [55:07] And so it's kind of just generalized version of this. [55:10] It turns out we can still solve that on a single query. [55:13] Exponential speedup, huh? [55:16] Exponential speedup. [55:18] A single query versus on [55:19] a classical computer you have to try all two to [55:21] the n values before you know [55:24] whether it is constant or variable. Pretty nuts. [55:27] Okay? Then there's a variant [55:29] of that problem building [55:31] everyone's kinda like building on top of each other, [55:33] it's called Simon's periodicity problem. [55:35] It's again you have like a black box and [55:37] you're trying to figure out some properties of [55:38] the function and then once that came [55:40] around Shor he looked at this and he's like, "Oh! [55:44] We can use this to factor large integers." [55:46] And so he came up with Shores algorithm and [55:48] that's when the whole field really caught fire. [55:50] So I hope I've convinced you that well [55:52] this individual problem is [55:53] kind of contrived and not that useful, [55:55] it's the base, like the foundation of [55:58] some very interesting computational properties. [56:00] Did that make sense? [56:02] Anyone have any questions? [56:05] You're all like convinced that we [56:07] just crushed a classical computer right here? Yes? [56:11] >>On the Microsoft site [56:13] there's an article where the girl was saying, [56:16] with quantum computers you can take programs that [56:21] take billions of years to run [56:22] and run them in a week. Is this... [56:25] [Croostalk]. [56:25] >>This could be that. I mean yeah. [56:26] We have an exponential speedup. [56:29] If you have like, I don't know. [56:30] What it would take something like a billion years to run? [56:32] Like if you have an 80 bit function, [56:35] like to the power of 80 versus like a single query that's [56:38] probably a billion years versus a week [56:40] something like that. So. [56:42] >> A question. So I understand speedup but this is [56:46] the speedup in answering this question from [56:48] the output coming to get the input. [56:51] Right? Whether the function was a constant function or. [56:54] >>Yes. [56:55] >> Right? But in [56:56] what context is that question unimportant? [57:00] >>Great question. Why do [57:01] we care about this sort of thing? [57:02] So for example in Shor's algorithm you [57:05] can construct a question like [57:07] does this integer have [57:09] a certain factor in structure basically? [57:12] And you can tell a property like whether it has [57:15] that property or not basically which will allow you to, [57:18] and if it does have that property you [57:19] can factor it pretty much. [57:22] It's very very hand-waverly [57:25] explaining how Shor's algorithm works. [57:27] So you can construct a lot of problems in terms [57:30] of does this function have a certain property or not, [57:34] which you can find efficiently on [57:36] a quantum computer. I hope, Yes? [57:38] >> Do you mean this decision helps? [57:41] >> Mainly decision problems. [57:44] Although, as we know from theoretical computer science, [57:46] decision problems can be usually be turned into [57:50] like generally finding the answer [57:52] to problems and vice versa. [57:54] So, yeah. [57:57] Okay, pretty good so far. [58:00] To recap the whole presentation, [58:02] we learned how to model classical computation with [58:04] basic linear algebra, we learned about qbits, [58:06] superposition, and the Hadamard gate, [58:08] and finally we learned about the Deutsch Oracle problem, [58:09] where quantum outperforms classical, pretty nifty? [58:12] Okay, now the bonus topics. [58:14] With all the tools we have [58:16] these will be a breeze for you. [58:18] You'll never have to read some pop science articles on [58:22] quantum entanglement and like try [58:24] and muddle through there a horrible metaphor. [58:26] You'll actually know the math, all right? [58:28] You'll know the math, that is incredible. [58:30] And we'll go on quantum teleportation, which is super, [58:32] super nifty like it is mind-blowing. [58:36] Okay, quantum entanglement. [58:38] You asked a great question, [58:39] a very impressing question earlier which is, [58:41] "Can we always factor [58:43] the product state into the qbit state?" [58:46] When we cannot do that, [58:48] that means that the qbits are entangled. [58:52] For example this state, [58:53] if we have qbits in this state which is one over, two, [58:57] 001 over root two, [58:59] if we try and factor this, we can. [59:01] So let's try and factor this. [59:02] If we can factor it, [59:04] we should be able to write it as [59:05] a tensor product of two matrices, right? [59:07] Where A times C is one over root two, [59:09] A times D is zero, [59:10] B times C is zero, [59:11] and B times D is one over root two. [59:13] So we have this set of equations right? [59:15] Now, A times D equals zero that [59:18] means A or D has to equal zero. [59:20] If A equals zero then [59:22] AC will be equal zero and it doesn't, [59:23] so A cannot equal zero. [59:25] If D equals zero then BD would equal zero but it doesn't, [59:28] so D cannot equal zero. [59:29] So the only solution is there is [59:31] no solution. We cannot factor this. [59:34] This is an percent unfactorable state. [59:35] And what this means is we cannot separate these qbits. [59:40] They have no individual value, [59:42] their value only make sense [59:44] together, they're called entangled. [59:46] And the way we might think of this is [59:48] that if we measure this state, [59:51] it has a 50 percent chance of collapsing to zero, [59:53] zero and 50 percent chance of collapsing to one,one, [59:56] so the qbits are coordinating, right? [59:58] Does anyone have any confusion with [60:00] this sort of mathematical representation? [60:03] Okay, let's talk about what it means. [60:05] Well, let's not talk about what it means [60:07] yet, you might be like, "Well, [60:08] Andrew I can sling any old value into [60:10] the vector how do you actually entangled [60:11] qbits?" It's really simple. [60:13] If we have two qbits, [60:15] we just put one qbit through [60:16] the Hadamard gate to put in superposition, [60:18] and then that qbit is the control bit in C naught. [60:21] Two gates, that's all we need. [60:22] Here's how it works mathematically. [60:24] We started with zero zero, [60:25] we put the most significant bit in superposition, right? [60:29] And then here's our familiar matrix, seen our matrix. [60:32] If we apply it to the product state, we get this. [60:35] This is the state from the previous slide. [60:37] So really simple to entangle qbits. [60:41] Okay? What does this mean? [60:43] I mean they seem to be coordinating, [60:46] or like communicating, or something [60:48] in some way, these two qbits. [60:49] And if you measure one qbit, [60:52] it collapses the other in coordinated state. [60:54] Now the weird thing, [60:56] here's how we're going do really weird stuff here, okay? [60:59] This happens across huge distances. [61:02] China just this year, [61:04] managed to do this between [61:06] Earth and a satellite in space. [61:08] They entangled qbits, put one half on the satellite, [61:12] it was launched into space. [61:13] When they measure them, they're the same value. [61:16] It happens across huge distances. [61:18] It happens faster than light, it is instantaneous. [61:23] A 2013 experiment entangled qbits, [61:26] moved them very far apart, [61:27] synchronizing with an atomic clock, [61:30] they measured them very close together. [61:31] So close together and time that it would have taken [61:34] like 10,000 times longer to travel between them. [61:37] So they aren't communicating with any sort of [61:39] radiation anything like that, okay? [61:42] They are instantaneous, it's faster than light. [61:45] And you might be like "Well, [61:47] it's pretty obvious what's going on here. [61:49] When the qbits were entangled, [61:50] they just decided ahead of [61:51] time what they're gonna do, right?" [61:53] Well I got to explain everything, [61:54] but that's called hidden variable theory, [61:56] this is hidden variable theory. [61:57] It's the same reason that when a qbits in superposition, [62:00] it isn't secretly zero, [62:01] or secretly one, it's both, it's the same thing. [62:04] Hidden variable theory, we're not [62:05] going to over the proof why it doesn't work, [62:07] but basically here's this guy named John Bell, [62:09] and he showed that if hidden variable theory were true, [62:12] it had some really weird implications, [62:14] and therefore it's unattainable. [62:17] This is just the state, this is how the universe works. [62:20] They coordinate faster than light, [62:22] they just do and that's nice. [62:24] And you might be like, "Well, [62:26] I've been told my entire life there's [62:27] a universal speed limit, the speed of light, right? [62:29] Like what's up with that? [62:30] We can't just chuck it all out." [62:32] And this is in fact a big source [62:33] of consternation to Einstein, [62:35] the idea that locality wasn't true, [62:39] and then it was discovered [62:40] that there's a really important qualifier. [62:42] You can have faster-than-light coordination, [62:44] but you cannot have faster-than-light communication, [62:47] so information cannot be communicated. So think about it. [62:51] If I entangle two qbits, I give you one, [62:54] we go to opposite ends of [62:55] the universe, if I collapse mine, [62:57] all I know is that you collapse yours, [62:59] and when you collapse yours, you will see the same thing. [63:02] That there's no information [63:05] that can be communicated there really. [63:07] So, faster than light coordination is okay, [63:09] faster than like light communication, not okay. Yes? [63:15] >> Coordination does not involve communication? [63:17] >> It does in a way, [63:20] but communication here is [63:21] a technical term which means like, [63:23] I have a bit of information that I can transfer [63:26] to you, pretty much. [63:29] So I use the term coordination to try and [63:31] give a name to something which is not that, [63:34] but still involves like some kind [63:35] of coordination I guess. [63:38] Like I said, there is a limitation of our language, [63:41] all we can do is look at the math and see what it does, [63:44] and our language it was not developed for this. [63:47] Anything I try and tell you is [63:48] fundamentally a lie, except for the math. [63:50] >> I have a question. [63:51] >> Yes. [63:52] >> So let's say I have two entangled qbits. [63:54] >> Yes. [63:55] >> And I measure one and I know its value. [63:59] Does that mean that the other one [64:02] is could potentially still not be measured, [64:05] but when it is measured it will have the same value? [64:08] >> Right, when you measure one [64:09] it instantly collapses the other. [64:11] >> I'm sorry, that was my question earlier. [64:12] >> Yeah, good question. [64:14] I said that's a simplification again of [64:16] language but you can think of it that way. [64:18] Yes, sorry you had a question. [64:21] >> So there's no way to tell [64:22] that something has been collapsed or not then. [64:24] >> Excellent question. If you [64:25] could tell whether something's been collapsed or not, [64:27] you could measure one and use that as synchronization, [64:29] faster than light synchronization, right? [64:31] Yeah you can't. The process of [64:34] telling whether something is in [64:35] superposition or not would just collapse it. [64:37] >> It seems like you will be able to tell through [64:38] some of the sort of quantum computation, [64:40] like you do some computation on that, they was collapsed, [64:42] they would only be this state and if [64:44] it wasn't it would sometimes do this, sometimes do that. [64:46] >> You would think so, but in fact it is not the case. [64:49] >> I believe you I was just creating imaginations, [64:53] is there any intuational ways about the case? [64:56] >> Is there intu can I say intu? [64:57] >> Shut up and do the math? [65:06] >> Shut up and calculate, [65:08] that's a good like a way out. [65:09] I'm not sure I can't say it intuitively, [65:12] I can say that if you do put [65:14] a pencil and paper it, try it yourself, [65:17] try and come with [65:18] some sequence of operations you can do on [65:19] the other qbit which would reveal [65:22] it as having being collapsed or not then maybe but, yes. [65:26] >> Doesn't this coordination communication conversation [65:29] that we're having violate causality or it doesn't? [65:32] >> Yes, this is the critical thing, [65:33] it does not violate causality. [65:34] If we could communicate then it would violate causality, [65:37] but since we coordinated does not violate causality. [65:39] >> But instead what you said was, [65:40] if you measure the other one is going [65:42] to be that as well, right? [65:43] >> Yes. [65:44] >> The act of measurement is in your control, right? [65:48] >> Yes. [65:49] >> So how can that happen on the other side of [65:52] the qbit if you don't have communication because that's. [65:57] >> Well let's define what communication is. [65:59] Communication is I have a bit, [66:00] either zero or one and I'm [66:01] able to send it to you in someway. [66:03] >> Somehow yeah. [66:04] >> Yes. [66:04] >> The state that is not collapsed, [66:06] be communicated to the other state, [66:08] this is what I'm saying. [66:10] >> Yeah I mean this is a language problem. [66:13] Qbits are like communicating but [66:15] we can't get information through them basically. [66:18] You might be able to say that. [66:20] I use that term coordinating [66:21] to try and avoid this problem. [66:23] Other times in literature [66:24] you'll just see the word correlated. [66:26] Which tries to avoid that whole problem. [66:29] >> Coordination, it state the word here when you are [66:34] using it, it has an action that you have performed. [66:37] >> Yes, you control when [66:39] you measure in qubits it collapses the other. [66:41] But there's no way you can change [66:43] causality in that other qubits frame. [66:46] Basically, there's no way you can get information from [66:48] your frame into that frame [66:49] which would affect their causality. [66:50] All we can know is, [66:52] we have generated [66:54] the same random numbers basically, yeah. [66:56] >> It's kind of like pre-coordination so these are. [67:00] >> I want to avoid that, pre-coordination is [67:02] the qubits decided ahead of time which is not the case. [67:06] >> Until you measure. [67:07] >> Yeah. [67:08] >> Or until these. [67:09] >> At the time they measure they [67:11] decide whether they're going [67:14] to zero or one and they somehow [67:15] communicate that coordinate, [67:16] correlate, whatever, to the other qubits [67:19] and it goes in the same. Yes. [67:20] >> So, if you cannot communicate [67:23] what's the practical application of quantum? [67:25] >> Great question. We're going to get into [67:26] quantum teleportation on the very next slide. [67:28] First, I want to tell a funny story about this. [67:31] So, you may have [67:34] heard the phrase spooky action at a distance. [67:37] This is Einstein coin that he was referring to this. [67:40] So, Einstein, Podolsky and Rosen are [67:42] three physicists who actually [67:45] came up with the idea of quantum entanglement. [67:46] They call it the EPR paradox, [67:48] there like the workings of [67:50] quantum mechanics result in this. [67:54] This is obviously absurd therefore, [67:56] quantum mechanics is garbage, [67:57] was the basic argument. [67:59] But then the experiments came out and they're like nope, [68:02] this is how it works, [68:05] the universe is in fact absurd, [68:07] locality is broken and so it's kind of [68:12] funny that a deep pair of paradox [68:14] is originally designed to discredit quantum mechanics, [68:17] it turned out to be the actual [68:19] way that the universe works, [68:20] I think it's a great little story. [68:22] Okay. Any other questions about entanglement, yes. [68:26] >> Let's say the same problem, the qubits. [68:29] >> Yes. [68:29] >> If we say that [68:32] this has a certain probability [68:34] collapsing to zero collapsing to one, [68:36] and then we observe that it collapses to one. [68:38] >> Yes. [68:39] >> How can we justify that our presumption that it had [68:43] a probability of collapsing to zero was valid? [68:47] >> Excellent question. [68:50] The answer is used a whole bunch of times and you see [68:52] that you get a 50 percent distribution of values. [68:53] >> Exactly they won't be occurring at the same time. [68:57] >> Experimentally, we know [68:59] that they occur at the same time. [69:00] With the 2013 experiment. [69:02] It entangled qubits took them far apart it used. [69:05] >> No, I mean the same qubits. [69:08] >> Yes. [69:10] >> It happened at time X. [69:12] >> Yes. [69:12] >> And now you take another pair of qubits [69:15] and this is another pair of [69:17] qubits but not necessarily the same ones. [69:19] >> Yes. [69:19] >> So, until it happened at that time, [69:22] that space or whatever, [69:25] you can't really tell that [69:27] this was happening with probability. [69:30] >> One half. [69:31] >> Yes. [69:32] >> You're questioning, okay so, [69:33] they could have decided ahead of time [69:34] for example maybe or. [69:36] >> Yeah, or probably the language of probability [69:39] itself is not active. [69:44] >> It works. Probability works I mean, [69:47] it's just the amplitude squared gives [69:51] you the classical probability of it [69:52] collapsing on zero or one I guess. [69:55] I'm not a 100 percent sure what you're driving at, so. [69:59] >> So, The question is once observed then we rationalize. [70:04] >> Once observed then we rationalize, yes. [70:06] And then if we do the experiment [70:07] a whole bunch of times we [70:09] see that it's about a 50 percent chance [70:10] of them both being zero or both being one. [70:12] Which in fact, I will show that to you live on [70:14] a quantum computer that we do that, okay. [70:17] All right, let's move on [70:19] teleportation This is the actual use which you [70:23] asked about and you've [70:25] probably read about quantum teleportation [70:27] again in pop science articles. [70:28] Needless to say, their explanation was complete trash, [70:32] made no sense at all, but now it will make [70:34] sense to you, okay? [70:35] It's the process by [70:37] which we take an arbitrary qubit state, [70:39] and transfer it across space and time somewhere else. [70:43] So, you use entangled qubits as a sort of [70:47] bridge to send a qubit from one place to another. [70:52] And here's a very important thing [70:55] it's called the no-cloning theorem. [70:57] You can transfer qubit states [70:59] so you can cut and paste them, [71:00] but you cannot copy them, [71:02] you cannot copy and [71:04] paste a qubit state, you cannot clone it. [71:05] This is called the no-cloning theorem. [71:07] It's actually pretty simple to prove you just show that [71:11] any off-such operation would not [71:12] be reversible or its own inverse, [71:14] but we're not going to go do that. [71:16] And, here's an important thing, the [71:18] teleportation despite using a [71:20] faster than light phenomenon of entanglement, [71:23] is not itself the whole protocol [71:24] is not itself faster than light [71:26] for communication because you [71:28] actually must exchange two classical bits. [71:30] So, if I'm teleporting my qubit to you in addition, [71:33] to us having an entangled qubit pair, [71:35] I also have to send you two bits of information [71:37] and we'll show why that is in the next slide. [71:39] So, everyone kind of conceptually grasp [71:41] the purpose of quantum teleportation? [71:44] Okay. So, here's what the circuit looks like. [71:48] We're not going to go over the math, there [71:50] are appendices to this slide deck [71:52] which you can see after the class to [71:54] go over the math but it gets a bit [71:55] complicated so we're not going to do it. [71:57] So, we have the qubit that we want to teleport [72:00] here we call it T and its value is phi, [72:02] is just this generic qubit value can be any value. [72:05] And then, we have [72:06] these two qubits A and [72:07] B which are both initialized to zero. [72:09] Now, you will recall this is the entanglement circuit. [72:13] So these two qubits are entangled, all right? [72:16] Now after they're entangled, [72:17] we'll say we have Alice and Bob. [72:20] Alice wants to send her entangled qubit to Bob. [72:22] So, Alice has these two qubits, [72:26] Bob has this qubit. [72:28] And these two qubits are entangled. [72:31] So, the qubits are like [72:33] these two qubits are separated right [72:34] after being entangled, basically. [72:36] Now, Alice then entangles [72:40] her qubit she wants [72:42] to teleport with the other two qubits. [72:44] So it's a three qubit entangled system. [72:46] If you were to write out [72:47] the product state you wouldn't be able to factor [72:48] it into three qubits. [72:51] Then she puts this qubit through the hadamard gate. [72:55] Finally, Alice measures both qubits in her possession, [72:59] and this results in two classical bits. [73:03] These are the two bits that Alice has to send to Bob, [73:07] and the measurement result of [73:09] this bit determines whether Bob [73:11] has to run his qubit through an X or bit flip gate. [73:16] And the measurement result of [73:18] this qubit to controls whether Bob has to run this qubit [73:21] through a new type of gate which we [73:23] haven't seen before is called the phase [73:24] flip gate or Z and this is what the matrix looks like. [73:29] And basically, once Bob has [73:32] applied those two gates or neither gate, [73:35] if both of these end up been [73:36] zero Bob doesn't have to apply anything, [73:38] he'll end up somewhat magically [73:40] with Alice's qubit value she wants to teleport. [73:44] Pretty nifty. And you might be like while we already [73:48] exchanging a qubit here why do we even care [73:51] like we're obviously just giving a qubit to Bob, [73:54] can't Alice just give her a qubit right there? [73:57] So, what you can do is you can [74:00] pre-entangle a whole bunch of [74:03] qubits a few billion qubits or something. [74:05] And then you ship them by mail they're called EPR halves. [74:09] You ship them by mail or something so Alice and Bob [74:12] have a big repository of these entangled qubits, [74:15] and then anytime Alice wants to send to a qubit to [74:17] Bob she can just use up one of the EPR pairs. [74:20] And at that point, [74:23] that EPR pair has been collapsed [74:26] can no longer be used so it's non-renewable resource. [74:29] But Alice can just send [74:31] as many qubits as she wants over to Bob. [74:33] Okay? Now, you might be saying, [74:35] "Well I don't really get this." [74:37] The math is in the appendix if [74:38] you really want to go see it. [74:39] It gets pretty complicated, [74:41] but I think I did an okay job of explaining it. [74:45] Okay, you might be like "Okay." [74:50] Oh by the way, I forgot to say, really important thing. [74:55] You may have heard that we can simulate [74:57] quantum computers on a classical computer [74:58] but it takes exponential slowdown or exponential memory. [75:01] This is the reason, if two qubits [75:05] become entangled you have to [75:06] keep their full product state around. [75:09] So, if N qubit with become entangled [75:11] you have a vector of size [75:12] two to the N you have to keep in memory. [75:14] And that is why, it takes [75:16] exponential memory to simulate [75:18] a quantum computer on a classical computer. [75:21] Pretty nifty, okay. [75:22] So maybe you're like, [75:24] "Okay this is all pretty [75:24] interesting, further learning goals." [75:26] You can learn the Deutsch-Jozsa algorithm that's [75:28] the one with N bits that I talked about, [75:30] and also Simon's periodicity problem which is another, [75:33] I figured out some property about this function. [75:35] We're not going to talk about the complexity stuff but [75:37] anyway you can also learn [75:38] Shor's algorithm, Grover's algorithm, [75:40] Quantum cryptographic key exchange, [75:41] that one's actually pretty simple [75:42] I recommend looking at that. [75:44] You can learn how they're actually [75:46] implemented in physical terms, [75:47] if you care about that. [75:49] An important thing quantum error correction since [75:51] these systems are so small like a spare cosmic gray could [75:54] just come out of nowhere and just wreck [75:56] your entire computation you [75:57] need very very stringent error Correction Schemes. [76:01] So, I think theoretically it takes [76:04] five physical qubits for [76:06] a single logical qubit like we've been operating that. [76:08] In practice, is looking more like we'll need one [76:10] or two hundred to get a qubit [76:12] of 100 percent probability [76:15] like we've been using pretty much. [76:17] So that's something to keep in mind. [76:18] When we see Google's coming out with [76:20] a 30 qubit computer that [76:21] maybe doesn't mean as much as we'd hope. [76:24] We've made only guys like [76:27] two or three really high-quality qubits. [76:29] And also quantum programming language design which [76:31] I will go over because I'll show you [76:34] a Q sharp example but anyway, recommended textbooks. [76:40] This one is my absolute favorite, [76:41] has the same title, [76:42] has the name of the talk, [76:43] Quantum Computing for Computer Scientists. [76:45] This algorithm is by our friend David Mermin, [76:47] the shut up and calculate guy. [76:49] It is a meat grinder of [76:51] a textbook but I started out with this one. [76:53] It was horrifying, it was just like, [76:55] but it skips a lot of steps basically. [76:58] It's more symbolic manipulation. [76:59] You won't see as many vectors and matrices. [77:01] I like to write out the vectors and [77:03] matrices to see what's going on which gets [77:05] really unwieldy when you're writing out like [77:07] a 64 by 64 vector or matrix. [77:10] But I like to have both of these. [77:13] So, I'll use this to fill in the gaps with this. [77:15] This has more interesting sides, stuff like that. [77:18] This is also in the MS library. [77:19] There's another one called [77:21] Quantum Computing Gentle Interaction, [77:22] also in the MS library. [77:23] I've heard mixed reviews or [77:24] semi decent reviews of it. I haven't looked at it myself. [77:27] There is also Mix of Quantum Development kit. [77:30] They have the docs. [77:31] They're actually pretty nice thing called [77:32] the Quantum Computing Simulator and Q Sharp as we'll see. [77:35] Now, I said I would end the talk on [77:37] some skepticism which there's an article, [77:41] came out I think was [77:42] Quantum Magazine pretty prominent recently, [77:44] interview with a mathematician who believes [77:48] that physically realizable [77:49] quantum computers cannot exist. [77:52] His basic argument simplifying is that the amount of [77:56] noise in the system grows [77:57] exponentially with the number of qubits. [78:00] So we cannot get a really large qubit system because [78:04] our computation will just keep collapsing [78:08] in the middle of it and [78:09] it's just like an exponential term. [78:11] And so, I'll be very sad if this happened. [78:16] I'd feel like the universe is against me. [78:18] It'd be really, it'd be very sad if [78:20] we could not realize the benefits of [78:22] Quantum Computing, like cosmetically sad. [78:26] But anyway, you can't argue with [78:28] the universe and yeah [78:30] you can read that article for some skepticism. [78:32] I think his name is Gil Kali, is the mathematician. [78:36] There's some appendices but [78:38] I'm going to do some demos now. [78:40] Okay, the first demo is [78:43] just the Doge Oracle problem in Q sharp. [78:45] So Q sharp is based on F-Sharp [78:47] and we have this function I've written, [78:51] IsBlackBoxConstant. [78:53] You've taken a black box and they tell [78:55] you whether it's constant. [78:57] Oh, gosh, sorry. Here, of course. [79:00] Okay. We have our function IsBlackBoxConstant [79:04] where it takes in a black box and it just [79:06] returns the Bool. Is it constant or not? [79:08] And it just uses this same protocol we went over. [79:11] It allocates two qubits, [79:13] calls one input one output, clears them, [79:15] sets them both to zero, does the preprocessing, [79:17] flips them, puts them through the Hadamard gate. [79:19] Then it sends them into the black box. [79:22] Afterward, it again put some through [79:24] the Hadamard gate and then it measures [79:27] both of them and again if the input results is one, [79:31] then it's constant otherwise its variable. [79:34] Okay? We have our black boxes [79:37] defined here. So, ConstantZero. [79:39] Again, remember it's nothing. [79:41] For ConstantOne we flip the output bit. [79:44] For Identity we run a CNOT gate with [79:48] input control up it is target [79:49] and Negation reducing our next, okay? [79:52] And we just have these, [79:54] like IsZeroConstantZero I call. [79:56] Is BlackBoxConstant with ConstantZero? [79:59] And then we have our classical driver. [80:01] Any quantum computation will have a sort of [80:03] classical computer to tell it what to do, [80:05] and so I ask [80:08] for each of those four, well, what's going on? [80:10] And we can run it and it runs on a simulator and we [80:14] see the output, IsConstantZero constant? [80:20] True. ConstantOne constant? [80:21] True. Identity constant? [80:23] False. Negation constant? [80:24] False. So there you go. [80:26] Yeah we wrote the Doge article, [80:28] ran it on a real quantum simulator, [80:30] you saw that it worked out. [80:31] Okay, the final demo of [80:33] the day and then I'll let you get out of [80:35] here is here we go. [80:40] This is called the IBM quantum experience. [80:44] There is a real like [80:46] world quantum computer that IBM has built. [80:49] It only has five qubits but they just let you online [80:53] just drag gates onto [80:56] this quantum circuit diagram and [80:57] run it on a real quantum computer. [80:58] So I thought it'd be pretty nifty if we demonstrated [81:01] entanglement live for you on stage. Let's see. [81:05] So, if you remember the first thing we do [81:07] is we drag a Hadamard gate onto [81:10] one debt and then we use the control not, oh no, okay. [81:17] So, the way that [81:18] quantum computers are constructed you can only [81:20] usually put CNOT between [81:22] certain debts basically it's just kind of, [81:25] otherwise it's just mechanically impossible to see. [81:28] Can we do that? Nope, okay. [81:31] How about, success. [81:39] Okay, we did it. [81:41] This is the CNOT gate. [81:44] You can see varying representations [81:46] of it. It's like the opass. [81:47] And I say we'll run it on [81:51] a quantum computer, oh right, measurement gates. [81:54] I forgot. We need to add [81:55] the two measurement gates obviously. [81:57] So we're measuring [81:59] both these qubits after entangling them. [82:01] And what we expect is to see them predominantly been [82:03] 0-0 and 1-1 right? Well, let's test it. [82:07] We'll call it that and [82:12] we can save the result from [82:13] cache but I want to do it live for you guys, [82:16] so I'm going to run a new execution. [82:20] And you can imagine right now deep at IBM Research Lab [82:24] nestled within a dilution refrigerator [82:27] operating at slightly above absolute zero, [82:29] we have real qubits being [82:31] entangled and measured thousands of [82:33] times for our entertainment. That's pretty cool. [82:37] >> It is. [82:37] >> That's pretty cool. [82:39] Okay, let's see if it's, [82:41] oh here we go, we got the results. [82:44] And executions it's pending, okay. [82:50] So it might take a couple minutes. [82:52] We're going to see now. [82:53] Does anyone have any questions while we're [82:54] waiting for this? Yes. [82:56] >> I don't know what question. [82:57] You said this experiment where [82:58] this sentiment tangled qubit to space and the satellite? [83:00] >> Yes. [83:00] >> Are we good at storing like qubits for a long time? [83:04] I'm really surprised they were able to [83:05] do that. I thought they kind of... [83:06] >> Yeah, yeah, that was actually a lot. [83:08] They will manage to send the entangled qubit up [83:11] file laser but, yes. [83:13] >> Okay. [83:14] >> I don't think we're that good at [83:15] storing qubits for awhile. [83:16] I think they're fairly short-lived. [83:18] >> [inaudible] [83:18] >> Yeah, they actually, [83:22] this Chinese satellite experiment, [83:24] they teleported a qubit up there. [83:25] So they sent one EPR half up by a laser and then they use [83:29] that EPR half to teleport [83:31] the qubit up there. Pretty cool. [83:33] >> That's awesome. [83:33] >> Yeah. [83:34] >> So we can send entangled qubits by laser? [83:35] >> You can send entangled qubits by laser, yes. [83:38] >> Okay, that's even cool. [83:39] >> Yeah. Let's see, it's still not. [83:46] Okay, that's fine. Anyway, yes. [83:49] >> You mentioned that there's [83:50] this new article by [83:52] the mathematician that says the noise has grown faster. [83:55] >> Yes. [83:55] >> What is the whole purpose of [83:57] a topological quantum computer resist that. [84:00] >> Of course. [84:01] Any corner computer will have issues with noise. [84:04] The topological quantum computer [84:05] is supposed to be better than [84:06] its IBM counterparts in [84:09] terms of noise but it'll still grow exponentially. [84:15] Like it can still be better but it [84:16] still runs into exponential barrier. [84:18] And so the next couple of years [84:20] are really sort of make or break for [84:21] quantum computing because we'll now have the ability to [84:26] create computers which run into [84:28] this exponential term if it exists, if it exists. [84:31] And so we will see with the next couple of years whether [84:33] quantum computing is really possible or not. [84:36] It's nervous and it makes me nervous but yeah, [84:41] because we'll run into [84:43] this limit probably like this year. [84:45] If Google does not [84:46] manage to demonstrate quantum supremacy [84:48] it'll be a bit scary I guess but yeah. [84:52] Let's see, we don't have, I'm just going to refresh this. [84:56] >> Question. [84:56] >> Yes. [84:57] >> Do we know what Google [84:58] uses Quantum theorem for, like what? [85:00] >> What they use it for? [85:03] >> Yeah. [85:04] >> I don't believe we do. I think they just have... [85:07] >> Is it experimental mostly? [85:12] >> Actually no. [85:14] They haven't announced what they use it for. [85:16] My manager is actually playing around with [85:18] the D-Wave simulator to... [85:20] >> The Canadian company. Is it the Canadian company? [85:23] >> D-Wave is Canadian company. [85:24] Yeah, everyone out there is [85:26] like really scammy and not really [85:27] quantum but everyone kind of believes [85:28] that they're quantum but it's a different paradigm. [85:30] It's like optimization basically [85:32] but it uses quantum computing. [85:34] They have a simulator you can use. [85:36] My manager has been using it to [85:38] kind of play around with finding routes in a network. [85:40] It has general applications like [85:42] that. Well, this is taking a lot. [85:46] >> The data is publicly available somewhere? [85:48] >> Yeah, it's in the invitation [85:50] and I think it'll probably be posted [85:52] on their resonant website or posted online. [85:59] >> So that application is like [86:00] a requesters type of application? [86:02] >> Yeah, yeah, it's like... [86:03] It's optimized. [86:05] You're able to express [86:08] the network graph in terms that like [86:10] an optimization result would be like [86:15] the least energy path in terms of like [86:17] the least cost path through the graph sort of. [86:20] That's different than the way the [inaudible]. [86:22] >> Open Shortest Path. [86:25] >> Come on, why isn't it going? [86:27] Pending. I'll be really sad if this [86:30] doesn't finish in time. Oh well. [86:34] >> So on D-Wave, [86:35] how are presentations centered you could do [86:38] classically faster than when they were doing. [86:41] So, they've improved in that or? [86:42] >> I don't know actually I haven't looked into that. [86:46] They're probably about comparable I would say. [86:48] Because given that it's just like [86:49] optimization and especially with the explosion of [86:52] machine learning there's been [86:54] a lot of development in making optimization better. [86:56] Optimization is like you have a surface and you're [86:58] trying to find the highest point or the lowest point. [87:01] So there's been a lot of research that goes into that. [87:06] We'll just run it from cache and okay. [87:15] Here we go, okay. So here's the results from cache. [87:19] Unfortunately our real execution didn't finish yet but. [87:22] So we see that indeed [87:25] they entangled some different qubit than ours but we [87:28] end up with 0-0 and 1-1 almost [87:31] exclusively but then there are some in [87:32] the middle because of the error rate, right? [87:34] So this is on a real quantum computer. [87:35] We have some error rate where it [87:36] doesn't exactly work according to [87:38] our model all the time but pretty cool, [87:40] these are entangled and they're [87:41] measured and we have that. [87:43] That's the experimental data right [87:44] there that entanglement is a real thing. [87:47] Yeah. Okay, that concludes the presentation. [87:52] Thank you very much. I hope you [87:54] all feel as though you followed the whole thing, [87:57] no real confusion and [87:59] feel that you could keep on learning. [88:01] This isn't like mad genius science. [88:03] This is very accessible science. [88:05] So, thank you very much.