# Keynotes

## Scott Aaronson

**University of Texas at Austin**

### BQP After 28 Years

I’ll discuss the now-ancient question of where BQP fits among

classical complexity classes. After reviewing some basics (not all of

them universally known) from the 1990s, I’ll discuss the Forrelation

problem that I introduced in 2009 to yield an oracle separation

between BQP and PH, and the dramatic completion of that program by Raz

and Tal in 2018. I’ll then discuss ongoing joint work, with William

Kretschmer and DeVon Ingram, which leverages the Raz-Tal theorem,

along with a new random restriction lemma for quantum algorithms, to

obtain results that illustrate just how differently BQP can behave

from BPP. These include an oracle relative to which BQP contains the

kth level of the polynomial hierarchy but not the (k+1)st (for any k);

an oracle relative to which BQP contains NP yet PH is infinite; an

oracle relative to which P=NP!=BQP=PP; and an oracle relative to which

PP=PostBQP is not in QMA^QMA^… By popular demand, I’ll also speculate

about the status of BQP in the unrelativized world.

## Srinivasan Arunachalam

**IBM T. J. Watson Research Center**

Srinivasan Arunachalam is a Research Staff Member at IBM T. J. Watson Research Center. Prior to this, he was a Postdoctoral Researcher at MIT. He received his Ph.D. in 2018 from QuSoft, Netherlands and his Masters degree from University of Waterloo. His research interests are in quantum learning theory, algorithms and complexity theory.

### Recent advances in learning quantum states

Learning an unknown n-qubit quantum state is a fundamental challenge in quantum computing theory and practice. Information-theoretically, it is well-known that tomography requires exponential in n many copies of an unknown state in order to estimate it upto small trace distance. But a natural question is, are there models of learning where fewer copies suffice and are there interesting classes of states that can be learned with fewer copies? In this talk I will discuss the following results: (1) learning local Hamiltonians on n qubits using poly(n) many samples of the quantum Gibbs state, (2) In the past few years, there have been various learning models introduced to capture the learnability of quantum states; here I will overview many recent results and discuss various equivalences between these learning models. Both these works pave the way towards a more rigorous application of using machine learning techniques to learning quantum states.

## Cécilia Lancien

**Institut de Mathématiques de Toulouse and CNRS**

Cécilia Lancien completed a joint PhD between the Université Lyon 1

(France) and the Universitat Autonoma de Barcelona (Spain) in June 2016.

She then spent two years as a post-doc at the Universidad Complutense de

Madrid (Spain). Since October 2018 she is a CNRS researcher at the

Institut de Mathématiques de Toulouse (France). Her research is mainly

focused on studying problems arising in quantum information theory, by

using and developing results in asymptotic geometric analysis and random

matrix/tensor theory.

### Typical correlations and entanglement in random MPS and PEPS

Tensor network states are used extensively as a mathematically

convenient description of physically relevant states of many-body

quantum systems. Those built on regular lattices, i.e. matrix product

states (MPS) in dimension 1 and projected entangled pair states (PEPS)

in dimension 2 or higher, are of particular interest in condensed matter

physics. In this talk, I will try to answer the following general

question: which features of MPS and PEPS are generic and which are, on

the contrary, exceptional? Or to rephrase it: given an MPS or PEPS

sampled at random, what are the features that it displays with either

high or low probability? One property which we will focus on is that of

having either rapidly decaying or long-range correlations. In a

nutshell, the main result I will state is that translation-invariant MPS

and PEPS typically exhibit exponential decay of correlations at a high

rate. I will show two distinct ways of getting to this conclusion,

depending on the dimensional regime under consideration. Both yield

intermediate results which are of independent interest, namely: the

parent Hamiltonian and the transfer operator of such MPS and PEPS

typically have a large spectral gap. If time allows, I will also present

on-going attempts at quantifying the amount of genuinely multipartite

entanglement in such random MPS and PEPS.

The talk will be based mainly on a joint work with David Perez-Garcia,

available at arXiv:1906.11682, and on some work in progress with Ion

Nechita.

## Kai-Min Chung

**Academia Sinica**

Kai-Min Chung is a Research Fellow at the Institute of Information Science (IIS), Academia Sinica, Taiwan. Before joining IIS, he was a postdoc at Cornell University supported by a Simons Postdoctoral Fellowship in 2010-2013 and received his Ph.D. in computer science at Harvard University. He was also a Simons Research Fellow at the Simons Institute at Berkeley for the Cryptography program in Summer 2015. Kai-Min’s research interests lie in the field of cryptography and its interplay with complexity and quantum theory. He has worked on diverse topics in cryptography with a recent focus on quantum cryptography. He serves on the PC of major crypto conferences frequently and co-organized PKC 2016 and AQIS 2016.

### Tight Quantum Time-Space Tradeoffs for Function Inversion

In time-space tradeoffs for function inversion, we are given a function f: [N] -> [N], and want to prepare some advice of size S, such that we can efficiently invert any image in time T. This is a fundamental problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of ST^2 = \Omega(N) for random permutations against classical advice, leaving open an intriguing possibility that Grover’s search can be sped up to time O(\sqrt{N/S}). Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains ST^2 = \Omega(N).

In this talk, I’ll present a general framework to answer the question negatively. Specifically, our framework shows that even with quantum advice, ST + T^2 = \Omega(N) is required for an algorithm to invert random functions. It means that for S = O(\sqrt{N}), even S qubits of quantum advice cannot help to speed up Grover’s search, which remains optimal. Furthermore, for S = \Omega(\sqrt{N}), further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). Our framework can also be used to prove (nearly) tight quantum time-space tradeoffs for several fundamental problems in cryptography, such as Yao’s box problem, distinguishing pseudorandom generators, and salted collision-finding.

I will also discuss other types of quantum time-space tradeoffs problems motivated by quantum cryptography and highlight some challenging open questions such as quantum time-memory tradeoffs for collision-finding and post-quantum memory-hard functions.