Quantum Innovators in Computer Science and Math will take place is the Lazaridis QNC 0101

**Monday, September 18, 2017**

9:30 am | Registration + coffee |

10:00 am |
Ankit Garg, Microsoft Research Quantum marginal problem, invariant theory and derandomization |

11:00 am | Lidia del Rio, ETH Zürich Composable security in relativistic quantum cryptography |

12:00 pm | Lunch |

2:00 pm | Anurag Ansha, Centre for Quantum Technologies Protocols for communication over quantum networks |

3:00 pm | Fernando Pastawski, Free University of Berlin Holographic quantum error-correcting codes |

4:00 pm | Reception with IQC faculty |

**Tuesday, September 19, 2017**

9:30 am | Coffee |

10:00 am |
David Sutter, ETH Zürich |

11:00 am |
Cecilia Lancien, Complutense University of Madrid |

12:00 pm | Lunch |

2:00 pm |
John Wright, Massachusetts Institute of Technology |

3:00 pm |
Sergii Strelchuk, University of Cambridge |

**Wednesday, September 20, 2017**

9:30 am | Coffee |

10:00 am | Chris Majenz, University of Copenhagen |

11:00 am |
Laura Mančinska, QMATH, University of Copenhagen |

12:00 pm | Lunch |

2:00 pm | Adam Bouland, Massachusetts Institute of Technology The space below BQP |

3:00 pm | Shalev Ben-David, Massachusetts Institute of Technology The Structure Necessary for Quantum Speedups |

6:00 pm | Banquet dinner |

**Thursday, September 21, 2017**

9:30 am |
Coffee |

10:00 am |
Gemma de las Cuevas, University of Innsbruck |

11:00 am |
Mischa Woods, University College London |

12:00 pm | Lunch |

1:00 pm |
Matt Courdron, Massachusetts Institute of Technology |

## Abstracts

**Ankit Garg, Microsoft Research**

Quantum marginal problem, invariant theory and derandomization

I will talk about the problem of finding locally maximally entangled states in the SLOCC-equivalence classes and present a polynomial time (classical) algorithm for it. This problem finds motivations in invariant theory and is closely related to the one-body quantum marginal problem. A special case is equivalent to problems in non-commutative algebra and derandomization. Our algorithm is a simple alternating minimization one and its analysis is based on tools from invariant theory. Several interesting problems are left open, which I am hoping some members of the audience will solve :) Based on two works: joint with Leonid Gurvits, Rafael Oliveira, Avi Wigderson and another one joint with Peter Burgisser, Rafael Oliveira, Michael Walter and Avi Wigderson.

Composable security in relativistic quantum cryptography

Relativistic protocols have been proposed to overcome some impossibility results in classical and quantum cryptography. In such a setting, one takes the location of honest players into account, and uses the fact that information cannot travel faster than the speed of light to limit the abilities of dishonest agents. For example, various relativistic bit commitment protocols have been proposed. Although it has been shown that bit commitment is sufficient to construct oblivious transfer and thus multiparty computation, composing specific relativistic protocols in this way is known to be insecure. A composable framework is required to perform such a modular security analysis of construction schemes, but no known frameworks can handle models of computation in Minkowski space. By instantiating the systems model from the Abstract Cryptography framework with causal boxes, we obtain such a composable framework, in which messages are assigned a location in Minkowski space (or superpositions thereof). This allows us to analyze relativistic protocols, and derive novel possibility and impossibility results. We show that (1) coin flipping can be constructed from the primitive channel with delay, (2) biased coin flipping, bit commitment and channel with delay are all impossible without further assumptions, and (3) it is impossible to improve a channel with delay. This implies in particular non-composability of all proposed relativistic bit commitment protocols, as well as non-composability of (quantum, but non-relativistic) biased coin flipping protocols.

This is joint work with V. Vilasini and Christopher Portmann.

**Anurag Ansha, Centre for Quantum Technologies**

Protocols for communication over quantum networks

