Did you know you can buy a quantum computer with 512 qubits for $10$ million dollars? It even has a Python interface. Does it work? The answer is yes. [But you can solve the same problems on a classical computer just as fast -- at least if you include the time it takes to put the data on the computer.] It uses a quantum annealing algorithm.

qbits

Information in a classical computer is stored in "bits" -- these are a sequence of zeros and ones. Calculations are done by a sequence of "logic gates".

A quantum computer (as it is typically envisioned) replaces the bits by quantum spins. Spin-up is one, spin-down is zero. One applies similar gates to the classical case -- in this case the gates are Unitary transformations (ie. time evolution with some Hamiltonian.)

There are two reasons quantum bits might be good:

Argument one (due to Feynman): describing the state of the quantum bits is hard. In fact, if you have $n$ bits, then the Hilbert space is spanned by a basis of $2^n$ states. That is, you need $2^n$ numbers to specify the state of the quantum computer, but only $n$ to specify the state of the classical computer. There appears to be exponentially more resources for the same size quantum computer.

Argument two: Since you can be in superpositions of states, you can in principle carry out multiple calculations in parallel.

There is also a problem. The problem is that there is no good way to get access to all this information. Any given measurement can only give you $n$ numbers.

It turns out that there are a handful of algorithms for which a quantum computer is faster than a classical computer. These are all closely related: Shor's algorithm (factoring large numbers), Simon's algorithm (a particular form of database search), Gauss sums (adding a large number of complex exponentials), Grover's Algorithm (database search), and a number of more abstract ones.

By far Shor's algorithm is the most often cited, as it in principle has implications for cryptography. [Most public key encryption schemes are based upon the difficulty of factoring large numbers.

Shor's Algorithm

To be honest, Shor's algorithm is not a factoring algorithm -- rather it is a period finding algorithm. The first step is to convert the factoring of a number into a problem of finding a period. This conversion can be done on a classical computer. If you haven't taken a number theory course this might be heavy going.

For example, lets take our number to be 21. We then pick a random number $a$ less than $N$. Say we choose 8.
We then calculate the greatest common divisor of $N$ and $a$. In this case it is $1$. If it was anything other than $1$ we would be done (as we have found a factor).

Finding the greatest common divisor is fast on a classical computer.

Assuming the greatest common divisor is $1$, we define a function $f(x)=a^x \mod N$. For this example $f(1)=8, f(2)=1,f(3)=8,...$ The function will always be periodic. In this case the period is $2$. Finding the period of this function is hard -- this is the task that the quantum computer will do. Once you have the period $r$, you look at $f(r/2)$. If $r$ happens to be odd, you are out of luck, and have to go back and choose a new $a$. If $f(r/2)$ happens to be $-1 \mod N$, you are also out of luck -- go back and choose a new $a$. We are lucky, $r$ is even, and $f(r/2)=f(1)=8$. A little number theory argument (which we will give in a moment) says that both $a^{r/2}+1$ and $a^{r/2}-1$ must have a common divisor with $N$ other than $1$. Indeed, $7=8-1$ is a factor, and $6=8-1$ has a GCD of 3.

Number Theory

Given that $f$ has period $r$, we must have $a^r=1 \mod N$. Equivalently $(a^r-1)=0 \mod N$. This means that $a^r-1$ is a multiple of $N$ Indeed $8^2-1=63$ is a multiple of 21.

Next we factor this relation, noting that $(a^{r/2}-1)(a^{r/2}+1)=0 \mod N$. This can only be true under one of the following circumstances:

Case 1:

$(a^{r/2}-1)$ is a multiple of $N$

Case 2:

$(a^{r/2}+1)$ is a multiple of $N$

Case 3:

neither $(a^{r/2}-1)$ nor $(a^{r/2}+1)$ are multiples of $N$, but their product is. This means that they must have a factor in common with $N$. (If you are a multiple of something, you must contain all of the factors.)

Case 1 is sad -- it is equivalent to $f(r/2)=-1 \mod N$. The only solution is to choose a new $a$. Case 2 can never happen: It means $f(r/2)=1$, which means the period wasn't $r$, but instead was $r/2$. Case 3 is the good one -- it gives us our answer.

How likely is Case 1, and how likely is it that $r$ is odd? It turns out that the probability of one of these failures is $1/2^(k-1)$ where $k$ is the number of prime factors of $n$. Thus at least half the time we are golden.

Quantum Period Estimation Algorithm

Where does quantum mechanics come in. So far, everything we have done is classical. The key quantum step is finding the period $r$ of $f(x)$.

Our first step is to initialize our computer in the state
\begin{equation}
||a\rangle\rangle =\sum_x |f(x)\rangle\otimes |x\rangle.
\end{equation}
This means we have two sets of qbits. We put it in an "entangled" state that whenever the second set is in state "x", the first is in the state $f(x)$. It turns out this can be done efficiently. Note, this defines the state $||a\rangle\rangle$, which is different from the state $|a\rangle$. In particular, $||a\rangle\rangle$ has $2n$ qbits, while $|a\rangle$ has n.

Our second step is to do a "Fourier Transform" on the last $n$ bits:
\begin{equation}
|x\rangle\to \frac{1}{\sqrt{N_b}}\sum_q e^{i 2\pi q x} |q\rangle,
\end{equation}
where $N_b$ is the number of bits, and $q=2\pi n/N_b$.
Again, this is efficient -- it essentially uses the FFT algorithm. Under this transformation:
\begin{eqnarray}
||a\rangle\rangle&\to&\frac{1}{\sqrt{N_b}}\sum_q \sum_x e^{i 2\pi q x} |f(x)\rangle\otimes |q\rangle\\
&=& \sum_q \sum_f c_{fq} |f\rangle\otimes |q\rangle.
\end{eqnarray}
The coefficient is
\begin{equation}
c_{fq}=\frac{1}{\sqrt{N_b}}\sum_{x: f(x)=f} e^{i2\pi q x}.
\end{equation}
Since $f$ is periodic with period $r$, we can write
\begin{equation}
c_{fq}=\frac{1}{\sqrt{N_b}}\sum_{n} e^{i2\pi q (x_0+n r)},
\end{equation}
where $x_0$ is the smallest $x$ such that $f(x_0)=f$. Aside from some subtleties about boundaries, this coefficient is zero unless $q = m N_b/r$ for some integer $m$.

One now measures the q-bits, one finds some $f$ and some $q$, but we are guaranteed that $q$ is a multiple of $ N_b/r$. One tries $r=N_b/q$, and $r= N_b/(2q)$ and $r= N_b/(3q)\cdots $

Of course, there is a small subtlety that if $R$ and $N_b$ are not commensurate, one instead gets sharp peaks, rather than delta-functions. The sharp peaks, however, are always near integer multiples of $2\pi N_b/r$. These subtleties are only important if you are trying to build a quantum computer.