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• 4 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

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•2 citations

Attainability of quantum state discrimination bounds with collective measurements on finite copies

Lorcán O. Conlon, Jin Ming Koh, Biveen Shajilal +3 more

One of the fundamental tenets of quantum mechanics is that nonorthogonal states cannot be distinguished perfectly. When distinguishing multiple copies of a mixed quantum state, a collective measurement, which generates entanglement between the different copies of the unknown state, can achieve a lower error probability than nonentangling measurements. The error probability that can be attained using a collective measurement on a finite number of copies of the unknown state is given by the Helstrom bound. In the limit where we can perform a collective measurement on asymptotically many copies of the quantum state, the quantum Chernoff bound gives the attainable error probability. It is natural to ask, then, what strategies can be employed to reach these two bounds---is entanglement across all available modes always necessary or can other, experimentally more simple measurements saturate these bounds? In this work we address this question. We find analytic expressions for the Helstrom bound for arbitrarily many copies of the unknown state in simple qubit examples. Using these analytic expressions, we investigate whether the quantum Chernoff bound can be saturated by repeatedly implementing the $M$-copy Helstrom measurement. We also investigate the necessary conditions to saturate the $M$-copy Helstrom bound. It is known that a collective measurement on all $M$ copies of the unknown state is always sufficient to saturate the $M$-copy Helstrom bound. However, general conditions for when such a measurement is necessary to saturate the Helstrom bound remain unknown. We investigate specific measurement strategies which involve entangling operations on fewer than all $M$ copies of the unknown state. For many regimes we find that a collective measurement on all $M$ copies of the unknown state is necessary to saturate the $M$-copy Helstrom bound.

arXiv:2408.06678•Physical Review A•Feb 21, 2025•2 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•0 citations

Quantum Inspired Classification Algorithms

Zambrini Cruzeiro, Emmanuel, De Mol, Christine, Massar, Serge +1 more

We present algorithms for supervised classification tasks in machine learning that are inspired by quantum mechanics. They rely on the so-called problem of quantum state discrimination, which consists in identifying which one of a known set of quantum states has been prepared based on the outcome of a quantum measurement on the state. After building the quantum states associated with the training data, which are encoded as density matrices, we explore various quantum measurement strategies suited for the classification task, including those based on semi-definite programming and on the so-called Pretty GoodMeasurement.We also consider how the measurement performs on multiple copies of the quantum state, since this in principle improves quantum state discrimination at the price of a higher computational cost. For the Pretty Good Measurement classifier, an analogue of the well-known Kernel Trick in learning theory can be devised, so that the cost scales only with the number of examples in the training dataset. This allows to study the performance of this classifier on tensor products of the quantum state. Finally, thedifferent classifiers are benchmarked on the MNIST and MNIST-1D datasets.

•Jan 1, 2025•0 citations

On the distinguishability of geometrically uniform quantum states

Juntai Zhou, Stefano Chessa, Eric Chitambar +1 more

