PaperlayerView exact revision on arXiv

Source-linked AI summary

A mixing time method for estimating the sample complexity of quantum state discrimination

Juntai Zhou, Felix Leditzky

arXiv:2609.40182v1quant-phcs.CCcs.ITmath.ITmath.PRmath.RT

TL;DR

Estimating discrimination sample complexity systematically is challenging despite the Gram matrix containing the needed information. This paper relates that complexity to quantum mixing times and, for suitable symmetry, to classical mixing. The framework yields applications to phase and hypergraph states and extends to arbitrary uniform mixed-state ensembles.

  • Problem

    A systematic way to estimate discrimination sample complexity beyond coarse pairwise-overlap bounds and case-by-case measurement analysis is needed.

    Source: §I · p. 2, A. Minimum-error state discrimination… · p. 6

  • Method

    The paper relates sample complexity to quantum mixing times and reduces geometrically uniform ensembles with Gelfand-pair symmetry to classical mixing problems.

    Source: §II · p. 2, A. From Gram matrix to mixing times · p. 2

  • Results

    For Gelfand-pair ensembles, the quantum mixing problem reduces to classical mixing, and the framework yields phase-state upper bounds and hypergraph-data estimates.

    Source: §VII · p. 27

  • Takeaways & Limitations

    The framework also extends to arbitrary uniform mixed-state ensembles, bounding minimum-error complexity by a quantum weakly mixing time and tightly characterizing worst-case complexity by a Dobrushin-type coefficient.

    Source: §VII · p. 27

Abstract

from arXiv · show

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{\'e}, 2022] and give an upper bound in terms of a strengthened data processing inequality constant.

I. INTRODUCTION

The introduction motivates a systematic alternative to pairwise-overlap bounds and case-by-case analyses. The overview develops mixing-time estimates for discrimination and reduces important symmetric cases to classical walks.

I. INTRODUCTION

  • Structured ensembles can be distinguishable with fewer copies than pairwise-fidelity bounds suggest, but tight estimates often require problem-specific measurement analysis.The Gram matrix contains enough information to determine sample complexity; the challenge is organizing its dependence on copy number without repeatedly solving growing measurement problems.Source: §I · pp. 1–2

II. OVERVIEW OF MAIN RESULTS

  • The paper relates discrimination sample complexity to mixing time, with a tight quantum estimate and a reduction to classical mixing in suitable cases.The overview identifies Theorems 3 and 5 as the central results.Source: §II · p. 2

A. From Gram matrix to mixing times

  • For geometrically uniform pure states, the pretty good measurement is optimal, and k-copy success has a mixing-time interpretation through the Gram-matrix Hadamard channel.Restricting the channel to the Hecke algebra addresses the fact that it fixes every diagonal matrix; within that algebra, the fixed initial state is worst-case for convergence.Source: A. From Gram matrix to mixing times · pp. 2–3

B. Contraction coefficients and the mixing scale

  • A quantum generalized Dobrushin coefficient characterizes the asymptotic mixing scale and, with the quantum mixing time, tightly estimates discrimination complexity for GU ensembles under a strict overlap condition.The stated condition is max_{g not in H} |⟨ψ|U_g|ψ⟩| < 1.Source: B. Contraction coefficients and the… · p. 3
  • For arbitrary ensembles without symmetry, the paper gives an unconditional tight estimate of worst-case discrimination complexity using a Dobrushin-type coefficient.The proof first establishes stability of worst-case sample complexity under constant changes in the error threshold.Source: B. Contraction coefficients and the… · p. 3

C. Classical mixing time on the dual hypergroup

  • For GU ensembles forming a Gelfand pair, quantum mixing reduces to total-variation mixing of a classical walk on the dual hypergroup.The generalized Dobrushin coefficient also reduces to its classical counterpart and admits a representation-theoretic formula using Krein parameters and primitive idempotents.Source: C. Classical mixing time on the dual… · p. 4
  • The framework recovers quantum coupon-collector sample-complexity scaling through a birth-death chain on the dual, using classical mixing-time theory.Permutation symmetry supplies the Gelfand pair in this example.Source: C. Classical mixing time on the dual… · p. 4
  • For phase-state ensembles, a feature-map construction yields an abelian random walk, while triangular structure supports bounds based on coordinate-block information.Applications include an O_{q,d,ε}(n^{d−1}) copy upper bound for degree-d phase states over F_q at fixed prime q and d ≥ 2, and the same upper bound for generalized degree-d Boolean phase states over Z_q for fixed even q; the framework also gives hypergraph-data estimates and recovers graph-state results.Source: C. Classical mixing time on the dual… · pp. 4–5

D. Summary of results in a table

The paper identifies a systematic way to improve on generic sample-complexity bounds and establishes threshold stability for worst-case discrimination. Its examples distinguish worst-case from minimum-error sample complexity.

E. Organization of this article

  • The article organizes its results across discrimination and mixing background, GU pure-state theory and classical reduction, applications, and uniform mixed-state ensembles.Table I is identified as a summary of the authors’ main results, but the supplied passage does not provide its entries.Source: Table I · p. 5, E. Organization of this article · p. 6

A. Minimum-error state discrimination and its sample complexity

  • A systematic method to estimate sample-complexity scaling beyond the generic O(log n) upper bound was an open question, which this work addresses with a mixing-time method.The Barnum–Knill bound uses pairwise fidelities but may not capture the collective geometry that makes an ensemble easier to distinguish.Source: A. Minimum-error state discrimination… · p. 6

B. Worst-case state discrimination and its sample complexity

  • Worst-case discrimination sample complexity is stable under constant changes in the error threshold.For thresholds ϵ and δ, the passage bounds k_wc(ϵ) between k_wc(δ) and m(ϵ, δ)k_wc(δ).Source: B. Worst-case state discrimination and… · p. 7
  • The example separates worst-case from minimum-error complexity: one state can be sacrificed under minimum-error discrimination, unlike under the worst-case criterion.The passage reports minimum-error complexity 1 and worst-case complexity n for the stated threshold example.Source: B. Worst-case state discrimination and… · p. 7

C. Basics of classical Markov chain mixing

The section reviews classical mixing and contraction coefficients, then extends the generalized Dobrushin approach to quantum channels. The resulting quantum coefficient bounds the homogeneous mixing time from both sides.

1) Classical Dobrushin coefficients:

  • When the classical single-step Dobrushin coefficient is 1, it may fail to capture contraction even for an ergodic chain; the generalized coefficient characterizes mixing time up to universal constants.The supplied bound relates t_mix(K, ϵ) to 1−κ_gen(K).Source: 1) Classical Dobrushin coefficients · p. 8

