@inproceedings{2b8faedb4dde4d6a86c41e974c718fbd,
title = "Quantum lower bounds by quantum arguments",
abstract = "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 input with a superposition of inputs. Using this method, we prove two new Ω(√N) lower bounds on AND of ORs and inverting a permutation and also provide more uniform proofs for some known lower bounds which have been previously proven via variety of different techniques.",
author = "Andris Ambainis",
year = "2000",
doi = "10.1145/335305.335394",
language = "English",
isbn = "1581131844",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
pages = "636--643",
booktitle = "Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000",
note = "32nd Annual ACM Symposium on Theory of Computing, STOC 2000 ; Conference date: 21-05-2000 Through 23-05-2000",
}