(2006):

ABSTRACT:
Høyer has given a generalisation of the Deutsch-Jozsa algorithm
which uses the Fourier transform on a group *G* which is (in general)
non-Abelian. His algorithm distinguishes between functions which are
either perfectly balanced (*m*-to-one) or constant, with certainty,
and using a single quantum query. Here, we show that this algorithm (which
we call the Deutsch-Jozsa-Høyer algorithm) can in fact deal with a
broader range of promises, which we define in terms of the irreducible
representations of *G*.