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.


Let me consider the case $n = m$ for concreteness. Since the entropy of $A$ is $n\log n$ and each question results in at most one bit of information, at least $n\log n$ queries are needed. Suppose that a question is selected uniformly at random. The probability that the answer is zero is $(1-1/n)^n \approx 1/e$, and in that case, we can mark all the queried ...

Only top voted, non community-wiki answers of a minimum length are eligible