Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2601.22005

Hierarchy of discriminative power and complexity in learning quantum ensembles

Jian Yao, Pengtao Li, Xiaohui Chen, Quntao Zhuang

quant-phmath.STstat.MLSubmitted Jan 29, 2026• Announced Jan 30, 2026• 3 citations• Revised Oct 1, 2026 (v2)
v1 · Jan 29, 2026v2 · Oct 1, 2026
arXivHTMLPDF

Abstract

Distance metrics are central to machine learning, yet distances between ensembles of quantum states remain poorly understood due to fundamental quantum measurement constraints. We introduce a hierarchy of integral probability metrics, termed MMD-$k$, which generalizes the maximum mean discrepancy to quantum ensembles and exhibits a strict trade-off between discriminative power and statistical efficiency as the moment order $k$ increases. For pure-state ensembles of size $N$, estimating MMD-$k$ with arbitrary measurement schemes requires $Θ(N^{1-1/k})$ samples for constant $k$. At the same time, we prove that any stable distance metric with full discriminative power admits an $O(N\log N)$ upper bound and an $Ω(N)$ instance-gap lower bound. For quantum Wasserstein distance, with sufficiently large fixed state dimension, we establish a nearly linear lower bound in the ensemble size at constant additive accuracy, together with an $O(N\log N)$ upper bound. These results provide principled guidance for the design of loss functions in quantum machine learning, as we illustrate in training quantum denoising diffusion probabilistic models.

Related papers

Machine Learning Framework for Efficient Prediction of Quantum Wasserstein Distance

Changchun Feng, Xinyu Qiu, Laifa Tao +1 more

The quantum Wasserstein distance (W-distance) is a fundamental metric for quantifying the distinguishability of quantum operations, with critical applications in quantum error correction. However, computing the W-distance remains computationally challenging for multiqubit systems due to exponential scaling. We present a machine learning framework that efficiently predicts the quantum W-distance by extracting physically meaningful features from quantum state pairs, including Pauli measurements, statistical moments, quantum fidelity, and entanglement measures. Our approach employs both classical neural networks and traditional machine learning models. On three-qubit systems, the best-performing Random Forest model achieves near-perfect accuracy ($R^2 = 0.9999$) with mean absolute errors on the order of $10^{-5}$. We further validate the framework's practical utility by successfully verifying two fundamental theoretical propositions in quantum information theory: the bound on measurement probability differences between unitary operations and the $W_1$ gate error rate bound. The results establish machine learning as a viable and scalable alternative to traditional numerical methods for W-distance computation, with particular promise for real-time quantum circuit assessment and error correction protocol design in NISQ devices.

quant-pharXiv:2511.12443•Nov 18, 2025•1 citation

Hypothesis testing between quantum ensembles

Jian Yao, Quntao Zhuang

Quantum state ensembles are important in quantum information processing. For example, quantum $t$-designs model highly entangled states in complex systems, while projected ensembles appear in generative quantum machine learning and studies of thermalization. With their sample state accompanied by a classical label, these ensembles contain operational information beyond their average density operators. Yet an ensemble differs from a classical-quantum state because it is invariant under permutations of labels. We formulate binary hypothesis testing between finite quantum ensembles and derive fundamental limits on error probability. Given an observed label pattern, we show that the joint sampled state can be described by power-weighted ensemble moments. This yields the Bayes-optimal measurement and exact finite-sample error, revealing that discrimination is governed by the full moment hierarchy up to the number of samples. In the many-sample limit, we derive Chernoff bounds and obtain exact error exponents for finite uniform pure-state ensembles. We apply these results to optical communication and $t$-designs. For finite uniform pure-state $t$-designs with large $t$, the maximal discrimination exponent scales sharply as $\sim t^{-2}$, while equal-prior fixed-error testing requires $\sim t^2$ samples.

quant-pharXiv:2608.21321•Aug 24, 2026•0 citations

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

Juntai Zhou, Felix Leditzky

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.

quant-pharXiv:2609.40182•Oct 1, 2026•0 citations

The power and limitations of restricted quantum learning models

Louis Schatzki

