THE QUANTUM QUERY COMPLEXITY OF AC
THE QUANTUM QUERY COMPLEXITY OF AC
复制标题
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
P. Beame
中科院分区：
文献类型：
--
作者：
P. Beame
我们表明，从[n]到[n]的输入函数F是否为2到1或几乎需要2-1的任何量子算法都需要θ（n）查询。从[2n -2]到[n]的功能f是汇总的。是由Aaronson和Shi的ω（N2/3）给出的ω（（n/logn）2/3），用于元素独特问题[1]。
We show that any quantum algorithm deciding whether an input function f from [n] to [n] is 2-to-1 or almost 2-to-1 requires Θ(n) queries to f . The same lower bound holds for determining whether or not a function f from [2n − 2] to [n] is surjective. These results yield a nearly linear Ω(n/ logn) lower bound on the quantum query complexity of AC0. The best previous lower bound known for any AC0 function was the Ω((n/ logn)2/3) bound given by Aaronson and Shi’s Ω(n2/3) lower bound for the element distinctness problem [1].