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
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
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
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...