Quantum Computing in the NISQ era and beyond

I’ve emphasized that eventually we are going to use quantum error correction to extend the size of the computations we can execute reliably using noisy quantum computers. But, because of the high overhead cost of quantum error correction, NISQ devices will not make use of it in the near term. Nevertheless, methods for mitigating the effects of noise may be an important consideration during the NISQ 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 quantum 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 qubit in the final measurement out-come, or because the damage caused by an error occurring early in the circuit decays away by a later time. Such noise resilience is characteristic of some tensor network constructions which can be invoked for solving quantum optimization problems using Variational Quantum Eigensolvers [35, 36].

There is a substantial opportunity for experimentalists and theorists, working together over the next few years, to find better ways of making quantum circuits noise resilient, 9 and so extend the computational reach of NISQ technology. We should be wary, though, of a potential tradeoff— making a quantum circuit more noise resilient may also make it easier to simulate classically.

Quantum 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 quantum technology. There are a variety of different notions of “quantum machine learning.” Much of the literature on the subject builds on quantum 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 quantum 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 quantum analog of such a machine could have a similar structure and function, but where the spins are qubits rather than classical bits. It may be that quantum deep learning networks have advantages over classical 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 quantum machine learning rests on the concept known as QRAM — quantum random access memory. By QRAM we mean representing a large amount of classical data very succinctly, by encoding a vector with N components in just log N qubits. But typical proposals for quantum machine learning applications are confounded by severe input/output bottlenecks. For applications to large classical data sets one should take into account the cost of encoding the input into QRAM, which can nullify the potential advantages. Furthermore, the output from a quantum network is itself a quantum state; to get useful information we need to measure the state, and we can acquire no more than log N bits of classical information in a singleshot measurement of log N qubits.

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

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

Quantum matrix inversion

QRAM has further implications for quantum algorithms. In particular, the task of matrix inversion admits an exponential quantum speedup, 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 |b⟩, encoded in QRAM as a quantum state of log N qubits. The output of the quantum algorithm is (with a small error) the quantum state |Ab⟩, the result of applying the inverse of the matrix A to the input vector |b⟩. This quantum algorithm runs in time O(log N), an exponential speedup relative to classical 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 |b⟩and the output vector |Ab⟩are quantum states. Once we have the output state, we can perform measurements to learn features of the output vector Ab, 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 classical input data, we need to take into account the potential cost of loading that classical data into QRAM, which could nullify the exponential speedup. Alternatively, loading classical data into QRAM might be avoided by computing |b⟩on a quantum computer rather than entering it from a database.

We do have good reason to believe this quantum matrix inversion algorithm is powerful, because it solves what we call a BQP-complete problem. That is, any problem that can be solved efficiently with a quantum computer 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 classical 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 NISQ era. The algorithm may just be too expensive to be executed successfully by a quantum computer which doesn’t use error correction.