A mixing time method for estimating the sample complexity of quantum state discrimination
Abstract
We develop a mixing time method for estimating the sample complexity of quantum state discrimination. We start with considering the minimum-error discrimination of geometrically uniform pure state ensembles, and prove that its sample complexity has a tight estimate given by a quantum homogeneous mixing time [George et al., 2026] and a quantum version of the generalized Dobrushin coefficient [Wolfer, 2020]. This quantum mixing time further reduces to a classical one when the generating group G forms a Gelfand pair with the stabilizer subgroup H of the generator state. In this case the generalized Dobrushin coefficient can be fully expressed by representation-theoretic quantities of the commutative Hecke algebra EndG(ℂ[G/H]). In particular, this method reduces the sample complexity estimation of learning quantum coupon collector states [Arunachalam et al., 2020] and learning phase states to classical mixing time problems. We apply this framework to answer the open problems of learning degree-d phase states over 𝔽q in [Alrabiah et al., 2026] and generalized Boolean phase states over ℤq [Arunachalam et al., 2023]. The framework also applies to hypergraph state ensembles, giving estimates expressed fully in terms of hypergraph data and recovering estimates for graph state ensembles in [Montanaro and Shao, 2022]. Finally, we extend the discussion to arbitrary mixed state ensembles with uniform priors, prove a sandwiched bound for minimum-error discrimination sample complexity by a quantum weakly mixing time, and provide a tight estimate for the minimax discrimination sample complexity from [D'Ariano et al., 2005] by a Dobrushin-type coefficient. We also discuss the method of strengthened data processing inequality [Gao and Rouz{é}, 2022] and give an upper bound in terms of a strengthened data processing inequality constant.
Related
- On the Impossibility of Estimating the Average Mixing Time
- KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling
- A general method for estimating reliability using Bayesian Measurement Uncertainty
- Adaptive Normalized Gradient Method for (L0,L1)-smooth Problems: Estimating Problem Parameters as a Region
- A Simple and Reliable Method for Estimating the Duration of an Online Questionnaire at the Design Stage
BibTeX
@misc{zhou2026mixing,
title = {{A mixing time method for estimating the sample complexity of quantum state discrimination}},
author = {Juntai Zhou and Felix Leditzky},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40182},
eprint = {2609.40182},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40182},
}
RIS
TY - UNPB
TI - A mixing time method for estimating the sample complexity of quantum state discrimination
AU - Juntai Zhou
AU - Felix Leditzky
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40182
UR - https://arxiv.org/abs/2609.40182
AB - We develop a mixing time method for estimating the sample complexity of quantum state discrimination. We start with considering the minimum-error discrimination of geometrically uniform pure state ensembles, and prove that its sample complexity has a tight estimate given by a quantum homogeneous mixing time [George et al., 2026] and a quantum version of the generalized Dobrushin coefficient [Wolfer, 2020]. This quantum mixing time further reduces to a classical one when the generating group G forms a Gelfand pair with the stabilizer subgroup H of the generator state. In this case the generalized Dobrushin coefficient can be fully expressed by representation-theoretic quantities of the commutative Hecke algebra End_G(ℂ[G/H]). In particular, this method reduces the sample complexity estimation of learning quantum coupon collector states [Arunachalam et al., 2020] and learning phase states to classical mixing time problems. We apply this framework to answer the open problems of learning degree-d phase states over 𝔽_q in [Alrabiah et al., 2026] and generalized Boolean phase states over ℤ_q [Arunachalam et al., 2023]. The framework also applies to hypergraph state ensembles, giving estimates expressed fully in terms of hypergraph data and recovering estimates for graph state ensembles in [Montanaro and Shao, 2022]. Finally, we extend the discussion to arbitrary mixed state ensembles with uniform priors, prove a sandwiched bound for minimum-error discrimination sample complexity by a quantum weakly mixing time, and provide a tight estimate for the minimax discrimination sample complexity from [D'Ariano et al., 2005] by a Dobrushin-type coefficient. We also discuss the method of strengthened data processing inequality [Gao and Rouz{é}, 2022] and give an upper bound in terms of a strengthened data processing inequality constant.
ER -