153 citations · 189 across the 6 of their papers we have counts for
6 papers
Are Quantum States Exponentially Long Vectors?
Scott Aaronson
I'm grateful to Oded Goldreich for inviting me to the 2005 Oberwolfach Meeting on Complexity Theory. In this extended abstract, which is based on a talk that I gave there, I demons…
Oracles Are Subtle But Not Malicious
Scott Aaronson
Theoretical computer scientists have been debating the role of oracles since the 1970's. This paper illustrates both that oracles can give us nontrivial insights about the barrier…
NP-complete Problems and Physical Reality
Scott Aaronson
Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adia…
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…