量子科技中心_量科网

该研究团队提供了新的证据，表明量子电路比经典电路具有显著更强的能力。他们证明，相对于随机预言机，多项式大小的量子电路可以采样出子指数大小的经典电路甚至无法在TV距离1-o(1)内近似的分布。Aaronson和Arkhipov（2011年）的先前工作已在精确采样（即TV距离0）的情况下展示了这种分离，但对于近似采样的分离此前仅针对均匀算法为人所知。 该研究证明中的一个关键要素是山川-詹德利（Yamakawa-Zhandry，2022年）搜索问题的经典查询复杂性的新硬度放大引理。该研究证明，任何查询算法家族共同找到k个不同解的概率在k上呈指数衰减。