<p>Not sure if this is directly linked to your question, but reading it made me think about an article by Peter Høyer I read some years ago. In it, he shows how the most popular quantum algorithms like Grover's or Shor's follow the same pattern of applying what he calls "conjugated operators" and he builds new algorithms also based on that same pattern. </p>

<p>As I said, it's been a few years since I've read it so my description is a bit sloppy, but here's the link in case you want to check it out. </p>

<p><a href="http://journals.aps.org/pra/abstract/10.1103/PhysRevA.59.3280" rel="nofollow">http://journals.aps.org/pra/abstract/10.1103/PhysRevA.59.3280</a></p>

CC BY-SA 3.0
2014-07-09T19:05:21.020Z
2014-07-09T19:05:21.020Z
lamontap
<p>I would like to add some more references to Scott's comment:</p>

<p>Indeed, <strong>Clebsch-Gordan transforms</strong> (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). </p>

<ul>
<li><p>Clebsch-Gordan transforms were used by <a href="http://arxiv.org/abs/quant-ph/0302112" rel="nofollow">Greg Kuperberg</a> and <a href="http://arxiv.org/abs/quant-ph/0406151" rel="nofollow">Oded Regev</a> 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.</p></li>
<li><p><a href="http://arxiv.org/abs/quant-ph/0612107" rel="nofollow">Dave Bacon</a> 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.</p></li>
</ul>

<p>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.</p>

<ul>
<li><p>In Shor's algorithm (or even in quantum phase estimation) the Fourier transforms can be replaced with <strong>Hadamard tests</strong>, therefore only using Hadamard gates instead of Fourier transforms: this trick is due to Kitaev and you can read about it <a href="http://arxiv.org/abs/1012.4727" rel="nofollow">here</a>. </p></li>
<li><p>There is yet another <a href="http://arxiv.org/abs/quant-ph/0504083" rel="nofollow">efficient algorithm</a> 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.</p></li>
</ul>

<p>Of course, this list is probably  incomplete. I hope someone will point out other results that have not yet been mentioned.</p>

CC BY-SA 3.0
2014-07-08T04:45:04.243Z
HSP = [hidden subgroup problem](http://en.m.wikipedia.org/wiki/Hidden_subgroup_problem)
vzn
CC BY-SA 3.0
2015-09-03T08:20:31.537Z
Thanks for pointing that out. I explained the acronym in the last edit.
Juan Bermejo Vega
CC BY-SA 3.0
2014-07-07T19:23:03.990Z
2015-09-04T19:17:34.167Z
2015-09-04T19:17:34.167Z
Juan Bermejo Vega
<p>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.</p>

<p>Has there been any fruitful research on other transforms?</p>

CC BY-SA 3.0
2014-07-07T14:58:05.133Z
Yes.  Yi-Kai Liu, Shelby Kimmel, and others have developed quantum algorithms based on wavelet transforms, and Stephen Jordan has developed quantum algorithms based on the Clebsch-Gordan transform.  You can google for references, or others might come along to provide some.  Of course, the problems solved by these algorithms aren't as high-profile as factoring and discrete log (otherwise you would've heard about it already).
Scott Aaronson
CC BY-SA 3.0
2014-07-07T15:15:02.413Z
@ScottAaronson comment-->answer
Alessandro Cosentino
CC BY-SA 3.0
2014-07-07T16:05:36.620Z
@ScottAaronson Great, I will look into them. Thanks!
Sam Burville
CC BY-SA 3.0
2014-07-08T04:42:16.167Z
[Hamiltonian oracles?](http://cs.stackexchange.com/questions/28234/quantum-computing-relationship-between-hamiltonian-and-unitary-model)
vzn
CC BY-SA 3.0
2015-09-03T11:11:07.920Z
Yi-Kai Liu has developed quantum algorithms using the _curvelet transform_ (see the [full version](http://arxiv.org/abs/0810.4968) on arXiv or the [short version](https://dl.acm.org/citation.cfm?id=1536469) from FOCS).
Māris Ozols
<quantum-computing><quantum-information>
Quantum algorithms based on transforms other than Fourier transforms
Sam Burville
# Quantum algorithms based on transforms other than Fourier transforms

(Asked by: username_0 on 2014-07-07)

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?

**Tags:** quantum-computing, quantum-information
> **Comments:**
> **username_1**: Yes.  Yi-Kai Liu, Shelby Kimmel, and others have developed quantum algorithms based on wavelet transforms, and Stephen Jordan has developed quantum algorithms based on the Clebsch-Gordan transform.  You can google for references, or others might come along to provide some.  Of course, the problems solved by these algorithms aren't as high-profile as factoring and discrete log (otherwise you would've heard about it already).  
> **username_2**: @ScottAaronson comment-->answer  
> **username_0**: @ScottAaronson Great, I will look into them. Thanks!  
> **username_3**: [Hamiltonian oracles?](http://cs.stackexchange.com/questions/28234/quantum-computing-relationship-between-hamiltonian-and-unitary-model)  
> **username_4**: Yi-Kai Liu has developed quantum algorithms using the _curvelet transform_ (see the [full version](http://arxiv.org/abs/0810.4968) on arXiv or the [short version](https://dl.acm.org/citation.cfm?id=1536469) from FOCS).  

---

## 2 answers

### Answer by username_6 on 2014-07-07. Score: 16 | Accepted answer

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](http://arxiv.org/abs/quant-ph/0302112) and [Oded Regev](http://arxiv.org/abs/quant-ph/0406151) 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](http://arxiv.org/abs/quant-ph/0612107) 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](http://arxiv.org/abs/1012.4727).
* There is yet another [efficient algorithm](http://arxiv.org/abs/quant-ph/0504083) 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.

> **Comments:**
> **username_3**: HSP = [hidden subgroup problem](http://en.m.wikipedia.org/wiki/Hidden_subgroup_problem)  
> **username_6**: Thanks for pointing that out. I explained the acronym in the last edit.  

---

### Answer by username_5 on 2014-07-09. Score: 4

Not sure if this is directly linked to your question, but reading it made me think about an article by Peter Høyer I read some years ago. In it, he shows how the most popular quantum algorithms like Grover's or Shor's follow the same pattern of applying what he calls "conjugated operators" and he builds new algorithms also based on that same pattern.

As I said, it's been a few years since I've read it so my description is a bit sloppy, but here's the link in case you want to check it out.

<http://journals.aps.org/pra/abstract/10.1103/PhysRevA.59.3280>


---

