Quantum Computing in the NISQ era and beyond

John Preskill

Source-linked AI summary

Quantum Computing in the NISQ era and beyond

John Preskill

arXiv:1801.00862v3Jan 2, 2018quant-phcond-mat.str-el

TL;DR

Quantum computing’s future applications and near-term commercial potential remain difficult to predict. This article assesses the technology’s status and prospects, concluding that quantum dynamics is especially promising while improved gate accuracy is needed to extend NISQ capabilities.

Problem
Quantum computing’s future applications and near-term commercial potential are difficult to predict, limiting confidence about its societal and commercial impact.
Method
The article assesses the current status and future potential of quantum computing across prospective applications and technological requirements.
Results
Quantum dynamics is a particularly promising arena for significant quantum advantage, while more accurate gates could enable larger circuits and extend NISQ technology’s power.
Takeaways & Limitations
NISQ computers should be regarded as a step toward more powerful quantum technologies, with quantum error correction eventually enabling protection and scale-up.
Takeaways & Limitations
Current two-qubit gate error rates exceed 0.1%, and it remains uncertain whether such accuracy can be maintained in larger devices.

Abstract

from arXiv · show

Noisy Intermediate-Scale Quantum (NISQ) technology will be available in the near future. Quantum computers with 50-100 qubits may be able to perform tasks which surpass the capabilities of today's classical digital computers, but noise in quantum gates will limit the size of quantum circuits that can be executed reliably. NISQ devices will be useful tools for exploring many-body quantum physics, and may have other useful applications, but the 100-qubit quantum computer will not change the world right away --- we should regard it as a significant step toward the more powerful quantum technologies of the future. Quantum technologists should continue to strive for more accurate quantum gates and, eventually, fully fault-tolerant quantum computing.

1 Introduction

The article assesses quantum computing’s current status and future potential amid unexpectedly rapid industrial activity, while emphasizing uncertainty about applications and timelines and urging cautious optimism.

Motivation: Quantum-computing investment by large public companies and startups has surged sooner and more suddenly than many academic quantum researchers expected.This industrial activity motivates discussion among researchers, entrepreneurs, managers, and investors interested in quantum computing.
Contribution: The article assesses quantum computing’s current status and future potential, but limited ability to foresee applications and timelines makes cautious optimism appropriate.Quantum computing differs substantially from current information technology, constraining projections about when applications will emerge.

2 Opportunities at the entanglement frontier

Quantum computing opens an entanglement frontier by enabling precise control of highly entangled many-particle states beyond the reach of classical simulation. Its promise rests on quantum complexity and quantum error correction, supporting deeper study of nature and scalable quantum devices.

The entanglement frontier: Quantum technologies are beginning to create and precisely control highly entangled many-particle states too complex for the best digital computers to simulate.This emerging frontier is described as fundamental and distinct from particle physics and cosmology.
Scientific opportunities: Quantum computers may efficiently simulate any process occurring in nature, unlike classical computers, which may not simulate highly entangled quantum systems.This capability could enable deeper investigations of complex molecules and exotic materials.
Foundations: The case for exploring the entanglement frontier rests on quantum complexity and quantum error correction.Quantum complexity motivates quantum computing’s power, while quantum error correction supports scalability to large devices solving hard problems.

3 The potential of quantum computing

Quantum computers may surpass classical capabilities through quantum algorithms, complexity-theoretic advantages, and the absence of known efficient classical simulations. Their most natural potential lies in simulating many-particle quantum systems, though building such machines requires isolation and quantum error correction.

Reasons for quantum advantage: Quantum algorithms may efficiently solve problems believed hard for classical computers, including factoring large composite integers.The text notes that factoring is believed hard because decades of effort have not produced better classical algorithms, although a future breakthrough remains possible.
Reasons for quantum advantage: Complexity theory suggests efficiently prepared quantum states can produce correlated probability distributions that efficient classical methods cannot sample.This conclusion holds under reasonable assumptions when all qubits in such a state are measured.
Reasons for quantum advantage: No known classical algorithm efficiently simulates a quantum computer despite decades of efforts to improve digital simulation methods.The text presents this absence as its most persuasive argument that quantum computing is powerful.
Many-particle simulation: Simulating many-particle quantum systems is a natural target because physicists and chemists have struggled to solve these problems with digital computers.The passage frames this as the setting where problems may be classically hard yet quantumly easy.
Implementation challenges: Quantum computing is difficult because observing quantum systems causes uncontrollable disturbance, requiring near-perfect isolation alongside strong qubit interactions.The tension between isolation and interaction is identified as a core challenge for storing and reliably processing information.
Implementation challenges: Quantum error correction could protect quantum systems by encoding information in highly entangled states that environmental interactions cannot easily reveal.The passage presents error correction as the principle expected to enable protection and scaling.

