BLOG

Published 8 June 2016 by Zak Burkley

The Teachings of a Quantum Cat: Quantum Computers and Communication Part 1

Cats and the Internet are a winning combination. Believe it or not, this winning combination extends all the way to the world of quantum mechanics. A simple, famous, albeit somewhat cruel, physics thought experiment involving a cat in a box reveals how quantum mechanics can create new types of computing and communication.

Figure 1: The author’s cat, Matilda, fittingly in a box. Don’t worry, no cruel physics experiments were done with Matilda or any live cats.
Figure 1: The author’s cat, Matilda, fittingly in a box. Don’t worry, no cruel physics experiments were done with Matilda or any live cats.

Classical and quantum information both utilize binary, i.e., systems that can only be in two possible states. This is why computers “talk” in 0’s or 1’s. These are bits, short for binary digits. What are these 1’s and 0’s and how do we use them for information/communication? Let’s first look at it classically.

The physical realization of classical binary comes in many forms such as the magnetization direction of an atom, two specific voltages, an electrical switch, or two specific light intensities. Since magnets and electronics are stationary components these are generally used in computers where manipulating information is needed.

This is accomplished through logic gates that read 0’s and 1’s, and spit out 0’s and 1’s following rules governed by Boolean algebra (algebra only concerned with binary systems). The simplest is the NOT gate that outputs the opposite of its input. This requires only one input. Most logic gates, such as the AND or OR gate require two inputs, but still give only one output. Somewhat hard to believe, these simple logic gates can be built up to execute the extremely complex manipulations that occur in everyday computers. However, by defining letters, numbers and symbols as certain combinations of 1’s and 0’s, we can start to see how this is possible.

 

An example of how logic gates work. The simplest, NOT, takes one input, x, and inverts the value. Most gates, like the AND or OR, take two inputs and give outputs defined by a Boolean operation. For example, the AND output is simply found by multiplying the inputs. The OR output is simply the maximum of the inputs. Figure: Zak Burkley
Figure 2: An example of how logic gates work. The simplest, NOT, takes one input, x, and inverts the value. Most gates, like the AND or OR, take two inputs and give outputs defined by a Boolean operation. For example, the AND output is simply found by multiplying the inputs. The OR output is simply the maximum of the inputs.
Table 1: An example of the alphabet could be defined using 5 bits for each letter, each with their own specific combination of 1’s and 0’s.
Table 1: An example of the alphabet could be defined using 5 bits for each letter, each with their own specific combination of 1’s and 0’s.
Light “bouncing” off the walls of a curvy plastic rod. The “bouncing” is actually reflection caused by the boundary between the plastic and the surrounding air. At certain entrance angles, the light can never bounce out. This is called total internal reflection and is how light travels through fiber optic cables. Figure: Zak Burkley
Figure 3: Light “bouncing” off the walls of a curvy plastic rod. The “bouncing” is actually reflection caused by the boundary between the plastic and the surrounding air. At certain entrance angles, the light can never bounce out. This is called total internal reflection and is how light travels through fiber optic cables.

What if we want to send information? We can utilize the binary system with light intensities. Sending bright and dim pulses of light through a fiber optic cable, which follows the operational principle seen in figure 3, can then be a way to send information. A bright pulse can correspond to a 1, a dim pulse to a 0. Using the table, I could send you a message in binary based on light intensity. For example, to send the letter W would require sending 10110, which corresponds to a bright pulse, a dim pulse, two bright pulses, and then a dim pulse. I leave a more complex, but topical message for the readers to figure out below in Figure 6.

Encoding bits in the intensity of light, with higher peaks corresponding to brighter light. Sending a sequence of bright and dim pulses is then equivalent to sending bits. Therefore, sending light pulses through fiber optic cables is a way to send information. Figure: Zak Burkley
Figure 4: Encoding bits in the intensity of light, with higher peaks corresponding to brighter light. Sending a sequence of bright and dim pulses is then equivalent to sending bits. Therefore, sending light pulses through fiber optic cables is a way to send information.
Figure 5: Using Table 1, decode the binary message above!
Figure 5: Using Table 1, decode the binary message above! The solution will be revealed at the end of the article.

An important restriction on classical binary is that it can only be in one state at a time. A single binary system is in the state 0 or 1. A two-bit system is in 1 of 4 states: 00, 01, 10, or 11. For N classical bits, the system is in one of 2N possible states, but only one. In quantum mechanics, through a principle called superposition, qubits (quantum bits) can exist in all 2N states at the same time! The behavior of superposition in the quantum world is what distinguishes quantum information from classical, so let’s take a minute to understand it.

Figure 6: Schrödinger’s Cat is a thought experiment that demonstrates the strange behavior of quantum mechanics. Without measuring our “quantum” cat, it can exist in two states at once, just like quantum particles. Picture: Dhatfield (CC-BY-SA 3.0)
Figure 6: Schrödinger’s Cat is a thought experiment that demonstrates the strange behavior of quantum mechanics. Without measuring our “quantum” cat, it can exist in two states at once, just like quantum particles. Picture: Dhatfield (CC-BY-SA 3.0)

