2 citations · 2 across the 3 of their papers we have counts for
4 papers
A Relativizing MIP for BQP
Scott Aaronson, Anand Natarajan, Avishay Tal +1
Complexity class containments involving interactive proof classes are famously nonrelativizing: although , Fortnow and Sipser showed that that there…
Limits to black-box amplification in QMA
Scott Aaronson, Phillip Harris, Freek Witteveen
We study the limitations of black-box amplification in the quantum complexity class QMA. Amplification is known to boost any inverse-polynomial gap between completeness and soundne…
Quantum Lower Bound for Approximate Counting Via Laurent Polynomials
Scott Aaronson
We consider the following problem: estimate the size of a nonempty set , given both quantum queries to a membership oracle for , and a device that ge…
The Power of Unentanglement
Scott Aaronson, Salman Beigi, Andrew Drucker +2
The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class…