4 The NISQ era unfolds

The NISQ era concerns near-term quantum computers with roughly 50 to a few hundred qubits, whose imperfect control will limit achievable computations. These devices will enable exploration of many-body physics and may have applications, but primarily represent a step toward future, more powerful quantum technologies.

NISQ technology: NISQ denotes Noisy Intermediate-Scale Quantum technology, referring to near-term devices with 50 to a few hundred qubits.The term emphasizes both device size and imperfect control over qubits.
NISQ technology: 50 qubits is significant because it exceeds what the most powerful existing digital supercomputers can simulate by brute force.The milestone is qualified because classical simulation resources also depend on circuit depth.
NISQ technology: Noise from imperfect qubit control will seriously limit what NISQ devices can achieve in the near term.Quantum-gate accuracy is a key concern alongside qubit count.
Potential applications: NISQ devices will provide new tools for exploring the physics of many entangled particles and may have useful business applications, though those applications remain uncertain.The passage cautions against assuming immediate broad impact.
Hardware requirements: Superconducting circuits execute gates about a thousand times faster than ion-trap quantum processors, while superconducting-qubit measurement error probability is about 1%.Gate duration and accurate qubit preparation and measurement also matter beyond qubit count and gate error rate.

5 What I won’t say much about

This section briefly identifies important quantum-technology topics that the article will not treat in depth. These include quantum-resistant cryptography, quantum communication and networking, randomness expansion, and quantum sensing, despite shared technological challenges with quantum computing.

Scope disclaimer: Quantum communication, networking, randomness expansion, and sensing share technological challenges with quantum computing but receive only brief treatment in this article.The author presents this as a deliberate limitation of the article’s scope.
Quantum-resistant cryptography: Quantum computers will eventually undermine today’s widely used public-key cryptosystems, motivating migration to cryptography resistant to quantum attacks.The section urges forward planning to protect privacy with new quantum-resistant cryptosystems.
Quantum key distribution, networks, and repeaters: Quantum key distribution uses traveling qubits, likely photons, to establish encryption keys because eavesdropping causes detectable disturbance.Global distribution of quantum entanglement and secret keys remains an unresolved technological challenge.
Quantum randomness expansion: Quantum devices can expand a short random seed into a longer string of certifiably random bits, even when the equipment is not trusted.This requires assumptions such as no communication between spacelike separated parties or suitable quantum-computational assumptions.
Quantum sensing: Quantum sensing can detect weak forces with greater sensitivity and spatial resolution than other sensing technologies, potentially enabling near-term medical applications.The section presents quantum sensing as a topic receiving only brief treatment here.

6 Quantum speedups? · 6.1 Quantum optimizers · 6.2 How quantum testbeds might help

The paper asks when quantum computers will deliver useful speedups, while emphasizing that near-term NISQ devices face validation and noise limitations. Quantum optimizers and testbeds may nevertheless reveal approximate advantages, hybrid algorithms, and experimentally discovered heuristics.

