Does anybody give a good textbook description of a quantum computer algorithm and how its different from an ordinary algorithm?

  • $\begingroup$ Even more importantly, I'd like to see an example of an algorithm that is useful and an exponential speedup (outside of number theory / cryptography), e.g. in optimization. Grover, Deutsch and Shor's are not exciting enough to me. I would also look at lists like: quantumalgorithmzoo.org (clear problem | speedup and comunity maintained, yay!) $\endgroup$ – Ciro Santilli新疆棉花TRUMP BAN BAD Jan 2 '20 at 14:59

I'll avoid talking about Shor's algorithm and leave it for you to read on your own -- Shor's algorithm is the quantum algorithm, and is the reason quantum computing has become such a hot topic, and is not only a must read, but Scott Aaronson has provided a better introduction than I could ever manage, http://www.scottaaronson.com/blog/?p=208

Instead, I will guide you through Deutsch's algorithm, which solves a fantastically useless problem exponentially faster than any classical algorithm:

Imagine I have a function $f$ on a configuration of $n$ bits, $C=\{0,1\}^n$ that takes each configuration to a single bit. I promise you beforehand that this function is either:

  1. Constant - all configurations are mapped to the same value.
  2. Balanced - exactly half of the configurations map to $1$, the other half to $0$.

So classically, in the worst case you must evaluate the function for $2^{n-1}+1$ configurations ($O(2^n)$) to verify which category $f$ falls into.

Now, a quantum computer isn't just a parallel processor, where you can give it a superposition of the configurations and get back $f$ evaluated on all of them. At the end of the day, you have to make a measurement which destroys our carefully crafted superposition -- so we have to be clever! The fundamental feature of a quantum algorithm is that we use unitary operations to transform our state and use interference between states so that when we measure the state at the end, it tells us something unambiguous.

So without further ado, the Deutsch algorithm for $n=2$ qubits (you can do this for many more qubits, of course, but you wanted a simple example). The "quantum version" of our function is a unitary operation (a "quantum gate") that takes me from $|a\rangle|b\rangle$ to $|a\rangle|b+f(a)\rangle$ (where the addition is modulo 2). Also at my disposal is a gate that takes any single bit and puts it in a particular superposition:



The first step in the algorithm is to prepare my two qubits as $|0\rangle|1\rangle$ and then apply this transformation, giving me the state $(|0\rangle+|1\rangle)(|0\rangle-|1\rangle)/2$. Now I evaluate the function by applying the gate I described earlier, taking my state to


If we stare at this carefully, and think about arithmetic mod 2, we see that if $f(0)=1$ the first term picks up a minus sign relative to its state before, and if $f(0)=0$ nothing happens. So we can rewrite the state as


or regrouping


Now we shed the second qubit (we don't need it anymore, and it's not entangled with the first bit), and apply the second transformation I listed once more (and regrouping, the algebra is simple but tedious) -- at last, our final state is


And lastly, we measure! It should be clear from the state above that we've solved the problem... If $f$ is constant, then $f(0)=f(1)$ and we will always measure $|0\rangle$, and if $f$ is balanced then $f(0) \neq f(1)$ and we always measure $|1\rangle$.

Some final comments: hopefully this gives you some taste for the structure of a quantum algorithm, even if it seems like kind of a useless thing -- I strongly recommend going and reading the article I linked to at the beginning of this answer.

  • $\begingroup$ nice job.+1. Its good to see the increasing number of well-formed questions and answers on this site! $\endgroup$ – user346 Jan 20 '11 at 5:53
  • 7
    $\begingroup$ "Now, a quantum computer isn't just a parallel processor, where you can give it a superposition of the configurations and get back f evaluated on all of them." Actually, it isn't -even- a parallel processor. Quantum parallelism is not the same as having an exponentially parallel classical computer, although an exponentially parallel classical computer can simulate a quantum computer efficiently. $\endgroup$ – Joe Fitzsimons Jan 20 '11 at 10:02
  • 1
    $\begingroup$ Thanks Joe, that's really what I meant to point out, although my word choice was rather poor. $\endgroup$ – wsc Jan 20 '11 at 22:17
  • $\begingroup$ I think the link is dead $\endgroup$ – rocketsarefast Dec 12 '17 at 8:11
  • $\begingroup$ What is the formula right after "we shed the second qubit"? Why is that allowed? $\endgroup$ – Albert Hendriks Jun 29 '18 at 14:36

Ok, since wsc gave you an explanation of Deutsch's algorithm, let me talk you through another, and more useful, algorithm: Grover's search algorithm. This is a search algorithm for an unsorted database, or for searching a black box for the input which results in a specific output (a very useful primitive in algorithms). For a set of $N$ entries, assuming there is only entry satisfying the search query, the algorithm takes only $O(\sqrt{N})$ queries, where as the best possible classical algorithm takes $O(N)$ queries of the database. Further, Grover's algorithm (with a small modification I won't go into here) is provably optimal. So, how does it work?

