Can anybody provide a simple example of a quantum computer algorithm?

Question

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

Answer 1

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:

$$|1\rangle\rightarrow(|0\rangle-|1\rangle)/\sqrt{2}$$

$$|0\rangle\rightarrow(|0\rangle+|1\rangle)/\sqrt{2}$$

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

$$[|0\rangle(|0+f(0)\rangle-|1+f(0)\rangle)+|1\rangle(|0+f(1)\rangle-|1+f(1)\rangle)]/2$$

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

$$[(-1)^{f(0)}|0\rangle(|0\rangle-|1\rangle)+(-1)^{f(1)}|1\rangle(|0\rangle-|1\rangle)]/2$$

or regrouping

$$(|0\rangle+(-1)^{f(0)+f(1)}|1\rangle)(|0\rangle-|1\rangle)/2$$

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

$$[(1+(-1)^{f(0)+f(1)})|0\rangle+((1-(-1)^{f(0)+f(1)})|1\rangle]/2$$

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.

Answer 2

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.

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 |$

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

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

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