量子科技中心_量科网

对于N×N厄米特矩阵（其特征值满足λ₁ ≥ λ₂ ≥ ... ≥ λ_N）而言，近似计算第k个谱隙Δₖ=|λₖ−λₖ₊₁|及其对应中点μₖ=(λₖ+λₖ₊₁)/2是特征值问题的重要特例，在科学与工程领域具有广泛应用。该研究团队提出一种量子算法，仅需使用对数级量子比特即可将这些值逼近至加性误差εΔₖ。值得注意的是，在QRAM模型中，其总复杂度（查询次数与门操作）上界为O(N²/ε²Δₖ²·polylog(N,1/Δₖ,1/ε,1/δ))，其中ε,δ∈(0,1)分别表示精度与成功概率。对于大谱隙Δₖ，该算法相较经典算法最优复杂度O(N^ω·polylog(N,1/Δₖ,1/ε))（其中ω≲2.371为矩阵乘法指数）具有加速优势。算法分析中的关键技术步骤是制备合适的随机初始态，该步骤最终使研究人员能在保持N二次方复杂度的前提下，高效计数低于阈值的特征值数量。在黑箱访问模型中，该工作还报告了判定二元矩阵（虽非对称）谱隙存在性的Ω(N²)查询下界。