In Quantum Computation and Quantum Information by Nielsen and Chuang they say that many of the algorithms based on quantum Fourier transforms rely on the Coset Invariance property of Fourier transforms and suggests that invariance properties of other transforms might yield new algorithms.Has there been any fruitful research on other transforms?
Quantum algorithms based on transforms other than Fourier transforms
quantum computing;quantum information
I would like to add some more references to Scott's comment:Indeed, Clebsch-Gordan transforms (that you can think of as multi-register quantum Fourier transforms) are a useful tool in the design of quantum algorithms for non-Abelian hidden subgroup problems (HSPs). Clebsch-Gordan transforms were used by Greg Kuperberg and Oded Regev to solve the dihedral HSP in subexponential (yet superpolynomial) time. These quantum algorithms are not efficient, but they have better query complexity than classical algorithms.Dave Bacon also used Clebsch-Gordan transforms to solve the hidden subgroup problem (HSP) over the Heisenberg group  $\mathbb{Z}_p^2\rtimes \mathbb{Z}_p$ in polynomial time. I can recommend that paper because it is quite clear.I am also writing to add that we should not forget that both quantum Fourier transforms and Clebsch-Gordan transforms are not always indispensable, even if they can be very useful.In Shor's algorithm (or even in quantum phase estimation) the Fourier transforms can be replaced with Hadamard tests, therefore only using Hadamard gates instead of Fourier transforms: this trick is due to Kitaev and you can read about it here. There is yet another efficient algorithm for the HSP over $\mathbb{Z}_p^2\rtimes \mathbb{Z}_p$, by Bacon, Childs, Van Dam, that does not use Clebsch-Gordan transforms. Instead, the algorithm uses a certain type of powerful POVM known as the Pretty Good Measurement.Of course, this list is probably  incomplete. I hope someone will point out other results that have not yet been mentioned.