1.5k citations · 3.7k across the 74 of their papers we have counts for
95 papers
A Separation Between Types of Quantum Oracle Separations
Scott Aaronson, Adam Bouland, Jordan Docter +1
Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of cer…
Sparsity and Out-of-Distribution Generalization
Scott Aaronson, Lin Lin Lee, Jiawei Li
Explaining out-of-distribution generalization has been a central problem in epistemology since Goodman's "grue" puzzle in 1946. Today it's a central problem in machine learning, in…
Demonstrating an unconditional separation between quantum and classical information resources
William Kretschmer, Sabee Grewal, Matthew DeCross +8
A longstanding goal in quantum information science is to demonstrate quantum computations that cannot be feasibly reproduced on a classical computer. Such demonstrations mark major…
On verifiable quantum advantage with peaked circuit sampling
Scott Aaronson, Yuxuan Zhang
Over a decade after its proposal, the idea of using quantum computers to sample hard distributions has remained a key path to demonstrating quantum advantage. Yet a severe drawback…
PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
Scott Aaronson, Sabee Grewal, Vishnu Iyer +2
We define and study a variant of QMA (Quantum Merlin Arthur) in which Arthur can make multiple non-collapsing measurements to Merlin's witness state, in addition to ordinary collap…
Testing GPT-4 with Wolfram Alpha and Code Interpreter plug-ins on math and science problems
Ernest Davis, Scott Aaronson
This report describes a test of the large language model GPT-4 with the Wolfram Alpha and the Code Interpreter plug-ins on 105 original problems in science and math, at the high sc…