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:quant-ph/0501177 · Quantum Information and Computation

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

Cristopher Moore, Alexander C. Russell

Published Nov 1, 2007• 51 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic7.8-5

Related papers

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

MooreCristopher, RussellAlexander

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 casewhere the hidden subgroup is chosen ...

Quantum Information and Computation•Nov 1, 2007•0 citations

Optimal measurements for the dihedral hidden subgroup problem

Dave Bacon, Andrew M. Childs, Wim van Dam

We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states.We show that the optimal measurement for solving this problem is the so-called pretty good measurement.We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density ν = k/ log 2 N , where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group.In particular, for ν < 1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N , while for ν > 1 the optimal measurement identifies the hidden subgroup with a probability of order unity.Thus the dihedral group provides an example of a group G for which Ω(log |G|) hidden subgroup states are necessary to solve the hidden subgroup problem.We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold.Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems.In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.

arXiv:quant-ph/0501044•Chicago Journal of Theoretical Computer Science•Jan 1, 2006•55 citations

Quantum measurements for hidden subgroup problems with optimal sample complexity

Masahito Hayashi, A. Kawachi, H. Kobayashi

One of the central issues in the hidden subgroup problem is to bound the sample complexity, i.e., the number of identical samples of coset states sufficient and necessary to solve the problem. In this paper, we present general bounds for the sample complexity of the identification and decision versions of the hidden subgroup problem. As a consequence of the bounds, we show that the sample complexity for both of the decision and identification versions is $\Theta(\log|\HH|/\log p)$ for a candidate set $\HH$ of hidden subgroups in the case \REVISE{where the candidate nontrivial subgroups} have the same prime order $p$, which implies that the decision version is at least as hard as the identification version in this case. In particular, it does so for the important \REVISE{cases} such as the dihedral and the symmetric hidden subgroup problems. Moreover, the upper bound of the identification is attained \REVISE{by a variant of the pretty good measurement}. \REVISE{This implies that the concept of the pretty good measurement is quite useful for identification of hidden subgroups over an arbitrary group with optimal sample complexity}.

arXiv:quant-ph/0604174•Quantum Information and Computation•Mar 1, 2008•35 citations

Implementing measurements and optimizing queries for the quantum hidden subgroup problem

Asif Shakeel

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

•Jan 1, 2011•0 citations

From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups

Dave Bacon, Andrew M. Childs, Wim van Dam

We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form /spl Zopf//sub p/ /sup r/ /spl times/ /spl Zopf//sub p/ fixed r (including the Heisenberg group, r = 2). In particular our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.

arXiv:quant-ph/0504083•Annual Symposium on Foundations of Computer Science•Nov 15, 2005•124 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
Recently Bacon, Childs and van Dam showed that the ``pretty good measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral group DnD_nDn​ in the case where the hidden subgroup is chosen uniformly from the nnn involutions. We show that, for any group and any subgroup HHH, the PGM is the optimal one-register experiment in the case where the hidden subgroup is a uniformly random conjugate of HHH. We go on to show that when HHH 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 consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states.We show that the optimal measurement for solving this problem is the so-called pretty good measurement.We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density ν = k/ log 2 N , where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group.In particular, for ν < 1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N , while for ν > 1 the optimal measurement identifies the hidden subgroup with a probability of order unity.Thus the dihedral group provides an example of a group G for which Ω(log |G|) hidden subgroup states are necessary to solve the hidden subgroup problem.We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold.Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems.In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.
One of the central issues in the hidden subgroup problem is to bound the sample complexity, i.e., the number of identical samples of coset states sufficient and necessary to solve the problem. In this paper, we present general bounds for the sample complexity of the identification and decision versions of the hidden subgroup problem. As a consequence of the bounds, we show that the sample complexity for both of the decision and identification versions is $\Theta(\log|\HH|/\log p)$ for a candidate set $\HH$ of hidden subgroups in the case \REVISE{where the candidate nontrivial subgroups} have the same prime order ppp, which implies that the decision version is at least as hard as the identification version in this case. In particular, it does so for the important \REVISE{cases} such as the dihedral and the symmetric hidden subgroup problems. Moreover, the upper bound of the identification is attained \REVISE{by a variant of the pretty good measurement}. \REVISE{This implies that the concept of the pretty good measurement is quite useful for identification of hidden subgroups over an arbitrary group with optimal sample complexity}.
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
We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form /spl Zopf//sub p/ /sup r/ /spl times/ /spl Zopf//sub p/ fixed r (including the Heisenberg group, r = 2). In particular our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.
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).