Journal of Modern Optics

A ‘Pretty Good’ Measurement for Distinguishing Quantum States

Paul A. Hausladen, William K. Wootters

Published Dec 1, 1994• 324 citations

Abstract

We address the problem of extracting information from a single quantum system whose state is known to be in one of several possible states. In the generic case, it is notoriously difficult to find the optimal measurement, that is the measurement that provides the most possible information about the system's state. We consider a simple general prescription for a measurement that is typically not optimal but appears to be quite good. It seems to be particularly good when the states to be distinguished are equally likely and almost orthogonal.

DOI: 10.1080/09500349414552221

Related papers

Pretty simple bounds on quantum state discrimination

Ashley Montanaro

arXiv:1908.08312Aug 22, 20194 citations

Distinguishing sets of quantum states

Rahul Jain

Given two sets finite $S_0$ and $S_1$ of quantum states. We show necessary and sufficient conditions for distinguishing them by a measurement.

arXiv:quant-ph/0506205Jun 24, 20054 citations

From Quantum Decoding to Sharp Subset Bounds: A Use Case for Extracted Mathematical Instruments

Ying Xie

Oct 17, 20260 citations

Optimal distinction between non-orthogonal quantum states

Asher Peres, Daniel R Terno

Given a finite set of linearly independent quantum states, an observer who examines a single quantum system may sometimes identify its state with certainty. However, unless these quantum states are orthogonal, there is a finite probability of failure. A complete solution is given to the problem of optimal distinction of three states, having arbitrary prior probabilities and arbitrary detection values. A generalization to more than three states is outlined.

arXiv:quant-ph/9804031Journal of Physics A Mathematical and GeneralAug 28, 1998116 citations

Local strategies are pretty good at computing Boolean properties of quantum sequences

Tathagata Gupta, Ankith Mohan, Shayeef Murshid +3 more

quant-pharXiv:2603.05452Mar 6, 20260 citations

For distinguishing conjugate Hidden subgroups, the pretty good measurement is as good as it gets

Cristopher Moore, Alexander C. Russell

arXiv:quant-ph/0501177Quantum Information and ComputationNov 1, 200751 citations

Journal of Modern Optics

A ‘Pretty Good’ Measurement for Distinguishing Quantum States

Paul A. Hausladen, William K. Wootters

Published Dec 1, 1994• 324 citations

Publisher

Abstract

DOI: 10.1080/09500349414552221

Related papers

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.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.08312Aug 22, 20194 citations

Distinguishing sets of quantum states

Rahul Jain

Given two sets finite $S_0$ and $S_1$ of quantum states. We show necessary and sufficient conditions for distinguishing them by a measurement.Given two sets finite $S_0$ and $S_1$ of quantum states. We show necessary and sufficient conditions for distinguishing them by a measurement.

arXiv:quant-ph/0506205Jun 24, 20054 citations

From Quantum Decoding to Sharp Subset Bounds: A Use Case for Extracted Mathematical Instruments

Ying Xie

Quantum communication requires a receiver to distinguish several, generally mixed, signal states. A useful theoretical question is whether errors on smaller signal alphabets can certify the error of a decoder for the full alphabet. We study this question for the pretty good measurement and present it as a use case for the programme of extracting reusable mathematical instruments from a large collection of research manuscripts. A constrained spectral optimization mechanism identified in that collection leads to the sharp pairwise coefficient (1 + sqrt(1 - 2/N))^2 for all equally likely pure ensembles. A separate matrix analysis proves the sharp coefficient (1 + sqrt(1 - k/N))^2 for every subset size when the average state is maximally mixed on its support, allowing arbitrary mixed signals. For general mixed ensembles, the sharp leave-one coefficient (1 + 1/sqrt(N))^2 holds whenever the normalized full error is at least 1/N; consequently it holds for all equally likely ensembles in dimension at most N - 1. We give a noisy qutrit decoding example, an unrestricted bound for nearly full subsets, and an exact polynomial certificate for a further four-signal family. The account separates the extracted mechanisms, their classical antecedents, and the additional arguments needed for the quantum problem. These results provide conditional error certificates, while the unrestricted sharp mixed-state subset problem and improvements to operational communication rates remain open.Quantum communication requires a receiver to distinguish several, generally mixed, signal states. A useful theoretical question is whether errors on smaller signal alphabets can certify the error of a decoder for the full alphabet. We study this question for the pretty good measurement and present it as a use case for the programme of extracting reusable mathematical instruments from a large collection of research manuscripts. A constrained spectral optimization mechanism identified in that collection leads to the sharp pairwise coefficient (1 + sqrt(1 - 2/N))^2 for all equally likely pure ensembles. A separate matrix analysis proves the sharp coefficient (1 + sqrt(1 - k/N))^2 for every subset size when the average state is maximally mixed on its support, allowing arbitrary mixed signals. For general mixed ensembles, the sharp leave-one coefficient (1 + 1/sqrt(N))^2 holds whenever the normalized full error is at least 1/N; consequently it holds for all equally likely ensembles in dimension at most N - 1. We give a noisy qutrit decoding example, an unrestricted bound for nearly full subsets, and an exact polynomial certificate for a further four-signal family. The account separates the extracted mechanisms, their classical antecedents, and the additional arguments needed for the quantum problem. These results provide conditional error certificates, while the unrestricted sharp mixed-state subset problem and improvements to operational communication rates remain open.

Oct 17, 20260 citations

Optimal distinction between non-orthogonal quantum states

Asher Peres, Daniel R Terno

arXiv:quant-ph/9804031Journal of Physics A Mathematical and GeneralAug 28, 1998116 citations

