Quantum Computing in the NISQ Era and Beyond — TEI-tagged view

John PreskillpersName (2018date). “Quantum Computing in the NISQ Era and Beyond.” Quantum / arXivtitle·j, PasadenaplaceName.

Object of study — Near-term quantumterm·key computersterm·key with tens to hundreds of noisy qubitsterm·key.

Research question — What can noisy intermediate-scale quantumterm·key (NISQterm·dom) devices realistically achieve before full fault tolerance is available?

Contribution — Names and frames the NISQterm·dom era, assessing what noisy quantumterm·key processors of 50-100 qubitsterm·key may accomplish, the prospects for quantum advantageterm·dom, and the long road to fault-tolerant quantum computingterm·dom.

Full text — tagged

The reference list is not part of the text we hold for this paper. Our copy was extracted from the publisher's page and the bibliography did not survive that extraction, so the article below ends before its references. Nothing has been removed by us.

8 1 0 2 l u J 1 3 ] h p -[ Passage withheld — in our stored copy of this paper these characters are set one per token and run backwards, which is what a PDF extractor returns for a table or a caption printed sideways. It is not what the page of the article looks like, so we do not reproduce it. The tags cut from this paper are unaffected. ] Quantumterm·key Computing in the NISQterm·dom era and beyond John PreskillpersName Institute for Quantumterm·key Information and Matter and Walter Burke Institute for Theoretical Physics, California Institute of Technology, Pasadena CA 91125, USA 30 July 2018 Noisy Intermediate-Scale Quantumterm·key (NISQterm·dom) technology will be available in the near future. Quantumterm·key computersterm·key with 50-100 qubitsterm·key may be able to perform tasks which surpass the capabilities of today’s classicalterm·key digital computersterm·key, but noiseterm·key in quantum gatesterm·dom will limit the size of quantumterm·key circuits that can be executed reliably. NISQterm·dom devices will be useful tools for exploring many-body quantumterm·key physics, and may have other useful applications, but the 100-qubit quantumterm·key computerterm·key will not change the world right away — we should regard it as a significant step toward the more powerful quantumterm·key technologies of the future. Quantumterm·key technologists should continue to strive for more accurate quantum gatesterm·dom and, eventually, fully fault-tolerant quantum computingterm·dom.

1 Introduction Now is an opportune time for a fruitful discussion among researchers, entrepreneurs, managers, and investors who share an interest in quantumterm·key computing. There has been a recent surge of investment by both large public companies and startup companies, a trend that has surprised many quantumists working in academia. While we have long recognized the commercial potential of quantumterm·key technology, this ramping up of industrial activity has happened sooner and more suddenly than most of us expected.

In this article I assess the current status and future potential of quantumterm·key computing. Because quantumterm·key computing technology is so different from the information technology we use now, we have only a very limited ability to glimpse its future applications, or to project when these applications will come to fruition. While this uncertainty fuels optimism, our optimism should be tempered with caution. We may feel confident that quantumterm·key technology will have a substantial impact on society in the decades ahead, but we cannot be nearly so confident about the commercial potential of quantumterm·key technology in the near term, say the next five to ten years. That is the main message I hope to convey. With that said, I’m sure that vigorous discussion among all the interested parties can help light the way toward future progress.

2 Opportunities at the entanglementterm·dom frontier I am a theoretical physicist with a background in particle physics and cosmology, but for more than 20 years much of my research effort has been directed toward quantumterm·key information science. I’m drawn to this field because I feel we are now in the early stages John PreskillpersName: preskillpersName@caltech.edu, Based on a Keynote Address at Quantumterm·key Computing for Business, 5 December 2017.

Accepted in Quantumterm·key 2018-07-30, click title to verify of exploring a new frontier of the physical sciences, what we might call the complexity frontier or the entanglementterm·dom frontier. This new frontier, while different than the frontier of particle physics or cosmology, is very fundamental and exciting. Now, for the first time in human history, we are acquiring and perfecting the tools to build and precisely control very complex, highly entangled quantumterm·key states of many particles, states so complex that we can’t simulate them with our best digital computersterm·key or characterize them well using existing theoretical tools. This emerging capability will open the door to new discoveries. For a physicist like me, what is really exciting about quantumterm·key computing is that we have good reason to believe that a quantumterm·key computerterm·key would be able to efficiently simulate any process that occurs in Nature. We don’t think that’s not true for classicalterm·key (i.e., nonquantum) digital computersterm·key, which (as far as we know) can’t simulate highly entangled quantumterm·key systems. With quantumterm·key computersterm·key we should be able to probe more deeply into the properties of complex molecules and exotic materials, and also to explore fundamental physics in new ways, for example by simulating the properties of elementary particles, or the quantumterm·key behavior of a black hole, or the evolution of the universe right after the big bang.

Our confidence that exploration of the entanglementterm·dom frontier will be rewarding rests largely on two principles: (1) quantum complexityterm (our basis for thinking that quantumterm·key computing is powerful), and (2) quantum error correctionterm·mth (our basis for thinking that quantumterm·key computersterm·key are scalable to large devices solving hard problems). Underlying both of these principles is the idea of quantumterm·key entanglementterm·dom. Entanglementterm·dom is the word we use for the characteristic correlations among the parts of a quantumterm·key system, which are quite different from the correlations we encounter in everyday life. To understand the concept of entanglementterm·dom, imagine a system with many parts, for example a book which is 100 pages long. For an ordinary classicalterm·key 100-page book, every time you read another page you learn another 1% of the content of the book, and after you have read all of the pages one by one you know everything that’s in the book. But now suppose instead that it’s a quantumterm·key book, where the pages are very highly entangled with one another. Then when you look at the pages one at a time you see only random gibberish, and after you have read all the pages one by one you know very little about the content of the book. That’s because the information in the quantumterm·key book is not imprinted on the individual pages; it is encoded almost entirely in how the pages are correlated with one another. If you want to read the book you have to make a collective observation on many pages at once. That’s quantumterm·key entanglementterm·dom, the essential feature making information carried by quantumterm·key systems very different from information processed by ordinary digital computersterm·key.