The problem of finding efficient means of communication in noisy or noiseless network settings has been very well studied in literature. Some well known examples of this include the source coding (Shannon 1948), point to point noisy channel coding (Shannon 1948), distributed source coding (Slepian and Wolf 1973), broadcast channel (Marton 1979) and channels with random parameters (Gelf'and and Pinsker, 1980). We consider quantum generalizations of these setting, which includes the tasks of quantum state redistribution and entanglement-assisted channel coding, and construct new one-shot protocols for the corresponding tasks. We construct all our protocols as simple applications of two techniques, namely convex-split and position-based decoding. We also discuss some further applications of the convex-split technique, in the context of port-based teleportation and quantum resource theory.

Based on joint works with Vamsi Krishna Devabathini, Min-Hsiu Hsieh, Rahul Jain and Naqueeb Ahmad Warsi. arXiv quant-ph identifiers: 1410.3031, 1702.01940, 1703.09961, 1708.00381 .

**Fernando Pastawski, Free University of Berlin**

Holographic quantum error-correcting codes

Approximate quantum Markov chains

A state on a tripartite quantum system A⊗B⊗C forms a Markov chain in order A↔B↔C if it can be reconstructed from its marginal on A⊗B by a recovery map from B to B⊗C. The properties of Markov chains are well studied and understood, e.g., we know algebraic and entropic characterizations for the set of Markov chains. In this talk we ask the question of how to define a robust version of Markov chains, so-called approximate Markov chains, that approximately satisfy (some of) the properties of Markov chains.

**Cecilia Lancien, Complutense University of Madrid**

Weak multiplicativity/additivity in quantum information theory - The possible role of de Finetti reductions and entanglement measure theory

Showing that certain quantities exhibit a multiplicative (or additive) behavior is an ubiquitous issue in information theory and theoretical computer science (both classical or quantum). In this talk, I will be focussing mainly on the following such problem: 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. 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. It will be based on joint work with Andreas Winter, appearing mostly in arXiv:1605.09013.

**John Wright, Massachusetts Institute of Technology**

Quantum state certification

**Sergii Strelchuk, University of Cambridge**

Optimal port-based teleportation in arbitrary dimension

Port-based teleportation (PBT), is a family of protocols which allow to transfer quantum states to another system without unitary correction. In this setting, Alice and Bob start by sharing N EPR pairs (ports). Alice performs a joint measurement on the state to be teleported and all of her ports communicating her classical measurement outcome to Bob who then discards all but one port identified by this outcome. Its performance is well understood in the qubit case for arbitrary number of ports. In higher dimensions this required exponential computational overhead. In this talk I will describe how by connecting PBT schemes to the algebra of partially transposed operators one can efficiently find an optimal solution for the fidelity of transmission and other quantities of interest for PBT protocols in all dimensions and all performance regimes. I will overview the mathematical tools we developed to analyze quantum systems with partial symmetries. Operators that appear in PBT protocols are one such example. Systems with partial symmetries arecommonplace but unlike their fully permutationally-invariant counterparts very little is known about how to efficiently analyze their properties.

**Chris Majenz****, University of Copenhagen**

**Gemma de las Cuevas, University of Innsbruck**

Matrix Product States: Irreducible forms and Continuum limits

This talk will consist of two parts. In the first part, I will present the irreducible form of a Matrix Product States (MPS), which is a generalization of the canonical form of an MPS in the sense that it is also defined for states with periodicity. I will then present a fundamental theorem for MPS in irreducible form, namely one that specifies how two tensors in irreducible form are related if they give rise to the same MPS. Finally, I will present two applications of this result: an equivalence between the refinement properties of a state and the divisibility properties of its transfer matrix, and a more general characterisation of tensors that give rise to matrix product states with symmetries.

In the second part, I will present a study of continuum limits of MPS, where we show that an MPS has a continuum limit (for a proper definition thereof) if and only if its transfer matrix is an infinitely divisible channel. We also consider continuum limits after a finite number of coarse graining steps, and characterize it in terms of the divisibility properties of the transfer matrix. I will present several examples of states with and without the two kinds of continuum limits.

Joint work with I. Cirac, D. Perez-Garcia and N. Schuch. Based on arXiv:1708.00880 and arxiv:1708.00029.

**Adam Bouland, Massachusetts Institute of Technology**

The space below BQP

This talk examines the space "below BQP" -- that is, the power of "weak" quantum devices which do not seem capable of universal quantum computation. We describe a number of "weak" models of quantum computation which can nevertheless perform sampling tasks which are difficult for classical computers. We show that prior models maintain hardness when their set of quantum operations is restricted, and describe two new models of "weak" quantum computation which also show advantage over classical devices. A major theme in this work is that almost any weak model can perform hard sampling tasks. We find that almost any model which is not universal, but not known to be efficiently classically simulable, admits a speedup over classical computing for sampling tasks under plausible assumptions. This work can be seen as progress towards classifying the computational power of all restricted quantum gate sets.

**Shalev Ben-David, Massachusetts Institute of Technology**

The Structure Necessary for Quantum Speedups

One of the central insights in quantum computing has been that quantum computation seems to provide exponential speedups over classical computation, but only for certain "structured" problems, such as factoring. For unstructured problems, like NP-complete problems, we do not expect an exponential quantum speedups. This raises the question: can we formalize this intuition? What types of structure suffice?

In this talk, I will outline some of what we know about this problem, focusing primarily on the query complexity model due to its relative tractability. In the query complexity setting, we know that exponential speedups are not possible for total functions, but are sometimes possible when there is a promise on the input; I will describe what we know about the problem of characterizing the promises that allow exponential quantum speedups.

**Laura Mančinska, QMATH, University of Copenhagen**

Quantum-inspired relaxations of graph isomorphism

We introduce a nonlocal game that captures and extends the notion of graph isomorphism. This game can be won in the classical case if and only if the two input graphs are isomorphic. Thus, by considering quantum strategies we are able to define the notion of quantum isomorphism. We also consider the case of more general non-signalling strategies, and show that such a strategy exists if and only if the graphs are fractionally isomorphic. We prove several necessary conditions for quantum isomorphism, including cospectrality, and provide a construction for producing pairs of non-isomorphic graphs that are quantum isomorphic.

We then show that both classical and quantum isomorphism can be cast as feasibility programs over the completely positive and completely positive semidefinite cones respectively. This leads us to considering relaxations of (quantum) isomorphism arrived at by relaxing the cone to either the doubly nonnegative (DNN) or positive semidefinite (PSD) cones. We show that DNN-isomorphism is equivalent to the previous defined notion of graph equivalence which can be tested in polynomial time. Finally, we show that all of the above mentioned relations form a strict hierarchy of weaker and weaker relations, with non-singalling/fractional isomorphism being the weakest. The techniques used are an interesting mix of algebra, combinatorics, and quantum information.

This is a joint work with Albert Atserias, Robert Šamal, David Roberson, Simone Severini, and Antonios Varvitsiotis.

**Mischa Woods, University College London**

Quantum clocks: applications and quantum advantages

Clocks have proven to be extremely useful for our everyday life and devices. But what can we use quantum clocks for, what are their fundamental limitations, and finally, are they more efficient than classical clocks? In this talk, after introducing the notion of a finite dimensional quantum clock, we will study two related but different tasks: how well they can autonomously control another quantum system (e.g. perform the gates in a quantum computation) and how well they can tell the time by producing a periodic stream of “ticks”. For the former, we will prove they can do so while only enduring an exponentially small error in clock dimension and clock energy; while for the latter, we will derive the optimal quantum clock as a function of its dimension and compare it to the optimal classical (stochastic) clock of the same dimension; thus proving a separation in space resources between the optimal quantum and classical (stochastic) clocks.

This work is based on arXiv:1607.04591 and an upcoming paper, both co-authored by myself and Ralph Silva et al.

**Matt Courdron, Massachusetts Institute of Technology**

On the complexity of approximately commuting provers in interactive proofs

The class $\MIP^*$ of promise problems that can be decided through an interactive proof system with multiple entangled provers provides a complexity-theoretic framework for the exploration of the nonlocal properties of entanglement. Little is known about the power of this class. The only proposed approach for establishing upper bounds is based on a hierarchy of semidefinite programs introduced independentlyby Pironio et al. and Doherty et al. This hierarchy converges to a value that is only known to coincide with the provers' maximum success probability in a given proof system under a plausible but difficult mathematical conjecture, Connes' embedding conjecture. No bounds on the rate of convergence are known.

We introduce a rounding scheme for the hierarchy, establishing that any solution to its N-th level can be mapped to a strategy for the provers in which measurement operators associated with distinct provers have pairwise commutator bounded by O(l^2/\sqrt{N}) in operator norm, where ℓ is the number of possible answers per prover. Our rounding scheme motivates the introduction of a variant of $\MIP^*$, called $\MIP_\delta^*$, in which the soundness property is required to hold as long as the commutator of operations performed by distinct provers has norm at most δ. Our rounding scheme implies the upper bound

$\MIP_\delta^* \subseteq\DTIME(\exp(\exp(\poly)/\delta^2))$. In terms of lower bounds we establish that $\MIP^*_{2^{-\poly}}$, with completeness 1and soundness $1-2^{-\poly}$, contains $\NEXP$. The relationship of $\MIP_\delta^*$ to $\MIPstar$ has connections with the mathematical literature on approximate commutation. Our rounding scheme gives an elementary proof that the Strong Kirchberg Conjecture implies that $\MIPstar$ is computable. We discuss applications to device-independent cryptography.