I’ve been meaning to write about physics for a while. When I started this blog the intention was to write about a wide variety of interests, but I ended up focusing on programming, despite the fact that I was doing more physics than programming for most of the lifetime of this blog. Time to change that, and hopefully write about other non-programming topics too.

Quantum Computing. It’s the new hip thing that’s going to change the world¹. Someday.

In it’s essence, where classical computing deals with “bits”, which are on/off states, quantum computing deals with “qubits”, which are probabalistic quantum states that are often a mixture of on and off. These have interesting properties which make certain kinds of so-far-hard computation very easy to perform.

The goal of this post is not to teach quantum computing, rather to garner interest. I come to praise quantum computing, not bury it². As a result, this post doesn’t require a background in physics. Having worked with very simple logic circuits is probably enough, though you may not even need that.

I’m basically going to sketch out an example of a very simple quantum algorithm. One that’s very logic-defying. It’s even logic-defying for many who have studied quantum mechanics; it certainly was for me. When I learned this first I could understand why it worked but there was a lot of dissonance between that and my intuitive conviction that it was wrong.

The algorithm

This is a quantum circuit (specifically, the circuit for the Deutsch-Jozsa algorithm). It’s used to find out the nature of a black-box function f(x), which takes in one qubit and outputs another³. For now, you can try to interpret this circuit as if it were a regular logic circuit. You’ll soon see that this interpretation is wrong, but it’s useful for the purposes of this explanation.

To run this algorithm, you first construct an “oracle” out of the black-box function. The oracle, given inputs x and y, has outputs x and y ⊕ f(x) (where ⊕ is the symbol for XOR, the “exclusive OR”).

As with logic circuits, data flow here goes from left to right. This circuit has two constant inputs, a zero and a one. This is similar to how we might have constant “true” and “false” inputs to logic circuits.

They are then passed through “Hadamard gates”. These are like NOT gates, in that applying them twice is a no-op (they are their own inverse), but they’re not actually NOT gates. I like to describe them as “sideways NOT gates” since that description somewhat intuitively captures what’s going on with the qubits. What’s important to note here is that they have one input and one output, so they’re unaffected by the goings-on in a different wire.

Once these inputs have been Hadamard’ed, they are fed to the oracle we constructed. The top input goes on to become the top output. It’s also passed through f(x) and XORd with the bottom input to make the bottom output.

The top output is then Hadamard’ed again, and finally we observe its value.

Here’s where the magic comes in. By observing the top output, we will know the nature of f(x)⁴.

Wait, what? The top output doesn’t appear to have any interaction with f(x) at all! How can that work?

In fact, we could try to rewrite this circuit such that the measured output definitely has no interaction with f(x) whatever, assuming that the Hadamard gate isn’t doing anything funky⁵ (it isn’t):

How in the world does this work?

Why it works

Sadly, I can’t give a satisfying explanation to exactly why this works. This requires some quantum mechanics background⁶ to grasp.

However, I can give a hopefully-satisfying explanation as to why our regular intuition doesn’t work here.

First and foremost: The rewritten circuit I showed above? It’s wrong. If this was a logic circuit, we could always do that, but in quantum computing, T-junctions like the following can’t exist:

This is due to the “No Cloning theorem”. Unlike regular logic circuits, you can’t just “duplicate” a qubit. In some cases (like this one), you can try to create a similar qubit via the same process (e.g. here we could take another 0 and pass it through a Hadamard gate), but it’s not the “same” qubit. Unlike bits, qubits have a stronger notion of unique identity.

And it’s this sense of identity that fuels this algorithm (and most of quantum computing).

You see, while the top output of the oracle was x, it wasn’t exactly the same x. This x had been mixed with the lower output. This means that the upper and lower outputs are now entangled, with their state depending on each other. In fact, it’s really misleading to show the output as two wires in the first place – it’s really a single “entangled” state of two qubits that can’t be decomposed as a “top half” and a “bottom half”. Of course, this way of representing quantum circuits is still used because it’s a tidy way of visualizing these circuits, and physicists are aware of the caveats involved.

So what happens is that when you observe the top output, you are really doing a partial observation on the combined state of the two outputs, and this includes some information about f(x), which leaks out when you perform the observation.

These properties of qubits make quantum circuits work significantly differently from regular logic ones. On one hand, this severely restricts what you can do with them, but at the same time, new avenues of erstwhile-impossible operations open up. Most useful quantum algorithms (like Shor’s factorization algorithm) involve a mixture of a classical algorithm and a quantum circuit due to this reason. It’s pretty cool!