There has been a revolution in the last few years in quantum simulation. The purpose of this talk is to provide an overview of these recent developments. Specifically, I will review Trotter-Suzuki simulation methods and discuss recent work that provides tighter estimates for the error in such approximations. I will then discuss truncated Dyson series simulations for time-dependent Hamiltonians before giving a discussion of qubitization. I will then conclude by discussing current open problems in quantum simulation and the strategies that may be needed to solve them.

The efficient simulation of quantum chemistry is among the most anticipated applications of quantum computers. However, as the age of industrial quantum technology dawns, so has the realization that even “polynomial” resource overheads are often prohibitive. There remains a large gap between the capabilities of existing hardware and the resources required to quantum compute classically intractable problems in chemistry. This talk will introduce the quantum chemistry problem and several popular approaches for its solution on a quantum computer. We will then survey recent advances in the field and discuss key challenges for implementing these quantum simulations on realistic quantum computers, both in the near-term and on the first fault-tolerant devices.

Reliable qubits are difficult to engineer. What can we do with just a few of them? Here are some ideas:

1. Dimension test. An n-qubit system should have 2^n dimensions, but systems with just polynomial(n) dimensions can look like they have n qubits. Is nature really exponential? We give a test for verifying that your system has 2^n dimensions.

2. Entanglement and nonlocality tests. A Bell-inequality violation establishes that your systems share some entanglement. We give a test to show that your systems share lots of entanglement. Additionally, we give a test to eliminate non-signaling correlations (like the Popescu-Rohrlich nonlocal box), giving a way to check whether multi-party entanglement breaks down.

3. Error test. Error correction will be needed for scalable quantum computers. But high qubit overhead makes it impractical for small devices. We show that a seven-qubit computer can fault tolerantly correct errors on one encoded qubit, and that a 17-qubit computer can protect and compute fault tolerantly on seven encoded qubits.

I'll discuss some of the complexity-theoretic foundations of quantum supremacy experiments with random quantum circuits, of the sort that Google is planning in the near future with its 72-qubit chip. (Based on my joint work with Lijie Chen.) Then, in a second part of the talk, I'll discuss how these experiments could be used to generate certified random bits.

We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms using quantum accessible data structures. We develop several tools within the block-encoding framework, including quantum linear system solvers using block-encodings. Our results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices.

Quantum adiabatic optimization (QAO) was one of the first quantum algorithms to be proposed for combinatorial optimization, but in spite of its long history the search for a quantum speedup with QAO still remains elusive.  This inability to find a speedup is often attributed to the use of stoquastic Hamiltonians, because ground states of these models can in many cases be efficiently classically simulated by Markov chain Monte Carlo methods.  In this talk I'll start by reviewing aspects of the general stoquastic simulation conjecture, with a particular focus on the role of the adiabatic path in these simulations.    More recently, this threat of classical simulation has motivated proposals to consider the use of general (nonstoquastic) Hamiltonians in QAO.  To further our understanding of these proposals I'll present a general isoperimetric inequality that constrains the spectral gap of a Hamiltonian in terms of its quantum ground state geometry, without a dependence on the details of the interaction couplings.  This result can be applied to see that some explicit probability distributions, even ones which are simple to describe, will inevitably take exponential time to be precisely reached by pure adiabatic evolution with local Hamiltonians.

No abstract available.

In this talk I will explain the blueprint for constructing succinct non-interactive (computationally sound) proofs from standard assumptions. The construction explores an interesting connection between cryptography and non-signaling.