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).
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).
The minimum probability of error (MPE) measurement discriminates between a set of candidate quantum states with the minimum average error probability allowed by quantum mechanics. Conditions for a measurement to be MPE were derived by Yuen, Kennedy, and Lax [H. P. Yuen et al., IEEE Trans. Info. Theory IT-21, 125134 (1975)]. MPE measurements have been found for states that form a single orbit under a group action, i.e., there is a transitive group action on the states in the set. For such state sets, termed geometrically uniform (GU) previously, it was shown that the ``pretty good measurement'' attains the MPE. Even so, evaluating the actual probability of error (and other performance metrics) attained by the pretty good measurement on a GU set involves inverting large matrices and is not easy in general. Our first contribution is a formula for the MPE and conditional probabilities of GU sets, using group representation theory. Next, we consider sets of pure states that have multiple orbits under the group action. Such states are termed compound geometrically uniform (CGU). MPE measurements for general CGU sets are not known. In this paper, we show how our representation-theoretic description of optimal measurements for GU sets naturally generalizes to the CGU case. We show how to compute the MPE measurement for CGU sets by reducing the problem to solving a few simultaneous equations. The number of equations depends on the sizes of the multiplicity space of irreducible representations. For many common group representations (such as those of several practical good linear codes), this is much more tractable than solving large semidefinite programs---which is what is needed to solve the Yuen-Kennedy-Lax conditions numerically for arbitrary state sets. We show how to evaluate MPE measurements for CGU states in some examples relevant to quantum-limited classical optical communication.
Minimum probability of error (MPE) measurements are quantum mechanical measurements that discriminate between a set of candidate states and achieve the minimum error allowed by quantum mechanics. Conditions for a measurement to be an MPE measurement have been derived by Yuen, Kennedy and Lax. But finding explicit measurements that satisfy these conditions is a hard problem in general and even in cases where an explicit measurement is known, calculating the MPE of the measurement is not easy. In some cases, MPE measurements have been found such as when the states form a single orbit under a group action i.e., there is a transitive group action on the states. For such state sets, termed Geometrically Uniform (GU) in [1], it was shown that the `pretty good measurement' (PGM) is optimal. However, calculating the MPE and other performance metrics for the PGM involves inverting large matrices, and it is therefore not easy in general to evaluate. Our first contribution is a formula for the MPE and conditional probabilities of GU sets using group representation theory. Next, we consider sets of pure states that have multiple orbits under the group action. Such states are termed compound geometrically uniform (CGU). CGU sets appear in many practical problems in quantum communication and imaging. For example, they include all linear codes formed using pure-state modulation constellations, which are known to achieve the ultimate (Holevo) capacity of optical communication. Optimal (MPE) measurement for general CGU sets are not known. In this paper, we show how our representation-theoretic description of optimal measurements for GU sets naturally generalizes to the CGU case. We show how to compute the optimal measurement for CGU sets by reducing the problem to solving a few simultaneous equations. The number of equations depends on the sizes of the multiplicity space of irreducible representations. For many group representations (such as those of several practical good linear codes), this is much more tractable than solving large semi-definite programs-which is what is needed to solve for MPE measurements for an arbitrary set of pure states using the Yuen-Kennedy-Lax conditions [2]. We show examples of the evaluation of optimal measurements for CGU states.
This dissertation concerns the Hidden Subgroup Problem (HSP) in quantum computation. We explore certain facets of the problem which, we expect, will lead towards a general framework for understanding such problems. We first present an implementation of an optimal measurement, the Pretty Good Measurement (PGM), for the problem of the hidden subgroup problem over the dihedral group. This is a problem for which no efficient algorithm is known. This problem is relevant to the shortest vector in a lattice problem (SVP) in cryptography. We give a representation theoretic implementation of the PGM, achievable with only abelian transforms. The subset sum problem, an NP-complete problem, is needed in identification of certain subspaces. There are some novel ideas and techniques used in the implementation that make it realizable. This brings into focus how a measurement specified through a POVM (positive operator valued measure) is achievable through a basis change in a particular representation. This has connections to the HSP for other groups. We also study the question of optimal query selection to maximize the probability of subgroup identification. This part of the research complements a well-researched topic of finding optimal measurements in the spirit of state discrimination as applied to the hidden subgroup problem. We find the optimal query, the "character query", over a class of queries that are an equal superposition over the group, for oracles that take values in a finite abelian group. This query outperforms the query used in the "standard method" of the HSP. This approach has connections to other domains of quantum computation. We then extend the query selection idea to the case of multiple queries in the HSP and find examples in which this gives significant gains over the standard method. We consider the problems that the analysis of this more general problem entails, and outline a possible program to be followed. This is a part of continuing research
Recently Bacon, Childs and van Dam showed that the ``pretty good measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral group Dn 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.
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≥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-divergence. Our analysis also yields a refined, one-shot pairwise Chernoff bound and explicit sufficient number of copies for a desired discrimination error.