6 Quantum speedups?: Quantum speedup means solving a problem faster than the best available classical hardware and algorithm performing the same task.Near-term quantum computers are likely to be special-purpose devices accessed through the cloud.
6 Quantum speedups?: Quantum computers must catch up with a moving target because classical hardware and algorithms continually improve.The comparison is against classical capabilities expected to advance over the coming years.
6 Quantum speedups?: Imperfect NISQ performance can make it difficult to validate whether a quantum computer produces correct answers, especially for quantum simulations.Researchers therefore need better methods for verifying quantum-computer outputs.
6.1 Quantum optimizers: Quantum devices are not expected to solve worst-case NP-hard optimization instances efficiently, but they might find better approximate solutions or find them faster.For some problems, approximation itself becomes NP-hard when the approximation ratio is sufficiently close to one.
6.1 Quantum optimizers: Whether quantum advantage exists for approximate optimization remains an open question that quantum hardware will soon allow researchers to explore experimentally.NISQ technology may be inadequate to demonstrate an advantage even if one exists.
6.1 Quantum optimizers: Hybrid quantum-classical optimization prepares and measures an n-qubit state, uses a classical optimizer to adjust its preparation, and repeats the cycle until convergence.This emerging near-term paradigm includes algorithms such as QAOA and VQE, whose performance against classical approximate-optimization methods is unknown.
6.2 How quantum testbeds might help: Quantum hardware may accelerate algorithm development by enabling experiments that uncover useful heuristics before theorists understand why they work.The paper compares this possibility with experimentally successful classical methods such as simplex and deep learning.
6.2 How quantum testbeds might help: NISQ imperfections severely limit computational power: near-term experiments will use of order 100 qubits and circuit depth less than 100, perhaps much less.Circuits with many imperfect gates become too noisy, making dialogue between algorithm designers and application users important for directing experiments.

6.3 Quantum annealing · 6.4 Noise-resilient quantum circuits

Quantum annealers already solve optimization problems, but their advantage over classical hardware remains unestablished, motivating further experiments, including non-stoquastic and quantum-simulation applications. During the NISQ era, noise mitigation and noise-resilient circuit design may extend computational reach before fault-tolerant error correction becomes practical, although increased resilience may ease classical simulation.

6.3 Quantum annealing: The 2000-qubit D-Wave 2000Q is a quantum annealer rather than a circuit-based quantum computer.It represents a different approach from the 50–100-qubit circuit-based milestone discussed in the paper.
6.3 Quantum annealing: Quantum annealers solve optimization problems by a method different from quantum-circuit execution and often solve these problems successfully.
6.3 Quantum annealing: No convincing theoretical argument or persuasive experimental evidence currently shows quantum annealers outperforming the best classical hardware and algorithms in time to solution.The D-Wave machine is described as a noisy version of adiabatic quantum computing with rather poor-quality qubits.
6.3 Quantum annealing: Most quantum-annealing applications so far are stoquastic, potentially making their behavior relatively easy for classical computers to simulate.Upcoming non-stoquastic annealers may have greater potential for speedups over the best classical algorithms.
6.3 Quantum annealing: Further experiments are needed to determine quantum annealing’s power, including applications to classical optimization and quantum simulation problems.Experiments over the next few years are expected to be informative.
6.4 Noise-resilient quantum circuits: High quantum-error-correction overhead means near-term NISQ devices will instead rely on methods that mitigate noise effects.
6.4 Noise-resilient quantum circuits: For some quantum-simulation algorithms, only a relatively small number of circuit locations may cause severe failure, enabling resilience through low depth, tolerated measurement errors, or decay of early errors.These mechanisms can make the generic 1/G gate-error reliability estimate too pessimistic for some problems.
6.4 Noise-resilient quantum circuits: Collaborative work could improve circuit noise resilience and extend NISQ computational reach, but greater resilience may also make circuits easier to simulate classically.

6.5 Quantum deep learning · 6.6 Quantum matrix inversion

Quantum deep learning may offer advantages especially for quantum inputs and outputs, but classical-data bottlenecks remain important. HHL provides an exponential quantum speedup for sparse, well-conditioned matrix inversion, although its cost likely prevents NISQ-era feasibility.

