Extending the promise of the Deutsch–Jozsa–Hřyer algorithm for finite groups
Michael Batty, Andrew J. Duncan and Samuel L. Braunstein
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. The authors of this paper show that this algorithm
(which they call the Deutsch–Jozsa–Høyer algorithm) can in
fact deal with a broader range of promises, which they define in
terms of the irreducible representations of G.
|
