Name
Abstract | ||
|---|---|---|
We prove a very general lower bound technique forquantum and randomized query complexity, that is easyto prove as well as to apply. To achieve this, we introducethe use of Kolmogorov complexity to query complexity.Our technique generalizes the weighted, unweightedmethods of Ambainis, and the spectral method of Barnum,Saks and Szegedy. As an immediate consequence of ourmain theorem, it can be shown that adversary methodscan only prove lower bounds for boolean functions f in0(\min (\sqrt {nC_0 (f)} ,\sqrt {nC_1 (f)})), where C_0, C_1 is the certificate complexity, and n is the size of the input. We also derive a general form of the ad hoc weighted method used byHøyer, Neerbek and Shi to give a quantum lower bound on ordered search and sorting. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/050639090 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
quantum query complexity,boolean function,immediate consequence,kolmogorov arguments,randomized query complexity,certificate complexity,kolmogorov complexity,lower bound,n c_0,n c_1,adversary method,bound technique,lower bounds,quantum computing | Boolean function,Quantum,Discrete mathematics,Combinatorics,Kolmogorov complexity,Upper and lower bounds,Quantum computer,Spectral method,Mathematics,Certificate | Journal |
Volume | Issue | ISSN |
38 | 1 | 0097-5397 |
ISBN | Citations | PageRank |
0-7695-2120-7 | 33 | 1.58 |
References | Authors | |
17 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sophie Laplante | 1 | 189 | 16.75 |
| Frédéric Magniez | 2 | 570 | 44.33 |