3 The potential of quantumterm·key computing 3.1 Why we think quantumterm·key computing is powerful An ordinary computerterm·key processes bits, where each bit could be, say, a switch which is either one or off. But to build highly complex entangled quantumterm·key systems, the fundamental information-carrying components of a quantumterm·key computerterm·key must be quantumterm·key bits, what we call qubitsterm·key. A qubitterm·dom 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 qubitterm·dom 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 complexityterm, what springs to mind is the staggering complexity of using ordinary classicalterm·key data to describe highly entangled quantumterm·key states of Accepted in Quantumterm·key 2018-07-30, click title to verify many qubitsterm·key. Giving a complete description of all the correlations among just a few hundred qubitsterm·key 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 qubitsterm·key using classicalterm·key language.

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

(1) Quantumterm·key algorithms for classically intractable problems. First, we know of problems that are believed to be hard for classicalterm·key computersterm·key, but for which quantumterm·key 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 classicalterm·key factoring algorithm will be discovered in the future, but that would be a big surprise.

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

(3) No known classicalterm·key algorithm can simulate a quantumterm·key computerterm·key. But perhaps the most persuasive argument we have that quantumterm·key computing is powerful is simply that we don’t know how to simulate a quantumterm·key computerterm·key using a digital computerterm·key; that remains true even after many decades of effort by physicists to find better ways to simulate quantumterm·key 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 quantumterm·key computerterm·key is not unlimited. We don’t expect, for example, that a quantumterm·key computerterm·key will be able to solve efficiently the hard instances of NPhard 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. Quantumterm·key computersterm·key can speed up exhaustive search [6], but only modestly [7], so NPhard 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 quantumterm·key 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 quantumterm·key world where entanglementterm·dom has profound consequences. Dramatizing the futility of the task they pro- Accepted in Quantumterm·key 2018-07-30, click title to verify claimed: “No computerterm·key 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 classicalterm·key dammit, and if you want to make a simulation of Nature you better make it quantumterm·key mechanical, and by golly it’s a wonderful problem because it doesn’t look so easy.” Feynman had envisioned using a quantumterm·key computerterm·key to solve the quantumterm·key physics problems that physicists and chemists had failed to solve using digital computersterm·key. 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 quantumterm·key computersterm·key can provide useful solutions to hard quantumterm·key problems.

3.2 Why quantumterm·key computing is hard So why is it taking so long? What is it about quantumterm·key computing that’s so difficult? The core of the problem stems from a fundamental feature of the quantumterm·key world — that we cannot observe a quantumterm·key system without producing an uncontrollable disturbance in the system. That means that if we want to use a quantumterm·key 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 qubitsterm·key 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 qubitsterm·key so we can find the result of our computation. It is very challenging to build a quantumterm·key 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 quantumterm·key systems and scale up quantumterm·key computersterm·key using the principle of quantum error correctionterm·mth [10]. The essential idea of quantum error correctionterm·mth is that if we want to protect a quantumterm·key 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 quantumterm·key information which is encoded in a highly entangled state. Unfortunately, there is a significant overhead cost for doing quantum error correctionterm·mth — writing the protected quantumterm·key information into a highly entangled book requires many additional physical qubitsterm·key — so reliable quantumterm·key computersterm·key using quantum error correctionterm·mth are not likely to be available very soon.

4 The NISQterm·dom era unfolds 4.1 The 50-qubit barrier Even with fault-tolerant quantum computingterm·dom still a rather distant dream, we are now entering a pivotal new era in quantumterm·key technology. For this talk, I needed a name to describe this impending new era, so I made up a word: NISQterm·dom. This stands for Noisy Intermediate- Scale Quantumterm·key. Here “intermediate scale” refers to the size of quantumterm·key computersterm·key which will be available in the next few years, with a number of qubitsterm·key ranging from 50 to a Accepted in Quantumterm·key 2018-07-30, click title to verify few hundred.1 50 qubitsterm·key is a significant milestone, because that’s beyond what can be simulated by brute force using the most powerful existing digital supercomputers.2 “Noisy” emphasizes that we’ll have imperfect control over those qubitsterm·key; the noiseterm·key will place serious limitations on what quantumterm·key devices can achieve in the near term.

Physicists are excited about this NISQterm·dom technology, which gives us new tools for exploring the physics of many entangled particles. It might also have useful applications of interest to the business community, but we’re not sure about that. We shouldn’t expect NISQterm·dom is to change the world by itself; instead it should be regarded as a step toward more powerful quantumterm·key technologies we’ll develop in the future. I do think that quantumterm·key computersterm·key will have transformative effects on society eventually, but these may still be decades away. We’re just not sure how long it’s going to take.

4.2 Qubitterm·dom “quality”

I’ve emphasized the number of qubitsterm·key as a measure of how difficult it is to do the simulation of a quantumterm·key computerterm·key on a classical deviceterm·dom, but the number of qubitsterm·key isn’t the only thing we care about. We also care about the quality of the qubitsterm·key, and in particular the accuracy with which we can perform quantum gatesterm·dom — well-controlled entangling operations acting on pairs of qubitsterm·key. With the best hardware we have now for controlling trapped ions [14] or superconducting circuits [15], the error rate per gate for two-qubit gates is above the .1% level (and often much worse). Furthermore, we don’t yet know whether error rates that low can be maintained in larger devices with many qubitsterm·key; perhaps we’ll find out soon. Naively, then, and as I’ll say later this might be too naive, with these noisy devices we don’t expect to be able to execute a circuit that contains many more than about 1000 gates — that is, 1000 fundamental two-qubit operations — because the noiseterm·key will overwhelm the signal in a circuit much larger than that. That limitation on circuit size imposes a ceiling on the computational power of NISQterm·dom technology. Eventually we’ll do better, using quantum error correctionterm·mth to scale up to larger circuits. But as I’ve already emphasized, since quantum error correctionterm·mth imposes a heavy overhead cost in number of qubitsterm·key and number of gates, scaling up using quantum error correctionterm·mth is a more distant goal. When I speak of the NISQterm·dom era, I’m imagining quantumterm·key computersterm·key with noisy gates unprotected by quantum error correctionterm·mth.

There are other things we care about, too, aside from the number of qubitsterm·key and the gate error rate. The time it takes to execute a single gate is also important for setting the time scale needed for a quantumterm·key computerterm·key to solve a problem, and it is noteworthy that superconducting circuits are about a thousand times faster than ion trap quantumterm·key processors. We need to be able to prepare and measure qubitsterm·key accurately; currently the measurement error probability is about 1% for superconducting qubitsterm·key, and much better than that for trapped ions. We care about the connectivity among the qubitsterm·key — for which pairs of qubitsterm·key in our device can we perform an accurate two-qubit gate? It is also important to know how reliably we can fabricate qubitsterm·key — if we attempt to construct a many-qubit device, how many of the qubitsterm·key actually perform well enough to be useful? These considerations and others, too, should be kept in mind when we make comparisons across different quantumterm·key computing platforms.

172-qubit and 50-qubit devices, based on superconducting circuits, have been announced recently by Google and IBM, respectively.

2This “milestone” is actually a bit fuzzy, in several respects. In particular, the resources needed in a classicalterm·key simulation depend on the depth (number of time steps) of the quantumterm·key circuit, as well as on the number of qubitsterm·key [11, 12, 13].

Accepted in Quantumterm·key 2018-07-30, click title to verify 5 What I won’t say much about Before moving on to the main focus of this article, I want to include a disclaimer to avoid misunderstanding. There are some very interesting and important aspects of quantumterm·key technology that I’m not really going to talk about, but I’ll mention them so you’ll know I’m not going to talk about them.

(1) Quantum-resistant cryptography. We foresee disruptive effects of quantumterm·key computersterm·key on how we protect our privacy — the public key cryptosystems that are in widespread use today will become obsolete in the years ahead because they can be easily broken by sufficiently powerful quantumterm·key computersterm·key. We should be thinking now about how we’re going to protect our privacy in the future. One possible way is to replace our existing cryptosystems with new ones which we’re confident are resistant to attacks by quantumterm·key computersterm·key [16].

(2) Quantumterm·key key distribution, quantumterm·key networks, and quantumterm·key repeaters. We might also use traveling qubitsterm·key — most likely photons — to create shared keys that can be used for encryption and decryption. Quantumterm·key key distribution exploits the principle that you cannot eavesdrop on quantumterm·key communication without producing a detectable disturbance [17]. But we don’t yet have the technology to distribute quantumterm·key entanglementterm·dom, and hence secret key, around the world; that’s another interesting technological challenge [18]. It is also notable that, aside from applications to key exchange, a global quantumterm·key network might be used for other purposes, like sharing information among quantumterm·key devices.

(3) Quantumterm·key randomness expansion. Unlike deterministic classical devicesterm·dom, quantumterm·key devices can generate intrinsic randomness. Remarkably, this feature of quantumterm·key physics can be exploited to expand a short random seed to a much longer string of certifiably random bits, even if one distrusts the equipment used for this purpose — it suffices to assume that spacelike separated parties are unable to communicate with one another [19], or to make suitable assumptions about (quantumterm·key) computational hardness [20]. Certifiable randomness has many potential applications, for example to secure communication protocols, unbiased statistical sampling, and Monte Carlo simulations.

(4) Quantumterm·key sensing. Quantumterm·key technology has advantages for some kinds of sensing. Quantumterm·key systems can sense weak forces with better sensitivity and higher spatial resolution than other sensing technologies [21]; thus quantumterm·key sensing could have relatively near-term high-impact applications, to medicine for example.

Quantumterm·key communication, networking, randomness expansion, and sensing cannot be cleanly separated from quantumterm·key computing, because similar technological challenges are faced by all these quantum-information goals. Nevertheless, I’ll give short shrift to these topics here.

6 Quantum speedupsterm?

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

Accepted in Quantumterm·key 2018-07-30, click title to verify At least in the near term quantumterm·key computersterm·key are likely to be special purpose devices, which most users will access via the cloud. When we speak of a quantum speedupterm, we typically mean that the quantumterm·key computerterm·key solves the problem faster than competing classicalterm·key computersterm·key using the best available hardware and running the best algorithm which performs the same task. (Arguably, though, quantumterm·key technology might be preferred even if classicalterm·key supercomputers run faster, if for example the quantumterm·key hardware has lower In any case, we should recognize that the power cost and lower power consumption.) of classicalterm·key computersterm·key will continue to increase, with exascale systems (surpassing 1018 FLOPS) expected to be available in a few years. Quantumterm·key computersterm·key are striving to catch up with a moving target, as both classicalterm·key hardware and classicalterm·key algorithms continually improve.

A few years ago I spoke enthusiastically about quantum supremacyterm·dom as an impending milestone for human civilization [22]. I suggested this term as a way to characterize computational tasks performable by quantumterm·key devices, where one could argue persuasively that no existing (or easily foreseeable) classical deviceterm·dom 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 supremacyterm·dom 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 NISQterm·dom technology, it may be hard to validate that a quantumterm·key computerterm·key is really giving the right answer. That’s particularly true for the quantumterm·key simulation problems physicists are excited about. So it’s important for researchers to continue seeking better methods for verifying the output of a quantumterm·key computerterm·key.

6.1 Quantumterm·key optimizers I have already emphasized that we don’t expect quantumterm·key computersterm·key 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 quantumterm·key 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 k0 for some k0 < k; the approximation ratioterm k0/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 ratioterm is sufficiently close to one [23], and in those cases we don’t expect a quantumterm·key computerterm·key 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 classicalterm·key algorithm we currently know and the barrier of NP-hardness. So it would not be shocking to discover that quantumterm·key computersterm·key have an advantage over classicalterm·key ones for the task of finding approximate solutions, an advantage that some users might find quite valuable.

Whether that quantum advantageterm·dom really exists is currently an open question, but we will soon have the opportunity to explore the question experimentally using quantumterm·key hardware. Of course, even if there is such a quantum advantageterm·dom for approximate optimization, NISQterm·dom Accepted in Quantumterm·key 2018-07-30, click title to verify 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 quantumterm·key In this scheme, we use a technology is a kind of hybrid quantum-classical algorithm. quantumterm·key processor to prepare an n-qubit state, then measure all the qubitsterm·key and process the measurement outcomes using a classicalterm·key optimizer; this classicalterm·key optimizer instructs the quantumterm·key processor to alter slightly how the n-qubit state is prepared. This cycle is repeated many times until it converges to a quantumterm·key state from which the approximate solution can be extracted. When applied to classicalterm·key combinatorial optimization problems, this procedure goes by the name Quantum Approximate Optimization Algorithmterm (QAOA) [24]. But it can also be applied to quantumterm·key problems, like finding low-energy states of many-particle quantumterm·key systems (large molecules, for example). When applied to quantumterm·key problems this hybrid quantum-classical procedure goes by the name Variational Quantum Eigensolverterm (VQE) [25].

Will NISQterm·dom technology running QAOA or VQE be able to outperform classicalterm·key 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 classicalterm·key methods we use to solve these problems are well honed after decades of development. On the other hand, even if early-generation NISQterm·dom devices are not yet ready to compete with the best classicalterm·key computersterm·key, experimental results might encourage our hopes that QAOA and/or VQE can surpass classicalterm·key methods in the future, and so spur further technological improvements.

6.2 How quantumterm·key testbeds might help The history of classicalterm·key 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 quantumterm·key computersterm·key.

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 quantumterm·key 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 quantumterm·key optimization algorithms we’re planning to test.

But I emphasize again that the imperfect gates in NISQterm·dom 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 qubitsterm·key, and with circuit depth (number of time steps) less than 100, maybe much less. A vibrant discussion between quantumterm·key 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.

6.3 Quantumterm·key annealing I have emphasized 50 to 100 qubitsterm·key as a coming milestone for quantumterm·key technology, but in fact we have a 2000-qubit quantumterm·key device now, the D-Wave 2000Q machine. This machine is not a circuit-based quantumterm·key computerterm·key. Rather it is what we call a quantum annealerterm; it Accepted in Quantumterm·key 2018-07-30, click title to verify solves optimization problems using a different method than execution of a quantumterm·key 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 annealersterm can really speed up the time to solution compared to the best classicalterm·key hardware running the best algorithms for the same problems [28, 29]. The situation is a bit nuanced. The quantum annealerterm is the noisy version (with rather poor quality qubitsterm·key, in the case of the D-Wave machine) of what we call adiabatic quantum computingterm [30]. We actually do have, for the case of noiseless qubitsterm·key, a theoretical argument showing that adiabatic quantum computingterm is as powerful as circuit-based quantumterm·key computing [31]. However, the argument demonstrating the equivalence of adiabatic and circuit-based quantumterm·key computation applies only if the adiabatic method is executed in a form that requires a high overhead cost in additional physical qubitsterm·key, which is quite different from the way quantum annealersterm are used today. In any event, this formal argument applies only to noiseless qubitsterm·key, and (in contrast to circuit-based quantumterm·key computing), we don’t have a good theoretical argument attesting that quantum annealersterm are scalable. That is, for the case of noisy qubitsterm·key we don’t know how to show that quantum annealersterm 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 noiseterm·key.

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

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

6.4 Noise-resilient quantumterm·key circuits I’ve emphasized that eventually we are going to use quantum error correctionterm·mth to extend the size of the computations we can execute reliably using noisy quantumterm·key computersterm·key. But, because of the high overhead cost of quantum error correctionterm·mth, NISQterm·dom devices will not make use of it in the near term. Nevertheless, methods for mitigating the effects of noiseterm·key may be an important consideration during the NISQterm·dom era.

Naively one might expect that, for a generic circuit with G gates, a single fault anywhere in the circuit could cause the computation to fail; if so, then we cannot execute the circuit reliably if the error rate per gate is much larger than 1/G. However, at least for some problems and algorithms, that conclusion might be too pessimistic.

In particular, for some of the quantumterm·key simulation algorithms of interest to physicists, there are only a relatively small number of circuit locations where a faulty gate can cause the computation to fail badly. This feature could arise because the circuit has low depth, and we can tolerate a constant probability of error per qubitterm·dom in the final measurement outcome, or because the damage caused by an error occurring early in the circuit decays away by a later time. Such noise resilienceterm is characteristic of some tensor network constructions which can be invoked for solving quantumterm·key optimization problems using Variational Quantum Eigensolversterm [35, 36].

There is a substantial opportunity for experimentalists and theorists, working together over the next few years, to find better ways of making quantumterm·key circuits noiseterm·key resilient, Accepted in Quantumterm·key 2018-07-30, click title to verify and so extend the computational reach of NISQterm·dom technology. We should be wary, though, of a potential tradeoff— making a quantumterm·key circuit more noiseterm·key resilient may also make it easier to simulate classically.

6.5 Quantumterm·key deep learning Machine learning is transforming technology and having a big impact on science as well, so it is natural to wonder about the potential of combining machine learning with quantumterm·key technology. There are a variety of different notions of “quantumterm·key machine learning.” Much of the literature on the subject builds on quantumterm·key algorithms that speed up linear algebra and related tasks [37, 38], and I’ll address such applications in the ensuing subsections.

First, though, I’ll comment on the potential of quantumterm·key deep learning [39]. Deep learning itself has become a broad subject [27], but to be concrete let us contemplate a restricted Boltzmann machine. This may be regarded as a spin system in thermal equilibrium at a low but nonzero temperature, with many hidden layers of spins separating the input and output. (The word “restricted” means that there are no couplings among spins within a given layer; instead only spins in successive layers are coupled.) The system may have millions of coupling parameters, which are optimized during a training phase to achieve a desired joint probability distribution for input and output. The training may be supervised, for example the network might be taught to recognize a labeled set of photos, or unsupervised, in which case the goal is to identify patterns in an unlabeled training set of data. The quantumterm·key analog of such a machine could have a similar structure and function, but where the spins are qubitsterm·key rather than classicalterm·key bits. It may be that quantumterm·key deep learning networks have advantages over classicalterm·key ones; for example they might be easier to train for some purposes. But we don’t really know — it’s another opportunity to try it and see how well it works.

One possible reason for being hopeful about the potential of quantumterm·key machine learning rests on the concept known as QRAMterm — quantum random access memoryterm. By QRAMterm we mean representing a large amount of classicalterm·key data very succinctly, by encoding a vector with N components in just log N qubitsterm·key. But typical proposals for quantumterm·key machine learning applications are confounded by severe input/output bottlenecks. For applications to large classicalterm·key data sets one should take into account the cost of encoding the input into QRAMterm, which can nullify the potential advantages. Furthermore, the output from a quantumterm·key network is itself a quantumterm·key state; to get useful information we need to measure the state, and we can acquire no more than log N bits of classicalterm·key information in a singleshot measurement of log N qubitsterm·key.

These bottlenecks arise when we try to train a quantumterm·key network to learn about correlations in classicalterm·key data. Perhaps it is more natural to think about quantumterm·key machine learning in a setting where both the input and the output are quantumterm·key states. Hence we might expect a quantumterm·key network to have advantages over a classicalterm·key one when used, for example, to control a complex quantumterm·key system. More broadly, it seems plausible that quantumterm·key deep learning would be more powerful than its classicalterm·key counterpart when trying to learn probability distributions for which quantumterm·key entanglementterm·dom has a significant role. That is, quantumterm·key deep learning networks might be very well suited for quantumterm·key tasks, but for applications of deep learning that are widely pursued today it is unclear why quantumterm·key networks would have an advantage.

On the encouraging side, it’s worth noting that a quantumterm·key deep learning machine won’t necessarily need to be a general purpose circuit-based quantumterm·key computerterm·key. It might be a special purpose device — perhaps a quantum annealerterm, if not too noisy.

Accepted in Quantumterm·key 2018-07-30, click title to verify 6.6 Quantumterm·key matrix inversion QRAMterm has further implications for quantumterm·key algorithms. In particular, the task of matrix inversion admits an exponential quantum speedupterm, which could have many applications.

The algorithm we call HHL [40] (after the three authors who first discussed it nine years ago) takes as input a succinct representation of a very large N ×N matrix A, which has to be sufficiently sparse and well conditioned, and also as input an N -component vector |bi, encoded in QRAMterm as a quantumterm·key state of log N qubitsterm·key. The output of the quantumterm·key algorithm is (with a small error) the quantumterm·key state |A−1bi, the result of applying the inverse of the matrix A to the input vector |bi. This quantumterm·key algorithm runs in time O(log N ), an exponential speedup relative to classicalterm·key matrix inversion (for fixed error and for fixed sparsity and condition number of A).

However, aside from the caveat that the matrix A must be sparse and well conditioned, note that both the input vector |bi and the output vector |A−1bi are quantumterm·key states. Once we have the output state, we can perform measurements to learn features of the output vector A−1b, and by repeating the scheme many times we can learn about the output vector in greater detail. But if we are trying to apply this matrix inversion algorithm to classicalterm·key input data, we need to take into account the potential cost of loading that classicalterm·key data into QRAMterm, which could nullify the exponential speedup. Alternatively, loading classicalterm·key data into QRAMterm might be avoided by computing |bi on a quantumterm·key computerterm·key rather than entering it from a database.

We do have good reason to believe this quantumterm·key matrix inversion algorithm is powerful, because it solves what we call a BQP-complete problemterm. That is, any problem that can be solved efficiently with a quantumterm·key computerterm·key can be encoded as an instance of this matrix inversion problem. And a number of potentially useful applications have been suggested. For example, we can use this matrix inversion algorithm to find approximate solutions to classicalterm·key linear field equations [41, 42, 43] (after discretizing the field on a spatial lattice, and applying a suitable preconditioner). This procedure could be used, say, to solve the equations of electromagnetism in a complex three-dimensional geometry, for the purpose of optimizing the performance of an antenna.

I expect HHL to have high-impact applications eventually, but it is not likely to be feasible in the NISQterm·dom era. The algorithm may just be too expensive to be executed successfully by a quantumterm·key computerterm·key which doesn’t use error correction.

6.7 Quantumterm·key recommendation systems Another recently proposed quantumterm·key algorithm [44] provides an exponential speedup over the best currently known classicalterm·key algorithm for a useful task: making high-value recommendations. The goal is to recommend a product to a customer that the customer will probably like, based on limited knowledge of the preferences of that customer and other customers.

To formulate a simplified version of the problem, consider m customers and n products, and let P be a binary m×n preference matrix such that Pai = 1 if customer a likes product i and Pai = 0 if customer a dislikes product i. In practice we might have m ≈ 108 users and n ≈ 106 products, but the rank k of the matrix is relatively small, perhaps k ≈ 100. This small rank indicates that there are only a limited number of customer types; therefore, once we know a few of the preferences of a new customer, we can accurately recommend other products that customer will like.

An algorithm for recommendation systems has two stages. In the first stage, performed offline, a low rank approximation to the preference matrix P is constructed. In the second Accepted in Quantumterm·key 2018-07-30, click title to verify stage, performed online, a new customer reveals some preferences, and the system outputs a recommendation which that customer will like with high probability. It is this second online stage that admits a quantum speedupterm. The quantumterm·key runtime is O(poly(k)polylog(mn)), while the best classicalterm·key algorithm known requires time poly(mn) to return a high-value recommendation. Crucially, the quantumterm·key algorithm, in contrast to the classicalterm·key one, does not attempt to reconstruct the full recommendation matrix, which would take too long. Instead it samples efficiently from the low-rank approximation to P .

This is a significant quantum speedupterm for a real-world application of machine learning, encouraging the hope that other such speedups will be discovered. However, we don’t currently have a convincing theoretical argument indicating that the task performed by quantumterm·key recommendation systems (returning a high-quality recommendation in polylog(mn) time) is impossible classically.3 Formulating such an argument would strengthen our confidence that quantumterm·key computersterm·key will have a significant impact on machine learning. Here too, though, the algorithm is probably too costly to be convincingly validated during the NISQterm·dom era.

6.8 Quantumterm·key semidefinite programming Semidefinite programming is the task of optimizing a linear function subject to matrix inequality constraints. Specifically, given as input the m+1 N ×N Hermitian matrices {C, A1, A2, . . . , Am} and real numbers {b1, b2, . . . , bm}, the problem is to find a positive semidefinite N × N matrix X that maximizes tr (CX) subject to the m constraints tr (AiX) ≤ bi. Convex optimization problems of this type have widespread applications, and can be solved classically in poly(m, N ) time.

A recently discovered quantumterm·key algorithm [46, 47] finds an approximate solution to the problem in time polylog(N ), an exponential speedup. In the quantumterm·key algorithm, the output is a quantumterm·key state, a density operator ρ which approximates the optimal matrix X. This quantumterm·key state can then be measured to extract information about X, and the procedure can be repeated many times to learn about X is more detail.

However, in the analysis of the quantumterm·key algorithm one assumes the availability of an initial quantumterm·key state of a particular form, the thermal Gibbs state associated with a Hamiltonian which is a linear combination of the input matrices for the semidefinite program. Whether the exponential speedup can actually be realized, then, depends on whether this Gibbs state can be prepared efficiently using a quantumterm·key computerterm·key.

For semidefinite programs with the right structure, the efficient preparation of the Gibbs state is possible, and therefore the exponential speedup really is feasible. In particular, the quantumterm·key algorithm achieves an exponential speedup if all the input matrices for the semidefinite program have low rank, or if the corresponding Hamiltonian system thermalizes rapidly. It is not yet clear to what extent these properties apply to semidefinite programs of practical interest; clarifying that issue is an important goal for further research.

It is intriguing that the crucial step in the quantumterm·key algorithm is the preparation of a thermal state at a nonzero temperature. That may suggest that the algorithm has some intrinsic robustness against thermal noiseterm·key, or that the thermalization stage of the algorithm could be executed by quantumterm·key annealing. Conceivably, then, a quantumterm·key solver 3Note added: After this paper was submitted, Tang [45] exhibited a “quantum-inspired” classicalterm·key algorithm which returns a high-value recommendation in runtime O(poly(k)polylog(mn)); thus the quantumterm·key algorithm proposed in [44] does not in fact achieve an exponential speedup compared to the best classicalterm·key algorithm performing the same task.

Accepted in Quantumterm·key 2018-07-30, click title to verify for semidefinite programs might be within reach of NISQterm·dom technology.

6.9 Quantumterm·key simulation As I have already emphasized, we expect quantumterm·key computersterm·key to be very well suited for studying the properties of highly entangled systems of many particles. As Laughlin and Pines [8] emphasized in the statement I quoted earlier, we think that simulating such “strongly correlated” matter is a difficult computational problem, because many very good physicists have tried to solve it for decades and have not succeeded. Thus, as Feynman argued [9], the simulation of highly entangled quantumterm·key matter is the natural arena where quantumterm·key computersterm·key seem to have a clear advantage over classicalterm·key ones.

In the long term, quantumterm·key simulation using quantumterm·key computersterm·key has great potential to wield a broad influence on the world [48, 49, 50]. Advances in quantumterm·key chemistry, facilitated by quantumterm·key computing, might precipitate the design of new pharmaceuticals, and new catalysts that improve the efficiency of nitrogen fixation or carbon capture. New materials arising from quantumterm·key simulations might lead to more effective power transmission or improved collection of solar energy. We probably lack the imagination to anticipate the most transformative discoveries which will flow from more powerful quantumterm·key simulators. But this promise is not so likely to be fulfilled in the NISQterm·dom era, because quantumterm·key algorithms for accurately simulating large molecules and exotic materials may be too expensive to succeed without error correction.

Classicalterm·key computersterm·key are especially bad at simulating quantumterm·key dynamics — that is, predicting how a highly-entangled quantumterm·key state will change with time. Quantumterm·key computersterm·key have a big advantage for that task, and physicists hope to learn interesting things about quantumterm·key dynamics using NISQterm·dom technology in the relatively near term. It is instructive to recall that the theory of classicalterm·key chaos (the extreme sensitivity to initial conditions in classicalterm·key dynamical systems, which accounts for our inability to predict the weather more than two weeks out) advanced rapidly in the 60s and 70s after it became possible to simulate chaotic dynamical systems using classicalterm·key computersterm·key. We may anticipate that the emerging ability to simulate chaotic quantumterm·key systems (those in which entanglementterm·dom spreads very rapidly) will promote advances in our understanding of quantumterm·key chaos. Valuable insights might already be gleaned using noisy devices with of order 100 qubitsterm·key.

6.10 Digital vs. analog quantumterm·key simulation Having emphasized the potential value of simulating quantumterm·key dynamics, I should comment about the distinction between analog and digital quantumterm·key simulation. When we speak of an analog quantum simulatorterm we mean a system with many qubitsterm·key whose dynamics resembles the dynamics of a model system we are trying to study and understand. In contrast, a digital quantum simulatorterm is a gate-based universal quantumterm·key computerterm·key which can be used to simulate any physical system of interest when suitably programmed, and can also be used for other purposes.

Analog quantumterm·key simulation has been a very vibrant area of research for the past 15 years, while digital quantumterm·key simulation with general purpose circuit-based quantumterm·key computersterm·key is just now getting started. But some of the same experimental platforms, for example trapped ions and superconducting circuits, can be used for both purposes. Analog quantum simulatorsterm have been getting notably more sophisticated, and are already being employed to study quantumterm·key dynamics in regimes which may be beyond the reach of classicalterm·key simulators [51, 52]. But analog quantum simulatorsterm are hampered by imperfect control — the actual quantumterm·key system in the lab only crudely approximates the model Accepted in Quantumterm·key 2018-07-30, click title to verify system of interest. For that reason, analog simulators are best suited for studying features that physicists call universal, properties which are relatively robust with respect to introducing small sources of error. A major challenge for research using analog quantum simulatorsterm is identifying accessible properties of quantumterm·key systems which are robust with respect to error, yet are also hard to simulate classically.

We can anticipate that analog quantum simulatorsterm will eventually become obsolete. Because they are hard to control, they will be surpassed some day by digital quantum simulatorsterm, which can be firmly controlled using quantum error correctionterm·mth. But because of the hefty overhead cost of quantum error correctionterm·mth, the reign of the analog quantum simulatorterm may persist for many years. Therefore, when seeking near-term applications of quantumterm·key technology, we should not overlook the potential power of analog quantum simulatorsterm.

6.11 Quantumterm·key games Advances in classicalterm·key computing launched a new world of digital games, touching the lives of millions and generating billions in revenue. Could quantumterm·key computersterm·key do the same?

Physicists often say that the quantumterm·key world is counter-intuitive because it is so foreign to ordinary experience. That’s true now, but might it be different in the future? Perhaps kids who grow up playing quantumterm·key games will acquire a visceral understanding of quantumterm·key phenomena that our generation lacks. Furthermore, quantumterm·key games could open a niche for quantumterm·key machine learning methods, which might seize the opportunity to improve game play in situations where quantumterm·key entanglementterm·dom has an essential role.

7 The daunting climb to scalability I’ve already emphasized repeatedly that it will probably be a long time before we have fault-tolerantterm·key quantumterm·key computersterm·key solving hard problems. Nevertheless, we can make significant progress in the near term by developing better methods and hardware for implementing quantum error correctionterm·mth, guided by relatively small-scale experiments with quantumterm·key error-correcting codes. We expect that, in the next few years, enhanced control of an error-corrected qubitterm·dom will be demonstrated convincingly in the lab for the first time. Further near-term experiments exploring quantum error correctionterm·mth are bound to advance our understanding of noiseterm·key in quantumterm·key devices, and to suggest more effective techniques for noiseterm·key mitigation [53, 54] and device validation [55].

Nevertheless, solving really hard problems (like factoring numbers which are thousands of bits long) using fault-tolerant quantum computingterm·dom is not likely to happen for a while, because of the large number of physical qubitsterm·key needed. To run algorithms involving thousands of protected qubitsterm·key we’ll need a number of physical qubitsterm·key which is in the millions, or more [56]. That’s a very large leap from where we will be for the next few years, with of order a hundred qubitsterm·key. Crossing the “quantum chasmterm,” from hundreds of physical qubitsterm·key to millions of physical qubitsterm·key, is going to take some time, but we’ll get there eventually.

