Gist of Quantum Computing

> Quantum Computers. Not like I'm five, but like I'm a software engineer who has a pretty decent understanding of how a classical turing machine works. I can't tell you how many times I've heard someone say "qubits are like bits except they don't have to be just 1 or 0" without providing any coherent explanation of how that's useful.

Think of a deterministic computer as a computer that has an initial memory given by a state vector, consisting of a list of bits.

(10111010100000)

Computation is specified via a sequence of logic gates, which operate on bits at a few specified locations and store the result in a specified location.

e.g. maybe the first few operations in our program are AND 1,2->1 , OR 1,3->2 , OR 3,7->1, NOT 1->1. Then our state vector would evolve as follows:

AND 1,2->1 : (00111010100000)

OR 1,3->2 : (01111010100000)

OR 3,7->1 : (11111010100000)

NOT 1->1 : (01111010100000)

We can define the output of our computation to be "yes", say, if the first bit at the end is 1, an "no" otherwise.

This model of computation is "universal" for efficient computation, in the sense that given any Turing machine which solves some decision problem in time T(n) where n is the size of the input, it's possible to efficiently turn a number n into a gate sequence of length polynomial in T(n) which solves the same problem on all inputs of size n.

So that's determinism. Onto probabilistic computation.

1/2 (101110100) + 1/2 (000010110)

Here our state vector isn't in one determined state, but rather somehow we know that it's either in state (101110100) with probability 1/2, or in state (000010110) with probability 1/2. If we open up our computer and look at the state, those probabilities determine the likelihood with which we'll see the corresponding state.

When we talk about probabilistic computation in this way, we call the deterministic state vectors *observables*. In general, a probabilistic state assigns a probability  in the range [0, 1] to every possible observable, but the probabilities over all observables need to sum to 1. If non-zero probabilities are assigned by a probabilistic state to more than 1 observable, then we say that the state is a *probabilistic superposition* of those observables.

Our computation still usually starts in a determined state. In order to actually generate interesting superpositions, we could add a new operation, the coin flip, which turns a specified bit into a 0 with probability 1/2 or 1 with probability 1/2. So for example if we start with

(111001)

and apply FLIP 1 , AND 1,2->2 , OR we get

FLIP 1 : 1/2 (011001) + 1/2 (111001)

AND 1,2->2 : 1/2 (001001) + 1/2 (111001)

OR 1,3->1 : 1/2 (101001) + 1/2 (111001)

NOT 2->2 : 1/2 (111001) + 1/2 (101001)

FLIP 4 : 1/2 (1/2 (111001) + 1/2 (111101)) + 1/2 (1/2 (101001) + 1/2 (101101))

= 1/4 (111001) + 1/4 (111101) + 1/4 (101001) + 1/4 (101101)

The output of our computation could be defined again to be "yes" if the first bit is observed to 1 when we open up our computer and look at the state, or "no" otherwise. Since this output is generally going to be random, we'll only consider the gate sequence to be useful if it outputs the correct answer on each input with probability 2/3 or greater. (If you want greater accuracy you can just rerun the circuit a bunch of times and take a majority vote. You can take a Chernoff bound to show that this will quickly give you very good odds of getting the right answer.)

This model captures efficient probabilistic computation, in that once again, an efficient probabilistic Turing machine and an input size n can be efficiently transformed into a gate sequence with ANDs, ORs, NOTs, and FLIPs, of reasonable length, that do the same thing as the Turing machine on inputs of size n.

Onto quantum computers.

1/sqrt(2) (101110100) - 1/sqrt(2) (000010110)

Oh, oops, I forgot that we get to use that cool looking bra-ket notation now.

1/sqrt(2) |101110100> - 1/sqrt(2) |000010110>

That's better.

The numbers next to the observables are called amplitudes. Amplitudes get to be negative, and they even get to be complex, but you don't need complex amplitudes to get universal quantum computation, so I'm not going to bother with complex numbers. The square of the amplitude determines how likely you are to see a given observable if you crack your computer open and look at the state. The amplitudes that a quantum state assigns to the observables need to square-sum to 1.

One wrinkle in setting up quantum computation is that nature says that quantum operations need to be *reversible* -- information can't be destroyed and all that. Up until this point most of our gates have been highly destructive, so we'll need to replace our gates with reversible ones.

First, we could replace all of our deterministic gates with the Toffoli gate: https://en.wikipedia.org/wiki/Toffoli_gate

The Toffoli gate is actually just a classical deterministic gate like AND, OR and NOT, but it's reversible. It requires us to specify three bits to operate on. (Qubits, same difference.) It does nothing if the first two bits specified aren't 1, but if they are both 1, then it negates the third specified bit. It's commonly denoted by CCNOT.

