量子科技中心_量科网

最坏情况到平均情况的归约是复杂性理论的基石，它为最坏情况下的计算难度与平均情况下的计算难度之间架起了桥梁。尽管最近的研究利用加性组合数学中的深度工具，为基础问题展示了此类归约，但这些方法通常面临较高的复杂性及次优的开销。该工作聚焦于量子场景，为矩阵-向量乘法问题提出了一种新归约方案，其效率更高且概念上比先前构造更为简洁。通过将难度自放大技术适配至量子领域，研究人员获得了一种对成功概率依赖性更优的量子最坏情况到平均情况归约，为量子细粒度复杂性中更广泛的应用奠定了基础。