5 papers
Spectrum Estimation is Almost as Hard as Tomography
Marco Fanizza, Ryan O'Donnell, Chirag Wadhwa
We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann…
SPAM Tolerance for Pauli Error Estimation
Ryan O'Donnell, Samvitti Sharma
The Pauli channel is a fundamental model of noise in quantum systems, motivating the task of Pauli error estimation. We present an algorithm that builds on the reduction to Populat…
Non-iid hypothesis testing: from classical to quantum
Giacomo De Palma, Marco Fanizza, Connor Mowry +1
We study hypothesis testing (aka state certification) in the non-identically distributed setting. A recent work (Garg et al. 2023) considered the classical case, in which one is gi…
Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes
Olakunle S. Abawonse, Jan Hazla, Ryan O'Donnell
An inequality by Samorodnitsky states that if is a nonnegative boolean function, and is chosen by randomly including each coor…
Instance-Optimal Quantum State Certification with Entangled Measurements
Ryan O'Donnell, Chirag Wadhwa
We consider the task of quantum state certification: given a description of a hypothesis state and multiple copies of an unknown state , a tester aims to determine whether…