Quantum lower bounds by quantum arguments
<|reference_start|>Quantum lower bounds by quantum arguments: 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.<|reference_end|>
@article{ambainis2000quantum,
    title={Quantum lower bounds by quantum arguments},
    author={Andris Ambainis},
    journal={arXiv preprint arXiv:quant-ph/0002066},
    year={2000},
    archivePrefix={arXiv},
    eprint={quant-ph/0002066},
    primaryClass={quant-ph cs.CC}
}