4

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.


2

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