A Unified Complexity Framework for Quantum Property Testing
Abstract
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form ℒϕ(ρ) = tr(ϕ(dρ))/d, where ρ is an unknown d-dimensional quantum state and ϕ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating ℒϕ(ρ) from properties of ϕ, 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ényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is Θ (d2/(εlog2(d)max{1, εlog2(d)}) + log2(d)/ε2), and the sample complexity of spectrum estimation is Θ (d2/(ε2log2(d)max{1, ε2log2(d)})). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
Related
- α-TCAV: A Unified Framework for Testing with Concept Activation Vectors
- A Unified Framework for Scenario Coverage Estimation and Representative Selection in Simulation-Based Testing of Automated Vehicles
- Sample complexity of quantum resource testing via one-shot quantum blurring
- Strong Topological Rokhlin Property: Finite-Index Ascent, Descriptive Complexity, and Effective Obstructions
- Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
BibTeX
@misc{wang2026unified,
title = {{A Unified Complexity Framework for Quantum Property Testing}},
author = {Qisheng Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.02600},
eprint = {2608.02600},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.02600},
}
RIS
TY - UNPB
TI - A Unified Complexity Framework for Quantum Property Testing
AU - Qisheng Wang
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2608.02600
UR - https://arxiv.org/abs/2608.02600
AB - We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form ℒ_ϕ(ρ) = tr(ϕ(dρ))/d, where ρ is an unknown d-dimensional quantum state and ϕ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating ℒ_ϕ(ρ) from properties of ϕ, 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ényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is Θ (d^2/(εlog^2(d)max{1, εlog^2(d)}) + log^2(d)/ε^2), and the sample complexity of spectrum estimation is Θ (d^2/(ε^2log^2(d)max{1, ε^2log^2(d)})). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
ER -