Quantum Lower Bounds by Quantum Argument
β
Andris Ambainis
π
Article
π
2002
π
Elsevier Science
π
English
β 160 KB
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