What's the simplest algorithm (like Deutsch's algorithm and Grover's Algorithm) for intuitively demonstrating quantum speed-up? And can this algorithm be explained intuitively?
Ideally this would be also illustrate clear how quantum interference is being utilized, and why it is not possible or useful using just interference of classical waves.
I would like to suggest that period finding (a subroutine, if you like, of the famous Shor algorithm) demonstrates a very intuitive, exponential speed-up: It should be intuitively clear that something on the order of (the square root of the uncertainty $\Delta p$) of the period $p$ of function evaluations is required classically to find an unknown period $p$ of a function that is guaranteed to be periodic in its integer input value. I've deliberately placed the paranthesis such that their content will be intuitive to people who have deeply ingrained the birthday paradox yet, for demonstrating a superpolynomial speedup, it is sufficient to intuitively understand that it is somewhere near $\Delta p$, the correct answer $\sqrt{\Delta p}$, or some polynomial thereof and not something like the number of digits of $p$, $O(\log p)$.
The quantum algorithm for period finding, as employed by Shor's algorithm, simply takes the quantum Fourier transform of the periodic function applied to the equal superposition of all states. Naturally, only integer multiples of the period can then have a non-zero probability amplitude, so doing this (typically) twice will allow you to quickly extract the common factor as greatest common denominator. But a quantum Fourier transform is trivially implementable by $O(\log p)$ controlled rotations (one per each input bit).
The biggest intuitive speedup obviously occurs if you make the function evaluation very costly: The quantum algorithm only requires a constant (single) evaluation! But even otherwise you get a gain as you have an algorithm that runs, assuming function evaluations are constant time, in $O(\log p)$ rather than in $O(\sqrt{\Delta p})$ which, if you have no idea of the correct period $p$ is essentially $O(\sqrt{p})$.
The difficulty with the question is the word intuitive. Intuition basically reflects our understanding of the world around us, which is described by classical physics. Quantum mechanics is exactly the regime where our intuition breaks down because it functions very differently from the world of our everyday experience. As Terry Pratchett said :
It’s very hard to talk quantum using a language originally designed to tell other monkeys where the ripe fruit is.
It is exactly that difference that we're using to get the computational speed-up.
There is a sequence of standard algorithms that most quantum computing texts progress through: Deutsch's algorithm, Deutsch-Jozsa, Simon's/Bernstein-Vazirani. These are chosen because they are the easiest to understand. They all have broadly the same structure, but increasing complexity, with a corresponding gain in computational speed (with Simon's giving exponential speed-up). You will not understand them intuitively. You have to do the maths. I think the closest that you will come is through the following explanation of Deutsch's algorithm:
Imagine a one-bit function $f(x)$. Either $f(0)=f(1)$, or it does not. Your task is to determine which. Obviously, in the classical world, you have to evaluate $f(0)$ and $f(1)$; two function calls. In the quantum world, crudely speaking, you can look at both values simultaneously, and perform a one-qubit measurement (which will give you one bit of information), but you can choose that measurement so that the one bit is a global property of the function, in this case $f(0)\oplus f(1)$. The same is broadly true of the other algorithms I mentioned: there is information, due to the structure of the problem, hidden in the collective properties of the function evaluations, and it is those collective properties that you are trying to determine.
There is nice example in the Microsoft lecture. Suppose you have a classical black box with 1 input and 1 output. How many queries you need to determine whether the output is constant or variable? Evidently you need 2 queries; first you input 0, second you input 1; if both outputs are identical you have constant, otherwise variable. It turns out that after you convert the classical black box into a quantum black box you can build a circuit that needs only a single query (the lecture explains how to do it).
