153 citations · 237 across the 10 of their papers we have counts for
13 papers · 1 filter
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…
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…
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…