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 nu=k/log 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 nu<1 the optimal measurement (and hence any measurement) identifies the

hidden subgroup with a probability that is exponentially small in log N, while

for nu>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 Omega(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.