Unbounded-error quantum query complexity
Unbounded-error quantum query complexity
复制标题
DOI：
10.1016/j.tcs.2011.04.043
复制
发表时间：
2011-08-12
影响因子：
1.1
通讯作者：
Raymond, Rudy
中科院分区：
文献类型：
--
作者：
Montanaro, Ashley;Nishimura, Harumichi;Raymond, Rudy
本文研究了布尔函数在无界错误情形下的量子查询复杂度，在这种情形下，只要求查询算法以严格大于1/2的概率成功。我们表明，就像在通信复杂性模型中一样，对于任何（部分或全部）布尔函数，无界错误量子查询复杂性恰好是其经典对应复杂性的一半。此外，结合查询和通信复杂性的结果，我们证明了Buhrman-Cleve-Wigderson [STOC'98]将量子查询算法转换为通信协议的“黑箱”方法即使在无界错误设置下也是最优的，我们还研究了一个相关的设置，称为弱无界错误设置，其中查询算法的成本由q+log给出（1/2（p 1/2）），其中q是进行的查询的数量，p > 1/2是算法的成功概率。在对比的情况下，通信的复杂性，我们展示了一个紧密的乘法Theta（log n）分离量子和经典的查询复杂性在此设置的部分布尔函数。对于一些研究得很好的全布尔函数，也证明了它们之间的渐近等价性。皇冠版权所有（C）2011由Elsevier B. V.出版。保留所有权利。
This work studies the quantum query complexity of Boolean functions in an unbounded-error scenario where it is only required that the query algorithm succeeds with a probability strictly greater than 1/2. We show that, just as in the communication complexity model, the unbounded-error quantum query complexity is exactly half of its classical counterpart for any (partial or total) Boolean function. Moreover, connecting the query and communication complexity results, we show that the "black-box" approach to convert quantum query algorithms into communication protocols by Buhrman-Cleve-Wigderson [STOC'98] is optimal even in the unbounded-error setting.We also study a related setting, called the weakly unbounded-error setting, where the cost of a query algorithm is given by q+log(1/2(p 1/2)), where q is the number of queries made and p > 1/2 is the success probability of the algorithm. In contrast to the case of communication complexity, we show a tight multiplicative Theta(log n) separation between quantum and classical query complexity in this setting for a partial Boolean function. The asymptotic equivalence between them is also shown for some well-studied total Boolean functions. Crown Copyright (C) 2011 Published by Elsevier B.V. All rights reserved.