A simple, somewhat cruel, way to understand superposition is a famous thought experiment involving a cat, a box, a radioactive atomic source, a hammer, and vile of poisonous gas. Put all these elements inside the box. If an atom from the source decays, the hammer falls, smashing open the vile and killing the cat. Now, this is a very special box. There is no way to look inside, not even with the most sophisticated technology in the world. We have no clue what is going on inside. Say we pick a certain radioactive atom that only has a 50% chance of decaying in a day’s time. Therefore, when we close the box we have no idea whether the cat is dead or alive. It exists in a superposition of these two possible states, dead or alive, with a 50% chance of being in one or the other after one day time. This superposition lasts until we open the box. The moment we look inside, the superposition is destroyed as we now know whether the cat has survived this traumatic physics experiment or not.

 

Figure 7: The Stern Gerlach experiment demonstrates the existence of quantum binary. Classically, an atom should have a continuous spin distribution. This spin produces a magnetic field around the atom. Therefore, a magnet should separate the atoms into a continuous distribution. Instead, in the famous Stern-Gerlach experiment, they found only two spots. This showed the atoms were only spinning in two possible directions. When created at the furnace, the spin of the atom exists in a superposition of these two states. Like the cat, this superposition is destroyed when measured. In this case, the measurement is done by North and South magnets. Picture: Theresa Knott (CC BY-SA 3.0)
Figure 7: The Stern Gerlach experiment demonstrates the existence of quantum binary. Classically, an atom should have a continuous spin distribution. This spin produces a magnetic field around the atom. Therefore, a magnet should separate the atoms into a continuous distribution. Instead, in the famous Stern-Gerlach experiment, they found only two spots. This showed the atoms were only spinning in two possible directions. When created at the furnace, the spin of the atom exists in a superposition of these two states. Like the cat, this superposition is destroyed when measured. In this case, the measurement is done by North and South magnets. Picture: Theresa Knott (CC BY-SA 3.0)

Thankfully, physical realizations of quantum binary don’t require dead or alive cats. They can be achieved through atomic spin (See Figure 7), a two level atom, the polarization of a photon, or any two level quantum system that exists simultaneously in two states until measured. By the way, if you don’t believe something can be in two states at once, there are really cool experiments that prove it! A classic experiment that takes superposition to the extreme is the double slit experiment with electrons. In this case, the superposition is not binary. The electron has a certain probability of existing everywhere in space! Although hard to believe and accept, quantum superposition is a proven scientific fact and here to stay. Scientists are using two important consequences of quantum superposition to drive quantum information research: quantum parallelism, and entanglement.

Figure 8: (Left) Light passing through two slits produces an interference pattern on a screen. The two slits cause the light waves to constructively or destructively interfere, resulting in bright and dark spots on the screen. Constructive interference is where peaks or dips of a wave add together. Destructive interference occurs when a peak meets a dip. (Right) Quantum superposition says the electron can exist at all possible positions in space. The likelihood the electron is found at each point in space is given by a probability wave. This probability wave gives an interference pattern like a light wave. Figure: Public Domain
Figure 8: (Left) Light passing through two slits produces an interference pattern on a screen. The two slits cause the light waves to constructively or destructively interfere, resulting in bright and dark spots on the screen. Constructive interference is where peaks or dips of a wave add together. Destructive interference occurs when a peak meets a dip. (Right) Quantum superposition says the electron can exist at all possible positions in space. The likelihood the electron is found at each point in space is given by a probability wave. This probability wave gives an interference pattern like a light wave. Figure: Public Domain

As we saw, quantum superposition means N qubits exist in 2N states simultaneously. However, just like our favorite cat in a box, the second we measure this superposition, it collapses to just 1 of the 2N possible states. We are right back to the classical case with only 1 output. What’s the point of this complicated quantum superposition stuff if in the end we can only extract the same amount of output, hence info, as the classical case? This is a great question, and the trick is figuring out a way to utilize superposition such that a quantum computer can get the same result as a classical computer with less computations. This is the key behind quantum parallelism.

Unfortunately, explanations for quantum parallelism in computing also obey a “quantum two-state system;” that is, they are either very basic or quite complex. I will stick to the basic explanation, but encourage people to research and try to understand the math and logic behind some of the simplest quantum computing algorithms such as the Deutsch or Grover algorithm. Now, on to the basic explanation.

Figure 9: Quantum parallelism is analogous to taking every road on a highway at once….with some complications and subtleties. Photo: whiz-ka (CC BY 2.0)
Figure 9: Quantum parallelism is analogous to taking every road on a highway at once….with some complications and subtleties. Photo: whiz-ka (CC BY 2.0)

