Are there any known quantum algorithms that clearly fall outside a few narrow classes? - MathOverflow

Are there any known quantum algorithms that clearly fall outside a few narrow classes?

2010-07-28T01:07:50Z

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.

Linear algebra
Quantum Fourier transform and hidden subgroup problems
Quantum search
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.)

Answer by Peter Shor for Are there any known quantum algorithms that clearly fall outside a few narrow classes?

2010-07-28T04:16:31Z

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.

Answer by Ashley Montanaro for Are there any known quantum algorithms that clearly fall outside a few narrow classes?

2010-07-28T10:11:59Z

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).