109 citations · 147 across the 16 of their papers we have counts for
8 papers · 1 filter
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…