Aug 2026· 4 citations· ⚡ 2 influential· 74 references
PhysicsComputer ScienceMathematics
Abstract
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_{\phi}(\rho) = \operatorname{tr}(\phi(d\rho))/d$, where $\rho$ is an unknown $d$-dimensional quantum state and $\phi$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_\phi(\rho)$ from properties of $\phi$, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields nearly tight bounds for a broad class of problems, including entropy estimation (von Neumann, R\'enyi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). Combined with known upper bounds, these results resolve several open problems and establish the optimality of 31 quantum algorithms since 2015, up to polylogarithmic factors.
Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $\delta$. Quantum singular value transformation gives an upper bound of $O\!\left(\fr...
A. Liu, Adam Wesolowski, Jayne Thompson et al.· 0 citations
We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state $|{\psi}\rangle$, a Hermitian matrix $H$, a polynomial $f$, and a set of observables $\{O_1,\dots,O_m\}$, the goal is to estimate $\langle{\psi}|f(H)^{\dagger}O_j f(H)|{\psi}\rangle$ for all $j\in\{1,\dots,m\}$. Shadow QSVT...
Nai-Hui Chia, Hyunseong Kim, Chia-Ying Lin· 0 citations
Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments $\operatorname{Tr}(\rho^t)$, allowing arbitrary adaptive single-copy measurements. While purity estimation...
We study estimation of the von Neumann entropy of a $d$-dimensional quantum state from independent outcomes of a fixed rank-one measurement. Let $\kappa_\nu\in[1,d+1]$ denote the normalized trace-zero frame spread; $\kappa_\nu=1$ for exact complex projective $2$-designs. For any fixed rank-one measurement and $n\le c_2...
Xin-Yu Song· Statistics & Probability...· 0 citations
We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-\beta E}$ on the torus $\mathbb{T}^d$ with smooth ($s$-Gevrey) potential and barrier amplitude $\alpha=e^{\beta\Delta}$, where $\Delta = \max E-\min E$, every classical algorithm qu...
Enrico Olivucci, Mariia Sobchuk, Sehmimul Hoque et al.· 1 citation
We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $\rho$, determine whether $\rho = \mathbb{I}_d/d$ or $\|\rho-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task in the practical setting of sing...
Jayadev Acharya, Abhilash Dharmavarapu, Yu-Han Liu et al.· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