Local strategies are pretty good at computing Boolean properties of quantum sequences

Tathagata Gupta, Ankith Mohan, Shayeef Murshid +3 more

Quantum memory is a scarce and costly resource, yet little is known about which learning tasks remain feasible under severe memory constraints. We study the problem of computing global properties of quantum sequences when quantum systems must be measured individually, without storing or jointly processing them. In our setting, a bit string $x \in \{0,1\}^n$ is encoded into an $n$ -qubit product state $|ψ_{x_1}\rangle \otimes \cdots \otimes |ψ_{x_n}\rangle$ , and the goal is to infer $f(x) \in \{0,1\}$ from measurements of this quantum encoding. We consider a simple local strategy, which we call the greedy strategy, that applies the same optimal single-system measurement independently to each subsystem and then infers $f(x)$ from the outcomes. Our main result gives a complete characterization of when the greedy strategy is optimal: it achieves the same maximum success probability as an unrestricted global measurement if and only if the target Boolean function is affine (in all but finitely many cases). We establish a universal performance guarantee for general Boolean functions, showing that the success probability of the greedy strategy is always at least the square of the optimal global success probability, in direct analogy with the Barnum-Knill bound for the pretty good measurement. These results demonstrate that even under extreme memory constraints, simple local measurement strategies can remain provably competitive for learning global properties of quantum sequences.Quantum memory is a scarce and costly resource, yet little is known about which learning tasks remain feasible under severe memory constraints. We study the problem of computing global properties of quantum sequences when quantum systems must be measured individually, without storing or jointly processing them. In our setting, a bit string $x \in \{0,1\}^n$ is encoded into an $n$-qubit product state $|ψ_{x_1}\rangle \otimes \cdots \otimes |ψ_{x_n}\rangle$, and the goal is to infer $f(x) \in \{0,1\}$ from measurements of this quantum encoding. We consider a simple local strategy, which we call the greedy strategy, that applies the same optimal single-system measurement independently to each subsystem and then infers $f(x)$ from the outcomes. Our main result gives a complete characterization of when the greedy strategy is optimal: it achieves the same maximum success probability as an unrestricted global measurement if and only if the target Boolean function is affine (in all but finitely many cases). We establish a universal performance guarantee for general Boolean functions, showing that the success probability of the greedy strategy is always at least the square of the optimal global success probability, in direct analogy with the Barnum-Knill bound for the pretty good measurement. These results demonstrate that even under extreme memory constraints, simple local measurement strategies can remain provably competitive for learning global properties of quantum sequences.

quant-pharXiv:2603.05452Mar 6, 20260 citations

For distinguishing conjugate Hidden subgroups, the pretty good measurement is as good as it gets

Cristopher Moore, Alexander C. Russell

Recently Bacon, Childs and van Dam showed that the ``pretty good measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral group $D_n$ in the case where the hidden subgroup is chosen uniformly from the $n$ involutions. We show that, for any group and any subgroup $H$ , the PGM is the optimal one-register experiment in the case where the hidden subgroup is a uniformly random conjugate of $H$ . We go on to show that when $H$ forms a Gel'fand pair with its parent group, the PGM is the optimal measurement for any number of registers. In both cases we bound the probability that the optimal measurement succeeds. This generalizes the case of the dihedral group, and includes a number of other examples of interest.Recently Bacon, Childs and van Dam showed that the ``pretty good measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral group $D_n$ in the case where the hidden subgroup is chosen uniformly from the $n$ involutions. We show that, for any group and any subgroup $H$, the PGM is the optimal one-register experiment in the case where the hidden subgroup is a uniformly random conjugate of $H$. We go on to show that when $H$ forms a Gel'fand pair with its parent group, the PGM is the optimal measurement for any number of registers. In both cases we bound the probability that the optimal measurement succeeds. This generalizes the case of the dihedral group, and includes a number of other examples of interest.

arXiv:quant-ph/0501177Quantum Information and ComputationNov 1, 200751 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

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.

Given two sets finite

S_0

and

S_1

of quantum states. We show necessary and sufficient conditions for distinguishing them by a measurement.

x \in \{0,1\}^n

is encoded into an

n

-qubit product state

|ψ_{x_1}\rangle \otimes \cdots \otimes |ψ_{x_n}\rangle

, and the goal is to infer

f(x) \in \{0,1\}

from measurements of this quantum encoding. We consider a simple local strategy, which we call the greedy strategy, that applies the same optimal single-system measurement independently to each subsystem and then infers

f(x)

from the outcomes. Our main result gives a complete characterization of when the greedy strategy is optimal: it achieves the same maximum success probability as an unrestricted global measurement if and only if the target Boolean function is affine (in all but finitely many cases). We establish a universal performance guarantee for general Boolean functions, showing that the success probability of the greedy strategy is always at least the square of the optimal global success probability, in direct analogy with the Barnum-Knill bound for the pretty good measurement. These results demonstrate that even under extreme memory constraints, simple local measurement strategies can remain provably competitive for learning global properties of quantum sequences.

Recently Bacon, Childs and van Dam showed that the ``pretty good measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral group

D_n

in the case where the hidden subgroup is chosen uniformly from the

n

involutions. We show that, for any group and any subgroup

H

, the PGM is the optimal one-register experiment in the case where the hidden subgroup is a uniformly random conjugate of

H

. We go on to show that when

H

forms a Gel'fand pair with its parent group, the PGM is the optimal measurement for any number of registers. In both cases we bound the probability that the optimal measurement succeeds. This generalizes the case of the dihedral group, and includes a number of other examples of interest.