Sample complexity for fidelity estimation to a rank-r reference state is O(r²/ε²) with lower bound Ω(r/ε²); O(r²/ε⁴) when unknown state also has rank ≤r.
A list of complexity bounds for property testing by quantum sample-to-query lifting
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
citation-role summary
method 1
citation-polarity summary
fields
quant-ph 4years
2026 4roles
method 1polarities
use method 1representative citing papers
A quantum multi-level framework achieves near-optimal query complexity for q-Tsallis entropy estimation for q>1 and a speedup for q<1 over classical methods.
A two-stage adaptive algorithm identifies a task-specific spectral cutoff to enable low-degree QSVT polynomials for nonlinear quantum property estimation, lowering cost versus conservative eigenvalue bounds.
Claims an exponential quantum-classical space separation for streaming Shannon entropy estimation, but the oracle at the algorithm's core is not constructible in the stated streaming model.
citing papers explorer
-
Estimating Fidelity to a Reference Quantum State
Sample complexity for fidelity estimation to a rank-r reference state is O(r²/ε²) with lower bound Ω(r/ε²); O(r²/ε⁴) when unknown state also has rank ≤r.
-
Quantum Multi-Level Estimation of Functionals of Discrete Distributions
A quantum multi-level framework achieves near-optimal query complexity for q-Tsallis entropy estimation for q>1 and a speedup for q<1 over classical methods.
-
Adaptive identification of low-degree polynomials in quantum singular value transformation: application to nonlinear quantum properties estimation
A two-stage adaptive algorithm identifies a task-specific spectral cutoff to enable low-degree QSVT polynomials for nonlinear quantum property estimation, lowering cost versus conservative eigenvalue bounds.
-
Exponential quantum space advantage for Shannon entropy estimation in data streams
Claims an exponential quantum-classical space separation for streaming Shannon entropy estimation, but the oracle at the algorithm's core is not constructible in the stated streaming model.