Quantum lower bounds by quantum arguments

Details Quantum lower bounds by quantum arguments Quantum lower bounds by quantum arguments

2000-02-24

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

Physics

Quantum Physics

14 pages, to appear at STOC'00

Scientific paper

We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. If the algorithm works correctly, its state becomes entangled with the superposition over inputs. We bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. Using this method, we prove two new $\Omega(\sqrt{N})$ lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via variety of different techniques.

Affiliated with

Also associated with

No associations

Rating

Quantum lower bounds by quantum 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 Quantum lower bounds by quantum arguments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum lower bounds by quantum arguments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-358760