HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is there a complexity class QPP?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thereclassqppcomplexity

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#122250, answer score: 5

Revisions (0)

No revisions yet.