AWPP

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

    General
    • Lance Fortnow; John Rogers (1998). "Complexity Limitations on Quantum Computation" (PDF). arXiv:cs/9811023. Bibcode:1998cs.......11023F. {{cite journal}}: Cite journal requires |journal= (help) Provides information on the connection between various complexity classes.
    • Stephen A. Fenner (June 19, 2002). "PP-lowness and a simple definition of AWPP". Electronic Colloquium on Computational Complexity. {{cite journal}}: Cite journal requires |journal= (help) Definition of AWPP and connection to APP and PP.
    • Lance Fortnow; John D. Rogers (November 12, 1998). "Complexity limitations on quantum computation". arXiv:cs/9811023. Proof of BPQ in AWPP.
    • "Gap-definable counting classes" by S. Fenner, L. Fortnow, and S. Kurtz from the Journal of Computer and System Sciences. Pages 116–148, 1994, issue 48. Contains definitions.
    • "An oracle builder's toolkit" by S. Fenner, L. Fortnow, S. Kurtz, and L. Li. in 8th IEEE Structure in Complexity Theory Conference Proceedings. Pages 120–131, 1993. Contains definitions.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.