Quantum lower bounds by quantum arguments
| dc.creator | Ambainis, Andris | |
| dc.date | 2000-02-24 | |
| dc.date.accessioned | 2026-07-07T05:59:39Z | |
| dc.date.available | 2026-07-07T05:59:39Z | |
| dc.description | 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 $Ω(\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. | |
| dc.description | 14 pages, to appear at STOC'00 | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0002066 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0002066 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/88759 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | Quantum lower bounds by quantum arguments | |
| dc.type | text |