量子科技中心_量科网

Forrelation问题是一个核心问题，它展示了量子计算与经典计算能力之间存在指数级差距。在该问题中，给定对两个n位布尔函数f和g的查询访问权限，目标是估算Forrelation函数forr(f,g)，该函数用于衡量g与f的傅里叶变换之间的相关性。 与先前解析方法不同，该工作为Forrelation问题提供了新的线性代数视角。研究人员建立了Forrelation问题与弯曲布尔函数之间的联系，并基于此分析了Forrelation问题的极值版本——其目标是对forr(f,g)=1和forr(f,g)=-1这两种极端情况进行区分。 研究表明，该问题可通过一次量子查询以100%成功率解决，但即便允许算法存在1/3的失败概率，经典随机化查询仍需要Ω~(2^(n/4))次，这突显了一次精确量子查询的非凡能力。该工作还研究了输入f,g可由小型经典电路计算的受限变体问题，并在密码学假设下证明了其经典计算难度。