153 citations · 237 across the 10 of their papers we have counts for
5 papers · 1 filter
Quantum Computing, Postselection, and Probabilistic Polynomial-Time
Scott Aaronson
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…
Limits on Efficient Computation in the Physical World
Scott Aaronson
More than a speculative technology, quantum computing seems to challenge our most basic intuitions about how the physical world should behave. In this thesis I show that, while som…
Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
Scott Aaronson
This paper shows that, if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum co…
The Complexity of Agreement
Scott Aaronson
A celebrated 1976 theorem of Aumann asserts that honest, rational Bayesian agents with common priors will never "agree to disagree": if their opinions about any topic are common kn…
Is Quantum Mechanics An Island In Theoryspace?
Scott Aaronson
This recreational paper investigates what happens if we change quantum mechanics in several ways. The main results are as follows. First, if we replace the 2-norm by some other p-n…