量子算法导论——超越经典的第一个证明Deutsch-Jozsa算法它不解决实际问题却首次向世界宣告量子计算机真的可以比经典计算机更快。在前四篇文章中我们搭建了量子编程环境学会了操作量子门理解了测量和退相干的残酷现实。现在终于到了见证奇迹的时刻——我们要亲手运行第一个真正意义上的量子算法。1992年David Deutsch和Richard Jozsa提出了一个看似“无聊”的问题如何判断一个函数是常数函数还是平衡函数这个问题本身毫无实用价值但它给出了一个惊人的结论量子计算机只需要一次函数调用而经典计算机在最坏情况下需要2ⁿ⁻¹1次。这是人类历史上第一个严格证明量子计算具有指数级加速能力的算法。2025年11月Richard Jozsa教授本人做客武汉大学珞珈讲坛再次讲述了这段历史。他在演讲中指出Deutsch-Jozsa算法的意义不在于解决实际问题而在于它首次揭示了量子计算潜力的存在。今天我们就沿着这位先驱的足迹亲手实现这个具有里程碑意义的算法。1. 问题描述一个刻意设计的游戏1.1 神秘的黑盒函数想象你面前有一个黑盒子它接受一个n位的二进制字符串比如001、“110”输出一个比特0或1[f: {0,1}^n \rightarrow {0,1}]现在有人向你保证这个函数一定属于以下两种类型之一常数函数Constant对所有输入输出都相同。要么全是0要么全是1。平衡函数Balanced对一半的输入输出0另一半输出1。注意当n≥1时2ⁿ一定是偶数所以“一半”是严格定义的。你的任务只通过查询这个黑盒子判断它到底是常数函数还是平衡函数。 举例当n2时输入有4种可能00、01、10、11。常数函数示例f(00)0, f(01)0, f(10)0, f(11)0平衡函数示例f(00)0, f(01)1, f(10)0, f(11)11.2 为什么这个问题有意义你可能会问这么刻意的问题有什么用确实Deutsch-Jozsa算法本身没有实用价值——现实世界的问题很少会保证函数要么常数要么平衡。但它的理论意义无与伦比第一个证明量子优势它首次严格证明了在某些问题上量子计算机可以指数级快于经典计算机。引入了关键概念量子并行性、相位反冲、量子干涉——这些后来在Shor算法、Grover算法中扮演核心角色的思想都在这个简单算法中首次亮相。测试平台价值由于实现相对简单Deutsch-Jozsa算法常被用来验证量子硬件的基本功能和量子编程框架的正确性。2. 经典解法运气好时很快运气差时很慢2.1 最优情况两次就能确定假设我们运气特别好。第一次查询某个输入得到0第二次查询另一个输入得到1。那么立刻就能判断这是平衡函数因为常数函数不可能给出两种不同的输出。2.2 最坏情况需要查一半以上但如果运气不好呢假设我们不断查询但每次都得到相同的输出比如全是0查了1次都是0 → 还可能是常数函数全0或平衡函数恰好这1次是0查了2次都是0 → 仍不能确定…查了2ⁿ⁻¹次都是0 → 仍然不能确定因为平衡函数恰好有2ⁿ⁻¹个0我们可能恰好查到了所有输出0的输入直到查了2ⁿ⁻¹1次如果还全是0这时才能肯定这一定是常数函数因为平衡函数最多只有2ⁿ⁻¹个0不可能在第2ⁿ⁻¹1次还输出0。所以最坏情况下经典算法需要2ⁿ⁻¹1次查询。当n10时这已经是513次当n100时这个数字比宇宙中的原子还多。2.3 概率算法呢如果允许一定概率出错我们可以提前终止。例如连续查到k个0后函数为常数的概率是 (1 - 1/2^{k-1})。当k10时这个概率已经超过99.9%。但如果要求100%确定就必须查2ⁿ⁻¹1次。3. 量子解法一次查询确定无疑Deutsch-Jozsa算法的核心思想是将函数的所有输入同时查询量子并行性然后通过干涉让错误结果相消让正确结果相长。3.1 算法电路图整个算法的量子电路如图所示┌───┐ ┌───┐┌─┐ q0: ┤ H ├──────■───┤ H ├┤M├ ├───┤ │ ├───┤├─┤ q1: ┤ H ├──────┼───┤ H ├┤M├ ├───┤ │ ├───┤├─┤ q2: ┤ H ├──────┼───┤ H ├┤M├ └───┘┌─────┴────┐└───┘└╥┘ q3: ─────┤ U_f(x) ├───────╫─ └──────────┘ ║ c: 2/═══════════════════════╩═ 0电路包含两个寄存器输入寄存器n个量子比特初始化为|0⟩辅助寄存器1个量子比特初始化为|1⟩注意不是|0⟩3.2 逐步推导让我们一步步推导算法的状态变化。步骤0初始化[|\psi_0\rangle |0\rangle^{\otimes n} |1\rangle]步骤1对所有量子比特施加H门辅助寄存器的|1⟩经过H门变成(|0⟩ - |1⟩)/√2带负号。输入寄存器的n个|0⟩经过H门变成所有计算基态的等幅叠加[|\psi_1\rangle \frac{1}{\sqrt{2n}}\sum_{x0}{2^n-1} |x\rangle \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}]步骤2应用Oracle U_fOracle的作用是(U_f |x\rangle|y\rangle |x\rangle|y \oplus f(x)\rangle)。当辅助寄存器处于(|0⟩ - |1⟩)/√2时会发生一个神奇的现象——相位反冲[\begin{aligned}U_f \left( |x\rangle \frac{|0\rangle - |1\rangle}{\sqrt{2}} \right) |x\rangle \frac{|0 \oplus f(x)\rangle - |1 \oplus f(x)\rangle}{\sqrt{2}} \ \begin{cases}|x\rangle \frac{|0\rangle - |1\rangle}{\sqrt{2}}, \text{if } f(x)0 \|x\rangle \frac{|1\rangle - |0\rangle}{\sqrt{2}}, \text{if } f(x)1\end{cases} \ (-1)^{f(x)} |x\rangle \frac{|0\rangle - |1\rangle}{\sqrt{2}}\end{aligned}]瞧函数值f(x)从辅助寄存器“反冲”到了输入寄存器的相位上。现在整个状态变为[|\psi_2\rangle \frac{1}{\sqrt{2n}}\sum_{x0}{2^n-1} (-1)^{f(x)} |x\rangle \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}]步骤3对输入寄存器再次施加H门此时辅助寄存器已经完成任务可以忽略。对输入寄存器施加H门后[|\psi_3\rangle \frac{1}{2n}\sum_{x0}{2n-1}\sum_{y0}{2^n-1} (-1)^{f(x) x\cdot y} |y\rangle]其中 (x\cdot y x_0y_0 \oplus x_1y_1 \oplus \cdots \oplus x_{n-1}y_{n-1}) 是按位点乘模2加法。步骤4测量输入寄存器测量得到 (|0\rangle^{\otimes n}) 的概率是[P(0\cdots 0) \left| \frac{1}{2n}\sum_{x0}{2^n-1} (-1)^{f(x)} \right|^2]现在关键来了如果 (f) 是常数函数那么所有 ((-1)^{f(x)}) 都相等要么全是1要么全是-1。求和结果为 (\pm 2^n)概率为1。如果 (f) 是平衡函数恰好一半 ((-1)^{f(x)} 1)另一半 ( -1)求和结果为0概率为0。因此测量得到全0 → 常数函数测量得到任何非0结果 → 平衡函数一次查询确定无疑3.3 算法的核心相位反冲相位反冲Phase Kickback是Deutsch-Jozsa算法的核心技巧也是许多量子算法的基石。它的美妙之处在于我们从未直接测量辅助寄存器却通过它将f(x)的信息“刻”在了输入寄存器的相位上相位本身不可直接观测但通过第二次H门和测量这些相位信息转化为可观测的振幅信息干涉效应让平衡函数的振幅恰好相消常数函数的振幅恰好相长4. 构造Oracle把函数变成量子电路在量子算法中函数 (f) 不能直接调用必须实现为一个量子Oracle(U_f)。Oracle是量子电路中的一个“黑盒子”模块它对计算基态的作用是确定性的但对叠加态的作用则体现了量子并行性。4.1 常数函数的Oracle常数函数非常简单如果 (f(x) \equiv 0)Oracle就是恒等变换什么门都不用加如果 (f(x) \equiv 1)需要对辅助比特施加X门相当于告诉辅助寄存器“输出永远是1”注意即使加了X门在相位反冲机制下也会产生正确的相位因子。4.2 平衡函数的Oracle构造平衡函数Oracle的经典方法是用输入寄存器的每个比特作为控制位对辅助寄存器施加CNOT门。为什么这样是平衡的以3量子比特为例# 平衡Oracle的经典构造fromqiskitimportQuantumCircuitdefcreate_balanced_oracle(n):创建n比特的平衡函数Oracle标准构造oracleQuantumCircuit(n1,nameU_f)# 用每个输入比特控制辅助比特foriinrange(n):oracle.cx(i,n)# 第n位是辅助比特returnoracle这个电路的效果是当输入 (x) 中有奇数个1时辅助比特被翻转奇数次输出1当输入 (x) 中有偶数个1时辅助比特被翻转偶数次输出0这正好是奇偶校验函数——一半输入有奇数个1一半有偶数个1完美平衡。4.3 更灵活的平衡Oracle我们还可以通过添加X门来“掩码”控制位实现不同的平衡函数defcreate_masked_balanced_oracle(n,mask):用二进制掩码mask指定哪些输入比特参与控制oracleQuantumCircuit(n1,nameU_f)# 根据掩码添加X门将控制位从0反转为1foriinrange(n):ifmask[i]1:oracle.x(i)# 添加CNOT门foriinrange(n):oracle.cx(i,n)# 恢复X门foriinrange(n):ifmask[i]1:oracle.x(i)returnoracle这个电路的效果是对于输入 (x)当 ((x \oplus mask)) 的奇偶性为奇数时输出1。改变mask就可以得到不同的平衡函数。5. Qiskit实战实现Deutsch-Jozsa算法现在让我们用Qiskit完整实现Deutsch-Jozsa算法分别测试常数函数和平衡函数。5.1 导入所需模块importnumpyasnpfromqiskitimportQuantumCircuit,transpilefromqiskit_aerimportAerSimulatorfromqiskit.visualizationimportplot_histogramimportmatplotlib.pyplotasplt# 设置随机种子保证可重复性np.random.seed(42)5.2 常数函数测试defdeutsch_jozsa_constant(n,constant_value0): 测试常数函数的Deutsch-Jozsa算法 constant_value: 0表示全0常数1表示全1常数 # 创建电路n个输入比特 1个辅助比特 n个经典比特用于测量qcQuantumCircuit(n1,n)# 步骤0初始化辅助比特为|1⟩qc.x(n)# 将辅助比特从|0⟩变为|1⟩# 步骤1对所有比特施加H门foriinrange(n1):qc.h(i)# 步骤2应用常数函数Oracleifconstant_value1:# 如果常数函数输出全1需要翻转辅助比特# 但注意相位反冲机制下X门在H门之后会正确产生相位qc.x(n)# 步骤3对输入寄存器再次施加H门foriinrange(n):qc.h(i)# 步骤4测量输入寄存器qc.measure(range(n),range(n))returnqc# 测试n3的常数函数全0n3qc_constdeutsch_jozsa_constant(n,constant_value0)print( 常数函数全0电路 )print(qc_const.draw())# 运行模拟simAerSimulator()jobsim.run(qc_const,shots1000)countsjob.result().get_counts()print(\n测量结果:,counts)预期输出应该几乎全是000理论概率100%。5.3 平衡函数测试defdeutsch_jozsa_balanced(n): 测试平衡函数的Deutsch-Jozsa算法 使用标准奇偶校验Oracle qcQuantumCircuit(n1,n)# 步骤0初始化辅助比特为|1⟩qc.x(n)# 步骤1对所有比特施加H门foriinrange(n1):qc.h(i)# 步骤2应用平衡函数Oracle奇偶校验foriinrange(n):qc.cx(i,n)# 步骤3对输入寄存器再次施加H门foriinrange(n):qc.h(i)# 步骤4测量输入寄存器qc.measure(range(n),range(n))returnqc# 测试n3的平衡函数qc_baldeutsch_jozsa_balanced(n)print(\n 平衡函数电路 )print(qc_bal.draw())# 运行模拟jobsim.run(qc_bal,shots1000)countsjob.result().get_counts()print(\n测量结果:,counts)预期输出应该几乎没有000而是各种非零结果理论上概率100%得到非零。5.4 可视化对比# 绘制结果对比fig,(ax1,ax2)plt.subplots(1,2,figsize(12,4))# 常数函数结果job_constsim.run(qc_const,shots1000).result()counts_constjob_const.get_counts()plot_histogram(counts_const,axax1,title常数函数结果)# 平衡函数结果job_balsim.run(qc_bal,shots1000).result()counts_baljob_bal.get_counts()plot_histogram(counts_bal,axax2,title平衡函数结果)plt.tight_layout()plt.show()5.5 封装成通用函数为了方便测试不同n和不同类型的函数我们可以封装一个通用函数defrun_deutsch_jozsa(n,function_typeconstant,shots1000): 运行Deutsch-Jozsa算法 参数: n: 输入比特数 function_type: constant0, constant1, 或 balanced shots: 运行次数 qcQuantumCircuit(n1,n)# 初始化辅助比特为|1⟩qc.x(n)# 第一层H门qc.h(range(n1))# Oracleiffunction_typeconstant0:# 什么都不做passeliffunction_typeconstant1:qc.x(n)eliffunction_typebalanced:# 标准奇偶校验Oracleforiinrange(n):qc.cx(i,n)else:raiseValueError(function_type必须是 constant0, constant1, 或 balanced)# 第二层H门只在输入寄存器上qc.h(range(n))# 测量qc.measure(range(n),range(n))# 运行simAerSimulator()jobsim.run(qc,shotsshots)resultjob.result()countsresult.get_counts()# 判断结果is_constant(0*nincountsandlen(counts)1)returncounts,is_constant# 测试不同情况forftypein[constant0,constant1,balanced]:counts,is_construn_deutsch_jozsa(4,ftype)print(f{ftype}: 测量结果{counts}, 判断为常数?{is_const})5.6 验证相位反冲机制为了更直观地理解相位反冲我们可以直接查看态向量fromqiskit_aerimportAerSimulatordefinspect_phase_kickback(n):查看相位反冲后的态向量qcQuantumCircuit(n1)# 初始化辅助比特为|1⟩qc.x(n)# 第一层H门qc.h(range(n1))# 应用平衡Oracle奇偶校验foriinrange(n):qc.cx(i,n)# 不进行第二层H门直接保存态向量qc.save_statevector()simAerSimulator(methodstatevector)resultsim.run(qc).result()statevectorresult.get_statevector()# 提取相位信息print(f态向量维度:{len(statevector)})print(前8个分量的相位:)foriinrange(min(8,len(statevector))):ampstatevector[i]phasenp.angle(amp)/np.pi# 以π为单位print(f|{i:0{n}b}⟩:{amp:.3f}, 相位 {phase:.2f}π)returnstatevector# 查看n3时的相位stateinspect_phase_kickback(3)你会看到有些分量的相位是0有些是π即乘了-1这正是f(x)的信息。6. 为什么这很重要算法的深层意义6.1 指数加速的首次证明Deutsch-Jozsa算法的伟大之处不在于它的实用性而在于它首次严格证明了量子计算机可以指数级快于经典计算机。经典算法需要O(2ⁿ)次查询量子算法只需要O(1)次——这个对比在1992年是震撼性的。6.2 三个核心量子特性的完美展示这个简单算法几乎囊括了量子计算的所有核心思想量子特性在算法中的作用叠加同时查询所有可能的输入相位反冲将函数值编码为量子相位干涉让错误结果相消正确结果相长后来的Shor算法、Grover算法本质上都是这些思想的更复杂应用。6.3 没有纠缠也能加速有趣的是研究表明Deutsch-Jozsa算法即使在没有纠缠的情况下也能实现加速。这提示我们量子加速的根源可能比我们想象的更深不完全是纠缠的功劳。6.4 理论与实践的距离当然Deutsch-Jozsa算法也有明显的局限问题本身是刻意设计的没有实用价值要求函数要么常数要么平衡现实中很少见Oracle模型假设函数可以完美实现为量子电路这在复杂函数上并不容易但这不妨碍它成为每个量子计算学习者的必修课——它是理解更复杂算法的基石。7. 延伸思考与练习7.1 思考题为什么辅助寄存器要初始化为|1⟩而不是|0⟩如果初始化为|0⟩相位反冲还会发生吗相位反冲的本质为什么 (U_f |x\rangle(|0\rangle-|1\rangle)) 会产生 ((-1)^{f(x)}) 因子请用矩阵运算验证。经典随机算法如果允许一定概率出错经典算法需要多少次查询当n100时要保证99.9%的置信度需要查多少次7.2 编程练习自定义平衡函数用掩码方式实现不同的平衡函数验证算法是否仍然正确。噪声环境测试给电路添加T₁和T₂噪声参考第四篇观察退相干如何影响算法成功率。可视化相位修改inspect_phase_kickback函数绘制所有分量的相位分布图。比较不同n测试n从1到10的算法运行时间验证量子模拟器的时间复杂度注意模拟器本身是指数复杂的但真实量子硬件是线性的。8. 小结从Deutsch-Jozsa到更广阔的世界今天我们学习了量子计算史上第一个里程碑算法——Deutsch-Jozsa算法。回顾一下关键点问题判断一个函数是常数函数还是平衡函数经典复杂度最坏情况需要2ⁿ⁻¹1次查询量子复杂度只需要1次查询核心技巧叠加 相位反冲 干涉历史意义首次证明量子指数加速的可能性这个算法虽然简单却包含了量子算法设计的全部要素。掌握它你就掌握了理解Shor算法、Grover算法的基础。下一篇文章我们将学习另一个重要算法——Grover搜索算法。它能在无序数据库中实现平方级加速比Deutsch-Jozsa更接近实用也是NISQ时代最有希望率先落地的量子算法之一。我们将看到如何用振幅放大的思想在O(√N)时间内找到目标项。思考题参考答案下一期公布欢迎在评论区讨论辅助寄存器初始化为|1⟩是为了创造(|0⟩-|1⟩)态这个态在受控操作下会产生相位反冲。如果初始化为|0⟩受控操作后得到|f(x)⟩不会产生相位因子。参考资料[1] Origin Quantum6.2 Deutsch–Jozsa算法介绍[2] Blackwell, A. (2025). Hardware Aware Study of Near-Term Quantum Algorithms[3] TuringQDeutsch-Jozsa 算法详解[4] 武汉大学新闻网Richard Jozsa畅谈量子物理百年历程[5] CSDN博客量子计算二十一Deutsch-Josza算法[6] Qiskit教程Deutsch-Jozsa algorithm implementation[7] ACM Digital LibraryQuantum advantage without entanglement[8] IBM Quantum LearningThe Deutsch-Jozsa algorithm[9] Qiskit API Documentationqiskit.aqua.algorithms.DeutschJozsa本文为系列第五篇后续将持续更新欢迎点赞收藏不错过每一次更新。