Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

To understand how amplitude amplification naturally fits in as a particularly simple quantum walk, I'd recommend understanding properly how Grover search works as a quantum walk. Try reading Andrew Childs' lecture notes, particularly lectures 14 and 15. He explains how to view Grover search as a discrete-time and continuous-time quantum walk. I think after understanding that, the case of amplitude amplification should be clear.

To answer your philosophical question, consider the classical case. Linear programming is P-complete, and thus every problem in P can be solved by linear programming. But you wouldn't apply linear programming to every problem you see. Some problems have natural LP formulations, and some don't. So you can't just say "Linear programming is P-complete, so I'll solve everything using linear programming."

Similarly, quantum walks are BQP-complete, but not all quantum algorithms have a natural quantum walk formulation. Calling any BQP-complete problem a computational primitive is a bit like calling the Circuit value problem and the Horn-satisfiability problem primitives for designing polynomial time algorithms. While linear programming is considered a classical algorithmic technique, it's not because of its P-completeness. It's because of the wide variety of problems that can be cast as LPs and solved in polynomial time. Similarly, quantum walks are a quantum algorithmic technique because many problems can be solved naturally using quantum walks, but not all BQP-complete problems can be considered to be algorithmic techniques.

share|improve this answer
add comment

One small remark to Robin's reply. Take a look at Lecture 16 of Child's lecture notes, more precisely, the footnote on the first page. It deals with this question.

share|improve this answer
Thanks, I went through the whole tail end of his notes. –  Steve Huntsman Feb 17 '11 at 12:31
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.