量子科技中心_量科网

该研究团队致力于探索当矩阵元素略微偏离零值时近似计算矩阵积和式的算法。这项研究源于理解线性光学和玻色子采样的经典计算复杂性的目标（参考Aaronson与Arkhipov 2011年、Eldar与Mehraban 2017年的工作）。Barvinok的插值方法能有效近似积和式，前提是能为多项式per(zJ+W)确立足够大的无零点区域——其中J为全1矩阵，W是具有独立零均值元素的随机矩阵。 研究人员证明：当W的元素服从标准复高斯分布时，随机多项式per(zJ+W)的所有零点都位于半径为Õ(n^(-1/3))的圆盘内，这为元素偏差达到Ω̃(n^(-1/3))时提供了近似算法。此前在偏差小于1/polylog(n)时不存在高效算法，且学界未知是否存在通常满足|z|≥1的零点z。作为补充结论，该团队发现主体零点（即(1-ε)n个零点）的模长为Θ(n^(-1/2))，这一特性避免了插值方法与积和式近似计算平均情况困难性猜想的矛盾。 该工作还针对具有复顶点逸度的广义图模型建立了硬核模型的类似无零点区域。此外，研究人员通过普适性结果证明了具有独立同分布亚指数元素的随机矩阵W的无零点区域。