Physics – Quantum Physics
Scientific paper
2001-09-14
Physics
Quantum Physics
12 pages, latex, no figures
Scientific paper
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
Graaf Mart de
Wolf Ronald de
No associations
LandOfFree
On Quantum Versions of the Yao Principle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Quantum Versions of the Yao Principle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Quantum Versions of the Yao Principle will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-258718