On Exact Quantum Query Complexity

被引：31

作者：

Montanaro, Ashley ^{[1
]}

Jozsa, Richard ^{[1
]}

Mitchison, Graeme ^{[1
]}

机构：

[1] Univ Cambridge, DAMTP, Ctr Quantum Informat & Fdn, Cambridge, England

来源：

ALGORITHMICA | 2015年 / 71卷 / 04期

基金：

英国工程与自然科学研究理事会;

关键词：

COMPUTATION;

D O I：

10.1007/s00453-013-9826-8

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：775 / 796

页数：22