Scott Aaronson

Scott Joel Aaronson (born 1979) is an American theoretical computer scientist whose work bridges computational complexity theory and quantum computing with an unusual combination of technical depth and philosophical ambition. A professor at the University of Texas at Austin, Aaronson has become the most visible public intellectual in complexity theory — not merely for his theorems, but for his insistence that the field's open problems are not technical puzzles to be solved and forgotten, but permanent fixtures that reshape how we think about knowledge, physics, and computation itself.

The Complexity-Quantum Bridge

Aaronson's signature contribution is the demonstration that quantum computing is not merely a faster way to do classical computation, but a different computational universe whose boundaries illuminate the structure of complexity itself. His 2005 result that PostBQP = PP showed that the gap between quantum and classical probabilistic computation collapses dramatically under postselection — a seemingly absurd computational power that, when removed, reveals exactly how much quantum mechanics adds. The result is not about postselection; it is a calibration tool. It tells us where quantum advantage lives and where it does not.

This bridging impulse runs through his entire career. Aaronson does not treat quantum computing as a subfield of physics or of computer science. He treats it as a meeting ground where both disciplines must give up their native assumptions. The physicist must accept that computational complexity is not an engineering inconvenience but a feature of physical law. The computer scientist must accept that the Turing machine is not merely an abstract model but a claim about what nature permits — and that quantum mechanics may permit more.

The Barrier Results

With Avi Wigderson, Aaronson identified the algebrization barrier (2008), showing that even proof techniques exploiting algebraic structure — arithmetization, interactive proofs, probabilistically checkable proofs — cannot resolve P versus NP. The result was devastating precisely because it targeted the methods complexity theorists trusted most. Where relativization had shown that black-box techniques fail, and natural proofs had shown that constructive lower-bound techniques fail, algebrization showed that even techniques that peek inside the oracle are still bounded by a horizon they cannot see past.

Aaronson's response to these barriers has been characteristic: rather than seeking a magic technique that evades all three, he has argued that the barriers themselves are data. They are not obstacles to be overcome but signatures of the problem's depth. A field that keeps discovering its best tools are insufficient and keeps responding by building better tools of the same kind is not persisting — it is recursing without escape. The honest conclusion, Aaronson insists, is that we do not yet know how to think about P versus NP. These are different predicaments, and confusing them is a failure mode the field cannot afford.

The Philosophy of Computation

Aaronson's 2013 book Quantum Computing Since Democritus is not a textbook. It is an argument that the foundational questions of computer science — P versus NP, the Church-Turing thesis, the measurement problem, the nature of randomness — are not technical questions with technical answers. They are philosophical questions that happen to admit mathematical formulation. The book ranges from ancient Greek atomism to quantum error correction to the problem of free will, treating all of it as a single conversation about what it means for something to be computable, knowable, or true.

His blog, Shtetl-Optimized, has become the informal parliament of complexity theory. Aaronson uses it to referee disputes, mock hype, defend the field against premature declarations of progress, and — most importantly — to insist that the standards of argument in theoretical computer science are not merely professional etiquette. They are the only protection against a field that could easily become a generator of formal noise. When a company claims quantum supremacy, Aaronson does not ask whether the claim is true. He asks whether the terms have been defined precisely enough for the question to have an answer.

Scott Aaronson is not merely a complexity theorist who writes well. He is a complexity theorist who believes that writing well is part of the job — because the problems are too deep to be left to the specialists. The barriers are not signs that we need better tools. They are signs that the tools we have are asking the wrong questions. And the person most willing to say this out loud, repeatedly, in public, is the person who has done the most to keep the field honest.