Sergey Bravyi

We present an end-to-end quantum algorithm with provable performance guarantees for simulating a large class of classical nonlinear dynamical systems. The considered dynamical systems are described by stochastic dissipative differential equations with a quadratic nonlinearity satisfying certain sparsity and divergence-free conditions. Our algorithm approximates the expected value of any sparse low-degree polynomial evaluated at the solution of the classical system. The runtime scales poly-logarithmically with the system size and polynomially with the evolution time, inverse error tolerance, and parameters quantifying sparsity, dissipation, and nonlinearity strength. The considered simulation problem is shown to be BQP-complete, providing a strong evidence for a quantum advantage. We benchmark the quantum algorithm via numerical experiments by simulating a vortex flow in the 2D Navier Stokes equation.

Checking whether two quantum circuits are approximately equivalent is a common task in quantum computing. We consider a closely related identity check problem: given a quantum circuit U, one has to estimate the diamond-norm distance between U and the identity channel. We present a classical algorithm approximating the distance to the identity within a factor alpha = D+1 for shallow geometrically local D-dimensional circuits provided that the circuit is sufficiently close to the identity. The runtime of the algorithm scales linearly with the number of qubits for any constant circuit depth and spatial dimension. We also show that the operator-norm distance to the identity || U - I || can be efficiently approximated within a factor alpha = 5 for shallow 1D circuits and, under a certain technical condition, within a factor alpha = 2D + 3 for shallow D-dimensional circuits. A numerical implementation of the identity check algorithm is reported for 1D Trotter circuits with up to 100 qubits.

Abstract Quantum computations promise the ability to solve problems intractable in the classical setting. Restricting the types of computations considered often allows to establish a provable theoretical advantage by quantum computations, and later demonstrate it experimentally. In this paper, we consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on. We show that n-bit symmetric Boolean functions can be implemented exactly through the use of quantum signal processing as restricted space quantum computations using O(n^2) gates, but some of them may only be evaluated with probability 1/2+O(n/sqrt{2}^n) by analogously defined classical computations. We experimentally demonstrate computations of 3-, 4-, 5-, and 6-bit symmetric Boolean functions by quantum circuits, leveraging custom two-qubit gates, with algorithmic success probability exceeding the best possible classically. This establishes and experimentally verifies a different kind of quantum advantage---one where quantum scrap space is more valuable than analogous classical space---and calls for an in-depth exploration of space-time tradeoffs in quantum circuits.