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:2609.28440

Sharp pairwise reduction for quantum hypothesis testing

Kuan-Yi Lee, Ludovico Lami

quant-phSubmitted Sep 23, 2026• Announced Sep 24, 2026• 2 citations
arXivHTMLPDF

Abstract

We determine the optimal universal coefficient in a reduction of multiple to binary quantum hypothesis testing. Specifically, for every finite ensemble in any Hilbert space dimension (finite or infinite), we prove that the error probability of the global pretty good measurement (PGM) is at most four times the sum of the optimal binary error probabilities. By constructing a family of regular-simplex ensembles, we further show that the coefficient four is optimal, even for arbitrary global measurements. This result improves on the pairwise bounds established by Cheng and Liu [arXiv:2606.06246 (2026)] and entails an explicit, sharp guarantee for the standard PGM itself. Our proof is also simpler: rather than constructing sequential measurements and applying a union bound, our proof relies on purely matrix-analytic techniques, combining a direct block Gram matrix analysis of the PGM error and a refined inequality between quantum Hellinger distance and Bures $χ^2$-divergence. Our analysis also yields a refined, one-shot pairwise Chernoff bound and explicit sufficient number of copies for a desired discrimination error.

AI Summary

The paper asks how tightly multiple quantum hypothesis testing can be reduced to binary discrimination, and whether an explicit measurement attains the best universal bound. For a finite ensemble $A_i=p_i\rho_i$, it proves $\operatorname{Err}^{\star}_N\leq\operatorname{Err}^{\mathrm{PGM}}_N\leq4\sum_{i<j}\operatorname{Err}^{\star}(A_i,A_j)$, with binary errors retaining the original, unnormalized priors. The coefficient is independent of dimension, priors, and ensemble size. This improves the previously established coefficient eight and applies directly to the standard pretty good measurement (PGM). The upper bound represents the PGM error through off-diagonal blocks of a block Gram matrix’s square root. A coefficient-one inequality between squared quantum Hellinger distance and Bures $\chi^2$-divergence reduces this expression to pairwise harmonic quantities, each bounded by the corresponding Helstrom error. Uniformly weighted regular-simplex ensembles show that no coefficient below four works universally, even for an optimal global measurement; the ratio approaches four as the number of hypotheses grows. The analysis also gives $\operatorname{Err}^{\mathrm{PGM}}_N\leq4\sum_{i<j}s_{ij}^{s_{ij}}(1-s_{ij})^{1-s_{ij}}\operatorname{Tr}A_i^{1-s_{ij}}A_j^{s_{ij}}$. For independent copies, choosing $s_{ij}=1/2$ yields the sufficient condition $n\geq\lceil\log((N-1)/\delta)/\log(1/\epsilon)\rceil$, where $\epsilon=\max_{i<j}\operatorname{Tr}\sqrt{\rho_i}\sqrt{\rho_j}<1$, for PGM error at most $\delta$. The results are stated for finite ensembles, including trace-class states in infinite dimension. The bound does not assert ensemble-specific optimality of the PGM. Optimal coefficients for fixed ensemble size, a proposed hierarchy of subset reductions, and extensions to continuous ensembles remain open.

Little sign of AI-generated textPossible error

Error found: The stated trace-class extension proves continuity only of the optimal discrimination error, leaving the infinite-dimensional PGM guarantee without the additional, valid continuity argument it needs.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
11 pages

Related papers

Multiple Quantum Hypothesis Testing: One-Shot Pairwise Bounds and Sharp Asymptotics

Hao-Chung Cheng, Po-Chieh Liu

