109 citations · 147 across the 16 of their papers we have counts for
24 papers
Pretty good shadow tomography
Sabee Grewal, Angelos Pelecanos, Jack Spilecki +2
We give a shadow tomography algorithm that uses copies of the input state. Specifically, given a quantum state and observables $O_1,\ldot…
A classical oracle separation between QMA and QMA(2)
Sabee Grewal, Saachi Mutreja, Kabir Tomer
We exhibit a classical oracle relative to which QMA \neq QMA(2). The separation is based on a separable Hamiltonian problem defined by signed edge constraints on a graph. The YES i…
Optimal and Verifiable Quantum Advantages in Communication Complexity
Ryan Anselm, Michelle Ding, Dar Gilboa +1
We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that…
Marton's conjecture in polynomial time
Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal +1
Gowers, Green, Manners, and Tao (Annals '25) recently resolved Marton's polynomial Freiman-Ruzsa conjecture. We give an algorithmic counterpart to their result: given uniform sampl…
QMA has perfect completeness
Sabee Grewal, Dorian Rudolph
We prove , i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and gates…
A quantum oracle separation between QMA(2) and QMA
John Bostanci, Sabee Grewal, Jonas Haferkamp +4
We find a quantum oracle relative to which . As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every , any $(ε,…
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- po…
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 of…
On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
Sabee Grewal, Dorian Rudolph
We prove several new results concerning the pure quantum polynomial hierarchy (pureQPH). First, we show that QMA(2) is contained in pureQSigma2, that is, two unentangled existentia…
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…
Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs
Sabee Grewal, William Kretschmer
We investigate two resources whose effects on quantum interactive proofs remain poorly understood: the promise of unentanglement, and the verifier's ability to condition on an inte…
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…
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…
Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements
Sabee Grewal, Vishnu Iyer, William Kretschmer +1
Recent work has shown that -qubit quantum states output by circuits with at most single-qubit non-Clifford gates can be learned to trace distance using $\mathsf{poly}(n,…
Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
Sabee Grewal, Vishnu Iyer, William Kretschmer +1
We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and non-Clifford gates. Specifically, for an -qubit state …
Improved Stabilizer Estimation via Bell Difference Sampling
Sabee Grewal, Vishnu Iyer, William Kretschmer +1
We study the complexity of learning quantum states in various models with respect to the stabilizer formalism and obtain the following results: - We prove that -gates are…
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
Sabee Grewal, Vishnu Iyer, William Kretschmer +1
We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an -qubit pure state , we give an…
Efficient Tomography of Non-Interacting Fermion States
Scott Aaronson, Sabee Grewal
We give an efficient algorithm that learns a non-interacting fermion state, given copies of the state. For a system of non-interacting fermions and modes, we show that $O(m…
Classical Shadows With Noise
Dax Enshan Koh, Sabee Grewal
The classical shadows protocol, recently introduced by Huang, Kueng, and Preskill [Nat. Phys. 16, 1050 (2020)], is a quantum-classical protocol to estimate properties of an unknown…
Computability Theory of Closed Timelike Curves
Scott Aaronson, Mohammad Bavarian, Toby Cubitt +4
We study the question of what is computable by Turing machines equipped with time travel into the past; i.e., with Deutschian closed timelike curves (CTCs) having no bound on their…