Skip to content

Author

Sabee Grewal

We have 4 of 23 papers

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Sep 2026

A quantum oracle separation between QMA(2) and QMA

We find a quantum oracle relative to which $\mathsf{QMA} \neq \mathsf{QMA}(2)$. As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every $\epsilon+\delta<1$, any $(\epsilon,\delta)$-disentangler requires input size exponential in the number of output qubits. Our proof combines the unitarily in...

John Bostanci, Sabee Grewal, Jonas Haferkamp et al. · 2 citations
Preprint Oct 2026

Pretty good shadow tomography

We give a shadow tomography algorithm that uses $O(\log(m) \log(m/\delta) / \varepsilon^2)$ copies of the input state. Specifically, given a quantum state $\rho$ and observables $O_1,\ldots,O_m$, the algorithm outputs estimates of $\mathrm{tr}(O_i\rho)$ for all $i\in[m]$ that are all accurate to within $\pm\varepsilon$...

Sabee Grewal, Angelos Pelecanos, Jack Spilecki et al. · 0 citations
Preprint Oct 2026

Optimal and Verifiable Quantum Advantages in Communication Complexity

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 it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $\Omega(2^n)$ bits of communication. We...

Ryan A. Anselm, Michelle Ding, D. Gilboa et al. · 1 citation
Preprint Sep 2026

Marton's conjecture in polynomial time

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 sampling and membership-oracle access to a set $A \subseteq \mathbb{F}_2^n$ with doubling constant at most $K$, our algorithm outputs a subspace o...

Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal et al. · 3 citations · ⚡1

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.