Journal
PROCEEDINGS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES
Volume 461, Issue 2063, Pages 3473-3482Publisher
ROYAL SOC
DOI: 10.1098/rspa.2005.1546
Keywords
quantum computers; computational complexity; Born's rule
Categories
Ask authors/readers for more resources
I study the class of problems efficiently solvable by a quantum computer, given the ability to 'postselect' on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or probabilistic polynomial-time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us Solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available