# Scott Aaronson

Scott Joel Aaronson (* 21. Mai 1981 in Philadelphia) ist ein US-amerikanischer Informatiker.
Aaronson wuchs teilweise in Hongkong auf und studierte ab 1997 Informatik an der Cornell University mit dem Bachelor-Abschluss 2000 und wurde 2004 an der University of California, Berkeley, bei Umesh Vazirani promoviert (Limits on Efficient Computation in the Physical World). Als Post-Doktorand war er 2004/05 am Institute for Advanced Study und 2005 bis 2007 am Institute of Quantum Computing der University of Waterloo. Er lehrte am Massachusetts Institute of Technology (Assistant Professor ab 2007 und ab 2013 Associate Professor mit tenure) und ist seit 2016 Professor an der University of Texas at Austin (David J. Bruton Centennial Professor für Informatik) und dort Direktor des Quantum Information Center.
Er forscht über Fähigkeiten und Grenzen von Quantencomputern und Komplexitätstheorie. Seine Motivation für das Studium von Quantencomputern ist unabhängig von der Frage ihrer Realisierbarkeit darauf gerichtet, welche Einsichten ihr Studium auch über den physikalischen Aufbau der Welt liefert.
2010 entwickelte er mit Alex Arkhipov ein rudimentäres Modell eines Quantencomputers mit linearen optischen Elementen und zeigte unter einigen plausiblen Voraussetzungen, dass dieses Probleme lösen kann, die ein klassischer Computer nicht effizient (in polynomialer Zeit) lösen kann (Quantenüberlegenheit). Ende 2020 kündigte eine Gruppe chinesischer Wissenschaftler um Jian-Wei Pan an, den Nachweis der Quantenüberlegenheit beim Problem des sogenannten Gaussian Boson Sampling nach dem Vorschlag von Aaronson und Arkhipov mit einem optischen Quantencomputer experimentell erbracht zu haben. Der erstmalige Nachweis der Quantenüberlegenheit war schon 2019 mit einem supraleitenden Quantencomputer von einer Gruppe von Wissenschaftlern bei Google erbracht worden.
2012 erhielt er den Alan T. Waterman Award. 2009 war er Sloan Fellow und erhielt einen NSF Career Award. Seit 2019 ist er Fellow der Association for Computing Machinery. Er erhielt den ACM Prize in Computing 2020.

## Schriften

* mit Daniel Gottesman: Improved Simulation of Stabilizer Circuits, Phys. Rev. A 70, 2004, S. 052328
* Limitations of quantum advice and one-way communication, Theory of Computing, Band 1, 2005, S. 1–28
* mit A. Ambainis: Quantum search of spatial regions, Theory of Computing, Band 1, 2005, S. 47–79,
* NP-complete problems and physical reality, SIGACT News Complexity Theory Column, März 2005, Arxiv
* Lower bounds for local search by quantum arguments, SIAM Journal on Computing, Band 35, 2006, S. 804–824
* mit G. Kuperberg: Quantum versus classical proofs and advice, Theory of Computing, Band 3, 2007, S. 129–157
* Quantum certificate complexity, Journal of Computer and System Sciences, Band 74, 2008, S. 313–322
* mit S. Beigi, A. Drucker, B. Fefferman, P. Shor: The power of unentanglement, Theory of Computing, Band 5, 2009, S. 1–42
* mit J. Watrous: Closed timelike curves make classical and quantum computing equivalent, Proceedings of the Royal Society A, Band 465, 2009, S. 631–647
* mit A. Wigderson: Algebrization: A new barrier in complexity theory, ACM Transactions on Computing Theory, Band 1, 2009, S. 2
* The limits of quantum computers, Scientific American, März 2008, Entwurf, pdf
* Why Philosophers Should Care About Computational Complexity, in: Computability, Gödel, Turing, Church and beyond, MIT Press 2012, Arxiv
* The ghost in the quantum Turing machine, Arxiv 2013
* Quantum computing since Democritos, Cambridge University Press 2013
* mit L. Chen: Complexity-Theoretic Foundations of Quantum Supremacy Experiments, Arxiv 2016
* P =? NP, in: John Forbes Nash, Michael Rassias (Hrsg.), Open problems mathematics, Springer 2016, S. 1–122