关键词:DQC1 完全性; 归一化迹估计; 多项式逼近次数

导  读

本文介绍入选第 67 届 IEEE 计算机科学基础年度研讨会(FOCS 2026)的论文 DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians。该工作由北京大学计算机学院李彤阳、王昕兆与清华大学季铮锋、中国科学院数学与系统科学研究院邵长鹏、张宇欣合作完成。论文作者按姓氏字母序署名。


论文研究对数局域哈密顿量函数的归一化迹估计问题,证明了一大类函数对应的迹估计问题具有 DQC1 完全性。此外,论文在稀疏矩阵查询模型下,建立了经典查询复杂度关于多项式逼近次数的指数下界。两项结果共同表明,多项式逼近次数是刻画此类问题计算复杂性的关键参数。在稀疏矩阵查询模型下,量子算法与经典算法之间还存在指数级的查询复杂度差距。

↑扫码跳转论文

论文地址:

https://arxiv.org/abs/2604.01519


01

研究背景

量子计算的能力与所使用的量子资源密切相关。通常,量子计算模型允许将量子比特初始化为纯态。相比之下,Knill 和 Laflamme 于 1998 年提出的单个纯态量子比特计算模型(One-Clean-Qubit Model,也称 DQC1 模型)[1],初始时只有一个量子比特处于纯态,其余量子比特均处于最大混合态。尽管初态受到严格限制,DQC1 仍能高效完成一些目前尚无已知高效经典算法的任务,因此成为研究受限量子计算能力的重要模型。


估计量子线路的归一化迹是 DQC1 模型中的一个基本任务,也是一个 DQC1 完全问题[1, 2]。由此可以进一步考虑矩阵函数的归一化迹估计。给定一个作用在  个量子比特上的哈密顿量 ,以及定义在其谱上的函数 ,研究目标是估计其中  是  的特征值。直观来说,就是计算  在各个特征值上的取值,再求这些函数值的平均值。


这类谱统计量在数值线性代数、统计物理和机器学习中有着广泛应用。例如,矩阵指数的迹与统计物理中的配分函数有关,矩阵对数的迹则对应对数行列式,后者在高斯过程等机器学习模型中经常出现。已有研究分别针对指数函数、矩阵幂、矩阵逆和矩阵对数等情形建立了 DQC1 困难性结果[3–6],但证明方法大多依赖于函数的具体性质。


这些针对特定函数的结果留下了一个更一般的问题:


对于什么样的函数  ,归一化迹估计具有 DQC1 完全性?是否存在一个统一的参数,能够刻画不同函数对应问题的计算难度?


02

主要结果

论文从函数的多项式逼近入手回答这一问题。给定精度 ,用多项式在指定区间上逼近函数  时,要使最大误差不超过 ,所需的最低次数称为  的逼近次数(approximate degree),记为 。如果  能够由低次多项式逼近,便可以通过计算若干矩阵幂的迹来估计矩阵函数的归一化迹,这也是已有经典算法的基本思路[5]。因此,多项式逼近次数自然会影响迹估计算法的计算代价。


论文首先证明了一般性的 DQC1 完全性定理。设  为常数精度下的逼近次数, 表示次数不超过  的多项式对  的最佳一致逼近误差。对于满足  且  的连续函数 ,论文证明,对数局域哈密顿量函数的归一化迹估计具有 DQC1 完全性。这里的对数局域哈密顿量指可以写成多项式个局部项之和、且每项至多作用于  个量子比特的哈密顿量。


DQC1 完全性意味着,该问题不仅能够在 DQC1 模型中高效求解,而且 DQC1 中的任意计算任务都可以高效规约到它。与此前逐个函数建立困难性证明的方法相比,这一定理为一大类矩阵函数的归一化迹估计提供了统一的困难性证明。


论文进一步研究经典算法的查询复杂度。对于每行最多有  个非零元素的稀疏矩阵,已有经典算法的查询复杂度上界包含  这样的指数因子[5]。这种对逼近次数的指数依赖能否消除?研究团队证明,在上述函数条件下,存在一类   -稀疏的厄米矩阵,使经典算法即使只要求常数加性误差,也至少需要 次查询。相比之下,已有量子算法可利用块编码和量子奇异值变换[7],以  量级的查询次数完成估计[10]。


因此,当稀疏度  为固定常数时,经典算法与量子算法在查询复杂度上存在关于逼近次数的指数级差距。这一结果说明,经典查询复杂度对逼近次数的指数依赖在最坏情形下无法消除。


03

技术贡献

证明上述 DQC1 完全性结果,关键在于如何将已知的 DQC1 完全问题规约到矩阵函数的归一化迹估计。此前的方法通常利用特定函数的展开形式,并逐一分析相应的谱求和误差[3, 5, 6]。为了避免针对每种函数分别处理,论文将量子线路到哈密顿量的构造、周期 Jacobi 矩阵的谱理论与多项式最佳一致逼近理论结合起来,建立了统一的规约方法。


研究团队首先从量子线路  出发,构造带有可调参数的环形哈密顿量 。对于  的每个特征相位 ,在与之对应的不变子空间上, 可以表示为一个周期 Jacobi 矩阵 。它的特征多项式具有如下形式:其中  是一个与  无关的  次多项式,称为周期 Jacobi 矩阵的判别式。它满足 。因此,如果能根据目标函数  构造合适的判别式,就有可能从   中恢复原量子线路的归一化迹信息。


