

关键词: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],但证明方法大多依赖于函数的具体性质。
这些针对特定函数的结果留下了一个更一般的问题:
对于什么样的函数
02
主要结果
论文从函数的多项式逼近入手回答这一问题。给定精度
论文首先证明了一般性的 DQC1 完全性定理。设
DQC1 完全性意味着,该问题不仅能够在 DQC1 模型中高效求解,而且 DQC1 中的任意计算任务都可以高效规约到它。与此前逐个函数建立困难性证明的方法相比,这一定理为一大类矩阵函数的归一化迹估计提供了统一的困难性证明。
论文进一步研究经典算法的查询复杂度。对于每行最多有
因此,当稀疏度
03
技术贡献
证明上述 DQC1 完全性结果,关键在于如何将已知的 DQC1 完全问题规约到矩阵函数的归一化迹估计。此前的方法通常利用特定函数的展开形式,并逐一分析相应的谱求和误差[3, 5, 6]。为了避免针对每种函数分别处理,论文将量子线路到哈密顿量的构造、周期 Jacobi 矩阵的谱理论与多项式最佳一致逼近理论结合起来,建立了统一的规约方法。
研究团队首先从量子线路
不过,判别式
借助这一构造,目标函数
为了证明经典查询下界,论文进一步考虑 Forrelation 问题[8]在 DQC1 模型中的归一化迹版本
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
实验室公众号:
课题组近期动态

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

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

点击“阅读原文”转论文链接
内容中包含的图片若涉及版权问题,请及时与我们联系删除



评论
沙发等你来抢