4 papers
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…
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…
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…