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.