3
$\begingroup$

The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach is exponentially fast) an infeasible number of repetitions may be required before we have a significant probability of confidently distinguishing satisfying inputs from non-satisfying ones. Nevertheless, PP is an interesting complexity class to study in its own right.

Is there a similar well-defined complexity class "QPP" of problems which a quantum computer has a greater than 50% chance of correctly solving in polynomial time? I understand that if so, this class of problems would not be feasible on a quantum computer, but are any nontrivial inclusions with the more "traditional" complexity classes either proven or suspected? How "big" do we think the class QPP is?

$\endgroup$
4
$\begingroup$

Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.