经典验证量子计算超越多项式层级

研究证明，相对经典 oracle，经典多项式时间验证器可在无计算假设下验证一个位于多项式层级之外、由量子多项式时间精确判定的语言。该协议为 public-coin，完美完备性、可靠性错误至多 1/4，消息数在常数因子内最优。研究还针对递归 Fourier sampling 变体证明了新的 switching 定理。