11 papers
No low-degree tests for quantum states
Omar Alrabiah, Srinivasan Arunachalam, Sabee Grewal +1
We study the problem of testing low-degree phase states, namely m-qudit quantum states of the form , where is a degree- p…
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…
Nearly Time-Optimal Pure State Tomography with Pauli Measurements
Sabee Grewal, Meghal Gupta, William He +2
We give an algorithm for pure state tomography with near-optimal copy and time complexity using only single-qubit measurements. Specifically, given copies o…
Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity
Sabee Grewal, Daniel Liang
We study the problem of efficiently learning an unknown -qubit unitary channel in diamond distance given query access. We present a general framework showing that if Pauli opera…
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 suc…
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…