Throughout the NISQterm·dom era it will remain important to strive for lower gate error rates in the various quantumterm·key platforms. With more accurate quantum gatesterm·dom, quantumterm·key computersterm·key operating without error correction will be able to go further by executing larger circuits. Better gates will also lower the overhead cost of doing quantum error correctionterm·mth when we eventually move on to fault-tolerant quantum computingterm·dom in the future. (Microsoft’s current program [57], focused on advancing topological quantumterm·key computing, is founded on the notion that much lower gate error rates will pay offhandsomely sometime in the Accepted in Quantumterm·key 2018-07-30, click title to verify future.) It is important to realize that we will need significant advances — in basic science as well as in systems engineering — to attain fully scalable fault-tolerantterm·key quantumterm·key computersterm·key. Therefore, the challenge of scalability poses compelling problems for scientists and engineers. Because we still have so far to go, new insights, developments, and innovations have the potential to substantially alter the long-term outlook.

8 Summary This article is the result of an uneasy compromise. I hope the content provides a useful overview for technically informed readers, but I’ve tried to minimize jargon and technical details which could be distracting or off-putting for a broader audience. I have not attempted to compile a comprehensive list of references; instead I have referred to just a few papers that amplify or clarify points I wanted to make, or that might provide instructive further reading. I apologize to many colleagues whose highly valuable contributions are not properly acknowledged here. Let me now summarize the main points I’ve tried to convey. Now is a privileged time in the history of science and technology, as we are witnessing the opening of the NISQterm·dom era (where NISQterm·dom = noisy intermediate-scale quantumterm·key). We’ll soon have the opportunity to experiment with NISQterm·dom technology to see what it can do. Perhaps NISQterm·dom will allow us to speed up the time to solution for problems of broad interest in the near future, but we don’t know yet whether that will happen. We have some specific ideas of things we’d like to try, such as hybrid quantum-classical algorithms for solving optimization problems, both classicalterm·key and quantumterm·key ones. We can expect that, once we have quantumterm·key computersterm·key to experiment with, the develop- ment of quantumterm·key algorithms will accelerate. Perhaps new heuristics will be discov- ered for solving useful problems, although we may not be able to explain why these heuristics work so well, at least not right away. Although we probably won’t be able to use full-blown quantum error correctionterm·mth to protect NISQ-era devices from noiseterm·key, we should design near-term quantumterm·key algorithms with noise resilienceterm in mind. Clever design of noise-resilient algorithms may extend the computational power of NISQterm·dom devices. Classicalterm·key computersterm·key are especially bad at simulating the dynamics of highly entangled many-particle quantumterm·key systems; therefore quantumterm·key dynamics is a particularly promis- ing arena where quantumterm·key computersterm·key may have a significant advantage over classicalterm·key ones. We should continue to focus on building quantumterm·key hardware with lower gate error rates. Improved quantum gateterm·dom accuracy will lower the overhead cost of quantum error correctionterm·mth when it is eventually implemented. In the nearer term, more accurate gates will allow us to execute larger quantumterm·key circuits, and so extend the power of NISQterm·dom technology. NISQterm·dom is not likely to change the world all by itself. Instead, the primary goal for near- term quantumterm·key platforms should be to pave the way for bigger payoffs which will be realized by more advanced quantumterm·key devices down the road. Accepted in Quantumterm·key 2018-07-30, click title to verify 15 The truly transformative quantumterm·key technologies of the future are probably going to have to be fault tolerantterm·key, and because of the very hefty overhead cost of quantum error correctionterm·mth, the era of fault-tolerant quantum computingterm·dom may still be rather distant. No one really knows how long it will take to get there. As the quantumterm·key community eagerly seizes the impending opportunity to experiment with NISQterm·dom devices, we must not lose sight of the essential longer-term goal: hastening the onset of the fault- tolerantterm·key era. I’ve adopted a cautionary stance in these remarks, because I think we should face the onset of the NISQterm·dom era with well-grounded expectations. But please don’t misunderstand me — like many of my colleagues, I’m eagerly anticipating the discoveries that will ensue as the NISQterm·dom era unfolds over the next few years. Quantumterm·key technology is rife with exhilarating opportunities, and surely many rousing surprises lie ahead. But the challenges we face are still formidable. All quantumists should appreciate that our field can fulfill its potential only through sustained, inspired effort over decades. If we pay that price, the ultimate rewards will more than vindicate our efforts. Acknowledgments This article is based on a Keynote Address delivered at Quantumterm·key Computing for Business on 5 December 2017. I thank Matt Johnson for organizing this stimulating meeting and inviting me to participate. My remarks here have been influenced by discussions with many colleagues, too many to list. But I’ve especially benefited from insights due to Scott Aaronson, Sergio Boixo, Fernando Brandão, Elizabeth Crosson, Toby Cubitt, Eddie Farhi, Steve Flammia, David Gosset, Daniel Gottesman, Stephen Jordan, Jordan Kerenidis, Isaac Kim, Seth Lloyd, Shaun Maguire, Oskar Painter, David Poulin, Peter Shor, Brian Swingle, Matthias Troyer, Umesh Vazirani, and Thomas Vidick. Some of this work was done while I attended the 2017 program on Quantumterm·key Physics of Information at the Kavli Institute for Theoretical Physics (KITP). I gratefully acknowledge support from ARO, DOE, IARPA, NSF, and the Simons Foundation. The Institute for Quantumterm·key Information and Matter (IQIM) is an NSF Physics Frontiers Center.