量子科技中心_量科网

文献中已有关于量子样本复杂度和量子查询复杂度的紧界，但量子时间复杂度（即量子电路规模）的紧界仍悬而未决。本文提出一个框架，通过从量子样本复杂度归约，建立量子态置换不变性测试中量子时间复杂度的下界。应用该框架，在给定输入量子态样本访问权限时，获得一系列匹配下界，包括：1. Buhrman、Cleve、Watrous和de Wolf（Phys. Rev. Lett. 2001）提出的SWAP测试在估计纯度 \(\operatorname{tr}(ρ^2)\) 和内积 \(\operatorname{tr}(ρσ)\) 时达到时间最优；2. Ekert、Alves、Oi、Horodecki、Horodecki和Kwek（Phys. Rev. Lett. 2002）提出的Shift测试在估计高阶泛函 \(\operatorname{tr}(ρ^k)\) 时达到时间最优；3. Harrow和Montanaro（J. ACM 2013）提出的多体纯态乘积性测试器达到时间最优；4. Lloyd、Mohseni和Rebentrost（Nat. Phys. 2014）提出的LMR协议在实现纯态反射算符时达到时间最优；5. Wang和Zhang（IEEE Trans. Inf. Theory 2025）提出的采样器对纯态达到时间最优；6. Wang和Zhang（ICALP 2026）提出的纯态迹距离和保真度估计器达到时间最优。据该团队所知，这是首个能够系统性地建立量子时间复杂度紧下界的方法。