Abstract A geometrically uniform (GU) ensemble is a uniformly weighted quantum state ensemble generated from a fixed state by a unitary representation of a finite group G. In this work we analyze the problem of discriminating GU ensembles from various angles. Assuming that the representation of G is irreducible, we first show that a particular optimal measurement can be understood as the limit of weighted ‘pretty good measurements’ (PGMs). This naturally provides examples of state discrimination for which the unweighted PGM is provably sub-optimal. We extend this analysis to certain reducible representations, and use Schur–Weyl duality to discuss two particular examples of GU ensembles in terms of Werner-type and permutation-invariant generator states. For the case of pure-state GU ensembles we give a streamlined proof of optimality of the PGM first proved in Eldar et al (2004 IEEE Trans. Inf. Theory 50 1198–207). We use this result to give simplified proofs of the optimality of the PGM, along with expressions for the corresponding success probabilities, for two tasks: the hidden subgroup problem (HSP) over semidirect product groups (first proved in Bacon et al (2005 46th Annual IEEE Symp. Foundations of Computer Science (FOCS’05) pp 469–78), and port-based teleportation (first proved in Mozrzymas et al (2019 New J. Phys. 20 053006) and Leditzky (2022 Lett. Math. Phys. 112 98). Finally, we consider the n-copy setting and adapt a result of Montanaro (2007 Commun. Math. Phys. 273 619–36) to derive a compact and easily evaluated lower bound on the success probability of the PGM for this task. This result can be applied to the HSP to obtain a new proof for an upper bound on the sample complexity by Hayashi et al (2006 Quantum Inf. Comput. 8 345–58).

arXiv:2501.12376•Journal of Physics A Mathematical and Theoretical•Sep 23, 2025•0 citations
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.
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.
One of the fundamental tenets of quantum mechanics is that nonorthogonal states cannot be distinguished perfectly. When distinguishing multiple copies of a mixed quantum state, a collective measurement, which generates entanglement between the different copies of the unknown state, can achieve a lower error probability than nonentangling measurements. The error probability that can be attained using a collective measurement on a finite number of copies of the unknown state is given by the Helstrom bound. In the limit where we can perform a collective measurement on asymptotically many copies of the quantum state, the quantum Chernoff bound gives the attainable error probability. It is natural to ask, then, what strategies can be employed to reach these two bounds---is entanglement across all available modes always necessary or can other, experimentally more simple measurements saturate these bounds? In this work we address this question. We find analytic expressions for the Helstrom bound for arbitrarily many copies of the unknown state in simple qubit examples. Using these analytic expressions, we investigate whether the quantum Chernoff bound can be saturated by repeatedly implementing the MMM-copy Helstrom measurement. We also investigate the necessary conditions to saturate the MMM-copy Helstrom bound. It is known that a collective measurement on all MMM copies of the unknown state is always sufficient to saturate the MMM-copy Helstrom bound. However, general conditions for when such a measurement is necessary to saturate the Helstrom bound remain unknown. We investigate specific measurement strategies which involve entangling operations on fewer than all MMM copies of the unknown state. For many regimes we find that a collective measurement on all MMM copies of the unknown state is necessary to saturate the MMM-copy Helstrom bound.
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.
We present algorithms for supervised classification tasks in machine learning that are inspired by quantum mechanics. They rely on the so-called problem of quantum state discrimination, which consists in identifying which one of a known set of quantum states has been prepared based on the outcome of a quantum measurement on the state. After building the quantum states associated with the training data, which are encoded as density matrices, we explore various quantum measurement strategies suited for the classification task, including those based on semi-definite programming and on the so-called Pretty GoodMeasurement.We also consider how the measurement performs on multiple copies of the quantum state, since this in principle improves quantum state discrimination at the price of a higher computational cost. For the Pretty Good Measurement classifier, an analogue of the well-known Kernel Trick in learning theory can be devised, so that the cost scales only with the number of examples in the training dataset. This allows to study the performance of this classifier on tensor products of the quantum state. Finally, thedifferent classifiers are benchmarked on the MNIST and MNIST-1D datasets.
Abstract A geometrically uniform (GU) ensemble is a uniformly weighted quantum state ensemble generated from a fixed state by a unitary representation of a finite group G. In this work we analyze the problem of discriminating GU ensembles from various angles. Assuming that the representation of G is irreducible, we first show that a particular optimal measurement can be understood as the limit of weighted ‘pretty good measurements’ (PGMs). This naturally provides examples of state discrimination for which the unweighted PGM is provably sub-optimal. We extend this analysis to certain reducible representations, and use Schur–Weyl duality to discuss two particular examples of GU ensembles in terms of Werner-type and permutation-invariant generator states. For the case of pure-state GU ensembles we give a streamlined proof of optimality of the PGM first proved in Eldar et al (2004 IEEE Trans. Inf. Theory 50 1198–207). We use this result to give simplified proofs of the optimality of the PGM, along with expressions for the corresponding success probabilities, for two tasks: the hidden subgroup problem (HSP) over semidirect product groups (first proved in Bacon et al (2005 46th Annual IEEE Symp. Foundations of Computer Science (FOCS’05) pp 469–78), and port-based teleportation (first proved in Mozrzymas et al (2019 New J. Phys. 20 053006) and Leditzky (2022 Lett. Math. Phys. 112 98). Finally, we consider the n-copy setting and adapt a result of Montanaro (2007 Commun. Math. Phys. 273 619–36) to derive a compact and easily evaluated lower bound on the success probability of the PGM for this task. This result can be applied to the HSP to obtain a new proof for an upper bound on the sample complexity by Hayashi et al (2006 Quantum Inf. Comput. 8 345–58).