1.3 Why quantum computing is different

I can write a simple app on a classical computer that simulates a coin flip. This app might be for my phone or laptop.

Instead of heads or tails, let’s use 1 and 0. The routine, which I call R, starts with one of those values and randomly returns one or the other. That is, 50% of the time it returns 1, and 50% of the time it returns 0. We have no knowledge whatsoever of how R does what it does. When you see “R,” think “random.”

This routine is a “fair flip.” It is not weighted to prefer one result or the other slightly. Whether we can produce a truly random result on a classical computer is another question. Let’s assume our app is fair.

If I apply R to 1, half the time I expect that same value and the other half 0. The same is true if I apply R to 0. I’ll call these applications R(1) and R(0), respectively.

If I look at the result of R(1) or R(0) in Figure 1.5, there is no way to tell if I started with 1 or 0. This process is like a secret coin flip, where I can’t know whether I began with heads or tails by looking at how the coin has landed. By “secret coin flip,” I mean that someone else does it, and I can see the result, but I have no knowledge of the mechanics of the flip itself or the starting state of the coin.

If R(1) and R(0) are randomly 1 and 0, what happens when I apply R twice?

I write this as R(R(1)) and R(R(0)). It’s the same answer: random result with an equal split. The same thing happens no matter how many times we apply R. The result is random, and we can’t reverse things to learn the initial value. In the language of section 4.1, R is not invertible. function$invertible

Now for the quantum version. Instead of R, I use H, which we learn about in section 7.6. It, too, returns 0 or 1 with equal chance, but it has two interesting properties:

• It is reversible. Though it produces a random 1 or 0, starting from either of them, we can always go back and see the value with which we began.
• It is its own reverse (or inverse) operation. Applying it twice in a row is the same as having done nothing at all.

There is a catch, though. You are not allowed to look at the result of what H does the first time if you want to reverse its effect.

If you apply H to 0 or 1, as shown in Figure 1.6, peek at the result, and apply H again to that, it is the same as if you had used R. If you observe what is going on in the quantum case at the wrong time, you are right back at strictly classical behavior.

To summarize, using the coin language: if you flip a quantum coin and then don’t look at it, flipping it again will yield the heads or tails with which you started. If you do look, you get classical randomness.

A second area where quantum is different is in how we can work with simultaneous values. Your phone or laptop uses a byte as the individual memory or storage unit. That’s where we get phrases such as “megabyte,” which means one million bytes of information.

We further break down a byte into eight bits, which we’ve seen before. Each bit can be 0 or 1. Doing the math, each byte can represent 2⁸ = 256 different numbers composed of eight 0s or 1s, but it can only hold one value at a time.

Eight qubits can represent all 256 values at the same time.

This representation is enabled not only through superposition, but also through entanglement, where we can tightly tie together the behavior of two or more qubits. These give us the (literally) exponential growth in the amount of working memory that we saw with a quantum representation of caffeine in section 1.2. We explore entanglement in section 8.2.