Hype drives curiosity but also causes un-necessary nuisances. Google claims the first demonstrated quantum supremacy with its 53-qubits Sycamore quantum processor that is built on superconducting circuits. This is significant because no real computers have solved a problem that traditional computer takes “forever” to solve. The random generator described in the paper is done in 200s while it will take 10,000 years, claimed by Google, to mathematically simulate the same generator by the classical computer. This is the quantum supremacy that the research community is looking for. However, don’t expect we will have a leapfrog in computing in the coming months. For more interesting problems, they are still plenty of progress needed.

Many magazines contribute the quantum breakthrough on how qubits can hold more information than a binary bit which is either zero or one only. Let’s say a qubit can hold 1 billion more information than a binary bit, a 53-qubit machine is simply equivalent to 6.6G bytes machine. I purchased a 16GB laptop 5 years ago. If you think quantum computing is about encoding more information into a single “bit”, we will miss its full potential badly. Instead of giving you a 60-second answer with all the buzzwords, we will build up the necessary foundation so we can explore the subject with greater depth.

Basically, a classical computer (the one we are using) stores information in the form of 0s and 1s called bits while a quantum computer encodes information in far richer states called qubits. While a single bit has 2 possible states, a qubit can be in any state on the surface of the sphere below.

So it seems natural to promote quantum computers as a way to design a smaller computer with higher capacity. No, in fact, scientists do not believe we will have a quantum computer as small as a laptop anytime soon. In 2018, the largest general quantum computer has 72 qubits only.

Quantum information is vulnerable to disturbance from the environment. Matters interact. Even the quantum processor holding the qubits is small, we need a lot of equipment to isolate the qubits.

For example, take a look at the IBM quantum computer that holds 50 qubits.

To isolate the environmental, the IBM quantum computer has a dilution refrigerator to cool down the quantum processor to 15 mili° Kelvin. It also contains many cables that send microwave pulses to read and to manipulate the qubits. In Quantum Physics, equipment size is not its strength. To access and control at a quantum scale, the machines usually go big rather than go small. So “bits v.s qubits” is part but not the whole story for quantum computing.

Motivation

First, we need to understand the motivation behind quantum computing. In 1981, the Nobel laureate Richard Feynman asked, “What kind of computer are we going to use to simulate physics?” In his speech,

Nature isn’t classical, dammit, and if you want to make a simulation of Nature, you’d better make it quantum mechanical, and by golly it’s a wonderful problem, because it doesn’t look so easy.

Let’s elaborate this difficulty with a real example. The fertilizer production accounts for approximately 1.2% of the world’s energy consumption. The current Haber-Bosch chemical synthesis process uses a metal catalyst to couple hydrogen with nitrogen at high temperature to form ammonia.

Unfortunately, this process consumes a lot of energy. Bacteria in the soil produces nitrogenase enzymes to pull nitrogen from the air to make ammonia at normal temperature. Scientists have been looking into this nitrogen-fixing process for a while.

However, while our computers can process petabytes of information (1,000,000 GB), it barely simulates the chemical interaction for the F cluster of the nitrogenase enzyme above. This is a very small portion of the enzyme which contains four atoms of iron and four atoms of sulfur only. As the number of atoms increases, the interactions grow exponentially and becomes too difficult for the classical method. This problem exposes a fundamental issue in our current computers, how can we speed up computation?

For example, A.I. training processes a huge amount of data. We want to parallelize the data processing as much as possible. For a double-core CPU below, we can process two tasks at a time. But even with an 8-core CPU, this is far from adequate for many AI problems.

Therefore, A.I. models are trained on GPUs (for example, the computer’s graphics card). For a high-end GPU, there are over 4K+ cores that can parallelize the same pipelines of operations over 4K+ data simultaneously.

But this strategy still has a significant limitation. For many real-life problems, the complexity grows exponentially (rather than linearly) with the number of input.

This is the reason behind the scalability issue of the fertilizer example.

If it takes an exponential amount of data to solve a problem, it is bad. Because it may need an exponential number of operations to manipulate them.

As Feynman put it:

If doubling the volume of space and time means I’ll need an exponentially larger computer, I consider that against the rules.

Data parallelization improves performance linearly so it is not a cure for problems with exponential complexity. We need new concepts to break the curse.

What do quantum computers offer? In a nutshell, entanglement and interference are two quantum phenomena integrated into the DNA of nature. Quantum computers offer them dirt cheap. We can also encode an exponential amount of information on qubits using superposition and manipulate the superposition in parallel, rather than one data at a time. This quantum parallelism allows us to solve some problems exponentially faster than existing classical algorithms. More importantly, the application of quantum computers is not limited to quantum dynamics problems. It provides solutions in areas that once thought to be too complicated. For example, Shor’s algorithm is designed to break the encryption commonly used for the Internet and considered to be one major candidate in demonstrating quantum supremacy over classical computing.

As a preview, a 64-qubit system contains

coefficients that we can encode and manipulate information already. Quantum parallelism lets us manipulate them all at once in providing parallel computations. Sounds magical but unfortunately, nature does provide a speed bump. We cannot access these coefficients directly. We access information through measurement. However, it returns a collapsed state but not the coefficient. That makes efficient algorithm designs extremely hard.

To understand it deeper, we need to know some basic knowledge of quantum mechanics.

Spin

Feel free to browse through this section at the speed you like. But understanding the counter-intuition of quantum mechanics is fun.

Many particles and atoms process magnetic behavior and can be deflected under a magnetic field. For example, when we shoot hydrogen atoms between two magnets, its trajectory will change.

In the example below, we are shooting particles towards the screen.

If we believe the spin behaves like a magnet, by observing the trajectory and its deflection, we can determine the spin of the particles, like the arrow inside the circle below.

