Quantum computing - Little, Big Science : Little, Big Science

Quantum computers [1]. We have all heard this term before. In every online discussion on the subject, myths and horror stories arise about how these mysterious miracle boxes will rapidly perform calculations we cannot even dream of, break all the encryption in the world, and generally usher us into a new and wondrous age of computing. But how much of this is actually true, and what exactly are quantum computers?

Before we jump into the heart of the matter, remember that there is a reason quantum computers—like everything quantum—are shrouded in confusion and mystery. Evolution did not equip us with the intuition needed to understand quantum theory. Quantum phenomena occur on scales that can be explored only with the best technology of the past few decades, and they appear to contradict common sense [2]. In the quantum world, concepts such as “impossible” or “cause and effect” become far more flexible than in the approximate picture of reality our senses provide in everyday life.

So what are quantum computers? In one sentence, they are computers that use specific quantum phenomena to perform computations. That is a bold statement, and the rest of this article is devoted to explaining more precisely what it means.

To answer, let’s start with classical computers. Mathematically, a computer consists of two components: bits [3] and logical gates that manipulate those bits in specific ways (for example, an AND gate, which receives two bits and returns 1 if and only if both are 1). We think of a bit as a box containing the value 0 or 1, and it is important to note that the bit is the box itself, not the value inside. Bits are essentially memory—our ability to store a value over time. The value inside the box is called the state of the bit. With bits and a relatively small set of gate types, we can carry out essentially any kind of computation.

A quantum computer is defined in exactly the same way, except that the bit is replaced by a strange entity (whose nature we will soon explore) called a “qubit,” and the logical gates are replaced by quantum gates—gates that manipulate qubits. The qubit is therefore the basic unit of information that distinguishes quantum from classical computing.

Like the bit, the qubit [4] is (metaphorically) a box that contains a value. A good example of a qubit is an electron. Electrons have a property called spin [5] which, unlike continuous properties such as velocity, can take only two values: up or down. To maintain the analogy to bits, these values are labeled zero and one. Now the quantum phenomena come into play: although an electron can be in only one of the two spin states when we measure it, as long as we have not measured it, it may be in a special state called a “quantum superposition” [6] of the two states.

There are many popular explanations of superposition. Some say the particle has not yet “decided” its spin and that measurement forces it to choose. Others claim that each measurement splits the universe into two: one where spin-up is measured and one where spin-down is measured. Additional explanations may involve boxes and cats. These stories are intriguing, but they are philosophical interpretations, not physical explanations, and there is no known experiment that can decide which, if any, is more correct (in his vivid phrasing, the legendary physicist Wolfgang Pauli dubbed such interpretations “Not even wrong” [7]). To understand quantum computing, it is better to think of superposition mathematically and precisely: if we measure a qubit, there is some probability of obtaining zero and some probability of obtaining one, and after measurement, the qubit collapses to the observed state and stays there unless something interacts with it to change that state.

Things become more interesting (and much more complicated!) when we consider systems with more than one qubit. Then we encounter an intriguing phenomenon called “quantum entanglement” [8]. To understand it, let’s look at a simple example. Just as a single qubit is in superposition between zero and one, a two-qubit system is in superposition among four possibilities: 00, 01, 10, 11. Suppose we create two qubits in an equal superposition of the states 00 and 11 (that is, if we measure the system, there is a 50% chance of obtaining 00 and a 50% chance of obtaining 11). Now give Alice one of the qubits and send her to the other side of the galaxy, and only after she arrives do we measure the qubit that stayed with us and find it is 0. When Alice began her journey, her qubit was in a state where a measurement would yield 0 or 1 with equal probability. But now it is not. By measuring our qubit and collapsing it to 0, we have caused Alice’s qubit to collapse to 0 as well, because the system must collapse to a state where the two qubits match!

This is quantum entanglement—a phenomenon with no parallel in the classical world. No classical manipulation on one bit can instantaneously change another bit on the other side of the galaxy.

Some of you may ask: “Wait, an instantaneous change in a qubit across the galaxy? Doesn’t that violate the rule that nothing happens faster than light?” No. The key is that no information travels faster than light. Even if Alice knows in advance that we will measure our qubit, she cannot deduce anything about hers from that. She knows it has collapsed to 0 or 1, but until we tell her our result, she still assigns a 50% chance to each. We can of course tell her, but that information cannot be conveyed faster than light. Entanglement is strange, but it does not break the laws of physics as we know them.

Entanglement is central to many quantum algorithms, and together with another phenomenon called “interference” enables computations we do not know how to perform with classical computers—the most famous example being the rapid factoring of numbers into primes.

This is only one viewpoint on quantum computing. There are other quantum phenomena we are just beginning to harness for computation. Nonetheless, remember that this is precisely the difference between quantum and classical computers: machines that exploit nature to compute very specific things quickly—things we cannot compute as quickly with classical devices. This is a fascinating computational model, but it is nothing more than what is described above. It is a common mistake to think a quantum computer can parallelize computations in ways classical computers cannot, or that running any computation on a quantum computer automatically makes it faster. The truth is we are far from fully understanding these machines. In fact, no one yet knows whether quantum computers are truly faster. No one knows whether there exists a problem that cannot be solved on a classical computer in the same time we can solve it on a quantum computer—and this is one of the most important open questions in the field.

English editing: Elee Shimshoni

References:

By:

Shai Wyborski, PhD

Advertisement