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

Pretty Good Bounds on the worst-case Pretty Good Measurement

Sergio Escobar, Austin Pechan

Published Aug 26, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2508.19085

Related papers

Sharp pairwise reduction for quantum hypothesis testing

Kuan-Yi Lee, Ludovico Lami

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.

quant-pharXiv:2609.28440•Sep 24, 2026•2 citations

Pretty simple bounds on quantum state discrimination

Ashley Montanaro

We show that the quantum measurement known as the pretty good measurement can be used to identify an unknown quantum state picked from any set of $n$ mixed states that have pairwise fidelities upper-bounded by a constant below 1, given $O(\log n)$ copies of the unknown state, with high success probability in the worst case. If the unknown state is promised to be pure, there is an explicit measurement strategy which solves this worst-case quantum state discrimination problem with $\widetilde{O}(\|G\|)$ copies, where $G$ is the Gram matrix of the states.

arXiv:1908.08312•Aug 22, 2019•19 citations

Error rates of Belavkin weighted quantum measurements and a converse to Holevo’s asymptotic optimality theorem

Jon Tyson

We compare several instances of pure-state Belavkin weighted square-root measurements from the standpoint of minimum-error discrimination of quantum states. The quadratically weighted measurement is proven superior to the so-called ``pretty good measurement'' (PGM) in a number of respects: (1) Holevo's quadratic weighting unconditionally outperforms the PGM in the case of two-state ensembles, with equality only in trivial cases. (2) A converse of a theorem of Holevo is proven, showing that a weighted measurement is asymptotically optimal only if it is quadratically weighted. Counterexamples for three states are constructed. The cube-weighted measurement of Ballester, Wehner, and Winter is also considered. Sufficient optimality conditions for various weights are compared.

arXiv:0907.1884•Physical Review A•Mar 31, 2009•19 citations

Robust Pretty Good Measurement via Hybrid Classical-Quantum Pseudoinverse Approximation and Circuit-Level Realization

Bikash K. Behera, Andrés Camilo Granda Arango, Giuseppe Sergioli +1 more

Pretty Good Measurement (PGM) is a near-optimal strategy for quantum state discrimination, but its practical realization becomes unstable when the ensemble operator is singular or ill-conditioned. We introduce a numerically robust PGM formulation based on the Moore-Penrose pseudoinverse, replacing the standard inverse square root with a threshold-regularized variant that remains well-defined across different spectral regimes. We develop a hybrid classical-quantum framework that combines pseudoinverse-based spectral preprocessing with quantum circuit realizations using block-encoding and spectral-transformation techniques. The framework incorporates support awareness, yielding physically meaningful measurement operators even in rank-deficient cases, and employs oblivious amplitude amplification to improve circuit-level success probabilities. Extensive numerical and circuit-level simulations show close agreement between theoretical predictions and quantum circuit outputs. Experiments on synthetic and real datasets, including ill-conditioned and degenerate scenarios, demonstrate stable discrimination performance where standard PGM becomes numerically unstable. The results establish a practical hybrid classical-quantum framework for robust quantum state discrimination and extend previous circuit-based implementations of the PGM testing stage toward pseudoinverse-aware measurement design.

quant-pharXiv:2606.13150•Jun 12, 2026•0 citations

Near-optimal performance of square-root measurement for general score functions and quantum ensembles

Hemant K. Mishra, Ludovico Lami, Mark M. Wilde

The Barnum-Knill theorem states that the optimal success probability in the multiple state discrimination task is not more than the square root of the success probability when the pretty good or square-root measurement is used for this task. An assumption of the theorem is that the underlying ensemble consists of finitely many quantum states over a finite-dimensional quantum system. Motivated in part by the fact that the success probability is not a relevant metric for continuous ensembles, in this paper we provide a generalization of the notion of pretty good measurement and the Barnum-Knill theorem for general quantum ensembles, including those described by a continuous parameter space and an infinite-dimensional Hilbert space. To achieve this, we also design a general metric of performance for quantum measurements that generalizes the success probability, namely, the expected gain of the measurement with respect to a positive score function. A notable consequence of the main result is that, in a Bayesian estimation task, the mean square error of the generalized pretty good measurement does not exceed twice the optimal mean square error.

arXiv:2505.20447•May 26, 2025•7 citations

