Publications (71)
AM with Multiple Merlins
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
Improved Simulation of Stabilizer Circuits
Scott Aaronson, Daniel Gottesman
Bounding the seed length of Miller and Shi's unbounded randomness expansion protocol
Renan Gross, Scott Aaronson
The Complexity of Agreement
Scott Aaronson
Multilinear Formulas and Skepticism of Quantum Computing
Scott Aaronson
The Classification of Reversible Bit Operations
Scott Aaronson, Daniel Grier, Luke Schaeffer
Impossibility of Succinct Quantum Proofs for Collision-Freeness
Scott Aaronson
BosonSampling with Lost Photons
Scott Aaronson, Daniel J. Brod
Book Review: 'A New Kind of Science'
Scott Aaronson
Separations in query complexity using cheat sheets
Scott Aaronson, Shalev Ben-David, Robin Kothari
Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent
Scott Aaronson, Travis Hance
Quantum POMDPs
Jennifer Barry, Daniel T. Barry, Scott Aaronson
Quantum Search of Spatial Regions
Scott Aaronson, Andris Ambainis
Limits on Efficient Computation in the Physical World
Scott Aaronson
The Learnability of Quantum States
Scott Aaronson
On Perfect Completeness for QMA
Scott Aaronson
Quantum lower bound for inverting a permutation with advice
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs +1
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
Scott Aaronson
PDQP/qpoly = ALL
Scott Aaronson
Lower Bounds for Local Search by Quantum Arguments
Scott Aaronson
Doubly infinite separation of quantum information and communication
Zi-Wen Liu, Christopher Perry, Yechao Zhu +2
The Computational Complexity of Linear Optics
Scott Aaronson, Alex Arkhipov
The Ghost in the Quantum Turing Machine
Scott Aaronson
Complexity-theoretic limitations on blind delegated quantum computation
Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu +1
The space "just above" BQP
Scott Aaronson, Adam Bouland, Joseph Fitzsimons +1
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
Scott Aaronson
Breaking and making quantum money: toward a new quantum cryptographic protocol
Andrew Lutomirski, Scott Aaronson, Edward Farhi +4
The Equivalence of Sampling and Searching
Scott Aaronson
Quantum Lower Bound for Approximate Counting Via Laurent Polynomials
Scott Aaronson
Psi-Epistemic Theories: The Role of Symmetry
Scott Aaronson, Adam Bouland, Lynn Chua +1
Quantum Certificate Complexity
Scott Aaronson
Near invariance of the hypercube
Scott Aaronson, Hoi Nguyen
The Computational Complexity of Ball Permutations
Scott Aaronson, Adam Bouland, Greg Kuperberg +1
Quantum Lower Bound for the Collision Problem
Scott Aaronson
Algorithms for Boolean Function Query Properties
Scott Aaronson
A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
Adam Yedidia, Scott Aaronson
Photonic Boson Sampling in a Tunable Circuit
Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari +4
Generation of Universal Linear Optics by Any Beamsplitter
Adam Bouland, Scott Aaronson
A Full Characterization of Quantum Advice
Scott Aaronson, Andrew Drucker
Quantum Computing and Dynamical Quantum Models
Scott Aaronson
BosonSampling Is Far From Uniform
Scott Aaronson, Alex Arkhipov
Gentle Measurement of Quantum States and Differential Privacy
Scott Aaronson, Guy N. Rothblum
Quantum Lower Bound for Recursive Fourier Sampling
Scott Aaronson
Shadow Tomography of Quantum States
Scott Aaronson
The Need for Structure in Quantum Speedups
Scott Aaronson, Andris Ambainis
Quantum Copy-Protection and Quantum Money
Scott Aaronson
Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton
Scott Aaronson, Sean M. Carroll, Lauren Ouellette
Query Complexity: Worst-Case Quantum Versus Average-Case Classical
Scott Aaronson
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Scott Aaronson, Lijie Chen
Oracles Are Subtle But Not Malicious
Scott Aaronson
Advice Coins for Classical and Quantum Computation
Scott Aaronson, Andrew Drucker
Quantum Computing, Postselection, and Probabilistic Polynomial-Time
Scott Aaronson
A Quantum Query Complexity Trichotomy for Regular Languages
Scott Aaronson, Daniel Grier, Luke Schaeffer
Closed Timelike Curves Make Quantum and Classical Computing Equivalent
Scott Aaronson, John Watrous
A Linear-Optical Proof that the Permanent is #P-Hard
Scott Aaronson
Quantum Money from Hidden Subspaces
Scott Aaronson, Paul Christiano
Sculpting Quantum Speedups
Scott Aaronson, Shalev Ben-David
NP-complete Problems and Physical Reality
Scott Aaronson
The Power of Unentanglement
Scott Aaronson, Salman Beigi, Andrew Drucker +2
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
Scott Aaronson, Andris Ambainis, JÄnis Iraids +2
Are Quantum States Exponentially Long Vectors?
Scott Aaronson
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Scott Aaronson, Andris Ambainis
A Counterexample to the Generalized Linial-Nisan Conjecture
Scott Aaronson
BQP and the Polynomial Hierarchy
Scott Aaronson
Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
Scott Aaronson
Experimental learning of quantum states
Andrea Rocchetto, Scott Aaronson, Simone Severini +5
Limitations of Quantum Advice and One-Way Communication
Scott Aaronson
Representing probabilistic data via ontological models
Nicholas Harrigan, Terry Rudolph, Scott Aaronson
Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
Scott Aaronson
Is Quantum Mechanics An Island In Theoryspace?
Scott Aaronson
Weak Parity
Scott Aaronson, Andris Ambainis, Kaspars Balodis +1