5
$\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$

1 Answer 1

6
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.