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.
A Survey of Quantum Property Testing , year =
7 Pith papers cite this work, alongside 82 external citations. Polarity classification is still indexing.
7
Pith papers citing it
82
external citations · OpenAlex
fields
quant-ph 7years
2026 7representative citing papers
A reduction framework from sample complexity yields matching time lower bounds for purity estimation, high-order functionals, productness testing, and related quantum protocols.
Optimal algorithms achieve query complexities Θ(d/ε²) for incoherent access, Θ(d/ε) for coherent access, and Θ(√d/ε) for source-code access in quantum channel certification to unitary, exactly matching prior lower bounds.
Random dimension reduction replaces full dimension with max rank in sample complexity for symmetric quantum state properties and connects to but differs from random purification.
A reduction from weak agnostic learning of class C to efficient tomography of states with bounded l1-extent w.r.t. C, with a concrete algorithm for stabilizer states running in poly(n, (ξ/ε)^log(ξ/ε)) time.
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.
Adding loop composition to branching quantum walk models produces a variable-time quantum search algorithm whose complexity matches the best known results.
citing papers explorer
-
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.
-
Quantum Time Lower Bounds by Permutation Invariance
A reduction framework from sample complexity yields matching time lower bounds for purity estimation, high-order functionals, productness testing, and related quantum protocols.
-
Strict Hierarchy for Quantum Channel Certification to Unitary
Optimal algorithms achieve query complexities Θ(d/ε²) for incoherent access, Θ(d/ε) for coherent access, and Θ(√d/ε) for source-code access in quantum channel certification to unitary, exactly matching prior lower bounds.
-
Random dimension reduction and learning symmetric properties of quantum states
Random dimension reduction replaces full dimension with max rank in sample complexity for symmetric quantum state properties and connects to but differs from random purification.
-
Tomography of quantum states with bounded extent
A reduction from weak agnostic learning of class C to efficient tomography of states with bounded l1-extent w.r.t. C, with a concrete algorithm for stabilizer states running in poly(n, (ξ/ε)^log(ξ/ε)) time.
-
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.
-
Loop Composition in Quantum Algorithms
Adding loop composition to branching quantum walk models produces a variable-time quantum search algorithm whose complexity matches the best known results.