It turns out that the Toffoli gate (together with some extra bits pre-set to 1) is actually universal for deterministic computation on its own. You can implement each of your AND, OR and NOT gates using a combination of Toffoli gates, but in order to overwrite an existing bit with the result, you'll generally need to generate garbage bits that you keep off to the side, as a consequence of the reversible nature of the Toffoli gate. This can matter, but it doesn't get in the way of a quantum computer doing a great impression of a classical computer for universality's sake.

In order to generate quantum superpositions, we could pick the Hadamard gate: https://en.wikipedia.org/wiki/Quantum_logic_gate#Hadamard_(H)_gate

I'll denote the Hadamard gate by H. The Hadamard gate is kinda like a quantum coin flip. The Hadamard gate operates on one bit, and does the following:

H|0> = 1/sqrt(2) |0> + 1/sqrt(2) |1>

H|1> = 1/sqrt(2) |0> - 1/sqrt(2) |1>

The combination of Toffoli and Hadamard gates turns out to be universal for quantum computing, i.e. any reasonable gate set can be simulated by some small combination of Hadamards and Toffolis. As before, computation is specified by a sequence of gates, e.g.

|00101000>

CCNOT 3,5,1 : |10101000>

H 2 : 1/sqrt(2) |10101000> + 1/sqrt(2) |11101000>

CCNOT 1,2,4 : 1/sqrt(2) |10101000> + 1/sqrt(2) |11111000>

Note what happens if you apply the Hadamard gate twice to the same bit, e.g.

|0>

H 1 : 1/sqrt(2) |0> + 1/sqrt(2) |1>

H 1 : 1/sqrt(2) (1/sqrt(2) |0> + 1/sqrt(2) |1>) + 1/sqrt(2) (1/sqrt(2) |0> - 1/sqrt(2) |1>)

= 1/2 |0> + 1/2 |1> + 1/2 |0> - 1/2 |1>

= |0>

You can unflip a coin in quantum computing! (Well, quantum operations are always reversible, so maybe we should've seen this one coming.)

Another perspective comes from interpreting each observable having non-zero amplitude as being a possible "branch" you could end up in. When we apply the first Hadamard gate, we end up in a branch where we observe |0> with amplitude 1/sqrt(2), and a branch where we observe |1> with amplitude 1/sqrt(2). But after applying the second gate, we see the branches where |0> is observed constructively interfere and reinforce, and the branches where |1> is observed interfere destructively and annihilate one another. By comparison, had we been flipping coins in the probabilistic world, we would've only observed constructive interference and ended up with 2 branches:

(0)

FLIP 1 : 1/2 (0) + 1/2 (1)

FLIP 1 : 1/2 (1/2 (0) + 1/2 (1)) + 1/2 (1/2 (0) + 1/2 (1))

= 1/4 (0) + 1/4 (1) + 1/4 (0) + 1/4 (1)

= 1/2 (0) + 1/2 (1)

It's a pretty common perspective in quantum computing that these interference patterns are what matters. The idea is that you get a speedup if you can rig things so that the branches carrying the correct answer reinforce, whilst the branches carrying the incorrect answers annihilate each other. This idea is supported by the fact that a quantum computer that deals only in, say, positive amplitudes, can be efficiently simulated by a probabilistic Turing machine. In order for quantum computers to offer a meaningful speedup, you need destructive interference.

So far a very limited number of amazing such speedups have been found (e.g. Shor's algorithm for integer factoring), and many more modest speedups have been found (e.g. Grover's algorithm and algorithms based on similar ideas).

> I've also heard that they can try every possible solution to a problem. What I don't understand is how a programmer is supposed to determine the correct solution when their computer is out in some crazy multiverse.

You can't! Well, at least not without exponentially more steps to fish out the value. Claims to the contrary are either pseudoscience or marketing nonsense.

The claims come from the following setup. Imagine you have a polynomial-time verifier implemented as a quantum circuit V, that operates on n input bits and a bunch of other working bits, and spits out a 1 in a designated output location if the n input bits encode a satisfying truth assignment for some arbitrary boolean formula f, or a 0 otherwise. (There's nothing wrong with this, it's always possible to construct such a V.)

Then here's a circuit: apply a Hadamard gate to each of the n input bits, then apply V.

So we start with

|n 0's>|working memory>|0>

apply H to bits 1..n : sum_{all bitstrings w} 1/sqrt(2^n)|w>|working memory>|0>

apply V : sum_{all bitstrings w} 1/sqrt(2^n)|w>|garbage>|1 if w satisfies f, 0 otherwise>

Now you simply reach into the machine and grab the branch that has the output bit set to 1, and you're done!

(But seriously, you can apply the Grover diffusion operator, then repeat the process sqrt(2^n) times, and after that if you look inside your computer at the state you'll have a good chance of observing the satisfying truth assignment you're looking for. That's decent, but you're not solving SAT in polynomial time with this.)