16
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Also, I welcome comments on improving the taxonomy 1)-4). $\endgroup$ Jul 28, 2010 at 1:17
  • 8
    $\begingroup$ 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. $\endgroup$ Jul 28, 2010 at 11:08
  • 2
    $\begingroup$ 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 $\endgroup$ Aug 1, 2010 at 0:33
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 6, 2010 at 0:51
  • $\begingroup$ BTW, some problems use more than one of these subroutines: notably, this is true of the matrix inversion problem. $\endgroup$ Nov 6, 2010 at 0:53

3 Answers 3

15
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, I will definitely check this out. I'm not familiar with the algorithm, but I think your judgement is a.s. appropriate. $\endgroup$ Jul 28, 2010 at 9:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Mar 25, 2011 at 16:00
11
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The last couple of paragraphs are especially good stuff, wish I could accept two answers. $\endgroup$ Jul 29, 2010 at 21:19
1
$\begingroup$

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.

$\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.