Take the 2-minute tour ×

I'm trying to refresh myself on quantum algorithms and have been skimming Childs and van Dam's 2008 RMP paper among other things. From my preliminary surfing it looks like the known quantum algorithms still essentially fall into (in that their nontrivial quantum aspect is governed by) four major classes, viz.

  1. Linear algebra
  2. Quantum Fourier transform and hidden subgroup problems
  3. Quantum search
  4. Quantum simulation/annealing

and I'm wondering: does this classification clearly miss anything?

(NB. Because I'm hoping for answers that discuss why a given algorithm does not fall into one of these classes, I'm not making this CW.)

share|improve this question
Also, I welcome comments on improving the taxonomy 1)-4). –  Steve Huntsman Jul 28 '10 at 1:17
Stephen Jordan's Quantum Algorithm Zoo (its.caltech.edu/~sjordan/zoo.html) lists many known quantum algorithms. It might be helpful for identifying gaps in your classification scheme. –  John Watrous Jul 28 '10 at 11:08
There are several algorithms based on quantum walks. I'm not sure if they fall under your classification scheme. See this survey by Miklos Santha: arxiv.org/abs/0808.0059 –  Robin Kothari Aug 1 '10 at 0:33
Having gone through the recent literature and the quantum zoo mentioned above, a revised taxonomy that appears to cover everything here or there is: 1) quantum Fourier transform; 2) quantum walks (incl. search); 3) quantum simulation. Contact me privately for a breakdown of the zoo problems along these lines. –  Steve Huntsman Nov 6 '10 at 0:51
BTW, some problems use more than one of these subroutines: notably, this is true of the matrix inversion problem. –  Steve Huntsman Nov 6 '10 at 0:53

2 Answers 2

up vote 10 down vote accepted

Does the Farhi-Goldstone-Gutman game tree evaluation algorithm and the extensions of it fall into one of these classes? You might put it in quantum simulation/annealing because of the technique used, but I think that would be a mistake. You might also put it in quantum search because it doesn't give a super-polynomial speed-up, but it has a very different flavor than all the other quantum search algorithms.

share|improve this answer
Thanks, I will definitely check this out. I'm not familiar with the algorithm, but I think your judgement is a.s. appropriate. –  Steve Huntsman Jul 28 '10 at 9:57
I should add that there are a number of generalizations of this which at first sight look quite different (see Ben Reichart's papers on span programs) that are worth a look. –  Peter Shor Mar 25 '11 at 16:00

While most famous quantum algorithms fall into your categories (2)-(4) ("linear algebra" isn't especially informative, as all of quantum computation can be understood as an application of linear algebra...), there are some others that don't.

First, there's an algorithm of Childs et al that uses a quantum walk to traverse a graph in polynomial time, for which any classical algorithm requires exponential time. This relies on the fact that quantum walks can hit exponentially faster than classical random walks. There are a number of other algorithms based around quantum walks; I guess you could characterise these as "quantum search", but some have a different feel to them.

Second, there are quantum algorithms for approximating the Jones polynomial and other graph invariants (see, for example, the paper of Aharonov, Jones and Landau, or Section X of the paper by Childs and van Dam you linked to). These algorithms essentially work by encoding the problem instance to be solved directly into a quantum circuit.

Third, there is an algorithm of Harrow, Hassidim and Lloyd which calculates properties of solutions to large systems of linear equations exponentially more efficiently. The main ingredient that goes into this (phase estimation) is also used in algorithms for factoring etc, but the application seems very different.

There are also some algorithms which may not achieve especially large speed-ups, but which demonstrate different design techniques. For example, there's a nice algorithm of Hoyer, Neerbek and Shi that solves the task of search in an ordered list somewhat faster than classical binary search. The algorithm is based on searching a number of subtrees of a binary tree in quantum parallel. I should also mention a nice algorithm of van Dam (quant-ph/9805006) which demonstrates that an n bit string can be read from an oracle using just over n/2 quantum queries.

Finally, there are algorithms for purely quantum information theoretic tasks, which are by their nature different again. In particular, the algorithm of Bacon, Chuang and Harrow for the Schur transform has a number of applications in quantum information theory (eg. state estimation, entanglement concentration and communication without a shared reference frame).

share|improve this answer
The last couple of paragraphs are especially good stuff, wish I could accept two answers. –  Steve Huntsman Jul 29 '10 at 21:19

Your Answer


