REVIEW 4 cited by
Distributional property testing in a quantum world
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
A fundamental problem in statistics and learning theory is to test properties of distributions. We show that quantum computers can solve such problems with significant speed-ups. In particular, we give fast quantum algorithms for testing closeness between unknown distributions, testing independence between two distributions, and estimating the Shannon / von Neumann entropy of distributions. The distributions can be either classical or quantum, however our quantum algorithms require coherent quantum access to a process preparing the samples. Our results build on the recent technique of quantum singular value transformation, combined with more standard tricks such as divide-and-conquer. The presented approach is a natural fit for distributional property testing both in the classical and the quantum case, demonstrating the first speed-ups for testing properties of density operators that can be accessed coherently rather than only via sampling; for classical distributions our algorithms significantly improve the precision dependence of some earlier results.
Forward citations
Cited by 4 Pith papers
-
On estimating operator norm distance, with optimal trace distance estimation when one state is pure
Rank-independent quantum estimators achieve Θ(1/ε) queries for operator-norm (and trace) distance when one state is pure, and Õ(1/ε^{3/2}) queries for general states, proving BQP-completeness.
-
On estimating Schatten norm and power distances between quantum states
For constant alpha > 1, the quantum Schatten alpha-norm distance between states given by preparation circuits can be estimated in polynomial time, and the corresponding decision problem QSD_alpha is BQP-complete; for ...
-
Estimation of Nonlinear Physical Quantities By Measuring Ancillas
The paper presents QSVT-based algorithms that estimate Renyi and von Neumann entropies from copies of a quantum state by measuring ancillas, with improved sample complexity over prior copy-based methods.
-
Quantum algorithm for estimating Renyi entropies of quantum states
A DQC1-based algorithm estimates α-Rényi entropies of non-singular quantum states to additive or multiplicative precision using purified access, at expected cost O(1/(xε)^2) measurements.
Discussion (0). Continue with ORCID to comment.