**The workshop schedule can be found here.**

**Titles and Abstracts (more titles and abstracts to come soon!):**

Speaker: Matthias Christandl

Title:Catalytic Decoupling of Quantum Information

Abstract: The decoupling technique is a fundamental tool in quantum information theory with applications ranging from quantum thermodynamics to quantum many body physics to the study of black hole radiation. In this work we introduce the notion of catalytic decoupling, that is, decoupling in the presence of an uncorrelated ancilla system. This removes a restriction on the standard notion of decoupling, which becomes important for structureless resources, and yields a tight characterization in terms of the max-mutual information. Catalytic decoupling naturally unifies various tasks like the erasure of correlations and quantum state merging, and leads to a resource theory of decoupling.

This is based on 1605.00514, which is joint work with Christian Majenz, Mario Berta, Frédéric Dupuis, and Renato Renner,.

Speaker: Aram Harrow Slides.

Title:Replacing hierarchies with nets

Abstract: The SDP hierarchy due to Lasserre and Parrilo has recently been shown to yield quasipolynomial time algorithms for some optimization problems related to quantum information. One representative example is to maximize over unentangled states the acceptance probability of a measurement that is implemented with local operations and one-way communication (1-LOCC). There have been a series of proofs of this fact, starting with Brandao-Christandl-Yard in 2010, mostly based on quantum information theory.

In this work we show how to achieve roughly the same performance instead using a simple enumeration over epsilon nets. This net-based approach gives a new geometric perspective into the problem that helps explain why 1-LOCC measurements appear to be easier than general measurements. It also yields two improvements of the SDP-based results. First, it gives faster algorithms for special cases of the problem, including estimating the 2->s norm of a matrix for s>=2. Second we give a similar algorithm for a generalization of the problem: estimating the injective tensor norm for a map between two Banach spaces, whose factorization norm through ell_1 is bounded. As a particular case we find the first PTAS for estimating the maximum output p-norms of entanglement breaking quantum channels for any p>=1.

This is based on 1509.05065, which is joint work with Fernando Brandao.

Speaker: Cécilia Lancien Slides.

Title: Soundness gap amplification of QMA(2) protocols by parallel repetition: the possible role of de Finetti reductions and entanglement measure theory

Abstract: Soundness gap amplification of QMA(2) protocols by parallel repetition - The possible role of de Finetti reductions and entanglement measure theory.

Based on joint work with Andreas Winter: arXiv:1605.09013[quant-ph].

If 2 unentangled provers cannot pass 1 instance of a given test with probability 1, it is reasonable to expect that requiring that they pass n instances of this test simultaneously should make their passing probability go to 0 exponentially fast. This intuitive parallel repetition result can be shown to hold true, but up to now with an exponential decay rate which depends, maybe artefactly, on the dimensions of the provers' systems.

In this talk, I will review two approachs to tackle this question. The first one is based on de Finetti reductions (which means roughly speaking that it exploits the permutation-symmetry of the problem to reduce its analysis to that of an iid scenario). The second one uses entanglement measure theory to mimic classical parallel repetition proofs in the setting of non-local games.

Speaker: Anand Natarajan Slides.

Title: An improved semidefinite programming hierarchy for the Best Separable State problem

Abstract: We present a stronger version of the Doherty-Parrilo-Spedalieri (DPS) hierarchy for solving the Best Separable State problem. Unlike DPS, our hierarchy converges exactly at a finite number of rounds for any fixed input dimension. This yields an algorithm which is singly exponential in the Hilbert space dimension and polylogarithmic in accuracy. Our analysis makes use of tools from algebraic geometry, but our algorithm is elementary and differs from DPS only by one simple additional collection of constraints. (arXiv:1506.08834)

Speaker: Martin Schwarz Slides.

Title: Towards new upper bounds for QMA(k)

Abstract:Proving a non-trivial, unconditional upper bound for QMA(k) has been an open problem since at least 2008. In this talk, we will review a recently proposed, novel approach towards an upper bound of EXP for QMA(k) and discuss open issues that are currently unresolved. The key ideas of the approach are to use perturbation theory to reduce the QMA(2)-complete Separable Sparse Hamiltonian problem to a variant of the Separable Local Hamiltonian problem with an exponentially small promise gap, and then to decide this instance using epsilon-net methods. Combining this approach with very recent results of Fefferman and Lin might even imply a PSPACE upper bound.

Speaker: Or Sattath Slides.

Title: The Complexity of the Separable Hamiltonian Problem

Abstract: In this paper, we study variants of the canonical Local-Hamiltonian problem where, in addition, the witness is promised to be separable. We define two variants of the Local-Hamiltonian problem. The input for the Separable-Local-Hamiltonian problem is the same as the Local-Hamiltonian problem, i.e. a local Hamiltonian and two energies a and b, but the question is somewhat different: the answer is YES if there is a separable quantum state with energy at most a, and the answer is NO if all separable quantum states have energy at least b. The Separable-Sparse-Hamiltonian problem is defined similarly, but the Hamiltonian is not necessarily local, but rather sparse. We show that the Separable-Sparse-Hamiltonian problem is QMA(2)-Complete, while Separable-Local-Hamiltonian is in QMA. This should be compared to the Local-Hamiltonian problem, and the Sparse-Hamiltonian problem which are both QMA-Complete. To the best of our knowledge, Separable-SPARSE-Hamiltonian is the first non-trivial problem shown to be QMA(2)-Complete.

Speaker: Xiaodi Wu Slides.

Title: Limitations of monogamy, Tsirelson-type bounds, and other semidefinite programs in quantum information

Abstract: We introduce a new method for proving limitations on the ability of semidefinite programs (SDPs) to approximately solve optimization problems. We use this to show specifically that SDPs have limited ability to approximate two particularly important sets in quantum information theory:

1. The set of separable (i.e. unentangled) states.

2. The set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state.

In both cases no-go theorems were previously known based on computational assumptions such as the Exponential Time Hypothesis (ETH) which asserts that 3-SAT requires exponential time to solve. Our unconditional results achieve the same parameters as all of these previous results (for separable states) or as some of the previous results (for quantum correlations). In some cases we can make use of the framework of Lee-Raghavendra-Steurer (LRS) to establish integrality gaps for any SDP, not only the SoS hierarchy. Our hardness result on separable states also yields a dimension lower bound of approximate disentanglers, answering a question of Aaronson et al.

These results can be viewed as limitations on the monogamy principle, the PPT test, the ability of Tsirelson-type bounds to restrict quantum correlations, as well as the SDP hierarchies of Doherty-Parrilo-Spedalieri, Navascues-Pironio-Acin and Berta-Fawzi-Scholz. Indeed a wide range of past work in quantum information can be described as using an SDP on one of the above two problems and our results put broad limits on these lines of argument.

This is joint work with Aram Harrow and Anand Natarajan.