> < ^ Date: Mon, 17 Jul 2000 05:19:26 -0700
> ^ From: Igor Markov <imarkov@cs.ucla.edu >
> ^ Subject: Fourier transform on groups

A quick question: suppose I have a function defined on a group.
What's the fastest way to compute its Fourier transform?
(I looked at the manual, but did not find "Fourier").
A similar question for the inverse Fourier transform.

For small groups, an explicit computation would suffice
(but since I have just installed GAP and haven't written
any programs in it, I would really appreciate if someone
could mail me those several lines as a syntax example ;-).

I also heard of some research, e.g., by Minkwitz on computing
Fourier transform for arbitray [solvable?] groups faster than
by evaluating the definition.

A related question --- what's the easiest way to construct an
indicator function for a given subgroup?

As you may guess, I am looking into quantum algorithms for the
hidden subgroup problem.. and Fourier transforms of subgroup
indicator functions can be evaluated by an efficient shortcut,
but I'd also like to do it generically... and for arbitrary functions.


P.S. Edmund and Steve, thanks for your replies to my question
about boolean functions. I will let you know if I have time
to work on such an implementation, but that would hardly happen
before October ;-( Sorry.
Igor Markov office: (310) 206-0179

Miles-Receive-Header: reply

> < [top]