7 papers
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 o…
A Classical Quadratic Speedup for Planted XOR
Meghal Gupta, William He, Ryan O'Donnell +1
A recent work of Schmidhuber et al (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted XOR problem running quartically faster than all known cla…
Few Single-Qubit Measurements Suffice to Certify Any Quantum State
Meghal Gupta, William He, Ryan O'Donnell
A fundamental task in quantum information science is state certification: testing whether a lab-prepared -qubit state is close to a given hypothesis state. In this work, we show…
Sampling and Identity-Testing Without Approximate Tensorization of Entropy
William Gay, William He, Nicholas Kocurek +1
Certain tasks in high-dimensional statistics become easier when the underlying distribution satisfies a local-to-global property called approximate tensorization of entropy (ATE).…
Faster Mixing of Higher-Dimensional Random Reversible Circuits
William Gay, William He, Nicholas Kocurek
We continue the study of the approximate -wise independence of random reversible circuits as permutations of . Our main result is the first construction of a natural…
Pseudorandom Permutations from Random Reversible Circuits
William He, Ryan O'Donnell
We study pseudorandomness properties of permutations on computed by random circuits made from reversible -bit gates (permutations on ). Our main result is…