On Exact Quantum Query Complexity
On Exact Quantum Query Complexity
复制标题
DOI：
10.1007/s00453-013-9826-8
复制
发表时间：
2015-04-01
期刊：
影响因子：
1.1
通讯作者：
Mitchison, Graeme
中科院分区：
文献类型：
--
作者：
Montanaro, Ashley;Jozsa, Richard;Mitchison, Graeme
我们提出了几个具有精确量子查询复杂度的布尔函数族，其量子查询复杂度是其经典查询复杂度的常数倍（在1/2到2/3之间），并表明这些函数的最佳量子算法不能通过简单地计算位对的偶对来获得。我们还从编码理论的角度描述了非自适应精确量子查询复杂性模型，并在此背景下完整地描述了对称布尔函数的查询复杂性。这些结果最初是受到数值解决小问题规模的量子查询复杂性的半确定程序的启发。
We present several families of total boolean functions which have exact quantum query complexity which is a constant multiple (between 1/2 and 2/3) of their classical query complexity, and show that optimal quantum algorithms for these functions cannot be obtained by simply computing parities of pairs of bits. We also characterise the model of nonadaptive exact quantum query complexity in terms of coding theory and completely characterise the query complexity of symmetric boolean functions in this context. These results were originally inspired by numerically solving the semidefinite programs characterising quantum query complexity for small problem sizes.