  We study the hardness of the dihedral hidden subgroup problem. It is known
that lattice problems reduce to it, and that it reduces to random subset sum
with density $> 1$ and also to quantum sampling subset sum solutions. We
examine a decision version of the problem where the question asks whether the
hidden subgroup is trivial or order two. The decision problem essentially asks
if a given vector is in the span of all coset states. We approach this by first
computing an explicit basis for the coset space and the perpendicular space. We
then look at the consequences of having efficient unitaries that use this
basis. We show that if a unitary maps the basis to the standard basis in any
way, then that unitary can be used to solve random subset sum with constant
density $>1$. We also show that if a unitary can exactly decide membership in
the coset subspace, then the collision problem for subset sum can be solved for
density $>1$ but approaching $1$ as the problem size increases. This
strengthens the previous hardness result that implementing the optimal POVM in
a specific way is as hard as quantum sampling subset sum solutions.
