This is the second of two articles on quantum computing. Read part one here. Both articles are part of the Science in Sci-fi, Fact in Fantasy blog series. Each week, we tackle one of the scientific or technological concepts pervasive in sci-fi (space travel, genetic engineering, artificial intelligence, etc.) with input from an expert.
Please join the mailing list to be notified every time new content is posted.
The Expert: Dan Allen
Dan Allen is a physicist and principal architect at a Bay Area sensor chip maker. He has designed lasers for the government that see through envelopes and (eek!) clothing, lit a three-story electron accelerator on fire, and created nanoparticles in a radioactive hot lab.
He is dad to his five children and husband to his drummer artist wife. You should check out his blog and follow him on Twitter.
Quantum Computing and Cryptography, Part 2: Curioser and Curioser
You survived Quantum Mechanics and Quantum Computing Part 1. You’ve been down the rabbit hole of wave mechanics and quantum phenomena. Now it’s time to go through the looking glass and see what we can do with uncertainty and entanglement.
RSA Encryption
Encryption puts a cipher on transmissions to make them unreadable. This is done on any data sent to or from a website that starts with https –the “s” stands for secure. The recipient has a key which it can use to decrypt (decode) the message. Someone intercepting the transmission that does not have the code is out of luck, because RSA encryption takes a long, long time to decipher.
Crazy thing, the RSA encryption algorithm is based on prime factoring numbers—very simple. I take two numbers, multiply them together to generate a big number. If you can figure out what factors I used, then you can crack the code. But good luck. 256 bit encryption uses a 77 digit long decimal. And you have to try just about every number up to the square root to see if it is a prime factor. Of course you can play tricks like skipping even numbers or checking to see if it is divisible by three. But even at a billion tries a second with a very powerful computer—you still need a number with like 30 some-odd zeros after it seconds to find the code. 32 years is only a billion seconds—just nine zeros. That’s not even making a dent.
Aside: It always perturbed me that when people teach factoring they let us all feel like idiots for not being able to guess the right answer, when in reality factoring is so hard that our entire internet security is based on it.
As it turns out, there is one way to factor insanely fast: Shor’s algorithm. But it requires bits which can not only be zero or one, but have an imaginary phase. To crack codes, we need quantum bits.
Quantum Bits
A quantum bit, or qubit for short, ideally has two quantum states, like energy levels or electronic spin states, or topological configurations (don’t worry, we’re not covering that). If we put the qubit in a state and don’t look at it, probe, allow anything to interact with it, ideally it should stay in that state for a long time. And the phase should just continue to evolve like that hand of a clock turning. Lifetime (T1) is how long it lasts before flipping and decoherence time (T2) is how long two qubits’ internal clocks stay in phase.
If you’ve ever studied NMR or MRI, you’ve probably heard those terms before. NMR (MRI) flips nuclear spins and listens for echoes when the atoms with magnetic moments that they’ve tipped and wound up, spring back into alignment. My multiple sclerosis was diagnosed by looking for white spots in my brain with a high energy T2 measurement. Apparently my brain makes bad quantum computer.
But that’s ok. Everything—practically everything makes a bad quantum computer. That’s because trying to set up enough qubits to run Shor’s algorithm and keep anything from interacting them is like building a house of cards with millions and millions of cards.
Luckily there is something called “quantum error correction” which allows a quantum computer to fix qubits that have gone astray. (Our computers also use error correction or cosmic rays would a crash a server about once a day.)
So how does a qubit do its magic and crack codes?
Shor’s Algorithm: Quantum Code Cracking
Because quantum bits can be in two states at once, we create a superposition state that effectively represents all numbers at once. Then we do operations on the bits in a particular sequence such that when we do look at the bits and measure them, there is high probability of getting a prime factor. Essentially, if you are a prime factor, we flip you and then amplify anything with negative values, then flip you back. We do this a lot of times and voila, when we look, we usually get a prime number. Yeah, like magic. But it’s just number theory with a twist—quantum phase.
If I show you a waveform and take the Fourier transform, I get the frequency components that show up on a stereo equalizer—the bouncing bars that indicate how much treble, mid-range or bass is in the wave. In a similar way, Shor’s algorithm takes the transform of a number and gives up peaks at all of its factors.
The trick is controlling quantum states. We’re just learning how to do that. Thousands of groups around the world are making painful progress, from atom traps in vacuum chambers, to superconductors and even defects in diamond crystals, the search for the ultimate qubit continues.
Grover’s Algorithm: Quantum “Voodoo” Searching
But wait there’s more! Suppose I have a black bag into which I’ve put four rocks—indistinguishable by touch. And somehow, as if by magic, about every other time I reach in, I get the right rock.
Grover’s algorithm is a quantum search method that uses quantum bits to represent the items to be searched. For a regular search of n items, where n could be anything from 10 to 10 billion or more, it usually takes about n/2 tries to find what you are looking for. Search one half, if it’s not there, divide the remainder in half and search that, etc.. So for a 10 billion item search it takes 5 billion tries—annoying, yeah?
The quantum search algorithm scales as as the square root of the number of items to be searched. That means a 10 billion item search only takes 100,000 tries. The search runs is 50,000 times faster!
Cool? Oh yeah. Quantum computers have the potential to revolutionize several of these types of number theory problems, but unfortunately they aren’t any better than regular computers at most tasks, so it isn’t a magic machine that computes everything faster—just searches, like searching for a code.
But wait—there is an application of quantum information that is already in use—secure code distribution using quantum entanglement. It’s the ability to send a code and know to an arbitrarily high degree of certainty that no unintended recipient intercepted it.
Quantum Key Distribution
The problem with any code is that it has a key. And you have to give that key to the recipient. How do you do that? How can you be sure that nobody has intercepted the key? Obviously if you know a key was intercepted, then you don’t use it. So the goal of any key interceptor is to get the key without anyone knowing. Like the enigma code in World War II, the Allies went to great efforts to keep the Axis from knowing that British scientists had cracked the code—even sacrificing people’s lives, so that Germany kept using it.
The secret to secure key distribution is quantum entanglement. In part 1 we introduced the idea of entangled states: two quantum systems like electrons, which started out in different states, then were allowed to exchange energy until they both got half. Or with light we can start with two photons which have equal, but opposite probability of being in either a vertical or horizontal polarization. We’ll stick with photons from here on out because these fundamental units of light energy postulated by Einstein are easier to send over a long distance in a fiber optic cable.
If Bob generates entangled photons and sends one to his love Alice, he can measure the one the he kept. Let’s say he sent eight photons. He measured the polarizations of the ones he kept: vertical = 1 and horizontal = 0. The results were 1, 0, 0, 1, 0, 1, 1, 1. If nobody intercepted any of the photons then Alice will always measure 0, 1, 1, 0, 1, 0 , 0, 0—the exact opposite. However, if some ex-flame Charles intercepts the photons and sends them on to Alice, then he has destroyed the entanglement. In this simple scheme there is no way to know if Charles measured first and sent photons with the measured polarizations on to Alice.
But, if Bob can tilt his polarizer and measure left-diagonal or right-diagonal polarization whenever he wants, and Alice as well, then Charles won’t know which question to ask the incoming photons. He can only ask one question, by orienting his polarizer vertically or diagonally. On the open channel Bob and Alice can share their orientations they chose and throw out the ones that weren’t a match. Then they can check the signal fidelity.
If Charles measured vertical and got a zero and sent out a horizontal photon, but Bob and Alice measurement diagonally, then the horizontally polarized photon has a 50:50 chance of being left-diagonal or right diagonal—it doesn’t know which it is. So 50% of the time he guesses the wrong orientation, and 50% of those times the bit he sends is completely wrong. The bit fidelity instantly drops to 75%. For a sequence with greater than 75% fidelity, Bob can go after the fact and find bits that he measured which represent his key. Then over a non-secure channel he can tell Alice which bits to look at. “Alice, look at bits number 2, 3, 5 and 8.” And that’s the code that only Alice and Bob know. (Of course, Alice has to remember to flip her bits, but that’s no problem for a clever girl like her.)
This method is used to distribute keys between banks in Zurich. Entangled photons are generated using down-conversion in a nonlinear crystal. Essentially this takes one high energy photon from a high energy laser pulse and splits it into two photons going in different directions with entangled polarizations.
Quantum key distribution is real.
Congratulations, the future is now.
Follow me and you'll never miss a post:
Please share this article:
Awesome! How far the world has come in all things cryptology. I read Cryptonomicon a few years back and that small beginning has kept burning in my head. I work at a diamond laboratory so I’ve seen, to a degree, the possibilities in diamond defects, and I’ve still only scratched the surface (though, not of the diamonds themselves).
Thank you for writing these two articles! I look forward to more from you in the future.