We consider Bayesian discrimination among multiple quantum states and establish a dimension-free one-shot upper bound on the minimum probability of error in terms of the sum of pairwise errors. This resolves a conjecture of Audenaert and Mosonyi [J. Math. Phys. 55 (2014)] and improves the multiple quantum Chernoff bound of Li [Ann. Statist. 44 (2016)] by removing its dimension-dependent prefactor. In the asymptotic many-copy regime, our bound proves the achievability of the multiple quantum Chernoff distance for arbitrary separable Hilbert spaces, thereby settling the previously open infinite-dimensional case, and further yields constant-factor sharp asymptotics for the optimal error probability. In binary quantum hypothesis testing, we prove that the minimum error probability is characterized, up to universal constants, by a trace harmonic-mean quantity. Consequently, the optimal binary quantum error probability is within a factor of two of the optimal classical error probability for the associated Nussbaum-Szkoła distributions, complementing the lower bound of Nussbaum and Szkoła [Ann. Statist. 37 (2009)].

quant-pharXiv:2606.06246•Jun 5, 2026•5 citations

Sharp pairwise reduction for quantum hypothesis testing — E8 Intelligence Research

Andrew Stewart Caldin

We determine the optimal universal coefficient in a reduction of multiple to binary quantum hypothesis testing. Specifically, for every finite ensemble in any Hilbert space dimension (finite or infinite), we prove that the error probability of the global pretty good measurement (PGM) is at most four times the sum of the optimal binary error probabilities. By constructing a family of regular-simplex ensembles, we further show that the coefficient four is optimal, even for arbitrary global measurements. This result improves on the pairwise bounds established by Cheng and Liu [arXiv:2606.06246 (2026)] and entails an explicit, sharp guarantee for the standard PGM itself. Our proof is also simpler: rather than constructing sequential measurements and applying a union bound, our proof relies on purely matrix-analytic techniques, combining a direct block Gram matrix analysis of the PGM error and a refined inequality between quantum Hellinger distance and Bures $χ^2$-divergence. Our analysis a Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 11, 2026•0 citations

Pretty Good Bounds on the worst-case Pretty Good Measurement

Sergio Escobar, Austin Pechan

We derive a new lower bound on the success probability of the Pretty Good Measurement (PGM) for worst-case quantum state discrimination among $m$ pure states. Our bound is strictly tighter than the previously known Gram-matrix-based bound for $m\geq 4$. The proof adapts techniques from Barnum and Knill's analysis of the average-case PGM, applied here to the worst-case scenario. By comparing the PGM to the sequential measurement algorithm, we obtain a guarantee showing that, in the low-fidelity regime, the PGM's success probability decreases quadratically with respect to the maximum pairwise overlap, rather than linearly as in earlier bounds.

arXiv:2508.19085•Aug 26, 2025•0 citations

An asymptotic error bound for testing multiple quantum hypotheses

Michael Nussbaum, Arleta Szkoła

We consider the problem of detecting the true quantum state among r possible ones, based of measurements performed on n copies of a finite-dimensional quantum system. A special case is the problem of discriminating between r probability measures on a finite sample space, using n i.i.d. observations. In this classical setting, it is known that the averaged error probability decreases exponentially with exponent given by the worst case binary Chernoff bound between any possible pair of the r probability measures. Define analogously the multiple quantum Chernoff bound, considering all possible pairs of states. Recently, it has been shown that this asymptotic error bound is attainable in the case of r pure states, and that it is unimprovable in general. Here we extend the attainability result to a larger class of r-tuples of states which are possibly mixed, but pairwise linearly independent. We also construct a quantum detector which universally attains the multiple quantum Chernoff bound up to a factor 1/3.

arXiv:1112.1529•The Annals of Statistics•Dec 1, 2011•21 citations

Binary Quantum Hypothesis Testing with a Rejection Option: The Exact Error-Exponent Trade-off

Yonglong Li

We characterize the exact error-exponent trade-off in binary quantum hypothesis testing with a rejection option for faithful states on a finite-dimensional Hilbert space. The probabilities of rejection under the two hypotheses are required to vanish exponentially, with exponents at least $K$ and $L$. We show that a quadruple $(a,b,K,L)$ of positive error and rejection exponents is achievable if and only if it satisfies three single-letter conditions: two conditions involve Petz--Rényi quantities and coincide with the converse bound conjectured to be tight by Ji and Regula; the third involves the $α$--$z$ Rényi quantities on the triangle $\max\{α,1-α\}\le z\le1$. The proof combines a sector decomposition inside Schur--Weyl blocks, an explicit one-shot measurement construction, and an exact minimax argument.

