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

Quantum Information and Computation

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

MooreCristopher, RussellAlexander

Published Nov 1, 2007• 0 citations
Publisher

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 Dn in the casewhere the hidden subgroup is chosen ...
DOI
10.5555/2011742.2011747

Related papers

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.

arXiv:quant-ph/0501177•Quantum Information and Computation•Nov 1, 2007•51 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

Optimal single-copy measurement for the hidden-subgroup problem

Dave Bacon, Thomas Decker

The optimization of measurements for the state distinction problem has recently been applied to the theory of quantum algorithms with considerable successes, including efficient alternative quantum algorithms for the non-Abelian hidden-subgroup problem. Previous work has identified the optimal single-copy measurement for the hidden-subgroup problem over Abelian groups as well as for the non-Abelian problem in the setting where the subgroups are restricted to be all conjugate to each other. Here we describe the optimal single-copy measurement for the hidden-subgroup problem when all of the subgroups of the group are given with equal a priori probability. The optimal measurement is seen to be a hybrid of the two previously discovered single-copy optimal measurements for the hidden-subgroup problem.

arXiv:0706.4478•Physical Review A•Mar 21, 2008•10 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

Pretty good state transfer on Cayley graphs over dihedral groups

Xiwang Cao, Dandan Wang, Keqin Feng

Discrete Mathematics•Aug 22, 2019•11 citations

Solving the Dihedral Hidden Subgroup Problem

Hachiro Fujita

IEICE Technical Report; IEICE Tech. Rep.•Sep 1, 2017•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.
The optimization of measurements for the state distinction problem has recently been applied to the theory of quantum algorithms with considerable successes, including efficient alternative quantum algorithms for the non-Abelian hidden-subgroup problem. Previous work has identified the optimal single-copy measurement for the hidden-subgroup problem over Abelian groups as well as for the non-Abelian problem in the setting where the subgroups are restricted to be all conjugate to each other. Here we describe the optimal single-copy measurement for the hidden-subgroup problem when all of the subgroups of the group are given with equal a priori probability. The optimal measurement is seen to be a hybrid of the two previously discovered single-copy optimal measurements for the hidden-subgroup problem.
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.