2) Quantum Dobrushin coefficient:

  • The paper generalizes Wolfer’s generalized Dobrushin coefficient from Markov kernels to quantum channels.The quantum homogeneous mixing time is defined for a channel with stationary state ω.Source: 2) Quantum Dobrushin coefficient · p. 9
  • Two-sided bounds relate quantum homogeneous mixing time to the generalized quantum Dobrushin coefficient.The bounds apply to a channel T with stationary state ω and error ϵ.Source: 2) Quantum Dobrushin coefficient · p. 9

E. Fourier analysis on finite abelian groups

The supplied passages cover Fourier analysis on finite abelian groups, hypergraph-state structure, and the mixing-time interpretation for GU pure-state ensembles. For GU ensembles, discrimination sample complexity is tied to convergence of a Hadamard channel.

E. Fourier analysis on finite abelian groups

  • For a finite abelian group, a positive-semidefinite function normalized at zero corresponds uniquely to a probability distribution on the character group through Fourier transformation.This is the stated finite-group form of Bochner’s theorem.Source: E. Fourier analysis on finite abelian… · p. 10

F. Graph states and hypergraph states

  • Graph states are the degree-2 hypergraph states with size-2 edges, whereas larger hyperedges generally use non-Clifford gates and yield states that are usually not stabilizer states.The passage notes that general hypergraph states still have a generalized stabilizer formalism and are described by phase polynomials.Source: F. Graph states and hypergraph states · p. 10

IV. SAMPLE COMPLEXITY AS A MIXING TIME FOR GEOMETRICALLY UNIFORM PURE STATE

  • For GU pure-state ensembles, the optimal PGM success probability gives a fidelity-based mixing-time interpretation, and sample complexity is tightly estimated by the associated mixing time.Averaging a measurement over the group gives identical conditional success probability for every label, equating average and worst-case success.Source: §IV · p. 11

A. Tight estimate by Quantum Dobrushin coefficient

For GU ensembles, a quantum mixing time and generalized quantum Dobrushin coefficient tightly estimate discrimination sample complexity under a strict overlap condition. When the symmetry gives a Gelfand pair, the mixing problem reduces to a classical walk on a dual hypergroup.

A. Tight estimate by Quantum Dobrushin coefficient

  • In the GU setting, the fixed initial state for the sample-complexity mixing time is also a worst-case starting state.This connects the fixed-start estimate with worst-case homogeneous mixing.Source: A. Tight estimate by Quantum Dobrushin… · p. 12
  • If every off-stabilizer generator overlap has magnitude below 1, the quantum mixing time and generalized quantum Dobrushin coefficient tightly estimate GU discrimination sample complexity.The coefficient is below 1 exactly when max_{g not in H} |⟨ψ|U_g|ψ⟩| < 1.Source: A. Tight estimate by Quantum Dobrushin… · p. 12

B. Mixing of classical random walk on dual hypergroup

  • For a Gelfand pair, the quantum mixing time reduces to total-variation mixing of a classical walk on the dual hypergroup, with the Gram matrix determining the walk.The generalized quantum coefficient also reduces to a classical Dobrushin coefficient, expressible using representation-theoretic data of the commutative Hecke algebra.Source: B. Mixing of classical random walk on… · p. 14
  • The quantum coupon collector example yields a birth-death walk and recovers the sample-complexity scaling Θ_ϵ(r log min{r, l − r}).The passage identifies this as recovering the result in [2].Source: B. Mixing of classical random walk on… · p. 14

