By: Chris Lee
Computers have radically changed society. Shortly after the end of World War II, scientists were using computers to solve all sorts of problems. Progress was unbelievably fast. By the 1970s, the home computer was born.
Yet for all that progress, some problems are still really hard. No matter how good computers get, challenges like factoring large numbers or optimizing courier routes remain difficult.
But bits are not the only way to compute. Quantum mechanics — the rules that govern the world of atoms and molecules — can also be used to compute. And those computations are performed in a remarkably different manner.
The hope is that some day these “quantum computers” will be able to solve hard problems. But what actually are quantum computers, and how do they work?
A detailed look under the hood of a quantum computer reveals why researchers are so hopeful that these computers will be so powerful—and not powerful like a new generation of processor from Intel. No, a practical quantum computer has the potential to change the world. Companies like D-Wave, IBM, and Google, along with research labs around the world, are all racing to produce the first practical quantum computers.
What Makes a Quantum Computer Different?
To illustrate the difference between quantum and traditional computing, Daniel Lidar, a professor of physical theoretical chemistry at the University of Southern California, uses the following analogy (which I’ve modified).
Imagine searching for a black ball in a box full of white balls, and you can’t see inside the box. To find the black ball, you blindly grab a ball, examine the color, and throw it away if it isn’t black. You might grab the black ball on the first try, or you might pick it last.
The most likely outcome: You destroy the box in frustration.
Now let’s switch to a quantum algorithm. Your quantum hands reach into the box, but they don’t grab a ball. Instead, these hands hold the probabilities of having picked each ball — including the black ball. If the box has 10 balls, your quantum hands hold 10 equal probabilities.
Next, you run a quantum algorithm that increases the probability that the ball is black. Afterward, you check your hand: Disappointingly, the ball is white. You reach back into the box. But this time the probabilities are not equal: The probability of you finding the black ball is higher now than for the other balls.
It is as if the previous attempt threw away an extra white ball along with the one you found. This occurs for every attempt, so the chance of finding the black ball rapidly increases. The key to the way these probabilities change is in how quantum states—or “qubits,” in the case of computing—are manipulated.
Quantum Superposition States
Let’s break down that box-of-balls story to see how it all works.
The quantum hand reaches into the box and grabs probabilities. In traditional computing, information is stored as bits that have definite values. A bit is either a one or a zero. Checking the value of a bit doesn’t modify it in any way.
But a qubit doesn’t directly represent the value of the bit; it holds the probability of the qubit being a one or a zero. This is called a “quantum superposition state.”
When we check the value of the qubit, however, we don’t get the probability. The measurement reveals a one or a zero—the choice randomly determined from the probabilities of the superposition. Measuring sets the value of the qubit. If we measure the qubit and get a one, checking again will also result in a one.
When we reach into the box, we are actually taking a set of qubits — enough to represent all the balls. The qubits are put into a superposition state that holds the probabilities of finding each ball. Since the search is completely random, each ball is represented with equal probability.
Now we run an algorithm that increases the probability of finding the black ball.
You might ask: How can you increase a probability without sneaking a peak? The answer lies in how a qubit holds probabilities. A probability is represented by a number between zero and one. But qubits hold probability amplitudes, which can be positive or negative.
As Lidar puts it: “[T]his is where there is a real difference. There is no notion of negative probability [in classical physics], that’s meaningless…But in the quantum case, we can have [a] negative [probability] amplitude cancelling the positive [probability] amplitudes. It is through the manipulations of these interferences that we can start to understand how quantum computing can get an advantage.”
Two key points are hidden in that quote. When a negative amplitude meets a positive amplitude, the net result is something closer to zero, so the probability of that particular outcome goes down; if two positive amplitudes meet, the chance of that outcome increases. That is, we can manipulate the probability of a particular outcome without measuring the qubit. (Remember, making a measurement will destroy the superposition state.)
More important, qubits can be made to do this to themselves. When we talk of a positive amplitude meeting a negative amplitude, these amplitudes may be from the same qubit. And if that doesn’t cause your mind to bend and creak a little, nothing will.
As a result, a quantum computer can quickly reduce the probability of obtaining an incorrect answer and increase the odds of getting the correct answer. This is exactly the sort of trick a quantum computer uses to increase the probability of finding the right ball.
An Error-Prone Process
To perform a computation, the superposition state of many qubits are modified. But in between deliberate modifications, the environment also changes the superposition state. This noise is the enemy of quantum computing, destroying superposition states almost as fast as we can create them.
The result is that qubits are unreliable and prone to error. And those errors have to be discovered and corrected.
This is not trivial. As Lidar puts it: “[W]e will need to use a high degree of redundancy in order to ensure that the quantum computation can be performed correctly. So, then, what is this overhead due to encoding? Well, it could be quite severe, it could be by factors of 1,000 or 1,000,000.”
In other words, every bit of information is encoded into a small army of qubits instead of a single qubit.
How to Build a Quantum Computer
There are several basic approaches to building a quantum computer. The most common approach is much like we build computers now, called the circuit model of quantum computing.
Each program is broken into a series of specific logic operations, most of which modify probability amplitudes of one qubit, depending on the probability amplitudes of a second qubit. A circuit-based quantum computer takes in a starting set of qubits and performs each operation in the program sequentially. After running the program, the qubit states are read to obtain an answer.
IBM builds quantum computers of this sort, and you can even play with them. But it is by no means certain that IBM’s or any other circuit model will become standard. Scaling the qubit number and lifetime up to a useful size is no easy task.
Other companies, like D-Wave and Google, are also taking an interest. But their approach is quite different from that of IBM and most research labs. The most common approach to building a quantum computer is to stick close to ideas from normal computers: logic gates that perform sequential operations. But it is also possible to make computers that work without direct logic operations.
The difference between the two approaches is quite profound. In a computer that uses sequential logic, the physical layout of the computer is reasonably simple, but the sequence of operations (or program) can become long and complicated. By abandoning sequential logic, the program becomes very simple — in fact, there is almost no programming—but the physical layout becomes very challenging, because every qubit has to be connected to all the other qubits.
Canadian startup D-Wave has been offering a limited form of quantum computing for some time, but at the moment, its processors are too small to take on practical problems. The layout of the D-Wave processor doesn’t connect all the qubits to each other. As a result, it can only be used to solve some types of problems but not others.
To complicate matters, it is not possible to know from the computer’s performance that it is a quantum computer. It could instead be a very efficient traditional computer. Google and Lidar (who does not work for Google) are using a similar approach to D-Wave’s; however, the difference is that they are aiming to control how the qubits influence each other. From that, they hope to prove that this approach leads to a quantum computer.
A Problem Looking for a Quantum Solution
Most people, if they are aware of quantum computers, associate them with breaking encryption. Modern-day cryptography relies on the fact that it is very hard to find prime factors of very large numbers.
A practical quantum computer will, most likely, put an end to that. But there are less-sinister applications.
The most exciting one under development is using quantum computers to solve quantum mechanics problems. That is the application that will likely change the world.
Quantum mechanics describes the properties of materials, from the cotton in your clothes to photosynthesis in plants. Even with the most powerful traditional computers, it is pretty much impossible to calculate the properties of any molecule containing more than about 30 atoms. Instead, we take shortcuts, which don’t always work very well.
A quantum computer can be much more exact, so we can have a lot more confidence in that calculation. Scientists can imagine much more outlandish properties, like materials that cool when exposed to sunlight, and then use a quantum computer to determine the required structure. And outlandish properties that are truly impossible can be eliminated more quickly.
How Close Are We?
Quantum computers arrived in theory with the first demonstrations in the 1990s. Still, your secrets are safe, and you won’t find a quantum computer doing nefarious things to your bank account. Researchers like Lidar don’t expect a practical quantum computer for some time yet.
Lidar says that with 100 qubits in a world where there is no need for quantum error correction, “We would be able to start simulating quantum systems using quantum computers on a scale that surpasses what is possible with the most powerful classical computers.”
But researchers have a goal called, alarmingly, quantum supremacy. Despite its grandiose name, quantum supremacy is just showing that any problem beyond the capabilities of a traditional computer, even one with no practical value, can be solved on a quantum computer.
Demonstrating that quantum computers can perform as predicted is an important step, and one that no one is absolutely sure will happen. But only then can we really trust that future quantum computers may deliver on their promises.
Lidar expects to see a computer that should be capable of achieving quantum supremacy in the next 12 months. Google, in particular, seems to be aiming to achieve quantum supremacy as quickly as possible, while IBM is taking a more cautious approach.
After that, a murky but exciting future awaits us.
This column does not necessarily reflect the opinion of the editorial board or OnlineHubNG.com and its owners.