But spin is not a magnet! If it is a magnet, the atoms should hit different points on the screen depending on the spin. Instead, the particles land on two major zones only.

(Note, the experimental settings and explanation have been simplified for easier demonstration.)

Spin has quantum behavior. The trajectory either go up or down, never sideways. i.e. the measured spin has two quantum states only, either as up spin or down spin.

Let’s explore the property of spin a little bit more. We have two black boxes that are set up to measure spin. In the first box, we measure the up spin. We set up the experiment such that all the particles exit on the right side have up spin while exit on the bottom have down spin. We feed the up spin particles into the second box to measure the up spin again. As expected, 100% of the particles exit on the right side. Being an up spin will be measured as an up spin.

We repeat the experiment except we rotate the magnet direction in the second box 180° to measure the down spin.

Without any surprise, all particles exit at the bottom. So spin up and spin down states are exclusive from each other.

Now we set up the last experiment. In the second and the fourth box below, we rotate the magnet clockwise by 90°. We term this measurement as the right spin. Interestingly, this setup comes with many surprises!

All the particles exit right in the first box have up spin. So what are the spin measurements for box 2? The experimental answer is half of particles exit to the right and half of particles exit to the bottom. It is different from what classical magnets predict. In classical mechanics, none of them should have the right spin. The second surprise is half of particles exit right and half exit bottom again in the fourth box. But, do we just filter out all the down spin particles in box 1 already? So why do we detect half of them to be down spin?

Try not to apply intuition to explain it. Intuition is developed from past experience and most people never observe objects in the quantum scale before.

So let’s start with some conspiracy theory on what is happening. Elon Musk believes we live in a simulation world. So let’s start with this concept. We are living in a computer world. All objects are created on-demand. That is the computer renders an object only if we observe it. When you leave your home, you see a man on the street. The computer pulls out a sheet of possible choices with the corresponding probabilities. For example, there is a 15% chance that the man will have green eyes and a 35% chance that he has brown eyes, etc... So when you look at his face, the computer rolls dices and determines what it finally renders according to the dices.

But let’s get some scientific opinion, namely, the Copenhagen interpretation. Let me quote from Wikipedia directly.

According to the Copenhagen interpretation, physical systems generally do not have definite properties prior to being measured, and quantum mechanics can only predict the probabilities that measurements will produce certain results. The act of measurement affects the system, causing the set of probabilities to reduce to only one of the possible values immediately after the measurement.

From this interpretation, some people explain this as if the particle lives in a private world that we have no access. The particle is in a superposition that is a linear combination of both.

But when the spin is measured, nature will make up its mind and set its state to the up spin or the down spin according to the amplitude value α. So measurements change states. In classical mechanics, our observation should be gentle enough so it should not impact the state of the particle. In quantum mechanics, measurements collapse superposition to one of the possible observed states. It is the rule of quantum dynamics. Naturally, you may ask why we have this rule. My personal answer is that it is either hardcoded as a fundamental rule in nature (indisputable) or there are some deeper Physics that need to be discovered. In fact, there are competing explanation including the many-worlds interpretation (a.k.a. parallel universe). This is not science fiction. It gets the attention of acclaimed scientists including Stephen Hawking.

The concept of superposition is the core of quantum mechanics. It is common to explain the pin is in both up and down at the same time. But I will resist this temptation because we simply reconcile the theory with our intuition. In Men In Black II, Tommy Jones does not care about the inner working of the letter sorting machine. He never opens it but the machine serves him well.

We don’t have the key to expose the whole quantum mystery yet. It is highly possible that nature sealed the door and is not accessible from outside. Or we are waiting for another smart scientist to give us the key. But it never stops Tommy Jones in using the sorter to process letters. So our focus is to develop a mathematical model for the superposition and use it to develop a quantum computer. But we are not doing it in blind faith. The mathematical model matches with experiments. As long as it models the box well, I will worry less on what exactly happens inside.

Caveats

But before explaining quantum computing in details, there is one thing I need to be upfront. We are not developing a quantum computer to replace a classical computer. Quantum computing needs new algorithms. We cannot just recompile the existing C++ programs.

One big misconception is that a quantum computer will solve all problems faster than a classical computer. This is a byproduct of overhyping the technology. This unrealistic expectation will hurt us in studying its constraints and lead us to the wrong path. Worse, it hinders us in discovering its real potential. There are many problems that quantum computing is not cost-effective, or they will not show performance advantage anytime soon. Quantum computers and classical computers will coexist and complement each other. Quantum algorithms have their limits. For example, they are unlikely to provide the exponential speedup for NP-complete problems — a common myth in quantum computing.

Fortunately, some complex problems belong to a class called BQP (bounded-error quantum polynomial time) — there is a good chance that we can find the solution in polynomial time, but there is no guarantee. Factorization, the most important part in cracking the RSA encryption, belongs to BQP. So, the success of quantum computing likely depends on what else may belong to BQP.

Classical computers are also a stiff competitor for quantum computers. We know quantum computing has great potential but we don’t have a deep understanding on what it offers that classical computing can’t. Scientists learn from quantum algorithms and introduce mathematical techniques to improve classical algorithms. In fact, it is possible to prove if no entanglement state is generated, classical algorithms can be as efficient as quantum algorithms. But we don’t know why entanglement is so important and therefore cannot uncover its full potential yet. So far we have not built a quantum computer with enough qubits to beat the classical computers.

Next

We cover the motivations of quantum computers and present some behavior that is not intuitive to us. To look further, we need to understand the superposition and the qubits more. We will develop some math on it but it will be surprisingly simple once you get familiar with the notation. In fact, many people find it so elegant that it provides an easier way to understand all these non-intuitive behaviors.

Here is the index for the whole series: