Quantum lower bounds by quantum arguments
By Andris Ambainis. Symposium on the Theory of Computing, 2000
486 citations recorded by the source corpus.
We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with on 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 Ω(√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 a variety of different techniques.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
View Paper: https://www.semanticscholar.org/paper/6073f459648db19bfc56f526b4fe47c77052f5db
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
Citations in the corpus
- The role of relative entropy in quantum information theory (2001, methodology): “The most general way of doing such a query in the quantum case is the black box unitary transformation (Ambainis, 2000) Any other unitary transformation performing a query matching the states of the M and the C registers, could be constructed from the above type of query.”