109 citations · 147 across the 16 of their papers we have counts for
5 papers · 1 filter
Improved Circuit Lower Bounds and Quantum-Classical Separations
Sabee Grewal, Vinayak M. Kumar
We continue the study of the circuit class GC^0, which augments AC^0 with unbounded-fan-in gates that compute arbitrary functions inside a sufficiently small Hamming ball but must…
Pseudoentanglement Ain't Cheap
Sabee Grewal, Vishnu Iyer, William Kretschmer +1
We show that any pseudoentangled state ensemble with a gap of bits of entropy requires non-Clifford gates to prepare. This bound is tight up to polylogarithmic factors i…
Agnostic Tomography of Stabilizer Product States
Sabee Grewal, Vishnu Iyer, William Kretschmer +1
We define a quantum learning task called agnostic tomography, where given copies of an arbitrary state and a class of quantum states , the goal is to output a succ…
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…
The Entangled Quantum Polynomial Hierarchy Collapses
Sabee Grewal, Justin Yirka
We introduce the entangled quantum polynomial hierarchy as the class of problems that are efficiently verifiable given alternating quantum proofs that may be entang…