arXiv:2609.40182
A mixing time method for estimating the sample complexity of quantum state discrimination
Juntai Zhou, Felix Leditzky
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 $\operatorname{End}_G(\mathbb C[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 $\mathbb F_q$ in [Alrabiah et al., 2026] and generalized Boolean phase states over $\mathbb Z_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.
AI Summary
The paper asks how to estimate the number of identical copies needed to distinguish a finite quantum-state ensemble without repeatedly optimizing measurements or relying only on pairwise overlaps. It relates discrimination sample complexity to mixing times associated with Gram matrices. For geometrically uniform pure-state ensembles, optimal pretty-good-measurement success equals the fidelity between the normalized tensor-power Gram matrix and the maximally mixed state. Taking another copy acts as a Hadamard channel. Restricting this channel to the ensemble’s Hecke algebra makes the all-ones initial state worst-case for mixing, yielding $k_{\min}=\Theta_\epsilon(t_{\mathrm{mix}})=\Theta_\epsilon((1-\kappa_{\mathrm{gen}})^{-1})$ at fixed error below $1/2$. For Gelfand pairs, this becomes a classical walk on a dual hypergroup, with transitions determined by representation-theoretic data. For phase states, the walk adds independently sampled feature vectors. A conditional Fourier bound for triangular feature maps gives $O_{q,d,\epsilon}(n^{d-1})$ copies for degree-$d$ phase states over prime fields and generalized Boolean phase states with fixed even modulus, resolving the stated upper-bound questions for fixed $d\geq2$. Applications also recover quantum coupon-collector scaling and give hypergraph-state bounds; bounded-degeneracy hidden graph states require $O_\epsilon(D+\log n)$ copies. For arbitrary uniformly weighted mixed ensembles, block-Gram estimates give $t_{\min}(4\sqrt\epsilon)\leq k_{\min}(\epsilon)\leq t_{\min}(\epsilon)$. A stabilized contraction coefficient tightly characterizes minimax sample complexity. Without symmetry, the average-error sandwich need not be tight; classifying tightness is left open. The graph-state bounds concern copies, not computational runtime, and further exploration of strengthened data-processing bounds is deferred.
The literature search, verification of calculations, and refinement of the writing were assisted by GPT-5 and subsequent models.
Error found: The quantum-coupon-collector example and summary table incorrectly state Θε(r log min{r,ℓ−r}) for all r<ℓ; when min{r,ℓ−r}=1 this vanishes, and the uniform scaling is Θε(r[1+log min{r,ℓ−r}]).
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.