Let's assume there is a database of $2^n$ entries. First we prepare a superposition of $2^n$ classical states with positive phase: $\mid S \rangle = 2^{-\frac{n}{2}} \sum_{x=1}^{2^n} | x \rangle$. This is can be done simply by applying a single quantum gate (in this case a Hadamard gate) to each of $n$ qubits initially prepared in the zero state. I'll represent the states encountered by a diagram, where the length of each line represents it's amplitude in the superposition, and whether it is direction from the center line to indicate its phase (in this case it will always be either positive or negative). The state we obtain after this initialisation step is then depicted as below.

alt text

The algorithm itself consists of $r$ rounds which each consist of two steps:

  1. The phase of a classical state in the superposition is flipped if (and only if) the entry in the database at that location matches the search query, as illustrated below. Here we assume entry $m$ is the entry matching the search query. Note that this is only a single query to the database, which is having different effects in each branch of the wavefunction. This is achieved by applying an operator $U_m = I - 2 | m \rangle \langle m |$

alt text

  1. The 'inversion about the mean' operator is applied. This is simply a unitary operator given by $U_S = 2 | S \rangle \langle S | - I$, where as before $| S \rangle = 2^{-\frac{n}{2}} \sum_{x=1}^{2^n} | x \rangle$. The effect of this operator is very simple: the amplitude $A_i$ of each entry $i$ is taken to $2\mu - A_i$, where $mu$ is the average amplitude. This is equivalent to inverting the distance above or below the mean. The first diagram below illustrates where the mean now lies, while the second shows the effect of applying this operator.

alt text

alt text

Clearly the effect of this operation is to amplify the amplitude of the entry matching the search query, and this will continue until the mean lies below the zero line (after $r$ rounds). This occurs after $O(\sqrt{N})$ queries. To see this, we first note that the state of the system after each round $i$ can always be written in the form $|\psi_i\rangle = \cos \theta_i |s\rangle + \sin \theta_i |m\mid$, where $|s\rangle = (2^n - 1)^{-\frac{1}{2}} \sum_{x\neq m} | x \rangle$. Clearly $|s\rangle$ and $|m\rangle$ are orthogonal, so we can represent any state encountered as a unit vector in the 2D plane spanned by $|s\rangle$ and $|m\rangle$.

alt text

Let's consider the effect of a single round. First $U_m$ is applied and then $U_S$ is applied. Note that $U_S = 2 |S\rangle\langle S| - I = (\frac{2(2^n - 1)}{2^n}-1)|s\rangle\langle s | + \frac{2\sqrt{2^n - 1}}{2^n}|s\rangle\langle m | + \frac{2\sqrt{2^n - 1}}{2^n}|m\rangle\langle s | + (\frac{2}{2^n} - 1)|m\rangle\langle m |$. When we multiply this by $U_m$ to get the total operation applied in a round $U_S U_m = (\frac{2(2^n - 1)}{2^n}-1)|s\rangle\langle s | - \frac{2\sqrt{2^n - 1}}{2^n}|s\rangle\langle m | + \frac{2\sqrt{2^n - 1}}{2^n}|m\rangle\langle s | + (\frac{2(2^n - 1)}{2^n})|m\rangle\langle m |$. This is simply a rotation through a constant angle $\phi=\sin^{-1}(\frac{2\sqrt{2^n - 1}}{2^n}) \approx \frac{2}{\sqrt{2^n}}$ for large $n$. Since we initially start very close to the state $|s\rangle$, we thus require $r \approx \frac{2}{\sqrt{2^n}}$, meaning that we achieve the maximum amplitude for $|m\rangle$ in just ~$2\sqrt{N}$ queries of the database.

It is easy to see that this is impossible classically, since if you make $m$ queries to the database, there are still $N-m$ entries which have not been checked which may possibly match the search term, meaning that a linear number of entries need to be checked to insure even a constant probability of finding the correct entry.

Hope this is useful

  • $\begingroup$ It is really hard when one is forced to choose one good answer over another +1 $\endgroup$ – Humble Jan 20 '11 at 10:47
  • $\begingroup$ Clearest explanation of Grover I've ever seen. Thanks! $\endgroup$ – Rococo Nov 14 '14 at 15:10
  • $\begingroup$ 5 years ! A great answer in a few lines ... Only about the conclusion : is the setting usable again ? to prepare the states, this algo must read all the entries. Does it this work each time or once ? At the opposite, classical algos may order the list once and after, get any value after Log N tries. $\endgroup$ – user46925 Feb 21 '16 at 15:16
  • $\begingroup$ @igael: It doesn't sort the list, just finds the marked element. $\endgroup$ – Joe Fitzsimons Mar 14 '16 at 14:14
  • 1
    $\begingroup$ Grover is potentially super useful in practice, but I wish there was an example of something that is useful with exponential speedup (outside of number theory / cryptography). $\endgroup$ – Ciro Santilli新疆棉花TRUMP BAN BAD Jan 2 '20 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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