1.5k citations · 3.7k across the 74 of their papers we have counts for
78 papers · 1 filter
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…
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…
Certified Randomness from Quantum Supremacy
Scott Aaronson, Shih-Han Hung
We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our pr…
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
Scott Aaronson, Harry Buhrman, William Kretschmer
Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FB…