153 citations · 237 across the 10 of their papers we have counts for
Showing 2005Show all
3 papers · 1 filter
quant-ph2005★ 6 cited
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…
cs.CC2005
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…
quant-ph2005★ 153 cited
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…