Quantum technologies have rapidly advanced over the past decade or so.However, noise and decoherence are still challenges.At the same time, quantum learning theory has quickly grown and many techniques have been developed with applications in verifying and benchmarking quantum devices.However, known generic but optimal protocols may require entangled measurements across many copies of a state, rendering experimental implementations rather difficult.With this mind, it is interesting to ask what learning tasks can and cannot be achieved with limited models of measurements, a question which has received much attention in recent years.In this thesis we answer several questions in this vein.First, we consider entangled versus separable measurements for exactly learning a function c ∈ C from a quantum example state |c⟩ = 1 √ 2 nx |x, c(x)⟩.We show that, if T copies suffice to learn f using entangled measurements, O(nT 2 ) copies suffice to learn f using only separable measurements.Second, we study the Quantum Statistical Query model.We exhibit a concept class C based of degree-2 functions with an exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise).This proves the "quantum analogue" of the seminal result of Blum, Kalai, & Wasserman.[1] that separates classical SQ learning from classical PAC learning with classification noise.To obtain these bounds, we introduce a quantum statistical query dimension (QSD).We prove superpolynomial QSQ lower bounds for testing purity of quantum states, reconstructing a state via shadow tomography, learning coset states for the Abelian hidden subgroup problem, approximating degree-2 functions, finding planted bi-cliques, and learning the output states of Clifford circuits of depth polylog(n).We also show that an extension of QSD characterizes the complexity of general search problems.Lastly, we give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model.Prior works by Quek et al. [2], Hinsche et al. [3], and Nietner et al. [4] proved analogous results assuming diagonal measurements and our work removes this assumption.Next, we consider the fundamental task of distributed inner product estimation when allowed limited communication.Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩ , |ϕ⟩ respectively.They are allowed to send q qubits to one another with the goal of estimating |⟨ψ|ϕ⟩| 2 up to constant additive error.We show that k = Θ( √ 2 n-q ) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when q = 0).Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M |ϕ⟩| 2 , for arbitrary Hermitian M .For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M |ϕ⟩| 2 when using only classical communication.Returning to separable vs entangled measurements, we make progress on proving a hierarchy of copycomplexity separations.To that end, we prove that estimating Tr[ρ k ], for k a constant, requires Ω(log d) samples with (k -1)-copy measurements.By contrast, O(1) samples suffice with k-copy measurements.To obtain our bounds, we extend Harrow's [5] method of PPT constraints on sums of permutations.This thesis and the work within would not have been possible without the support and encouragement of many people.I would like to start with my PhD advisor Eric Chitambar, whose support and guidance has been invaluable over the past five years.I have been fortunate to have had the opportunity to spend time at both Los Alamos and IBM while a PhD student and want to thank my collaborators and friends at those institutions.In particular, I want to express my gratitude to my close collaborations and mentors Srinivasan

•Aug 25, 2025•0 citations

Optimal single-copy estimation of quantum state moments: why $\operatorname{Tr}(ρ^3)$ and $\operatorname{Tr}(ρ^4)$ are equally hard

Zhenhuan Liu

Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments $\operatorname{Tr}(ρ^t)$, allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity $Θ(\sqrt d)$ at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer $t\ge 2$: for any sufficiently small constant additive error, the optimal sample complexity is \[ Θ\!\left(d^{\frac{\lceil\log_2 t\rceil}{1+\lceil\log_2 t\rceil}}\right) \] with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer $h\geq1$, all moment orders $2^{h-1}<t\leq2^h$ share the same exponent. In particular, the third and fourth moments both require $Θ(d^{2/3})$ copies. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. We also establish an $Ω(d^{1-1/t})$ lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every $t\geq4$. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond $\sqrt d$.

quant-pharXiv:2609.37781•Sep 30, 2026•1 citation

IQP Born Machines under Data-dependent and Agnostic Initialization Strategies

Sacha Lerch, Joseph Bowles, Ricard Puig +3 more

Quantum circuit Born machines based on instantaneous quantum polynomial-time (IQP) circuits are natural candidates for quantum generative modeling, both because of their probabilistic structure and because IQP sampling is provably classically hard in certain regimes. Recent proposals focus on training IQP-QCBMs using Maximum Mean Discrepancy (MMD) losses built from low-body Pauli-$Z$ correlators, but the effect of initialization on the resulting optimization landscape remains poorly understood. In this work, we address this by first proving that the MMD loss landscape suffers from barren plateaus for random full-angle-range initializations of IQP circuits. We then establish lower bounds on the loss variance for identity and an unbiased data-agnostic initialization. We then additionally consider a data-dependent initialization that is better aligned with the target distribution and, under suitable assumptions, yields provable gradients and generally converges quicker to a good minimum (as indicated by our training of circuits with 150 qubits on genomic data). Finally, as a by-product, the developed variance lower bound framework is applicable to a general class of non-linear losses, offering a broader toolset for analyzing warm-starts in quantum machine learning.

