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

Pretty simple bounds on quantum state discrimination

Ashley Montanaro

Published Aug 22, 2019• 19 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1908.08312

Related papers

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

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

Quantum state exclusion through offset measurement

Caleb McIrvin, Ankith Mohan, Jamie Sikora

The quantum state discrimination problem has Alice sending a quantum state to Bob who wins if he correctly identifies the state. The pretty good measurement, also known as the square root measurement, performs pretty well at this task. We study the version of this problem where Bob tries to lose with the greatest probability possible (which is harder than it sounds). We define the pretty bad measurement, which performs pretty well at this task, or in other words, pretty poorly for the original task. We show that both the pretty good measurement and the pretty bad measurement are always no worse than blind guessing at their respective tasks. As an application, we apply the pretty bad measurement to the quantum state anomaly detection problem and show how to avoid pretty bad qubits.

arXiv:2403.17252•Physical Review A•Oct 10, 2024•5 citations

Bounds on unambiguous discrimination between quantum states

Lvjun Li

In this paper, we present a general upper bound on the success probability for unambiguous discrimination among arbitrary $m$ mixed quantum states with given a priori probability. We further analyze how this upper bound can be achievable by presenting a sufficient condition related to it, and we compare this upper bound with three other upper bounds. Moreover, for the issue of the unambiguous identification of $m$ unknown multicopy qudit pure states, we also get a bound.

Physical Review A•Sep 17, 2012•6 citations

Optimal unambiguous state discrimination of two density matrices: Lower bound and class of exact solutions

Philippe Raynal, Norbert Lütkenhaus

Recently the problem of unambiguous state discrimination of mixed quantum states has attracted much attention. So far, bounds on the optimum success probability have been derived [T. Rudolph, R. W. Spekkens, and P. S. Turner, Phys. Rev. A 68, 010301(R) (2003)]. For two mixed states they are given in terms of the fidelity. Here we give tighter bounds as well as necessary and sufficient conditions for two mixed states to reach these bounds. Moreover we construct the corresponding optimal measurement strategies. With this result, we provide analytical solutions for unambiguous discrimination of a class of generic mixed states. This goes beyond known results which are all reducible to some pure state case. Additionally, we show that examples exist where the bounds cannot be reached.

arXiv:quant-ph/0502165•Physical Review A•Aug 29, 2005•46 citations

Pretty good shadow tomography

Sabee Grewal, Angelos Pelecanos, Jack Spilecki +2 more

We give a shadow tomography algorithm that uses $O(\log(m) \log(m/δ) / \varepsilon^2)$ copies of the input state. Specifically, given a quantum state $ρ$ and observables $O_1,\ldots,O_m$, the algorithm outputs estimates of $\mathrm{tr}(O_iρ)$ for all $i\in[m]$ that are all accurate to within $\pm\varepsilon$, except with probability at most $δ$. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on $O(\log(m)/\varepsilon^2)$ copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining $\log(m)$ factor separating the complexity of the quantum problem from its classical counterpart.

quant-pharXiv:2610.06781•Oct 6, 2026•1 citation
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 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.
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.
The quantum state discrimination problem has Alice sending a quantum state to Bob who wins if he correctly identifies the state. The pretty good measurement, also known as the square root measurement, performs pretty well at this task. We study the version of this problem where Bob tries to lose with the greatest probability possible (which is harder than it sounds). We define the pretty bad measurement, which performs pretty well at this task, or in other words, pretty poorly for the original task. We show that both the pretty good measurement and the pretty bad measurement are always no worse than blind guessing at their respective tasks. As an application, we apply the pretty bad measurement to the quantum state anomaly detection problem and show how to avoid pretty bad qubits.
In this paper, we present a general upper bound on the success probability for unambiguous discrimination among arbitrary mmm mixed quantum states with given a priori probability. We further analyze how this upper bound can be achievable by presenting a sufficient condition related to it, and we compare this upper bound with three other upper bounds. Moreover, for the issue of the unambiguous identification of mmm unknown multicopy qudit pure states, we also get a bound.
Recently the problem of unambiguous state discrimination of mixed quantum states has attracted much attention. So far, bounds on the optimum success probability have been derived [T. Rudolph, R. W. Spekkens, and P. S. Turner, Phys. Rev. A 68, 010301(R) (2003)]. For two mixed states they are given in terms of the fidelity. Here we give tighter bounds as well as necessary and sufficient conditions for two mixed states to reach these bounds. Moreover we construct the corresponding optimal measurement strategies. With this result, we provide analytical solutions for unambiguous discrimination of a class of generic mixed states. This goes beyond known results which are all reducible to some pure state case. Additionally, we show that examples exist where the bounds cannot be reached.
We give a shadow tomography algorithm that uses O(log⁡(m)log⁡(m/δ)/ε2)O(\log(m) \log(m/δ) / \varepsilon^2)O(log(m)log(m/δ)/ε2) copies of the input state. Specifically, given a quantum state ρρρ and observables O1,…,OmO_1,\ldots,O_mO1​,…,Om​, the algorithm outputs estimates of tr(Oiρ)\mathrm{tr}(O_iρ)tr(Oi​ρ) for all i∈[m]i\in[m]i∈[m] that are all accurate to within ±ε\pm\varepsilon±ε, except with probability at most δδδ. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on O(log⁡(m)/ε2)O(\log(m)/\varepsilon^2)O(log(m)/ε2) copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining log⁡(m)\log(m)log(m) factor separating the complexity of the quantum problem from its classical counterpart.