# Scott Aaronson

#2,078

Most Influential Person Now

American scientist, working on the field of quantum computing, (1981 - ), Philadelphia, Pennsylvania

## Scott Aaronson's AcademicInfluence.com Rankings

Scott Aaronsoncomputer-science Degrees

Computer Science

#164

World Rank

#171

Historical Rank

#97

USA Rank

Database

#2510

World Rank

#2631

Historical Rank

#538

USA Rank

## Download Badge

Computer Science

## Scott Aaronson's Degrees

- PhD Computer Science University of California, Berkeley
- Bachelors Computer Science Cornell University

## Similar Degrees You Can Earn

## Why Is Scott Aaronson Influential?

(Suggest an Edit or Addition)According to Wikipedia, Scott Joel Aaronson is an American theoretical computer scientist and David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin. His primary areas of research are quantum computing and computational complexity theory.

## Scott Aaronson's Published Works

### Published Works

- The computational complexity of linear optics (2010) (1132)
- Improved Simulation of Stabilizer Circuits (2004) (843)
- Photonic Boson Sampling in a Tunable Circuit (2012) (512)
- Quantum computing, postselection, and probabilistic polynomial-time (2004) (311)
- Complexity-Theoretic Foundations of Quantum Supremacy Experiments (2016) (259)
- Quantum search of spatial regions (2003) (247)
- Algebrization: A New Barrier in Complexity Theory (2009) (232)
- Quantum Computing since Democritus (2013) (209)
- Shadow tomography of quantum states (2017) (209)
- NP-complete Problems and Physical Reality (2005) (204)
- BQP and the polynomial hierarchy (2009) (202)
- The learnability of quantum states (2006) (198)
- Read the fine print (2015) (185)
- Synthetic recombinase-based state machines in living cells (2016) (183)
- Guest Column: NP-complete problems and physical reality (2005) (171)
- The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes (2016) (166)
- Limitations of quantum advice and one-way communication (2004) (144)
- Quantum Copy-Protection and Quantum Money (2009) (138)
- Quantum lower bound for the collision problem (2001) (125)
- Quantum money from hidden subspaces (2012) (121)
- Bosonsampling is far from uniform (2013) (115)
- Why Philosophers Should Care About Computational Complexity (2011) (109)
- The Need for Structure in Quantum Speedups (2009) (107)
- Forrelation: A Problem that Optimally Separates Quantum from Classical Computing (2014) (105)
- Closed timelike curves make quantum and classical computing equivalent (2008) (99)
- A linear-optical proof that the permanent is #P-hard (2011) (91)
- Lower bounds for local search by quantum arguments (2003) (86)
- Quantum Approximate Counting, Simplified (2019) (85)
- Quantum versus Classical Proofs and Advice (2006) (82)
- The Power of Unentanglement (2008) (76)
- Separations in query complexity using cheat sheets (2015) (75)
- The Complexity Zoo (2008) (71)
- Is Quantum Mechanics An Island in Theoryspace (2004) (70)
- Gentle measurement of quantum states and differential privacy (2019) (67)
- Online learning of quantum states (2018) (65)
- Experimental learning of quantum states (2017) (64)
- ψ-epistemic theories: The role of symmetry (2013) (64)
- BosonSampling with Lost Photons (2015) (63)
- The Limits of Quantum Computers (2007) (62)
- Multilinear formulas and skepticism of quantum computing (2003) (61)
- The limits of quantum computers. (2008) (61)
- AM with Multiple Merlins (2014) (60)
- Quantum computing and hidden variables (2004) (52)
- Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol (2009) (51)
- Quantum certificate complexity (2002) (51)
- The Classification of Reversible Bit Operations (2015) (49)
- Is P Versus NP Formally Independent? (2003) (48)
- The Ghost in the Quantum Turing Machine (2013) (47)
- Quantum partially observable Markov decision processes (2014) (46)
- On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking (2019) (46)
- A very preliminary analysis of DALL-E 2 (2022) (39)
- Generation of universal linear optics by any beam splitter (2013) (38)
- Improved simulation of stabilizer circuits (14 pages) (2004) (38)
- Generalizing and derandomizing Gurvits's approximation algorithm for the permanent (2012) (38)
- On the implausibility of classical client blind quantum computing (2017) (36)
- The Equivalence of Sampling and Searching (2010) (33)
- Limits on Efficient Computation in the Physical World (2004) (32)
- Quantum lower bound for recursive fourier sampling (2002) (32)
- The complexity of agreement (2004) (30)
- Oracles are subtle but not malicious (2005) (30)
- Representing probabilistic data via ontological models (2007) (29)
- Complexity Theory and Cryptology : An Introduction to Cryptocomplexity (2007) (28)
- On perfect completeness for QMA (2008) (27)
- Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem (2020) (27)
- Impossibility of succinct quantum proofs for collision-freeness (2011) (27)
- Quantum Machine Learning Algorithms : Read the Fine Print (2015) (26)
- A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory (2016) (25)
- New Approaches for Quantum Copy-Protection (2020) (23)
- QMA/qpoly ⊆ PSPACE/poly: De-Merlinizing Quantum Protocols (2006) (23)
- Complexity-Theoretic Limitations on Blind Delegated Quantum Computation (2017) (22)
- Quantum lower bounds for approximate counting via laurent polynomials (2018) (22)
- QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols (2005) (20)
- Polynomials, Quantum Query Complexity, and Grothendieck's Inequality (2015) (20)
- Algebrization: a new barrier in complexity theory (2008) (20)
- Quantum Computing since Democritus: Contents (2013) (20)
- Computational complexity: Why quantum chemistry is hard (2009) (19)
- On the quantum complexity of closest pair and related problems (2019) (19)
- A full characterization of quantum advice (2010) (19)
- QMA/qpoly /spl sube/ PSPACE/poly: de-Merlinizing quantum protocols (2006) (18)
- Quantum money (2012) (18)
- The Polynomial Method in Quantum and Classical Computing (2008) (17)
- A Quantum Query Complexity Trichotomy for Regular Languages (2018) (17)
- Quantum lower bound for inverting a permutation with advice (2014) (16)
- On Circuit Lower Bounds from Derandomization (2011) (15)
- The Space "Just Above" BQP (2014) (15)
- Open Problems Related to Quantum Query Complexity (2021) (14)
- A Counterexample to the Generalized Linial-Nisan Conjecture (2011) (14)
- Algorithms for Boolean Function Query Properties (2001) (13)
- Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton (2014) (13)
- Computability Theory of Closed Timelike Curves (2016) (12)
- A note on circuit lower bounds from derandomization (2010) (11)
- Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories (2004) (11)
- Are Quantum States Exponentially Long Vectors (2005) (11)
- The computational complexity of ball permutations (2016) (11)
- How Much Structure Is Needed for Huge Quantum Speedups? (2022) (11)
- Doubly infinite separation of quantum information and communication (2015) (10)
- Sculpting Quantum Speedups (2015) (10)
- On the Hardness of Detecting Macroscopic Superpositions (2020) (10)
- Quantum Implications of Huang's Sensitivity Theorem (2020) (10)
- Sophistication as Randomness Deficiency (2013) (10)
- Book Review: 'A New Kind of Science' (2002) (10)
- Advice Coins for Classical and Quantum Computation (2011) (9)
- Utility Investments in Resilience of Electricity Systems (2019) (8)
- Near invariance of the hypercube (2014) (8)
- A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games (2010) (7)
- Get real (2012) (6)
- Bounding the seed length of Miller and Shi's unbounded randomness expansion protocol (2014) (5)
- Quantum Copy-Protection from Hidden Subspaces (2020) (5)
- Certified Randomness from Quantum Supremacy (2023) (5)
- An Automated Approach to the Collatz Conjecture (2021) (4)
- The Quest for Randomness (2014) (4)
- The Computational Complexity Column (2004) (4)
- The Busy Beaver Frontier (2020) (4)
- P\mathop{ =}\limits^{?}NP (2016) (3)
- The acrobatics of BQP (2021) (3)
- Oncogenes and the Molecular Origins of Cancer. Robert A. Weinberg, Ed. Cold Spring Harbor Laboratory Press, Cold Spring Harbor, NY, 1989. xii, 367 pp., illus. Paper, $55. Cold Spring Harbor Monograph 18. (1990) (3)
- PDQP/qpoly=ALL (2018) (3)
- Optimal demand-oriented topology for hypertext systems (1997) (3)
- Ask Me Anything (2009) (3)
- The One-Way Communication Complexity of Subgroup Membership (2009) (3)
- Efficient Learning of Non-Interacting Fermion Distributions (2021) (3)
- Weak Parity (2013) (3)
- The Fewest Clues Problem (2016) (3)
- Quantum Search of Spatial Regions ( Extended Abstract ) ∗ (2003) (3)
- A Qubit, a Coin, and an Advice String Walk Into a Relational Problem (2023) (2)
- Quantum Computing since Democritus: Quantum computing (2013) (2)
- On quantum versus classical query complexity (2021) (2)
- Quantum Computing and Dynamical Quantum Models (2002) (2)
- Psi-Epistemic Theories: The Role of Symmetry (2018) (2)
- PLOS ONE 2015 Reviewer Thank You (2016) (2)
- Discrete bulk reconstruction (2022) (2)
- Any Beamsplitter Generates Universal Quantum Linear Optics (2013) (1)
- Review of "The Access Principle by John Willinsky," MIT Press, 2005 (2007) (1)
- Experimental Boson Sampling (2013) (1)
- Quantum Computing since Democritus: Interactive proofs, circuit lower bounds, and more (2013) (1)
- Efficient Tomography of Non-Interacting Fermion States (2021) (1)
- PLOS Computational Biology 2015 Reviewer Thank You (2016) (1)
- Learning Distributions over Quantum Measurement Outcomes (2022) (1)
- QIP = PSPACE breakthrough (2010) (1)
- Experimental BosonSampling (2012) (1)
- The Communication Cost of Agreement (2004) (1)
- 04 01 06 2 v 2 1 7 M ar 2 00 4 Is Quantum Mechanics An Island In Theoryspace ? (2004) (1)
- Proceedings of the Annual IEEE Conference on Computational Complexity: Preface (2005) (1)
- Bell inequality violation finally done right (2015) (1)
- BosonSampling with realistic single-photon sources (2013) (0)
- BQP After 28 Years (Invited Talk) (2021) (0)
- Near invariance of the hypercube (2016) (0)
- Quantum Computing since Democritus: Paleocomplexity (2013) (0)
- Session details: Session 14A (2006) (0)
- Special Section on Foundations of Computer Science (2011) (0)
- Quantum Computing since Democritus: How big are quantum states? (2013) (0)
- The Equivalence of Sampling and Searching (2013) (0)
- Quantum Computing since Democritus: Sets (2013) (0)
- Quantum Versus Classical Proofs and Advice. (arXiv:quant-ph/0604056v4 UPDATED) (2020) (0)
- Sophistication as Randomness Deficiency (chapter) (2013) (0)
- Quantum Information, Mathematical Knowledge, and the Laws of Physics (2017) (0)
- A simple refractory depression scale (1989) (0)
- 05 07 24 2 v 1 2 6 Ju l 2 00 5 Are Quantum States Exponentially Long Vectors ? (2008) (0)
- O ct 2 01 8 Online Learning of Quantum States (2018) (0)
- Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 (2010) (0)
- Quantum Computing since Democritus: Time travel (2013) (0)
- Applications of complex modulation (2020) (0)
- Quantum Computing since Democritus: Gödel, Turing, and friends (2013) (0)
- Technical Perspective QIP = PSPACE Breakthrough (2010) (0)
- The complexity class PDQP SPUR Final Paper: Summer 2013 (2013) (0)
- Formula Size Lower Bounds and Quantum States Scott Aaronson (2005) (0)
- Experimental BosonSampling in a tunable optical network (2013) (0)
- Query Complexity: Worst-Case Quantum Versus Average-Case Classical (2000) (0)
- Upcoming events (2020) (0)
- Quantum Computing since Democritus: Preface (2013) (0)
- Ja n 20 14 AM with Multiple Merlins (2018) (0)
- Doomsday and the Dice Room Murders (2015) (0)
- M ay 2 00 2 Quantum Computing and Dynamical Quantum Models (2008) (0)
- Quantum Computing since Democritus: Crypto (2013) (0)
- Session details: Session 15A (2006) (0)
- Entangled states as resources in quantum complexity theory (2012) (0)
- Quantum Computing since Democritus: P, NP, and friends (2013) (0)
- P=?np (2017) (0)
- Session details: Session 10B (2006) (0)
- The Power of Unentanglement (Extended Abstract) (2008) (0)
- Atoms and the void (2013) (0)
- Salute to Our Reviewers. (2016) (0)
- Breaking and making quantum money (2009) (0)
- Mixed Base Rewriting for the Collatz Conjecture (2021) (0)
- Quantum Computing since Democritus: Fun with the Anthropic Principle1 (2013) (0)
- Experimental bosonsampling in a photonic circuit (2013) (0)
- Juba 1 Quantum circuits that can be efficiently simulated (2008) (0)
- Book review: On "A New Kind of Science" by Stephen Wolfram (2002) (0)
- Prospects for Long-Term Information Security in the Face of Quantum Computing (2018) (0)
- Quantum Computing since Democritus: Penrose (2013) (0)
- JAMA Network Open Peer Reviewers in 2020. (2021) (0)
- Quantum Computing since Democritus: Cosmology and complexity (2013) (0)
- Quantum Computing since Democritus: Skepticism of quantum computing (2013) (0)
- A Summer Internship at Bell Labs (2003) (0)
- Quantum Computing since Democritus: Quantum (2013) (0)
- 6.845 Final Project: Classifying Beamsplitters (2012) (0)
- Constrained quantum CNOT circuit re-synthesis using deep reinforcement learning (2019) (0)
- news & views QUANTUM MECHANICS Get real (0)
- Quantum Computing since Democritus: Learning (2013) (0)
- Last Time: Quantum Interactive Proofs 1.1 Ip = Pspace ⊆ Qip = Qip(3) ⊆ Exp 1.2 Mip = Nexp 1.4 Graph Two-coloring (2008) (0)
- Lecture 17 Classical Interactive Proofs (2008) (0)
- Quantum Computing since Democritus: Minds and machines (2013) (0)
- Quantum Computing since Democritus: Decoherence and hidden variables (2013) (0)
- Black Holes, Firewalls, and the Limits of Quantum Computers (2017) (0)
- Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006) (2009) (0)
- N ov 2 00 1 Quantum Lower Bound for the Collision Problem (2018) (0)
- Quantum Computing since Democritus: Free will (2013) (0)
- Quantum Computing since Democritus: Proofs (2013) (0)

This paper list is powered by the following services:

## Other Resources About Scott Aaronson

## What Schools Are Affiliated With Scott Aaronson?

Scott Aaronson is affiliated with the following schools: