Computer Science

Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Relaxed Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem.  https://arxiv.org/abs/1906.08890

In the past few years there have been a number of major advances for quantum simulation.  I will be reviewing a number of them in this talk including the interaction picture simulation method, the QDRIFT algorithm, well conditioned multi-product formulas and new commutator bounds for high-order Trotter Suzuki methods which show that those algorithms are much more efficient than previously thought.  Finally I will discuss applications of these algorithms to problems in chemistry and simulation of the Schwinger model in 1+1D.

This talk aims at providing an overview of some of the major ideas and techniques that were developed for Hamiltonian simulation, including Trotterization, linear combination of unitaries, oblivious amplitude amplification and quantum signal processing. The adaptation and clever combination of these techniques led to a flurry of new results in different variants of Hamiltonian simulation problems, as well as in other important quantum algorithmic tasks.

Noisy quantum computers can outperform classical computers on certain sampling tasks, but it's unclear whether NISQ machines can outperform classical computers on a commercially relevant task. If NISQ machines can't do this, then it will be necessary to build fault tolerant quantum computers before a "quantum information age" could truly begin. The goal of this talk is to contextualize the expected overhead of fault tolerant quantum computation using superconducting qubits and the surface code. We will cover the cost of performing the simplest possible classically intractable task (random circuit sampling) in a fault tolerant fashion.

The subject of this talk will be quantum distributed computing, i.e., distributed computing when the processors of the network can exchange quantum information. After describing the basics of distributed computing, I will explain a result obtained with Frédéric Magniez (arXiv:1804.02917) on quantum algorithms computing the diameter of the network. I will then present others results (arXiv:1810.10838 and arXiv:1908.11488) that show separations between the computational powers of quantum and classical distributed algorithms in several fundamental models of distributed computing. I will conclude my talk by mentioning interesting and important open questions in quantum distributed computing.

"st-connectivity" is the problem of deciding whether two points in a graph are connected or not (i.e. whether there is a path between them). I will show that a range of common problems can be reduced to st-connectivity, and furthermore, this reduction leads to an optimal quantum algorithm in many cases of interest. The analysis of the quantum algorithm is fairly simple, and uses standard graph theoretic quantities. These properties suggest that st-connectivity would make a good building block, or primitive, for designing and analyzing quantum algorithms.

As the search continues for useful applications of noisy intermediate scale quantum devices, variational simulations of fermionic systems remain one of the most promising directions. Here, we demonstrate an experimental quantum simulation of chemistry with more than ten times times the number of entangling gates as the largest prior implementation. We variationally model the isomerization of diazene and correctly distinguish between competing reaction mechanisms to within the model chemistry. The parameterized circuits explored in our work realize the Givens rotation approach to free fermion evolution. This ubiquitous algorithmic primitive performs an arbitrary change of orbital basis and is required by many proposals for correlated simulations of molecules and Hubbard models. Because free fermion evolutions are classically tractable to simulate yet still generate highly entangled states over the computational basis, we are able to use these experiments to benchmark the performance of our quantum processor while establishing a foundation for scaling up intermediate scale correlated electron simulations.

I will survey some recent results that illustrate the current state-of-the-art in classical simulations of chemical and materials systems and discuss some areas of near-term interest for quantum computers.

Recent advances in the technologies related to quantum computing have allowed the achievement of the so-called "quantum supremacy" milestone.  In this talk, I will briefly recap this achievement, and address how it relates to progress towards practical applications of quantum computers to problems in physics, chemistry, machine learning, and related areas.  I will overview some of the promising algorithms in this area, such as hybrid quantum-classical algorithms and variational quantum eigensolvers (VQE), including challenges that remain in their successful implementation.  This will naturally lead to a discussion of the impact of errors and the road towards quantum error correction prior to full fault tolerance using methods such as quantum subspace expansions.

Consider the task of estimating the expectation value of an n-qubit tensor product observable in the output state of a shallow quantum circuit. This task is a cornerstone of variational quantum algorithms for optimization, machine learning, and the simulation of quantum many-body systems. In this talk I will describe three special cases of this problem which are "easy" for classical computers. This is joint work with Sergey Bravyi and Ramis Movassagh.

I will survey recent works highlighting the power and limitations of the quantum approximate optimization algorithm (QAOA). First I will discuss a recent paper of Hastings (arXiv:1905.07047) describing a local classical algorithm which outperforms p=1 QAOA on MAXCUT instances and which matches its performance on MAX-3LIN2. I will also discuss a recent paper of Bravyi, Kliesch, Koeing, and Tang (arXiv:1910.08980) which uses symmetries of the QAOA to prove that it will not outperform the Goemans-Williamson algorithm for MAXCUT for any value of p.