19
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 10
    $\begingroup$ 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). $\endgroup$
    – Scott Aaronson
    Commented Jul 7, 2014 at 14:58
  • 5
    $\begingroup$ @ScottAaronson comment-->answer $\endgroup$
    – Alessandro Cosentino
    Commented Jul 7, 2014 at 15:15
  • $\begingroup$ @ScottAaronson Great, I will look into them. Thanks! $\endgroup$
    – Sam Burville
    Commented Jul 7, 2014 at 16:05
  • $\begingroup$ Hamiltonian oracles? $\endgroup$
    – vzn
    Commented Jul 8, 2014 at 4:42
  • $\begingroup$ Yi-Kai Liu has developed quantum algorithms using the curvelet transform (see the full version on arXiv or the short version from FOCS). $\endgroup$
    – Māris Ozols
    Commented Sep 3, 2015 at 11:11

2 Answers 2

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ HSP = hidden subgroup problem $\endgroup$
    – vzn
    Commented Jul 8, 2014 at 4:45
  • $\begingroup$ Thanks for pointing that out. I explained the acronym in the last edit. $\endgroup$
    – Juan Bermejo Vega
    Commented Sep 3, 2015 at 8:20
4
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.