quant-pharXiv:2611.00931•Nov 3, 2026•0 citations

Discriminating quantum states: The multiple Chernoff distance

Ke Li

We consider the problem of testing multiple quantum hypotheses $\{\rho_{1}^{\otimes n},\ldots,\rho_{r}^{\otimes n}\}$, where an arbitrary prior distribution is given and each of the $r$ hypotheses is $n$ copies of a quantum state. It is known that the minimal average error probability $P_{e}$ decays exponentially to zero, that is, $P_{e}=\exp\{-\xi n+o(n)\}$. However, this error exponent $\xi$ is generally unknown, except for the case that $r=2$. In this paper, we solve the long-standing open problem of identifying the above error exponent, by proving Nussbaum and Szkoła’s conjecture that $\xi=\min_{i\neq j}C(\rho_{i},\rho_{j})$. The right-hand side of this equality is called the multiple quantum Chernoff distance, and $C(\rho_{i},\rho_{j}):=\max_{0\leq s\leq1}\{-\log\operatorname{Tr}\rho_{i}^{s}\rho_{j}^{1-s}\}$ has been previously identified as the optimal error exponent for testing two hypotheses, $\rho_{i}^{\otimes n}$ versus $\rho_{j}^{\otimes n}$. The main ingredient of our proof is a new upper bound for the average error probability, for testing an ensemble of finite-dimensional, but otherwise general, quantum states. This upper bound, up to a states-dependent factor, matches the multiple-state generalization of Nussbaum and Szkoła’s lower bound. Specialized to the case $r=2$, we give an alternative proof to the achievability of the binary-hypothesis Chernoff distance, which was originally proved by Audenaert et al.