C. Tight estimate by classical Dobrushin coefficient

For the restricted Schur channel, the quantum Dobrushin coefficient reduces exactly to the classical coefficient of a dual-hypergroup random walk. The resulting estimate expresses discrimination sample complexity through representation-theoretic quantities.

V. PHASE STATE CASE

In the phase-state setting, a Gelfand-pair structure turns quantum mixing into classical random-walk mixing. The section applies this framework to structured feature maps, including triangular maps used for degree-d phase states.

V. PHASE STATE CASE

  • For G = A ⋊ K with H = K, the double cosets correspond to K-orbits in A, making the associated Hecke algebra commutative.Source: §V · p. 15
  • The phase-state mixing time is the total-variation mixing time of the induced walk on the dual hypergroup, equivalently of the corresponding walk on the dual group.Source: §V · p. 16
  • For feature-map phase states, the walk is built from independent feature values, and its generalized Dobrushin coefficient is expressible using A, ν, and Φ.Source: §V · p. 16
  • The lifted walk's generalized Dobrushin coefficient can differ from the coefficient in Eq. 90, although both give the same sample-complexity order up to ε.Source: §V · p. 17

A. Triangular feature map

  • Knothe–Rosenblatt triangular transport converts a global high-dimensional mixing problem into low-dimensional conditional Fourier estimates.Source: A. Triangular feature map · p. 17
  • The section proves the conjectured upper-bound order for degree-d phase-state sample complexity over Fq by applying the triangular mixing framework.Source: A. Triangular feature map · p. 18

C. Generalized degree-d Boolean phase states over Zq

The section addresses the open tight upper-bound question for learning generalized degree-d Boolean phase states with entangled measurements. It represents these states through a feature map and uses a polynomial nonvanishing bound.

D. Hypergraph state ensembles

Hypergraph state ensembles fit the feature-map framework, and their generalized Dobrushin coefficient can be expressed entirely through hypergraph data. The section also gives an upper bound organized by a vertex ordering.

1) Graph state ensemble:

For graph states, the paper gives an O_ε(D + log n)-copy identification bound when the graph is a subgraph of a bounded-degeneracy graph. For arbitrary uniform mixed-state ensembles, it relates minimum-error sample complexity to a quantum weakly mixing time, but the bound need not be tight without additional structure.

1) Graph state ensemble:

  • O_ε(D + log n) copies suffice to identify a graph state when the graph is a subgraph of a graph with bounded degeneracy D.The result concerns sample complexity and does not reproduce the cited work’s computational runtime guarantees.Source: 1) Graph state ensemble · p. 22

VI. GENERIC NON-GU ENSEMBLES

  • The quantum weakly mixing time gives a sandwiched bound on minimum-error discrimination sample complexity for arbitrary uniform mixed-state ensembles.The passage identifies the bound as sandwiched but does not state its endpoints.Source: §VI · p. 24
  • Without additional structure such as geometrical uniformity, the mixing-time bound is not guaranteed to be tight, even for pure states.The passage contrasts this general case with the paper’s tighter characterization under added structure.Source: §VI · p. 24

A. Tight estimate for worst-case discrimination sample complexity by Dobrushin-type coefficient

The section connects a multi-step Dobrushin-type coefficient to worst-case discrimination sample complexity. The bound is not always tight, and the structural classification of a stated condition is left for future work.

B. Pure state ensembles

For pure-state ensembles, the framework connects sample complexity to quantum homogeneous mixing and, under a Gelfand-pair condition, reduces the mixing problem to a classical one. The paper also gives an SDPI-based upper bound and summarizes extensions and open directions.

1) A strengthened data processing inequality upper bound:

VII. CONCLUSION

  • For arbitrary uniform mixed-state ensembles, the paper establishes two-sided bounds using a quantum weakly mixing time and a tight worst-case characterization using a generalized Dobrushin coefficient.Source: §VII · p. 27
  • For geometrically uniform pure states, the quantum homogeneous mixing time and generalized Dobrushin coefficient tightly estimate discrimination sample complexity.When the group and stabilizer form a Gelfand pair, the mixing problem reduces to a classical one and the coefficient is expressed using commutative Hecke-algebra representation quantities.Source: §VII · p. 27
  • Assuming a triangular feature-map structure, the framework yields mixing-time upper bounds for degree-d phase, generalized Boolean phase, and hypergraph states.Source: §VII · p. 27
  • The paper identifies tightness conditions for arbitrary-ensemble mixing bounds, quantum-discrimination cutoff, and further strengthened data-processing bounds as future directions.Source: §VII · p. 27
Loading 2609.40182v1…