Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer
Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer
复制标题
任何大小为 N 的 AND-OR 公式都可以在量子计算机上在 N^{1/2 o(1)} 时间内计算
DOI：
10.1137/080712167
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Shengyu Zhang
中科院分区：
文献类型：
--
作者：
A. Ambainis;Andrew M. Childs;B. Reichardt;R. Spalek;Shengyu Zhang
对于任何大小为 N 的 AND-OR 公式，都存在基于离散时间量子行走的有界误差 N1/2+o(1) 时间量子算法，该算法在黑盒输入上评估该公式。平衡或“近似平衡”的公式可以在 O(radicN) 查询中进行评估，这是最佳的。由此可见，量子查询复杂度的 (2-o(1)) 次方是公式大小的下界，几乎正面解决了 Laplante、Lee 和 Szegedy 提出的开放问题。
For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.