arXiv:1508.06624•The Annals of Statistics•Jul 7, 2016•61 citations
We determine the optimal universal coefficient in a reduction of multiple to binary quantum hypothesis testing. Specifically, for every finite ensemble in any Hilbert space dimension (finite or infinite), we prove that the error probability of the global pretty good measurement (PGM) is at most four times the sum of the optimal binary error probabilities. By constructing a family of regular-simplex ensembles, we further show that the coefficient four is optimal, even for arbitrary global measurements. This result improves on the pairwise bounds established by Cheng and Liu [arXiv:2606.06246 (2026)] and entails an explicit, sharp guarantee for the standard PGM itself. Our proof is also simpler: rather than constructing sequential measurements and applying a union bound, our proof relies on purely matrix-analytic techniques, combining a direct block Gram matrix analysis of the PGM error and a refined inequality between quantum Hellinger distance and Bures χ2χ^2χ2-divergence. Our analysis also yields a refined, one-shot pairwise Chernoff bound and explicit sufficient number of copies for a desired discrimination error.
The paper asks how tightly multiple quantum hypothesis testing can be reduced to binary discrimination, and whether an explicit measurement attains the best universal bound. For a finite ensemble Ai=piρiA_i=p_i\rho_iAi​=pi​ρi​, it proves Err⁡N⋆≤Err⁡NPGM≤4∑i<jErr⁡⋆(Ai,Aj)\operatorname{Err}^{\star}_N\leq\operatorname{Err}^{\mathrm{PGM}}_N\leq4\sum_{i<j}\operatorname{Err}^{\star}(A_i,A_j)ErrN⋆​≤ErrNPGM​≤4∑i<j​Err⋆(Ai​,Aj​), with binary errors retaining the original, unnormalized priors. The coefficient is independent of dimension, priors, and ensemble size. This improves the previously established coefficient eight and applies directly to the standard pretty good measurement (PGM).
The upper bound represents the PGM error through off-diagonal blocks of a block Gram matrix’s square root. A coefficient-one inequality between squared quantum Hellinger distance and Bures χ2\chi^2χ2-divergence reduces this expression to pairwise harmonic quantities, each bounded by the corresponding Helstrom error. Uniformly weighted regular-simplex ensembles show that no coefficient below four works universally, even for an optimal global measurement; the ratio approaches four as the number of hypotheses grows.
The analysis also gives Err⁡NPGM≤4∑i<jsijsij(1−sij)1−sijTr⁡Ai1−sijAjsij\operatorname{Err}^{\mathrm{PGM}}_N\leq4\sum_{i<j}s_{ij}^{s_{ij}}(1-s_{ij})^{1-s_{ij}}\operatorname{Tr}A_i^{1-s_{ij}}A_j^{s_{ij}}ErrNPGM​≤4∑i<j​sijsij​​(1−sij​)1−sij​TrAi1−sij​​Ajsij​​. For independent copies, choosing sij=1/2s_{ij}=1/2sij​=1/2 yields the sufficient condition n≥⌈log⁡((N−1)/δ)/log⁡(1/ϵ)⌉n\geq\lceil\log((N-1)/\delta)/\log(1/\epsilon)\rceiln≥⌈log((N−1)/δ)/log(1/ϵ)⌉, where ϵ=max⁡i<jTr⁡ρiρj<1\epsilon=\max_{i<j}\operatorname{Tr}\sqrt{\rho_i}\sqrt{\rho_j}<1ϵ=maxi<j​Trρi​​ρj​​<1, for PGM error at most δ\deltaδ.
The results are stated for finite ensembles, including trace-class states in infinite dimension. The bound does not assert ensemble-specific optimality of the PGM. Optimal coefficients for fixed ensemble size, a proposed hierarchy of subset reductions, and extensions to continuous ensembles remain open.
We consider Bayesian discrimination among multiple quantum states and establish a dimension-free one-shot upper bound on the minimum probability of error in terms of the sum of pairwise errors. This resolves a conjecture of Audenaert and Mosonyi [J. Math. Phys. 55 (2014)] and improves the multiple quantum Chernoff bound of Li [Ann. Statist. 44 (2016)] by removing its dimension-dependent prefactor. In the asymptotic many-copy regime, our bound proves the achievability of the multiple quantum Chernoff distance for arbitrary separable Hilbert spaces, thereby settling the previously open infinite-dimensional case, and further yields constant-factor sharp asymptotics for the optimal error probability. In binary quantum hypothesis testing, we prove that the minimum error probability is characterized, up to universal constants, by a trace harmonic-mean quantity. Consequently, the optimal binary quantum error probability is within a factor of two of the optimal classical error probability for the associated Nussbaum-Szkoła distributions, complementing the lower bound of Nussbaum and Szkoła [Ann. Statist. 37 (2009)].
We determine the optimal universal coefficient in a reduction of multiple to binary quantum hypothesis testing. Specifically, for every finite ensemble in any Hilbert space dimension (finite or infinite), we prove that the error probability of the global pretty good measurement (PGM) is at most four times the sum of the optimal binary error probabilities. By constructing a family of regular-simplex ensembles, we further show that the coefficient four is optimal, even for arbitrary global measurements. This result improves on the pairwise bounds established by Cheng and Liu [arXiv:2606.06246 (2026)] and entails an explicit, sharp guarantee for the standard PGM itself. Our proof is also simpler: rather than constructing sequential measurements and applying a union bound, our proof relies on purely matrix-analytic techniques, combining a direct block Gram matrix analysis of the PGM error and a refined inequality between quantum Hellinger distance and Bures χ2χ^2χ2-divergence. Our analysis a Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
We derive a new lower bound on the success probability of the Pretty Good Measurement (PGM) for worst-case quantum state discrimination among mmm pure states. Our bound is strictly tighter than the previously known Gram-matrix-based bound for m≥4m\geq 4m≥4. The proof adapts techniques from Barnum and Knill's analysis of the average-case PGM, applied here to the worst-case scenario. By comparing the PGM to the sequential measurement algorithm, we obtain a guarantee showing that, in the low-fidelity regime, the PGM's success probability decreases quadratically with respect to the maximum pairwise overlap, rather than linearly as in earlier bounds.
We consider the problem of detecting the true quantum state among r possible ones, based of measurements performed on n copies of a finite-dimensional quantum system. A special case is the problem of discriminating between r probability measures on a finite sample space, using n i.i.d. observations. In this classical setting, it is known that the averaged error probability decreases exponentially with exponent given by the worst case binary Chernoff bound between any possible pair of the r probability measures. Define analogously the multiple quantum Chernoff bound, considering all possible pairs of states. Recently, it has been shown that this asymptotic error bound is attainable in the case of r pure states, and that it is unimprovable in general. Here we extend the attainability result to a larger class of r-tuples of states which are possibly mixed, but pairwise linearly independent. We also construct a quantum detector which universally attains the multiple quantum Chernoff bound up to a factor 1/3.
We characterize the exact error-exponent trade-off in binary quantum hypothesis testing with a rejection option for faithful states on a finite-dimensional Hilbert space. The probabilities of rejection under the two hypotheses are required to vanish exponentially, with exponents at least KKK and LLL. We show that a quadruple (a,b,K,L)(a,b,K,L)(a,b,K,L) of positive error and rejection exponents is achievable if and only if it satisfies three single-letter conditions: two conditions involve Petz--Rényi quantities and coincide with the converse bound conjectured to be tight by Ji and Regula; the third involves the ααα--zzz Rényi quantities on the triangle max⁡{α,1−α}≤z≤1\max\{α,1-α\}\le z\le1max{α,1−α}≤z≤1. The proof combines a sector decomposition inside Schur--Weyl blocks, an explicit one-shot measurement construction, and an exact minimax argument.
We consider the problem of testing multiple quantum hypotheses {ρ1⊗n,…,ρr⊗n}\{\rho_{1}^{\otimes n},\ldots,\rho_{r}^{\otimes n}\}{ρ1⊗n​,…,ρr⊗n​}, where an arbitrary prior distribution is given and each of the rrr hypotheses is nnn copies of a quantum state. It is known that the minimal average error probability PeP_{e}Pe​ decays exponentially to zero, that is, Pe=exp⁡{−ξn+o(n)}P_{e}=\exp\{-\xi n+o(n)\}Pe​=exp{−ξn+o(n)}. However, this error exponent ξ\xiξ is generally unknown, except for the case that r=2r=2r=2. In this paper, we solve the long-standing open problem of identifying the above error exponent, by proving Nussbaum and Szkoła’s conjecture that ξ=min⁡i≠jC(ρi,ρj)\xi=\min_{i\neq j}C(\rho_{i},\rho_{j})ξ=mini=j​C(ρi​,ρj​). The right-hand side of this equality is called the multiple quantum Chernoff distance, and C(ρi,ρj):=max⁡0≤s≤1{−log⁡Tr⁡ρisρj1−s}C(\rho_{i},\rho_{j}):=\max_{0\leq s\leq1}\{-\log\operatorname{Tr}\rho_{i}^{s}\rho_{j}^{1-s}\}C(ρi​,ρj​):=max0≤s≤1​{−logTrρis​ρj1−s​} has been previously identified as the optimal error exponent for testing two hypotheses, ρi⊗n\rho_{i}^{\otimes n}ρi⊗n​ versus ρj⊗n\rho_{j}^{\otimes n}ρj⊗n​. The main ingredient of our proof is a new upper bound for the average error probability, for testing an ensemble of finite-dimensional, but otherwise general, quantum states. This upper bound, up to a states-dependent factor, matches the multiple-state generalization of Nussbaum and Szkoła’s lower bound. Specialized to the case r=2r=2r=2, we give an alternative proof to the achievability of the binary-hypothesis Chernoff distance, which was originally proved by Audenaert et al.