Lower bounds for randomized and quantum query complexity using Kolmogorov arguments

Details Lower bounds for randomized and quantum query complexity using Kolmogorov arguments Lower bounds for randomized and quantum query complexity using Kolmogorov arguments

2003-11-27

arxiv.org/abs/quant-ph/0311189v1

Physics

Quantum Physics

Scientific paper

We prove a very general lower bound technique for quantum and randomized query complexity, that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks and Szegedy. As an immediate consequence of our main theorem, adversary methods can only prove lower bounds for boolean functions $f$ in $O(\min(\sqrt{n C_0(f)},\sqrt{n C_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 by Hoyer, Neerbek and Shi to give a quantum lower bound on ordered search and sorting.

Affiliated with

Also associated with

No associations

Rating

Lower bounds for randomized and quantum query complexity using Kolmogorov arguments does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower bounds for randomized and quantum query complexity using Kolmogorov arguments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower bounds for randomized and quantum query complexity using Kolmogorov arguments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-519549