A lot of extremely clever mathematicians and theorists have proven computing with qubits, due to their ability to be in multiple states simultaneously, can do certain computations faster than the classical result. The simplest example is Deutsch’s algorithm, which is easy to understand if you are trying to program a vending machine. A simple test to determine if a coin is fake is to look at both sides. If one side is heads, the other tails, the coin passes through the machine for further tests of counterfeiting. However, if both sides are tails or both sides are heads, the coin is determined fake and rejected by the machine. As humans that observe a classical world, we clearly realize that we must look at both sides of the coin for this test. However, Deutsch’s algorithm reveals the unintuitive strangeness behind quantum mechanics, and how we can cleverly exploit it. Using Deutsch’s algorithm, we only need to look at one side of the coin for this test.

In more technical terms, Deutsch’s algorithm applies to binary functions that can only give two outputs, and computations that require knowledge of both these outputs in order to draw a conclusion. In our coin analogy, the two outputs are heads or tails, and if both outputs are the same the conclusion is that the coin is fake. If different outputs, the conclusion is that machine must proceed with further tests of genuineness. A classical computer would have to look at a binary function twice to determine a relationship between its two possible outputs. Deutsch’s algorithm only needs to look at the function once, making it twice as fast as a classical computer.

Another algorithm utilizing quantum parallelism is Grover’s algorithm. Much more complex than Deutsch’s, Grover is a search algorithm that can search a dataset of N values for a specific value with only approximately N1/2 operations. A classical computer would take approximately N/2. Imagine you are looking someone up in a global database where N = 7 billion, the approx. population of Earth. With Grover’s algorithm, this would take only 84,000 operations on a quantum computer versus several billion for a classical computer! Grover’s quantum algorithm is 40,000 times faster than a classical search algorithm.

Figure 10: RSA encryption protects millions of financial transactions. Photo: Maxpayne473 (CC BY-SA 4.0).
Figure 10: RSA encryption protects millions of financial transactions. Photo: Maxpayne473 (CC BY-SA 4.0).

The most mentioned quantum algorithm is Shor’s algorithm. It is a quantum algorithm that factors numbers. For example, it would find that the factors of 21 are 7 & 3. Note that 21 only has two factors since it is a product of two prime numbers. Shor’s algorithm is widely mentioned in popular media because it is directly applicable to RSA encryption. Created by Ron Rivest, Adi Shamir, and Leonard Adleman, hence the acronym RSA, RSA is a public key encryption widely used on the internet to securely send sensitive financial and personal information. Public key encryption means a key is put out in the open for everyone to see. In RSA, the key is a large number that is the product of two primes. For the public to actually utilize the key requires knowledge of these two prime factors, 7 & 3 for our case above of 21. However, for much larger numbers, finding the products is not easy. In fact, it is incredibly time consuming for classical computers. This is why the large number can be a public key. Even in the wrong person’s hands, they couldn’t crack it. It took several extremely intelligent theorists 2 years to crack a 768-bit (that is a number with 232 digits) RSA encrypted code! However, Shor’s algorithm utilizes quantum parallelism to factor numbers exponentially faster than the most efficient classical factorization method. Proof that the math is complicated, for a number of size N, Shor’s algorithm takes a time of the order (log N)2(log(log (N))(log(log(log(N))) whereas classical take time of the order Exp[1.9 * Log(N)1/3Log(Log(N))2/3]. However, it is much easier to look at a graph to see how much faster a quantum computer is at cracking RSA encryption. Comparing the two in the figure below, we see for a number with 200 digits, classical computers would take a thousand trillion times longer! For example, the code that took 2 years above classically, would only take about a nanosecond, 1/trillionth of a second, for a quantum computer!

Figure 11: Speed comparison of Shor’s algorithm vs. classical algorithm. The horizontal axis is the number of digits of the RSA encrypted public key. The vertical axis is how much faster a quantum computer would crack the RSA code compared to the best classical algorithm.
Figure 11: Speed comparison of Shor’s algorithm vs. classical algorithm. The horizontal axis is the number of digits of the RSA encrypted public key. The vertical axis is how much faster a quantum computer would crack the RSA code compared to the best classical algorithm.

We see that RSA encryption is in jeopardy with quantum computers. Since the key is public, any “quantum hacker” could quickly crack the code. Why not make the key private? Classically, there is no way to tell if there is an eavesdropper intercepting the key. If a classical message is sent through a fiber optic cable, all a hacker needs to do is recreate the sequence of dim and bright pulses. This task is easily accomplished with the right technology, and the receiver and sender have no way to know.

Can our favorite cat in the box come to the rescue here? In the next post, we see how Schrödinger’s cat is still alive and how quantum mechanics is able to send 100% secure private messages through quantum cryptography.

For the solution to the binary code from Figure 5 please click here.

Zak Burkley

Zak Burkley

Zak Burkley, Lindau Alumnus 2016, is currently pursuing a PhD in Atomic, Molecular and Optical Physics at Colorado State University. He loves the elegance and beauty behind physics, and seeing math describe the increasingly complex physical phenomena he has encountered. In his spare time, Zak enjoys spending time with his wife, his dog and cat, and cooking simple homemade meals for everyone to enjoy.