On Quantum Versions of the Yao Principle

Details On Quantum Versions of the Yao Principle On Quantum Versions of the Yao Principle

2001-09-14

arxiv.org/abs/quant-ph/0109070v1

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

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-258718