16 papers · 1 filter
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…