1.5k citations · 3.7k across the 74 of their papers we have counts for
8 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…
Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
Scott Aaronson
This paper initiates the study of hidden variables from the discrete, abstract perspective of quantum computing. For us, a hidden-variable theory is simply a way to convert a unita…
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…
Improved Simulation of Stabilizer Circuits
Scott Aaronson, Daniel Gottesman
The Gottesman-Knill theorem says that a stabilizer circuit -- that is, a quantum circuit consisting solely of CNOT, Hadamard, and phase gates -- can be simulated efficiently on a c…