AWPP
Jump to navigation
Jump to search
Script error: No such module "Unsubst". In theoretical computer science, almost wide probabilistic polynomial-time (AWPP) is a complexity class contained in PP defined via GapP functions. The class often arises in the context of quantum computing.
AWPP contains the complexity class BQP (bounded-error quantum polynomial time), which contains the decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. In fact, it is the smallest classical complexity class that upper bounds BQP. Furthermore, it is contained in the APP class.
References
<templatestyles src="Reflist/styles.css" />
Script error: No such module "Check for unknown parameters".
General
- Script error: No such module "Citation/CS1". Provides information on the connection between various complexity classes. Proof of BPQ in AWPP.
- Script error: No such module "Citation/CS1". Definition of AWPP and connection to APP and PP.
- Script error: No such module "Citation/CS1". Contains definitions.
- Script error: No such module "Citation/CS1". Contains definitions.
External links
- "Complexity Zoo" Template:Webarchive: Contains a list of complexity classes, including AWPP, and their relation to other classes.