REVIEW 6 cited by
Sublinear quantum algorithms for estimating von Neumann entropy
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
abstract
Entropy is a fundamental property of both classical and quantum systems, spanning myriad theoretical and practical applications in physics and computer science. We study the problem of obtaining estimates to within a multiplicative factor $\gamma>1$ of the Shannon entropy of probability distributions and the von Neumann entropy of mixed quantum states. Our main results are: $\quad\bullet$ an $\widetilde{\mathcal{O}}\left( n^{\frac{1+\eta}{2\gamma^2}}\right)$-query quantum algorithm that outputs a $\gamma$-multiplicative approximation of the Shannon entropy $H(\mathbf{p})$ of a classical probability distribution $\mathbf{p} = (p_1,\ldots,p_n)$; $\quad\bullet$ an $\widetilde{\mathcal{O}}\left( n^{\frac12+\frac{1+\eta}{2\gamma^2}}\right)$-query quantum algorithm that outputs a $\gamma$-multiplicative approximation of the von Neumann entropy $S(\rho)$ of a density matrix $\rho\in\mathbb{C}^{n\times n}$. In both cases, the input is assumed to have entropy bounded away from zero by a quantity determined by the parameter $\eta>0$, since, as we prove, no polynomial query algorithm can multiplicatively approximate the entropy of distributions with arbitrarily low entropy. In addition, we provide $\Omega\left(n^{\frac{1}{3\gamma^2}}\right)$ lower bounds on the query complexity of $\gamma$-multiplicative estimation of Shannon and von Neumann entropies. We work with the quantum purified query access model, which can handle both classical probability distributions and mixed quantum states, and is the most general input model considered in the literature.
Forward citations
Cited by 6 Pith papers
-
Towards Minimax Estimation of High-Order Functionals by Quantum Arguments
Quantum-inspired estimators for F_alpha(P) and F_alpha(rho) achieve optimal sample complexity n ~ alpha and minimax MSE rate alpha/n, improving prior O(alpha^2) bounds.
-
Simultaneous Estimation of Nonlinear Functionals of a Quantum State
Estimating k powers of a quantum state against one observable simultaneously costs Θ~(k) samples, matching the cost of the single hardest term.
-
Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation
A quantum estimator achieves near-optimal query complexity for integer-order Tsallis entropy, and the same technique yields a new information-theoretic proof that approximating x^n needs polynomials of degree Ω(√n).
-
Query-Optimal and Sample-Optimal Quantum Algorithms for Estimating Fidelity to a Pure State
A quantum algorithm estimates the fidelity between a mixed state and a pure state to error ε with Θ(1/ε) queries to the state-preparation circuits.
-
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.
-
A quantum algorithm for modular flow
A QSVT-based algorithm implements modular flow of an operator with respect to a density matrix in O~(κ²|t|log(κ²/ε)) queries to a block encoding of the state.
Discussion (0). Continue with ORCID to comment.