Quantum Computing in the NISQ era and beyond

Another recently proposed quantum algorithm [44] provides an exponential speedup over the best currently known classical 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 P = 1 if customer a likes product i and P = 0 if customer a dislikes product i. In practice we might have m ≈10 users and n ≈10 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

Quantum semidefinite programming

recommendation which that customer will like with high probability. It is this second online stage that admits a quantum speedup. The quantum runtime is O(poly(k)polylog(mn)), while the best classical algorithm known requires time poly(mn) to return a high-value recommendation. Crucially, the quantum algorithm, in contrast to the classical 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 speedup 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 quantum recommendation systems (returning a high-quality recommendation in polylog(mn) time) is impossible classically. Formulating such an argument would strengthen our confidence that quantum computers will have a significant impact on machine learning. Here too, though, the algorithm is probably too costly to be convincingly validated during the NISQ era.

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

A recently discovered quantum algorithm [46, 47] finds an approximate solution to the problem in time polylog(N), an exponential speedup. In the quantum algorithm, the output is a quantum state, a density operator ρ which approximates the optimal matrix X. This quantum 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 quantum algorithm one assumes the availability of an initial quantum 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 quantum computer.

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 quantum 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 quantum algorithm is the preparation of a thermal state at a nonzero temperature. That may suggest that the algorithm has some intrinsic robustness against thermal noise, or that the thermalization stage of the algorithm could be executed by quantum annealing. Conceivably, then, a quantum solver

12 for semidefinite programs might be within reach of NISQ technology.

Quantum simulation

As I have already emphasized, we expect quantum computers 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 quantum matter is the natural arena where quantum computers seem to have a clear advantage over classical ones.

In the long term, quantum simulation using quantum computers has great potential to wield a broad influence on the world [48, 49, 50]. Advances in quantum chemistry, facilitated by quantum 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 quantum 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 quantum simulators. But this promise is not so likely to be fulfilled in the NISQ era, because quantum algorithms for accurately simulating large molecules and exotic materials may be too expensive to succeed without error correction.

Classical computers are especially bad at simulating quantum dynamics — that is, pre-dicting how a highly-entangled quantum state will change with time. Quantum computers have a big advantage for that task, and physicists hope to learn interesting things about quantum dynamics using NISQ technology in the relatively near term. It is instructive to recall that the theory of classical chaos (the extreme sensitivity to initial conditions in classical 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 classical computers. We may anticipate that the emerging ability to simulate chaotic quantum systems (those in which entanglement spreads very rapidly) will promote advances in our understanding of quantum chaos. Valuable insights might already be gleaned using noisy devices with of order 100 qubits.

Digital vs. analog quantum simulation

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

Analog quantum simulation has been a very vibrant area of research for the past 15 years, while digital quantum simulation with general purpose circuit-based quantum computers 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 simulators have been getting notably more sophisticated, and are already being employed to study quantum dynamics in regimes which may be beyond the reach of classical simulators [51, 52]. But analog quantum simulators are hampered by imperfect control — the actual quantum system in the lab only crudely approximates the model

13 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 simulators is identifying accessible properties of quantum systems which are robust with respect to error, yet are also hard to simulate classically.

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

Quantum games

Advances in classical computing launched a new world of digital games, touching the lives of millions and generating billions in revenue. Could quantum computers do the same?

Physicists often say that the quantum 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 quantum games will acquire a visceral understanding of quantum phenomena that our generation lacks. Furthermore, quantum games could open a niche for quantum machine learning methods, which might seize the opportunity to improve game play in situations where quantum entanglement has an essential role.