机构名称：
¥ 1.0
[ Aar10 ] 提出了一个量子算法，只需 1 次查询，时间复杂度为 O (log N ) = O ( n )。接下来，只需证明 D 可以欺骗具有拟多项式 ( N ) (或 2 poly( n ) ) 门的恒定深度电路，即电路无法区分 D 和均匀分布 U 。Aaronson “几乎”做到了这一点，特别是他证明了关系版本 BQP 和 PH (我们允许具有许多有效输出的问题的版本) 的 oracle 分离。[ RT19 ] 通过稍微修改 Forrelation 分布并证明布尔电路的下限，最终解决了量子复杂性理论中这个巨大的未解问题。这是他们的主要定理，
量子复杂性理论
主要关键词
相关文件推荐
