Quantum Computing in the NISQ era and beyond

What I would like to focus on instead is whether quantum computers will have widely used applications, particularly in the relatively near term. The main question is: When will quantum computers be able to solve problems we care about faster than classical computers, and for what problems?

At least in the near term quantum computers are likely to be special purpose devices, which most users will access via the cloud. When we speak of a quantum speedup, we typically mean that the quantum computer solves the problem faster than competing classical computers using the best available hardware and running the best algorithm which performs the same task. (Arguably, though, quantum technology might be preferred even if classical supercomputers run faster, if for example the quantum hardware has lower cost and lower power consumption.) In any case, we should recognize that the power of classical computers will continue to increase, with exascale systems (surpassing 10

FLOPS) expected to be available in a few years. Quantum computers are striving to catch up with a moving target, as both classical hardware and classical algorithms continually improve.

A few years ago I spoke enthusiastically about quantum supremacy as an impending milestone for human civilization [22]. I suggested this term as a way to characterize computational tasks performable by quantum devices, where one could argue persuasively that no existing (or easily foreseeable) classical device could perform the same task, disregarding whether the task is useful in any other respect. I was trying to emphasize that now is a very privileged time in the coarse-grained history of technology on our planet, and I don’t regret doing so. But from a commercial perspective, obviously we should pay attention to whether the task is useful! Quantum supremacy is a worthy goal, notable for entrepreneurs and investors not so much because of its intrinsic importance but rather as a sign of progress toward more valuable applications further down the road.

We should also bear in mind that, because of the imperfect performance of NISQ technology, it may be hard to validate that a quantum computer is really giving the right answer. That’s particularly true for the quantum simulation problems physicists are excited about. So it’s important for researchers to continue seeking better methods for verifying the output of a quantum computer.

Quantum optimizers

I have already emphasized that we don’t expect quantum computers to be able to solve efficiently worst-case instances of NP-hard problems like combinatorial optimization problems; still, it’s conceivable (though not guaranteed) that quantum devices will be able to find better approximate solutions or find such approximate solutions faster. For example, we might formulate m constraints on n bits, and seek an n-bit string which solves as many of the m constraints as possible. We may say we have solved this optimization problem exactly if we can find the maximal number k of constraints that can be satisfied simultaneously, and that we have an approximate solution if we can guarantee that the maximal number of satisfiable constraints is at least k for some k < k; the approximation ratio k/k is a measure of the quality of our approximate solution.

For some optimization problems, even finding an approximation solution is NP-hard if the approximation ratio is sufficiently close to one [23], and in those cases we don’t expect a quantum computer to be able to find the approximate solution efficiently for hard instances of the problem. But for many problems there is a big gap between the approximation achieved by the best classical algorithm we currently know and the barrier of NP-hardness. So it would not be shocking to discover that quantum computers have an advantage over classical ones for the task of finding approximate solutions, an advantage that some users might find quite valuable.

Whether that quantum advantage really exists is currently an open question, but we will soon have the opportunity to explore the question experimentally using quantum hardware. Of course, even if there is such a quantum advantage for approximate optimization, NISQ

7 technology might be inadequate for demonstrating the advantage; still, it will be fun to try it and see how well it works.

The emerging paradigm for solving optimization problems using near-term quantum technology is a kind of hybrid quantum-classical algorithm. In this scheme, we use a quantum processor to prepare an n-qubit state, then measure all the qubits and process the measurement outcomes using a classical optimizer; this classical optimizer instructs the quantum processor to alter slightly how the n-qubit state is prepared. This cycle is repeated many times until it converges to a quantum state from which the approximate solution can be extracted. When applied to classical combinatorial optimization problems, this procedure goes by the name Quantum Approximate Optimization Algorithm (QAOA) [24]. But it can also be applied to quantum problems, like finding low-energy states of many-particle quantum systems (large molecules, for example). When applied to quantum problems this hybrid quantum-classical procedure goes by the name Variational Quantum Eigensolver (VQE) [25].

Will NISQ technology running QAOA or VQE be able to outperform classical algorithms that find approximate solutions to the same problems? Nobody knows, but we’re going to try it and see how well we can do. It’s an ambitious goal, because the classical methods we use to solve these problems are well honed after decades of development. On the other hand, even if early-generation NISQ devices are not yet ready to compete with the best classical computers, experimental results might encourage our hopes that QAOA and/or VQE can surpass classical methods in the future, and so spur further technological improvements.

How quantum testbeds might help

The history of classical computing teaches us that when hardware becomes available that stimulates and accelerates the development of new algorithms. There are many examples of heuristics that were discovered experimentally, which worked better than theorists could initially explain. We can anticipate that the same thing will happen with quantum computers.

For example, theorists eventually explained why the simplex method for linear programming works well in practice [26], but only long after it had been found to be useful experimentally. A current example is deep learning [27]; we lack a good theoretical explanation for why it works as well as it does. In the quantum case, too, experiments may validate the performance of heuristic algorithms, where we don’t understand why they work. That might happen in particular for the quantum optimization algorithms we’re planning to test.

But I emphasize again that the imperfect gates in NISQ systems will severely limit their computational power, because circuits with many gates will be too noisy to give useful results. Near-term experiments will explore what we can do with of order 100 qubits, and with circuit depth (number of time steps) less than 100, maybe much less. A vibrant discussion between quantum algorithm designers and application users might point those experiments in promising directions; I hope that this article can help to facilitate and inspire that discussion.

Quantum annealing

I have emphasized 50 to 100 qubits as a coming milestone for quantum technology, but in fact we have a 2000-qubit quantum device now, the D-Wave 2000Q machine. This machine is not a circuit-based quantum computer. Rather it is what we call a quantum annealer; it

8 solves optimization problems using a different method than execution of a quantum circuit, and it often solves these problems successfully.

But as of now we don’t have a convincing theoretical argument or persuasive experimental evidence indicating that quantum annealers can really speed up the time to solution compared to the best classical hardware running the best algorithms for the same problems [28, 29]. The situation is a bit nuanced. The quantum annealer is the noisy version (with rather poor quality qubits, in the case of the D-Wave machine) of what we call adiabatic quantum computing [30]. We actually do have, for the case of noiseless qubits, a theoretical argument showing that adiabatic quantum computing is as powerful as circuit-based quantum computing [31]. However, the argument demonstrating the equivalence of adiabatic and circuit-based quantum computation applies only if the adiabatic method is executed in a form that requires a high overhead cost in additional physical qubits, which is quite different from the way quantum annealers are used today. In any event, this formal argument applies only to noiseless qubits, and (in contrast to circuit-based quantum computing), we don’t have a good theoretical argument attesting that quantum annealers are scalable. That is, for the case of noisy qubits we don’t know how to show that quantum annealers will continue to work successfully as the problem size increases, even if we are willing to accept a sizable overhead cost to enforce robustness against noise.

So far quantum annealers have been applied mostly to cases where the annealing is stoquastic — that means it might be relatively easy for a classical computer to simulate what the quantum annealer is doing [32, 33]. What’s coming soon are non-stoquastic quantum annealers, which may have greater potential for achieving speedups over what the best classical algorithms can do.

Since theorists have not settled whether quantum annealing is powerful, further experiments are needed. Experiments with quantum annealers over the next few years are likely to be quite informative. In particular, aside from the applications of quantum annealers to classical optimization problems, applications to quantum simulation problems should also be explored [34].