# Simplest algorithm for intuitively demonstrating quantum speed-up?

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.

• what kind of speed-up (polynomial vs exponential), and what kind of advantage (unconditional vs oracular)? – glS Aug 7 '18 at 10:14
• Doesn't matter, as long as it's clear. Exponential speedup might be nice to see though. – Steven Sagona Aug 7 '18 at 15:38
• The simplest examples will also work with classical waves. In fact, all examples, except that the classical waves can (and must) take exponentially many paths in the number of qubits involved. – Norbert Schuch Aug 13 '18 at 15:37

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 and Bernstein-Vazirani 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.

• "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. " This word is commonly used within mathematics, and often doesn't mean "analogous to classical physics." What I mean (and often is meant) by intuition is having an /understanding/ of a mechanism within a framework. It's easy to teach someone to plug in formulas to get an answer, but getting them to fundamentally /understand/ the framework and the logic is what this standard definition of intuition is about. – Steven Sagona Aug 10 '18 at 16:45
• @StevenSagona “having an understanding of a mechanism within a framework”. Yes, I agree. If you know some mechanisms within a framework, you can understand a new one without solving all the details because you have context, provided by the existing knowledge. And if you understand something, you should be able, with some work, to reconstruct the mathematical details. But you cannot understand the first mechanism in a completely new framework intuitively. Many interested but inexperienced people try to do this, e.g. through classical analogs, and they fail, but may believe they’re succeeding. – DaftWullie Aug 11 '18 at 5:27

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

• Otherwise known as Deutsch's algorithm. – DaftWullie Aug 7 '18 at 7:43
• If you're interested in learning more about the Deutsch–Jozsa problem, I'd recommend taking a look at the Quantum Katas. The Deutsch–Jozsa kata goes through the concepts needed as a series of self-paced exercises, and can be a neat way to learn. – Chris Granade Aug 9 '18 at 20:24
• Note that this only gives a quantum speed-up if you want an answer with certainty. If you want the answer with some certainty, a constant number of queries is needed, even if the problem size increases (as with Deutsch-Jozsa) – nippon Aug 10 '18 at 14:05