Name
Abstract | ||
|---|---|---|
The quantum adversary method is one of the most versatile lower-bound meth- ods for quantum algorithms. We show that all known variants of this method are equivalent: spectral adversary (Barnum, Saks, and Szegedy, 2003), weighted adversary (Ambainis, 2003), strong weighted adversary (Zhang, 2005), and the Kolmogorov complexity adver- sary (Laplante and Magniez, 2004). We also present a few new equivalent formulations of the method. This shows that there is essentially one quantum adversary method. From our approach, all known limitations of these versions of the quantum adversary method easily follow. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11523468_105 | IEEE Transactions on Information Theory |
Keywords | DocType | Volume |
quantum algorithm,lower bound,quantum computer,quantum physics | Journal | 3580 |
Issue | ISSN | ISBN |
1 | Theory of Computing, 2(1):1-18, 2006 | 3-540-27580-0 |
Citations | PageRank | References |
33 | 1.61 | 20 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert Spalek | 1 | 234 | 12.63 |
| Mario Szegedy | 2 | 3358 | 325.80 |