quant-pharXiv:2603.14576•Mar 17, 2026•15 citations
Distance metrics are central to machine learning, yet distances between ensembles of quantum states remain poorly understood due to fundamental quantum measurement constraints. We introduce a hierarchy of integral probability metrics, termed MMD-kkk, which generalizes the maximum mean discrepancy to quantum ensembles and exhibits a strict trade-off between discriminative power and statistical efficiency as the moment order kkk increases. For pure-state ensembles of size NNN, estimating MMD-kkk with arbitrary measurement schemes requires Θ(N1−1/k)Θ(N^{1-1/k})Θ(N1−1/k) samples for constant kkk. At the same time, we prove that any stable distance metric with full discriminative power admits an O(Nlog⁡N)O(N\log N)O(NlogN) upper bound and an Ω(N)Ω(N)Ω(N) instance-gap lower bound. For quantum Wasserstein distance, with sufficiently large fixed state dimension, we establish a nearly linear lower bound in the ensemble size at constant additive accuracy, together with an O(Nlog⁡N)O(N\log N)O(NlogN) upper bound. These results provide principled guidance for the design of loss functions in quantum machine learning, as we illustrate in training quantum denoising diffusion probabilistic models.
The quantum Wasserstein distance (W-distance) is a fundamental metric for quantifying the distinguishability of quantum operations, with critical applications in quantum error correction. However, computing the W-distance remains computationally challenging for multiqubit systems due to exponential scaling. We present a machine learning framework that efficiently predicts the quantum W-distance by extracting physically meaningful features from quantum state pairs, including Pauli measurements, statistical moments, quantum fidelity, and entanglement measures. Our approach employs both classical neural networks and traditional machine learning models. On three-qubit systems, the best-performing Random Forest model achieves near-perfect accuracy (R2=0.9999R^2 = 0.9999R2=0.9999) with mean absolute errors on the order of 10−510^{-5}10−5. We further validate the framework's practical utility by successfully verifying two fundamental theoretical propositions in quantum information theory: the bound on measurement probability differences between unitary operations and the W1W_1W1​ gate error rate bound. The results establish machine learning as a viable and scalable alternative to traditional numerical methods for W-distance computation, with particular promise for real-time quantum circuit assessment and error correction protocol design in NISQ devices.
Quantum state ensembles are important in quantum information processing. For example, quantum ttt-designs model highly entangled states in complex systems, while projected ensembles appear in generative quantum machine learning and studies of thermalization. With their sample state accompanied by a classical label, these ensembles contain operational information beyond their average density operators. Yet an ensemble differs from a classical-quantum state because it is invariant under permutations of labels. We formulate binary hypothesis testing between finite quantum ensembles and derive fundamental limits on error probability. Given an observed label pattern, we show that the joint sampled state can be described by power-weighted ensemble moments. This yields the Bayes-optimal measurement and exact finite-sample error, revealing that discrimination is governed by the full moment hierarchy up to the number of samples. In the many-sample limit, we derive Chernoff bounds and obtain exact error exponents for finite uniform pure-state ensembles. We apply these results to optical communication and ttt-designs. For finite uniform pure-state ttt-designs with large ttt, the maximal discrimination exponent scales sharply as ∼t−2\sim t^{-2}∼t−2, while equal-prior fixed-error testing requires ∼t2\sim t^2∼t2 samples.
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 GGG forms a Gelfand pair with the stabilizer subgroup HHH 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(C[G/H])\operatorname{End}_G(\mathbb C[G/H])EndG​(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-ddd phase states over Fq\mathbb F_qFq​ in [Alrabiah et al., 2026] and generalized Boolean phase states over Zq\mathbb Z_qZq​ [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.
Quantum technologies have rapidly advanced over the past decade or so.However, noise and decoherence are still challenges.At the same time, quantum learning theory has quickly grown and many techniques have been developed with applications in verifying and benchmarking quantum devices.However, known generic but optimal protocols may require entangled measurements across many copies of a state, rendering experimental implementations rather difficult.With this mind, it is interesting to ask what learning tasks can and cannot be achieved with limited models of measurements, a question which has received much attention in recent years.In this thesis we answer several questions in this vein.First, we consider entangled versus separable measurements for exactly learning a function c ∈ C from a quantum example state |c⟩ = 1 √ 2 nx |x, c(x)⟩.We show that, if T copies suffice to learn f using entangled measurements, O(nT 2 ) copies suffice to learn f using only separable measurements.Second, we study the Quantum Statistical Query model.We exhibit a concept class C based of degree-2 functions with an exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise).This proves the "quantum analogue" of the seminal result of Blum, Kalai, & Wasserman.[1] that separates classical SQ learning from classical PAC learning with classification noise.To obtain these bounds, we introduce a quantum statistical query dimension (QSD).We prove superpolynomial QSQ lower bounds for testing purity of quantum states, reconstructing a state via shadow tomography, learning coset states for the Abelian hidden subgroup problem, approximating degree-2 functions, finding planted bi-cliques, and learning the output states of Clifford circuits of depth polylog(n).We also show that an extension of QSD characterizes the complexity of general search problems.Lastly, we give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model.Prior works by Quek et al. [2], Hinsche et al. [3], and Nietner et al. [4] proved analogous results assuming diagonal measurements and our work removes this assumption.Next, we consider the fundamental task of distributed inner product estimation when allowed limited communication.Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩ , |ϕ⟩ respectively.They are allowed to send q qubits to one another with the goal of estimating |⟨ψ|ϕ⟩| 2 up to constant additive error.We show that k = Θ( √ 2 n-q ) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when q = 0).Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M |ϕ⟩| 2 , for arbitrary Hermitian M .For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M |ϕ⟩| 2 when using only classical communication.Returning to separable vs entangled measurements, we make progress on proving a hierarchy of copycomplexity separations.To that end, we prove that estimating Tr[ρ k ], for k a constant, requires Ω(log d) samples with (k -1)-copy measurements.By contrast, O(1) samples suffice with k-copy measurements.To obtain our bounds, we extend Harrow's [5] method of PPT constraints on sums of permutations.This thesis and the work within would not have been possible without the support and encouragement of many people.I would like to start with my PhD advisor Eric Chitambar, whose support and guidance has been invaluable over the past five years.I have been fortunate to have had the opportunity to spend time at both Los Alamos and IBM while a PhD student and want to thank my collaborators and friends at those institutions.In particular, I want to express my gratitude to my close collaborations and mentors Srinivasan
Optimal single-copy estimation of quantum state moments: why Tr⁡(ρ3)\operatorname{Tr}(ρ^3)Tr(ρ3) and Tr⁡(ρ4)\operatorname{Tr}(ρ^4)Tr(ρ4) are equally hard
Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments Tr⁡(ρt)\operatorname{Tr}(ρ^t)Tr(ρt), allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity Θ(d)Θ(\sqrt d)Θ(d​) at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer t≥2t\ge 2t≥2: for any sufficiently small constant additive error, the optimal sample complexity is Θ ⁣(d⌈log⁡2t⌉1+⌈log⁡2t⌉) Θ\!\left(d^{\frac{\lceil\log_2 t\rceil}{1+\lceil\log_2 t\rceil}}\right) Θ(d1+⌈log2​t⌉⌈log2​t⌉​) with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer h≥1h\geq1h≥1, all moment orders 2h−1<t≤2h2^{h-1}<t\leq2^h2h−1<t≤2h share the same exponent. In particular, the third and fourth moments both require Θ(d2/3)Θ(d^{2/3})Θ(d2/3) copies. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. We also establish an Ω(d1−1/t)Ω(d^{1-1/t})Ω(d1−1/t) lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every t≥4t\geq4t≥4. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond d\sqrt dd​.
Quantum circuit Born machines based on instantaneous quantum polynomial-time (IQP) circuits are natural candidates for quantum generative modeling, both because of their probabilistic structure and because IQP sampling is provably classically hard in certain regimes. Recent proposals focus on training IQP-QCBMs using Maximum Mean Discrepancy (MMD) losses built from low-body Pauli-ZZZ correlators, but the effect of initialization on the resulting optimization landscape remains poorly understood. In this work, we address this by first proving that the MMD loss landscape suffers from barren plateaus for random full-angle-range initializations of IQP circuits. We then establish lower bounds on the loss variance for identity and an unbiased data-agnostic initialization. We then additionally consider a data-dependent initialization that is better aligned with the target distribution and, under suitable assumptions, yields provable gradients and generally converges quicker to a good minimum (as indicated by our training of circuits with 150 qubits on genomic data). Finally, as a by-product, the developed variance lower bound framework is applicable to a general class of non-linear losses, offering a broader toolset for analyzing warm-starts in quantum machine learning.