This is a followup to an earlier question on a taxonomy for quantum algorithms in which I ultimately concluded in a comment that all known nontrivial quantum algorithm speedups (in Jordan's quantum zoo) could be regarded as arising from four basic classes of quantum subroutines: 1) quantum Fourier transform; 2) amplitude amplification [incl. Grover]; 3) quantum simulation/annealing; 4) quantum walks.

Now I wonder if it would be more fair to say *three* classes...

Today I read in more than one place specifically that amplitude amplification can be regarded as a quantum walk algorithm, but have not been able to find a definitive demonstration or reference (I have glanced at Santha's paper and similar things; while I may have missed something, this smells like it would be a MO-hard reference request) other than the overly general result that quantum walks are universal for quantum computation.

The nearest statement I can feel comfortable with (especially having not gone over any details yet for myself) having some obvious meaning is that Grover search can be regarded as a quantum walk algorithm, but it's not clear to me why this would entail that amplitude amplification would be realizable as a quantum walk algorithm. Perhaps I'm missing some "amplitude amplification is Grover-hard" result...?

Anyway, how is amplitude amplification explicitly realizable as a quantum walk algorithm?

As a more philosophical followup, if quantum walks are universal for quantum computation, does it really make sense to talk about them as subroutines?

[This makes me think that I might be justified in going so far as to classify all known quantum algorithm speedups as relying in principle on either a) the quantum Fourier transform or b) an arbitrary **BQP**-complete computational primitive (e.g., simulation or walk). In this setting the taxonomic question would be appropriately recast about what sorts of problems are better suited to solution via a given **BQP**-complete primitive, and what architectures are better suited to implementing a given **BQP**-complete primitive.]