6.5 Quantum deep learning: Quantum machine learning includes approaches based on quantum algorithms that accelerate linear algebra and related tasks.The paper frames quantum machine learning as a broad set of ideas rather than a single method.
6.5 Quantum deep learning: Quantum deep learning can be illustrated with a restricted Boltzmann machine modeled as a low-temperature spin system with hidden layers.Restricted connectivity permits couplings only between successive layers, not within a layer.
6.5 Quantum deep learning: QRAM encodes an N-component classical vector in log N qubits, but quantum machine-learning proposals face severe input/output bottlenecks.These bottlenecks are especially relevant when applications use large classical data sets.
6.5 Quantum deep learning: Quantum networks may be more advantageous when both inputs and outputs are quantum states, including for controlling complex quantum systems.The passage presents this as a plausible setting in which quantum deep learning could outperform classical methods.
6.5 Quantum deep learning: A quantum deep-learning machine could be a special-purpose device, potentially a quantum annealer if its noise is sufficiently limited.It would not necessarily require a general-purpose circuit-based quantum computer.
6.6 Quantum matrix inversion: Matrix inversion admits an exponential quantum speedup through QRAM, creating potential applications for quantum algorithms.The paper identifies this as a further implication of QRAM.
6.6 Quantum matrix inversion: HHL takes a succinct, sufficiently sparse and well-conditioned N×N matrix A and a QRAM-encoded vector |b⟩, outputting approximately |A−1b⟩.The input vector is represented as a quantum state of log N qubits.
6.6 Quantum matrix inversion: HHL’s matrix-inversion power is supported by BQP-completeness and proposed applications such as approximate solutions of classical linear field equations.However, applying it to classical input data requires accounting for the quantum-state nature of both input and output vectors.

6.7 Quantum recommendation systems · 6.8 Quantum semidefinite programming

Quantum algorithms were proposed for recommendation systems and semidefinite programming, with exponential speedups under stated conditions. The recommendation-system speedup was later eliminated by a quantum-inspired classical algorithm, while practical semidefinite-program applicability remains uncertain.

6.7 Quantum recommendation systems: Quantum recommendation systems target high-value product recommendations from limited customer-preference information.The task uses a binary preference matrix whose practical dimensions may be m ≈108 users and n ≈106 products, with rank k ≈100.
6.7 Quantum recommendation systems: The recommendation algorithm constructs a low-rank preference approximation offline, then generates an online recommendation after a new customer reveals preferences.Only the online stage admits the claimed quantum speedup.
6.7 Quantum recommendation systems: The online quantum runtime is O(poly(k)polylog(mn)), versus poly(mn) for the best classical algorithm known to return a high-value recommendation.The quantum method avoids reconstructing the full recommendation matrix.
6.8 Quantum semidefinite programming: Semidefinite programming optimizes a linear function under matrix inequality constraints and can be solved classically in poly(m, N) time.The solution is a positive semidefinite N × N matrix X maximizing tr(CX) subject to tr(AiX) ≤bi.
6.8 Quantum semidefinite programming: A quantum algorithm finds an approximate semidefinite-program solution in polylog(N) time, outputting a density operator ρ that approximates the optimal matrix X.Repeated measurements of ρ can extract increasingly detailed information about X.
6.8 Quantum semidefinite programming: The semidefinite-program speedup depends on efficiently preparing a thermal Gibbs state, and is feasible when input matrices have low rank or the Hamiltonian thermalizes rapidly.The extent to which these conditions hold for practical semidefinite programs remains unclear.
6.8 Quantum semidefinite programming: Because the algorithm prepares a thermal state at nonzero temperature, it may be intrinsically robust against thermal noise or compatible with quantum annealing.The paper suggests that a quantum solver might therefore be within reach of NISQ technology.
6.7 Quantum recommendation systems: A quantum-inspired classical algorithm later returns a high-value recommendation in O(poly(k)polylog(mn)), removing the claimed exponential advantage.This note revised the comparison with the best classical algorithm performing the same task.

6.9 Quantum simulation · 6.10 Digital vs. analog quantum simulation · 6.11 Quantum games

Quantum simulation is especially promising for highly entangled many-body systems and quantum dynamics, where classical computers struggle. Digital simulators offer broad programmability and eventual error-corrected control, while analog simulators and quantum games may retain important near-term or educational value.