不过,判别式   并不能任意选择。对任意 ,方程  都需要有  个实根(按重数计),这要求  具有特定的交替振荡结构。因此,不能直接把一般函数  当作判别式。论文的关键观察是,虽然  本身未必具有这样的振荡结构,但它的最佳一致逼近误差却具有等振性质。 根据切比雪夫等振定理(Chebyshev Equioscillation Theorem), 与其  次最佳一致逼近多项式之差,会在至少  个有序点上交替取得绝对值相同、符号相反的极值。研究团队再取一个逼近误差更小的  次多项式,将它与前述最佳逼近多项式之差适当归一化,得到满足判别式条件的  。最后,利用周期 Jacobi 矩阵的逆谱结果,确定哈密顿量中的可调参数。


借助这一构造,目标函数  可以表示为三项之和:一个低次多项式 、判别式  的常数倍,以及一个大小可控的误差项。其中, 与特征相位  无关,可以单独计算。原因在于,长度小于环长的闭合路径无法完整绕环一周,因而不会留下边界上的特征相位因子。而 ,因此判别式项对迹的贡献正比于 ,保留了原量子线路的特征相位信息。扣除低次多项式部分的贡献并控制误差项后,就能通过矩阵函数的归一化迹估计来估计线路  的归一化迹,从而完成 DQC1 困难性规约。相邻最佳逼近误差的比值条件则保证规约中的误差足够小。由于周期 Jacobi 矩阵的维数等于逼近次数 ,这一参数也就自然出现在最终的复杂度结果中。


为了证明经典查询下界,论文进一步考虑 Forrelation 问题[8]在 DQC1 模型中的归一化迹版本  ,并证明这一迹估计问题同样具有 DQC1 完全性。在下界证明中,研究团队借助 Shepherd 对四次查询迹估计任务的经典查询下界[9],将其与前述线路到哈密顿量的规约结合,并控制构造所得矩阵的稀疏度,最终得到关于逼近次数的指数下界。


04

总结与展望

对于对数局域哈密顿量,本文以多项式逼近次数为参数,为一大类函数的归一化迹估计建立了 DQC1 完全性定理。在标准稀疏矩阵查询模型下,论文进一步证明了经典查询复杂度关于逼近次数的指数下界。这两项结果从不同的计算模型出发,说明多项式逼近次数在理解矩阵函数归一化迹估计的计算难度时具有重要作用。


在证明方法上,论文利用最佳多项式逼近误差的振荡性质,构造了能够编码量子线路迹信息的周期 Jacobi 矩阵。这一思路也为研究其他矩阵函数及谱统计量的计算复杂性提供了新的工具。后续研究进一步表明,在保持逼近次数要求的前提下,原先关于相邻最佳逼近误差比值的条件还可以放宽为 Lipschitz 连续性。


参考文献

[1] E. Knill and R. Laflamme. Power of One Bit of Quantum Information. Physical Review Letters, 81, 5672–5675 (1998).

[2] D. J. Shepherd. Computation with Unitaries and One Pure Qubit. arXiv:quant-ph/0608132 (2006).

[3] F. G. S. L. Brandão. Entanglement Theory and the Quantum Simulation of Many-Body Physics. PhD thesis, Imperial College London (2008). arXiv:0810.0026.

[4] C. Cade and A. Montanaro. The Quantum Complexity of Computing Schatten p-norms. Proceedings of TQC 2018, LIPIcs 111, 4:1–4:20 (2018).

[5] R. Edenhofer, A. Hasegawa, and F. Le Gall. Dequantization and Hardness of Spectral Sum Estimation. arXiv:2509.20183 (2025).

[6] C. Shao and X. Wang. DQC1-hardness of estimating log-determinants. Research note (2025).

[7] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics. Proceedings of STOC 2019, 193–204 (2019).

[8] S. Aaronson and A. Ambainis. Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. SIAM Journal on Computing, 47(3), 982–1038 (2018). Conference version: STOC 2015.

[9] D. J. Shepherd. Quantum Complexity: Restrictions on Algorithms and Architectures. PhD thesis, University of Bristol (2009). arXiv:1005.1425 (2010).

[10] Y. Zhang and C. Shao. Quantum Space-Depth Tradeoffs for Coherent Block Encodings. arXiv:2607.01843v2 (2026).


图文 | 王昕兆

PKU QUARK Lab


关于量子算法实验室

量子算法实验室 QUARK Lab (Laboratory for Quantum Algorithms: Theory and Practice) 由李彤阳博士于2021年创立。该实验室专注于研究量子计算机上的算法,主要探讨机器学习、优化、统计学、数论、图论等方向的量子算法及其相对于经典计算的量子加速;也包括近期 NISQ (Noisy, Intermediate-Scale Quantum Computers) 量子计算机上的量子算法。


实验室新闻:#PKU QUARK

实验室公众号:


课题组近期动态

ICML 2026 | 仅用比较完成梯度测试与估计

HPCA 2026 | DC-MBQC:首个面向基于测量的量子计算的分布式编译框架

NeurIPS 2025 | 计算一般形式多玩家博弈的相关均衡的近最优量子算法

NeurIPS 2025 | QCircuitBench: 面向大模型驱动的量子算法设计的基准测试



—   版权声明  —

本微信公众号所有内容,由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料,版权属北京大学前沿计算研究中心微信所有;从公开渠道收集、整理及授权转载的文字、图片和音视频资料,版权属原作者。本公众号内容原作者如不愿意在本号刊登内容,请及时通知本号,予以删除。

点击“阅读原文”转论文链接

内容中包含的图片若涉及版权问题,请及时与我们联系删除