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

Question

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

Answer 1

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 2

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

Answer 3

I'll posit that perhaps asking for a taxonomy on quantum algorithms might be overly narrowing, and searching for elusive superpolynomial speedups might be white whales. In actuality quantum computation might offer opportunities that are somewhat orthogonal to anything conceivable classically.

As an example, I think of proposals for quantum money, such as by Farhi, Gosset, Hassidim, Lutomirski, and Shor and/or by Kane. A key part of such proposals involve the evaluation and execution of walks along a Markov chain/large matrix. The walks are classically simulatible and describable, and there's no obvious computational speedup in the execution on a quantum computer.

However, in order to validate the money the walks are executed on a superposition of qubits, e.g. an eigenstate of the large matrix. The ideas work because we ask a quantum computer to maintain a coherent superposition in a Hilbert space of a large enough dimension. At least in my eyes, there does not appear to be a classical counterpart to maintaining such a superposition.