6.9 Quantum simulation: Quantum computers are expected to be well suited to studying highly entangled systems of many particles, whose strongly correlated behavior is computationally difficult.The difficulty is motivated by decades of unsuccessful efforts by many physicists to solve such problems.
6.9 Quantum simulation: Quantum simulation could eventually influence quantum chemistry, pharmaceuticals, catalysts, materials, power transmission, and solar-energy collection.The passage presents these as potential long-term consequences of advances enabled by quantum computing.
6.9 Quantum simulation: Classical computers are especially bad at simulating quantum dynamics, giving quantum computers a major advantage for studying highly entangled states over time.Physicists hope to investigate quantum dynamics with NISQ technology in the relatively near term.
6.10 Digital vs. analog quantum simulation: Analog simulators use many qubits whose dynamics resembles a target model, whereas digital simulators are gate-based universal quantum computers programmed to simulate physical systems.The distinction concerns how the simulator represents and controls the system of interest.
6.10 Digital vs. analog quantum simulation: Analog simulation is more established than general-purpose digital simulation, and both can use platforms such as trapped ions and superconducting circuits.Analog quantum simulation has been vibrant for 15 years, while digital circuit-based simulation is just getting started.
6.10 Digital vs. analog quantum simulation: Analog simulators’ imperfect control limits them to properties that are robust to small errors, yet identifying such properties that remain classically hard is a major challenge.The laboratory system only crudely approximates the model system of interest.
6.10 Digital vs. analog quantum simulation: Digital simulators may eventually surpass analog simulators through quantum error correction, but analog systems may remain important for many years because error correction has hefty overhead costs.The passage advises not overlooking analog simulators when seeking near-term quantum-technology applications.
6.11 Quantum games: Quantum games could popularize quantum computing, provide intuitive understanding of quantum phenomena, and create opportunities for quantum machine learning to improve gameplay.The passage connects these possibilities to the broad social and economic impact of classical digital games.

7 The daunting climb to scalability

Fully scalable fault-tolerant quantum computing remains a distant goal requiring major advances in error correction, hardware, basic science, and systems engineering. Near-term progress will come from better error-corrected-qubit control and lower gate error rates, while hard applications may require millions of physical qubits.

The daunting climb to scalability: Near-term progress can come from better quantum error-correction methods and hardware, guided by small-scale experiments with quantum error-correcting codes.Enhanced control of an error-corrected qubit is expected to be demonstrated convincingly in the next few years.
The daunting climb to scalability: Millions or more physical qubits may be needed to run algorithms involving thousands of protected qubits, far beyond the roughly hundred qubits expected in the next few years.This scale gap makes fault-tolerant solutions to very hard problems, such as factoring thousands-bit numbers, unlikely for a while.
The daunting climb to scalability: Lower gate error rates would let non-error-corrected quantum computers execute larger circuits and reduce the overhead of future quantum error correction.Improving gate accuracy remains important throughout the NISQ era across quantum platforms.
The daunting climb to scalability: Fully scalable fault-tolerant quantum computers require significant advances in basic science and systems engineering, making scalability a compelling scientific and engineering challenge.New insights, developments, and innovations could substantially alter the long-term outlook because the field still has far to go.

8 Summary

The NISQ era will enable experiments and potentially useful quantum applications, but its benefits remain uncertain and constrained by noise. Progress depends on noise-resilient algorithms and more accurate gates, while NISQ platforms primarily pave the way toward fault-tolerant quantum computing.

NISQ opportunities and limits: NISQ technology will soon enable experiments, but whether it accelerates solutions to broadly interesting problems remains unknown.The paper adopts a cautious stance while anticipating discoveries and surprises as the NISQ era unfolds.
NISQ opportunities and limits: Hybrid quantum-classical algorithms for classical and quantum optimization are among the specific applications to investigate.The development of quantum algorithms may accelerate once experimental quantum computers become available, potentially yielding useful but initially unexplained heuristics.
NISQ opportunities and limits: Noise-resilient algorithm design may extend NISQ computational power despite the likely absence of full-blown quantum error correction.Near-term algorithms should be designed with noise resilience in mind because NISQ devices probably cannot be protected from noise through full error correction.
Potential applications: Quantum dynamics of highly entangled many-particle systems is a particularly promising area for quantum advantage because classical computers simulate it poorly.The paper identifies quantum dynamics as an arena where quantum computers may significantly outperform classical ones.
Long-term quantum computing: More accurate quantum gates will permit larger NISQ circuits and reduce the eventual overhead of quantum error correction, but transformative technologies will likely require fault tolerance.NISQ is not expected to change the world by itself; near-term platforms should instead prepare for larger payoffs from advanced devices, while the fault-tolerant era may remain distant.