Quantum Computing in the NISQ era and beyond

Why we think quantum computing is powerful

An ordinary computer processes bits, where each bit could be, say, a switch which is either one or off. But to build highly complex entangled quantum systems, the fundamental information-carrying components of a quantum computer must be quantum bits, what we call qubits. A qubit can be realized physically in many different ways. It can be carried by a single atom, or a single electron, or a single photon (a particle of light). Or a qubit can be carried by a more complicated system, like a very cold superconducting electrical circuit in which many electrons are moving.

When we speak of quantum complexity, what springs to mind is the staggering complexity of using ordinary classical data to describe highly entangled quantum states of

2 many qubits. Giving a complete description of all the correlations among just a few hundred qubits may require more bits than the number of atoms in the visible universe. It will never be possible, even in principle, to write that description down, or to faithfully describe the processing of a few hundred qubits using classical language.

This apparently extravagant complexity of the quantum world, though highly suggestive, does not by itself ensure that quantum computers are more powerful than classical ones. But we have at least three good reasons for thinking that quantum computers have capabilities surpassing what classical computers can do.

(1) Quantum algorithms for classically intractable problems. First, we know of problems that are believed to be hard for classical computers, but for which quantum algorithms have been discovered that could solve these problems easily. The best known example is the problem of finding the prime factors of a large composite integer [1]. We believe factoring is hard because many smart people have tried for many decades to find better factoring algorithms and haven’t succeeded. Perhaps a fast classical factoring algorithm will be discovered in the future, but that would be a big surprise.

(2) Complexity theory arguments. The theoretical computer scientists have provided arguments, based on complexity theory, showing (under reasonable assumptions) that quantum states which are easy to prepare with a quantum computer have superclassical properties; specifically, if we measure all the qubits in such a state we are sampling from a correlated probability distribution that can’t be sampled from by any efficient classical means [2, 3].

(3) No known classical algorithm can simulate a quantum computer. But perhaps the most persuasive argument we have that quantum computing is powerful is simply that we don’t know how to simulate a quantum computer using a digital computer; that remains true even after many decades of effort by physicists to find better ways to simulate quantum systems.

It’s a remarkable claim — one of the most amazing ideas I’ve encountered in my scientific life — that there is a distinction between problems that are classically hard and problems that are quantumly hard. And it is a compelling challenge to understand better what problems are classically hard but quantumly easy [4, 5]. We should recognize in particular that the power of a quantum computer is not unlimited. We don’t expect, for example, that a quantum computer will be able to solve efficiently the hard instances of NP-hard problems like the traveling salesman problem. For such hard combinatorial search problems we probably can’t do much better than exhaustively searching for a solution. Quantum computers can speed up exhaustive search [6], but only modestly [7], so NP-hard problems are likely to be quantumly hard as well as classically hard.

For a physicist seeking problems which are classically hard and quantumly easy, the natural place to look is the task of simulating a many-particle quantum system. As two great physicists, Bob Laughlin and David Pines, put it some years ago [8], we have a “theory of everything that is relevant to ordinary life.” We have high confidence this theory is correct, and we can write down the equations precisely — they are the equations that describe how atomic nuclei and electrons interact electromagnetically. But we can’t solve those equations. And so as Laughlin and Pines put it: “We have a theory of everything only to discover that it has revealed exactly nothing about many things of great importance.” Those things of importance they envisaged are the situations in the quantum world where entanglement has profound consequences. Dramatizing the futility of the task they pro-3 claimed: “No computer existing, or that will ever exist, can break this barrier” of solving the equations describing many entangled particles.

But in fact, years before Laughlin and Pines wrote these words, the physicist Richard Feynman had articulated a rebuttal [9]. As Feynman put it: “Nature isn’t classical dammit, and if you want to make a simulation of Nature you better make it quantum mechanical, and by golly it’s a wonderful problem because it doesn’t look so easy.” Feynman had envisioned using a quantum computer to solve the quantum physics problems that physicists and chemists had failed to solve using digital computers. Laughlin and Pines knew well that Feynman had made this proposal years earlier, but had dismissed his idea as impractical. Now, some 35 years after Feynman’s proposal, we’re just beginning to reach the stage where quantum computers can provide useful solutions to hard quantum problems.

Why quantum computing is hard

So why is it taking so long? What is it about quantum computing that’s so difficult? The core of the problem stems from a fundamental feature of the quantum world — that we cannot observe a quantum system without producing an uncontrollable disturbance in the system. That means that if we want to use a quantum system to store and reliably process information, then we need to keep that system nearly perfectly isolated from the outside world. At the same time, though, we want the qubits to strongly interact with one another so we can process the information; we also need to be able to control the system from the outside, and eventually read out the qubits so we can find the result of our computation. It is very challenging to build a quantum system that satisfies all of these desiderata. It has taken many years of development in materials and control and fabrication to get where we are now.

Eventually we expect to be able to protect quantum systems and scale up quantum computers using the principle of quantum error correction [10]. The essential idea of quantum error correction is that if we want to protect a quantum system from damage then we should encode it in a very highly entangled state; like that 100-page book I described earlier, this entangled state has the property that the environment, interacting with parts of the system one at a time, is unable to glimpse the encoded information and therefore can’t damage it. Furthermore, we’ve understood in principle how to process quantum information which is encoded in a highly entangled state. Unfortunately, there is a significant overhead cost for doing quantum error correction — writing the protected quantum information into a highly entangled book requires many additional physical qubits — so reliable quantum computers using quantum error correction are not likely to be available very soon.