On Quantum Versions of the Yao Principle
| dc.creator | de Graaf, Mart | |
| dc.creator | de Wolf, Ronald | |
| dc.date | 2001-09-14 | |
| dc.date.accessioned | 2026-07-07T06:02:42Z | |
| dc.date.available | 2026-07-07T06:02:42Z | |
| dc.description | The classical Yao principle states that the complexity R_epsilon(f) of an optimal randomized algorithm for a function f with success probability 1-epsilon equals the complexity max_mu D_epsilon^mu(f) of an optimal deterministic algorithm for f that is correct on a fraction 1-epsilon of the inputs, weighed according to the hardest distribution mu over the inputs. In this paper we investigate to what extent such a principle holds for quantum algorithms. We propose two natural candidate quantum Yao principles, a ``weak'' and a ``strong'' one. For both principles, we prove that the quantum bounded-error complexity is a lower bound on the quantum analogues of max mu D_epsilon^mu(f). We then prove that equality cannot be obtained for the ``strong'' version, by exhibiting an exponential gap. On the other hand, as a positive result we prove that the ``weak'' version holds up to a constant factor for the query complexity of all symmetric Boolean functions | |
| dc.description | 12 pages, latex, no figures | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0109070 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0109070 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/89707 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | On Quantum Versions of the Yao Principle | |
| dc.type | text |