从叠加态到干涉：理解Deutsch-Jozsa算法与量子计算入门

三月初整理量子计算笔记翻到编号0303那一篇标题写的是“世界本来就是叠加态”。那是我第一次彻底看懂Deutsch-Jozsa算法的当天记下的想法也是从那天起我真正理解了量子计算的出发点。如果你刚接触量子计算想找一个既简单又有足够深度、能一次性看清叠加态到底是怎么参与计算的入口Deutsch-Jozsa算法几乎是绕不开的第一个。它总共就两个Hadamard层加一个黑盒查询线路上站着的却是所有后面大算法的共同骨架用叠加态铺开指数维空间让函数值改变相位再用干涉把答案收束到一组可测量的振幅上。这篇笔记就从这个算法出发聊聊叠加态为什么值得重新认识以及DJ算法为什么被称为量子计算的第一块敲门砖。1. 叠加态不是玄学它就是我们世界的底层描述1.1 一个抛硬币的比喻曾经误导了我很久很多科普讲叠加态时都会先说抛硬币硬币还在空中你没看到它的正反所以它是“正反叠加”的。这个比喻直观但它实际上是错的。错误在于硬币在空中时物理上早就确定了正反你不知道只是因为你没看这是认识论意义上的不确定性和量子叠加毫无关系。真正的量子叠加指的不是“你不知道”而是体系的状态本身就等于多个基矢的线性组合。拿常见的电子自旋来说一个电子可以处在|↑⟩和|↓⟩的叠加态α|↑⟩β|↓⟩上其中α、β是复数并且|α|²|β|²1。在没有测量之前电子不处于原始的“朝上”或“朝下”状态它的全部信息都藏在这组系数里。测量会以|α|²的概率给出|↑⟩以|β|²给出|↓⟩但这只是测量行为本身带来的投影不是“‘原本’就藏在某个确定方向”后被我们发现了。为了更准确理解可以把叠加态想成一个向量坐标轴是|↑⟩和|↓⟩状态就是平面上的一个单位向量两个方向的分量同时存在。这和抛硬币“要么正要么反只是我不知道”有本质区别。这个区别正是量子计算能跑出额外信息量的前提。双缝实验是另一个佐证。单个电子一粒一粒地发射最终还是在屏上形成干涉条纹——如果你用“粒子在某条路径上”来描述它条纹完全无法解释。只有当每个电子都同时走了两条缝、以两条路径的振幅相干叠加时干涉项才会出现。所以叠加态不是数学上的把戏它是实验反复确认的物理事实。1.2 宏观世界为什么看不到叠加退相干把答案藏起来了既然叠加态是物理实在的基本形态为什么我们日常看不到一个杯子同时出现在两个位置关键在于退相干。量子系统一旦和环境发生相互作用状态就会和环境的无数自由度纠缠起来。这些纠缠不可控相当于给系统的相位信息加上了一大堆随机扰动宏观系统在极短时间通常远小于10⁻¹³秒内就丧失了相干性于是你能观察到的只有“要么这、要么那”的经典投影。量子计算机最难的部分之一就是在这段相干时间内完成计算让量子比特保持叠加精心设计门操作最后赶在退相干发生之前完成测量。从这个角度看“世界本来就是叠加态”这句话不算夸张。微观世界的基本运动规律由薛定谔方程描述它是线性方程线性方程天然允许解的叠加。宏观世界看起来不叠加是因为我们生活在退相干这一端而已。理解了这个物理背景你再看Deutsch-Jozsa算法里的那句“对每个输入做并行处理”就不会觉得是科幻了。它只是让整个计算过程始终停留在叠加态输入是叠加的、Oracle是叠加的、输出是叠加的直到最后一刻测量。2. Deutsch-Jozsa问题的本质一个概念上很小的黑盒谜题2.1 黑盒、常数函数和平衡函数的定义DJ问题可以这样讲假设你面前有一个黑色盒子它接收一个n位的0/1字符串作为输入输出一个二进制的0或1。盒子里是什么逻辑你完全不知道。但你被告知这个函数满足一个承诺它要么是常数函数也就是无论输入什么输出永远都是0或者永远都是1要么是平衡函数也就是在全部2^n种输入中恰好一半输出0、另外一半输出1。你的任务是用尽量少的查询次数确定这盒子到底是哪一种。为什么叫“黑盒”因为我们不在乎它内部电路的复杂度只统计你调用它多少次。这种设定在实际工程里当然很理想化但它非常适合用来对比经典计算机和量子计算机的信息获取手段。既然题目只要求“判断类型”经典的做法是逐点试探而量子算法则可以让2^n个输入点同时在黑盒中走过一遍。问题规模被完全剥离成“你到底需要查几次才能定性”这正好是复杂度理论最干净的实验场。2.2 经典查询复杂度的计算指数真的是硬伤我们认真算一下经典确定性算法的开销。最坏情况是这样的假设你一连试了若干个输入全部输出0。这时候你依然无法区分眼前到底是常值函数还是那个“只有最后一个输入输出1、其余全为0”的极端平衡函数。必须继续试。更精确地说判定“这不是常值而是平衡”的下界是2^(n-1)1次因为平衡函数恰好只有一半输入输出1如果这2^n个输入中输出1的那些恰好排在后面你需要翻过2^(n-1)个输出0的输入之后才能遇到第一个输出1。如果你是确认“这是常值0”那更要试完全部输入才能排除平衡的可能。综合最坏情况经典确定性算法的查询次数约为2^(n-1)1。n20时这个是524289次看起来还能忍。n50大约是5.6×10^14次任何常规计算设备都会失去耐心。n200时这个数字超过10^60整个可观测宇宙的原子数量也才约10^80量级即使是理论上的经典算法也望尘莫及。随机化算法也好不到哪去如果采样不到1你永远只能给出一个带误差的概率结论无法确定性地说明“这是常值”。也就是说在查询复杂度这个评价维度里经典算法实打实地撞上了一堵指数墙。算法类型最坏情况查询次数是否确定性结论经典确定性算法约2^(n-1)1是经典随机算法固定采样期望指数级且无法完全确定否带误差Deutsch-Jozsa量子算法1次是量子算法这边给出的答案异常简单一次Oracle调用配合有限的量子门操作就能确定性的判定常值还是平衡。这个巨大的反差正是DJ算法在量子信息课程里拥有“第一课”地位的原因。3. 单比特Deutsch算法的手推全程3.1 为什么辅助比特要初始化成|1⟩正式推导之前先交代线路结构。Deutsch算法需要两个量子比特第一个是数据比特承载输入第二个是辅助比特用来把Oracle的信息“反冲”到数据比特上。辅助比特初始化为|1⟩而不是更常见的|0⟩。这一点非常关键直接决定整个算法能不能工作。我们对两个比特分别施加Hadamard门。Hadamard门的作用是H|0⟩(|0⟩|1⟩)/√2H|1⟩(|0⟩-|1⟩)/√2。于是初始态|0⟩|1⟩变成(|0⟩|1⟩)/√2 ⊗ (|0⟩-|1⟩)/√2。注意辅助比特处在|0⟩-|1⟩这个“负相位叠加态”上这正是为相位反冲准备的。接着让Oracle作用。Oracle实现的是|x⟩|y⟩ → |x⟩|y⊕f(x)⟩。当y是|0⟩-|1⟩时代进去看一下|0⊕f(x)⟩ - |1⊕f(x)⟩。如果f(x)0得到|0⟩-|1⟩如果f(x)1得到|1⟩-|0⟩也就是-(|0⟩-|1⟩)。合起来就是(-1)^{f(x)} (|0⟩-|1⟩)。Oracle虽然没有直接改变数据比特的内容却把函数值注入到了辅助比特的全局相位中。由于辅助比特初始是|1⟩而不是|0⟩这个负号才会出现如果初始是|0⟩经过H得到|0⟩|1⟩代入相似推导会发现函数值不会产生任何可测差异等于白忙。这个靠|1⟩构造反冲的技巧后面所有黑盒类量子算法都会用到。3.2 四种函数逐一走一遍结论停在两个正交态上单比特情形下f一共只有四种可能穷举一下常值0f(0)0, f(1)0、常值1f(0)1, f(1)1、恒等函数f(0)0, f(1)1、取反函数f(0)1, f(1)0。经过Oracle之后第一个比特处于(|0⟩±|1⟩)/√2正负号由f(0)⊕f(1)决定。如果f(0)f(1)两个分支同相整体是±(|0⟩|1⟩)/√2如果f(0)≠f(1)两个分支反相整体是±(|0⟩-|1⟩)/√2。关键信息全在那一个正负号里。现在对第一个比特再做一次Hadamard。H会把(|0⟩|1⟩)/√2变回|0⟩把(|0⟩-|1⟩)/√2变回|1⟩整体符号不影响测量概率。于是两条清晰的路浮现出来f为常值测量第一个比特一定得到0f为平衡测量第一个比特一定得到1。辅助比特从头到尾都维持在(|0⟩-|1⟩)/√2不需要测量。f类型f(0)f(1)Oracle后的数据比特相位再H后测量结果常值0000⟩常值111-(0⟩恒等010⟩-取反10-(0⟩-整个流程只调用了一次Oracle而经典最坏需要两次。单比特的例子虽然小但相位反冲、干涉这些要素一个都不少。我至今记得第一次亲手把这个推导写在纸上时的感受那些叠加的数学符号不是抽象摆设它们是真正让两个分支“同时经过”黑盒、再用最后一道Hadamard把差异放大的物理过程。4. 扩展到n比特并行、相位反冲与干涉的三重奏4.1 H^⊗n把指数个输入同时装进一个状态从1比特到n比特线路结构几乎不变前n个数据比特全部置于|0⟩辅助比特置|1⟩全部过Hadamard过Oracle对前n个数据比特再做一次Hadamard最后测量。由于Hadamard门对每个比特独立作用n个|0⟩经过H^⊗n变成(1/√(2^n))∑_{x∈{0,1}^n}|x⟩。这个求和号不再只是数学简写它意味着量子寄存器实际处于2^n个计算基态的均匀叠加中。这就是常说的“量子并行性”的载体你只需要n个量子比特就能线性地维护一个维度为2^n的向量。把Oracle作用上去辅助比特同样采用|0⟩-|1⟩的初始化于是相位反冲给出(-1)^{f(x)}|x⟩。现在每一个x的振幅都包含了f(x)的信息而且这种包含是以相干的方式进行的各个x的振幅保持确定的相对相位不会像经典那样变成混合态。下一步的关键是怎么把“藏在相位里的信息”重新转化成“能被测量的信息”。4.2 第二次Hadamard和干涉为什么平衡函数的全0振幅一定为0这里需要给出Hadamard在n比特下的公式。对于n比特计算基态|x⟩H^⊗n作用后等于(1/√(2^n))∑_{z∈{0,1}^n} (-1)^{x·z}|z⟩其中x·z x_1z_1⊕x_2z_2⊕…⊕x_nz_n是模2内积。把Oracle之后的态 1/√(2^n)∑_x (-1)^{f(x)}|x⟩ 再做一次H^⊗n就会得到 1/2^n ∑_x ∑_z (-1)^{f(x)}(-1)^{x·z}|z⟩。我们关心的重点是|0…0⟩项的振幅代入z0由于x·00系数变成1/2^n∑_x (-1)^{f(x)}。如果f是常值这个求和结果要么是1要么是-1模平方取1也就是说测量必然全0。如果f是平衡恰好一半x对应(-1)^{f(x)}1另一半对应-1求和严格为零测量永远不可能得到全0态。两条结论都只花了一次Oracle调用。宏观上看第二次Hadamard的作用是让2^n个分支的振幅进行干涉同向的增强、反向的抵消。常值函数的同相叠加让能量全部集中到全0态平衡函数的正负对消让全0态的振幅严格归零。这是量子干涉最纯粹的一次展示比任何抽象描述都直观。4.3 这里的“同时计算”和经典“并行”有什么不同还要澄清一点说量子算法“同时计算了所有输入”容易引起误解。在2^n个输入的叠加态上应用Oracle确实相当于所有输入同时经过了U_f但我们的寄存器同时只保存一个叠加向量而不是2^n个独立答案。如果真的在Oracle之后立刻测量你会以近似均等的概率得到某个随机的|x⟩所有分支结果混在一起你拿不到任何有效信息。只有通过第二次Hadamard让不同x的振幅干涉把答案编码成“某个基态是否出现”这个并行才转化为真正有用的加速。打个比方你不能让2^n个学生同时把答案交给你但你可以让他们把答案写在同一个黑板上按“同相加、反相消”的规则自动汇总。量子并行性的本质不是多线程而是向量空间的指数维度加干涉筛选。这一点越到后面的量子算法越重要。5. 上机实操用Qiskit写一个DJ线路并观察噪声5.1 一个完整的可运行示例理论推完了上代码。我用Qiskit写一个最直接的实现辅助比特用最后一位数据比特用前n位。为方便演示平衡函数我取最简单的f(x)b·x mod 2其中b是任意非零n比特串。这样的线性函数恰好有一半输入输出1满足平衡函数的定义常值函数直接用f(x)0。构造Oracle时要注意常值函数不需要任何操作平衡函数只需在b的每个为1的位上放一个CNOT控制位是数据比特目标位是辅助比特。代码如下from qiskit import QuantumCircuit from qiskit_aer import AerSimulator def build_dj_circuit(n, bNone): qc QuantumCircuit(n 1, n) # 辅助比特置 |1 qc.x(n) # 对所有比特做 Hadamard qc.h(range(n 1)) # Oracle: # 如果 b 为 None表示常值函数 f(x)0什么也不做 # 如果 b 非空表示平衡函数 f(x)b·x mod 2 if b is not None: for i in range(n): if b[i] 1: qc.cx(i, n) # 对数据比特再做 Hadamard qc.h(range(n)) # 测量数据比特 qc.measure(range(n), range(n)) return qc sim AerSimulator() for name, b in [(constant, None), (balanced, 101)]: qc build_dj_circuit(3, b) counts sim.run(qc, shots1024).result().get_counts() print(name, counts)这段代码在模拟器上跑常值函数给出的计数集中在000平衡函数给出的计数集中在非000的串上。为什么不是只出现一个非零串因为平衡函数用的是f(x)b·x干涉之后所有非全零的|z⟩都有概率最终分布与b的具体值有关。但判断规则只有一个只要测到非全零串f就不是常值反之如果测到000f就是常值。注意这里的shots1024只是重复实验的次数算法本身真正需要的查询次数只有一次。5.2 从模拟器切换到真实量子硬件后事情变得微妙模拟器上干净利落的结果在真机上会走样。我把同一个线路提交到IBM公开量子计算机上跑过几次第一次跑平衡函数测出十几个000和其他杂散结果原因是门错误、退相干、测量误差叠加到了一起。这个时候你反而需要一个统计判据设置一个阈值例如000的占比接近1则判常值明显偏离则判平衡。噪声不是量子算法设计层面能解决的它属于量子纠错和误差缓解的范畴。但正因为真机上的这个体验我才真正理解为什么DJ算法在理论教学中那么有用、在实际生产中却看不到它的身影。真实硬件的噪声让单个理想查询变成了多次统计重复Oracle本身的实现成本也没有被查询复杂度计入。可以说DJ算法是复杂度理论里最干净的语言却不是工程视角下划算的快捷键。不过亲手跑一次从模拟器到真机的全流程那种从“数学上的必然”跌落到“物理上的概率”的落差比看书深刻得多。6. 关于量子优势的三个常见误解6.1 量子并行不是同时跑所有答案常见科普文喜欢说量子计算机同时计算了2^n种情况所以它快2^n倍。上面的推导已经表明这个说法不严谨。在计算过程中确实有2^n个分支同时存在但它们不是2^n个独立的“答案副本”它们共享同一个向量中的复数系数彼此之间会干涉。你在Oracle之后立刻测量得到的只是一个随机基态看不到任何汇总结果。只有精心安排第二次Hadamard以及后续算法里的量子傅里叶变换让不同分支的振幅按同相增强、反相对消的规则合并答案才会以“某个结果是否出现”的形式呈现。所以量子优势的精确来源是构造干涉让错误结果的振幅相互抵消让正确结果的振幅集中放大。这个机制在Simon算法、Shor算法、Grover算法里反复出现Deutsch-Jozsa只不过是最小的演示单元。6.2 Oracle不是免费的别把查询复杂度理解成全流程加速DJ问题的前提是黑盒已存在比较的只是“查询次数”。但如果把你需要解决的问题本身摊开构建那个黑盒可能需要指数资源或者Oracle设计本身就是高成本的。实际应用场景里Oracle通常是一个把数据加载进量子态的预处理单元它的开销不能忽略。所以DJ算法不是用来直接解决工程问题的工具它更像复杂度理论的第一块试金石证明量子查询复杂度确实可以指数低于经典查询复杂度。在此之上发展的Simon算法、Shor算法有更真实的背景和更强的实用价值。理解到这一层就不会被“量子霸权”的标题党带偏优势永远是对特定计算模型、特定成本度量而言的。6.3 理解了DJ算法就拿到了读懂其他量子算法的钥匙把DJ算法的四步抽象出来制备均匀叠加态以相位形式调用Oracle施加某种变换典型是Hadamard或量子傅里叶变换让振幅干涉测量并获得答案。几乎所有量子算法都踩在这四步上。Shor算法的核心是相位估计本质也是把周期信息编码进相位再通过量子傅里叶变换读出来Grover算法是用Oracle给目标项振幅加负号再用“均值反转”让目标振幅放大。每次我再读这些算法时脑子里都会浮现出DJ线路中那两个Hadamard层的对称感。可以说学会手推Deutsch-Jozsa不是学了一个孤立的小技巧而是拿到了量子算法共同的说明手册。最后说一点我个人在实际操作中的体会。我每次带新人入门都让他们先不看辅助比特的|1⟩初始化把这个比特改成|0⟩再跑一遍他们看到结果立刻变乱才会真正记住相位反冲为什么是算法的心脏。如果你也想动手试试建议先用模拟器把单比特的四种函数各跑一次记录每次测量结果再去云端真机跑一次同样的线路你会在噪声里直观感受到退相干意味着什么。这个小算法简单到几行代码就能完成背后的解释却足够支撑你理解接下来所有的量子算法。