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