Family of generalized “pretty good” measurements and the minimal-error pure-state discrimination problems for which they are optimal

Carlos Mochon

Given a quantum pure state chosen from a set with some a priori probabilities, what is the optimal measurement needed to correctly guess the given state? We show that a good choice is the family of square-root or ``pretty good'' measurements, as each measurement in the family is optimal for at least one discrimination problem with the same quantum states but possibly different a priori probabilities. Furthermore, the map from measurement to discrimination problems can be explicitly described. In fact, for linearly independent states, every pair of discrimination problem and optimal measurement can be explicitly generated this way.

arXiv:quant-ph/0506061•Physical Review A•Mar 22, 2006•48 citations
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 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.
We show that the quantum measurement known as the pretty good measurement can be used to identify an unknown quantum state picked from any set of nnn mixed states that have pairwise fidelities upper-bounded by a constant below 1, given O(log⁡n)O(\log n)O(logn) copies of the unknown state, with high success probability in the worst case. If the unknown state is promised to be pure, there is an explicit measurement strategy which solves this worst-case quantum state discrimination problem with O~(∥G∥)\widetilde{O}(\|G\|)O(∥G∥) copies, where GGG is the Gram matrix of the states.
We compare several instances of pure-state Belavkin weighted square-root measurements from the standpoint of minimum-error discrimination of quantum states. The quadratically weighted measurement is proven superior to the so-called ``pretty good measurement'' (PGM) in a number of respects: (1) Holevo's quadratic weighting unconditionally outperforms the PGM in the case of two-state ensembles, with equality only in trivial cases. (2) A converse of a theorem of Holevo is proven, showing that a weighted measurement is asymptotically optimal only if it is quadratically weighted. Counterexamples for three states are constructed. The cube-weighted measurement of Ballester, Wehner, and Winter is also considered. Sufficient optimality conditions for various weights are compared.
Pretty Good Measurement (PGM) is a near-optimal strategy for quantum state discrimination, but its practical realization becomes unstable when the ensemble operator is singular or ill-conditioned. We introduce a numerically robust PGM formulation based on the Moore-Penrose pseudoinverse, replacing the standard inverse square root with a threshold-regularized variant that remains well-defined across different spectral regimes. We develop a hybrid classical-quantum framework that combines pseudoinverse-based spectral preprocessing with quantum circuit realizations using block-encoding and spectral-transformation techniques. The framework incorporates support awareness, yielding physically meaningful measurement operators even in rank-deficient cases, and employs oblivious amplitude amplification to improve circuit-level success probabilities. Extensive numerical and circuit-level simulations show close agreement between theoretical predictions and quantum circuit outputs. Experiments on synthetic and real datasets, including ill-conditioned and degenerate scenarios, demonstrate stable discrimination performance where standard PGM becomes numerically unstable. The results establish a practical hybrid classical-quantum framework for robust quantum state discrimination and extend previous circuit-based implementations of the PGM testing stage toward pseudoinverse-aware measurement design.
The Barnum-Knill theorem states that the optimal success probability in the multiple state discrimination task is not more than the square root of the success probability when the pretty good or square-root measurement is used for this task. An assumption of the theorem is that the underlying ensemble consists of finitely many quantum states over a finite-dimensional quantum system. Motivated in part by the fact that the success probability is not a relevant metric for continuous ensembles, in this paper we provide a generalization of the notion of pretty good measurement and the Barnum-Knill theorem for general quantum ensembles, including those described by a continuous parameter space and an infinite-dimensional Hilbert space. To achieve this, we also design a general metric of performance for quantum measurements that generalizes the success probability, namely, the expected gain of the measurement with respect to a positive score function. A notable consequence of the main result is that, in a Bayesian estimation task, the mean square error of the generalized pretty good measurement does not exceed twice the optimal mean square error.
Given a quantum pure state chosen from a set with some a priori probabilities, what is the optimal measurement needed to correctly guess the given state? We show that a good choice is the family of square-root or ``pretty good'' measurements, as each measurement in the family is optimal for at least one discrimination problem with the same quantum states but possibly different a priori probabilities. Furthermore, the map from measurement to discrimination problems can be explicitly described. In fact, for linearly independent states, every pair of discrimination problem and optimal measurement can be explicitly generated this way.