Note: Once your done with this, check out Part 2 for more secret codes, this time using quantum entanglement!
To most people, the idea of quantum computing is fascinating, even though most of us (myself included) don’t really understand much about it. Then again, nobody understands quantum mechanics, as Richard Feynman declared in 1965. Since then, we’ve learned some stuff, although quantum computing was pretty much completely theoretical until the early 2000’s.
Humans have wanted to send things secretly to people for a long time (important things, like banking information, passwords, dick pics). In both quantum and normal (‘classical’) computing, we use encryption to do so. The first step in encryption is getting a secret code (or “key”) that both you and the other party know, so that they can unencrypt your message. This is known as ‘key distribution’ or ‘key exchange’. This is a VERY important step, because if this secret key gets in the hands of someone else, then you’re pretty much screwed (at least according to Kirchoff and Shannon). If you can whisper the key in your friend’s ear, making this secret key isn’t so hard, but if they are far away, you have to rely on some sort of public communication line, where baddies could be listening in (known as ‘public’ key distribution).
Computing and Quantum Superposition
Before we get started, a very (very) brief intro to computing and quantum mechanics.
The fundamental difference between classical and quantum computing is that normally a computer has a memory made up of bits, a one or a zero, but a quantum computer uses qubits (pronounced Q-bits, likely relatives of Q*Bert). Qubits take advantage of quantum superposition, so they can be a one, a zero, or any probabilistic combination of the two. This doesn’t mean a qubit can be a .5 or a .75, it means it can be prepared so that when the computer uses it, there’s a 50% or 75% chance that it will be a one. Also, because the act of measuring a quantum system in general disturbs that system, quantum key distributions have a very useful and unique feature where users are able to detect the presence of an eavesdropper.
*If nothing makes sense in this paragraph, just skip it.*
The clever part about qubits is that we have many choices for what a “0” or a “1” can mean. The choice we make is called a “basis”. Let’s think about polarizers and light. If you put light through a horizontal linear polarizer, only horizontally polarized light gets through. If you put that horizontally polarized light through another polarizer with the same orientation, it all goes through. We can call that a one. If instead we try to put it through a vertical linear polarizer, none of it goes through. Call it a zero. We just constructed the “+” basis (check out the table). We take advantage of the nature of qubits when we establish two orthogonal (a.k.a perpendicular) bases (basis’s, pronounced ‘base ease’). Once you have two perpendicular bases (and two definitions of one or zero), you can define, say, the plus basis, as a superposition of combinations of the parts of the cross basis. Now that we can think about “1”s and “0”s in one basis in terms of another basis, we can take advantage of quantum superposition.
While that’s all pretty interesting, it isn’t obvious to me how that is better than boring ol bits. Well, it isn’t, necessarily. This is a common misconception. Quantum computing is a fundamentally different way to store information, so it leads to fundamentally different algorithms. It’s like if you got mad because your CDs keep getting scratched up by the record player. You just can’t expect to maximize (or even properly use) the new technology within the old framework.
For some problems, quantum computers are efficient (known as BQP), but for other things they are terrible. Lucky (or unlucky) for us, there are some math problems that are impossibly hard with normal computers (for example, factoring the product of a few really big prime numbers), that are doable with quantum computing (don’t ask me how). It’s kind of unlucky because we use tricks** like that to encrypt** information online (y’know, things like banking information, passwords, dick pics).
**click through the link to the Diffie–Hellman Key Exchange for a very cool and clear diagram or video and mathematical explanation of a standard classical cryptography technique (also make sure you understand mod).
Quantum Key Distribution: E91
Alright, enough of that. Let’s talk about quantum encryption.
This is Alice and Bob.
Alice and Bob want to talk to each other without anyone listening, so they want to make a secret key that protects their information. Unfortunately they can’t meet in person, and people are around. Normally this would be impossible, but we’ve got some quantum tricks up our sleeve. Instead of photons or other quantum particles, we’ll use coins and a funky device called a Penny or Quarter Maker (for quantum stuff, this would be analogous to, say, photons going through linear polarizers oriented 45° apart, or silver atoms going through two perpendicular Stern-Gerlach devices [check this out!]). Heads or tails is the bit, and penny or quarter is the basis.
Say Alice has her pockets full with pennies and quarters. She takes one out randomly, flips it, writes down the result, then sends it to Bob (in this analogy, maybe she glues it to a paper airplane and throws it to him. Lets say it’s a tails up penny.
She then repeats this to make a long string of coins to send to Bob.
Now here’s the quantum part. Before Bob can see what coin it was and whether it was heads or tails, it has to go through one of two machines he has: a Quarter Maker® and a Penny Maker®.
If a quarter goes into the Quarter Maker, the machine simply burns away the paper, and the quarter comes out with the same side up as it went in. If a penny goes into the Quarter Maker, the machine devours it and spits out a freshly minted quarter. However (and this is important), it randomly (randomly!) makes the quarter heads or tails side up. Same rules for a Penny Maker (except it destroys quarters and makes pennies). Got it? If you understand the rules behind these machines, you understand quantum mechanics (oh… wait not really).
So Alice sends a tails up quarter to Bob. He doesn’t know which kind she sent, so he randomly picks the Penny Maker. It goes through unscathed, and he writes down that he got a tails up penny.
Then she sends him a heads up penny. This time he picks the Quarter Maker. It devours her penny and spits out a tails up quarter. He writes that down.
She then repeats this to make a long string of coins to send to Bob. Bob picks either the Quarter or Penny Maker with every coin that Alice sends him, and writes down what gets spit out.
Alice and Bob know that they don’t have the same list of coins, so Bob publicly yells to Alice whether each coin he received was a penny or a quarter. It matches what Alice sent only when he chose the right machine to measure it with, which is only 50% of the time. Whenever they don’t match, Alice and Bob throw out the information about those coins.
With the leftover string of coin flips, they now know that they can agree not only on which are pennies and quarters, BUT ALSO on which are heads or tails. They can turn this string of heads and tails into, say, binary (tails=0, heads=1) and make their key from it. Anyone who was listening to their shouting match knows the order of coins they have, but DOESN’T know the order of heads or tails. It’s a secret!
Now, this is Eve. Eve is an eavesdropper (see what we did there?). Eve wants to know their key.
If Eve wanted to know their key, the best thing she could do would be to intercept each of the coins Alice sends to Bob, find out what it is, send it on to Bob, and hope Bob and Alice don’t notice. Unfortunately, Eve has to use a Quarter Maker or a Penny Maker to get information about the coins, just like Bob. Let’s assume that Alice and Bob are much farther away from each other than in the picture, so they can’t see what Eve is doing. Let’s say Alice sends a tails up penny, Eve randomly chooses the Penny Maker, then sends the tails up penny to Bob, who then randomly uses the Penny Maker. That means Eve has successfully eavesdropped!
Fortunately, odds are that this won’t happen with every coin. If Alice sends a tails up penny, there are three other possible combinations of choices for Eve and Bob. If Bob picks the Quarter Maker, Eve can pick the Penny Maker OR the Quarter Maker, it doesn’t matter, because Alice and Bob are going to throw that coin out anyway when they start yelling to each other. That’s two possibilities. For the final possibility, with another heads up penny from Alice, Eve chooses the Quarter Maker, which spits out a quarter, randomly heads or tails up. She sends this to Bob, who chooses the Penny Maker. In this situation, there is a 50% chance he will get a heads up penny (same as Alice) and a 50% chance he will get a tails up penny (which is wrong!). In this situation, Eve has unsuccessfully eavesdropped (she has the wrong answer) and there is a 50% chance that Bob and Alice have different answers.
All Alice and Bob need to do to check if there is an eavesdropper is to publicly compare the first few coins in their “secret” key. If there is a discrepancy, say Alice sent a tails up penny but Bob received a heads up penny, then they know that someone was eavesdropping. An error of this sort will happen ¼ of the time (it’s one of four possible combinations when Eve is eavesdropping). Because they know the chance of discovering an error, Alice and Bob can share enough of their key to be sure to any level of confidence that they aren’t being eavesdropped on (sharing 10 values from their key gives them ~95% confidence).
Of course, this doesn’t fix the eavesdropping problem, they’ll have to start over and try to get those airplanes to Bob more safely, but it’s pretty cool that they can tell someone was eavesdropping in the first place.
Pretty crazy, right? To recap: thanks to a quantum measurement effect that we mimicked with our Penny and Quarter Makers, Alice and Bob can not only establish a key or password without every communicating it out loud, but they can also check whether anyone was trying to eavesdrop. How cool is that?