Mathematics of Quantum Information Theory


On May 6-10 2019, there was a workshop `Mathematics of Quantum Information Theory' at the Lorenz center in Leiden, organised by Jop Briet, Martijn Caspers, Bas Janssens and Maris Ozols. The focus of the workshop is on geometric functional analysis,(approximate) representation theory and quantum Markov processes.

Talks

Below you can find the title and abstract of the talks, and the slides if available.

Guillaume Aubrun: Tensor products of convex cones and generalized probabilistic theories

In the category of finite-dimensional convex cones, there are natural notions of minimal and maximal tensor products. A basic question is to determine when both notions coincide. It is natural to conjecture that this happens exactly when one of the cones is linearly isomorphic to an orthant. We report progress towards this conjecture, including a solution for polyhedral cones. This question is strongly motivated by foundations of physics, within the framework of generalized probabilistic theories (GPTs). There, the conjecture postulates that entanglement exists between any pair of non-classical theories. A related question can be asked in the category of finite-dimensional normed spaces: how much do the projective and injective norms differ? The framework of GPTs allows us to give operational interpretations to both norms, and to their ratio, whose study naturally involves Banach space techniques (see also the talk by S.Szarek). Based on joint work with L.Lami, C.Palazuelos, S.Szarek, A.Winter.

Toby Cubitt: TBA

Alex Bredariol Grilo: Hamiltonian complexity meets derandomization (slides)

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the MA-completeness of the problem of deciding whether the groundenergy of a uniform stoquastic local Hamiltonian is zero or inverse polynomial. We show that the gapped version of this problem, i.e. deciding if a given uniform stoquastic local Hamiltonian is frustration-free or has energy at least some constant epsilon, is in NP. Thus, if there exists a gap-amplification procedure for uniform stoquastic Local Hamiltonians (in analogy to the gap amplification procedure for constraint satisfaction problems in the original PCP theorem), then MA = NP (and vice versa). Furthermore, if this gap amplification procedure exhibits some additional (natural) properties, then P = RP. We feel this work opens up a rich set of new directions to explore, which might lead to progress on both quantum PCP and derandomization. As a small side result, we also show that deciding if commuting stoquastic Hamiltonian is frustration free is in NP. Joint work with Dorit Aharonov.

Matthias Christandl: Tensor network representations from the geometry of entangled states

Tensor network states provide successful descriptions of strongly correlated quantum systems with applications ranging from condensed matter physics to cosmology. Any family of tensor network states possesses an underlying entanglement structure given by a graph of maximally entangled states along the edges that identify the indices of the tensors to be contracted. Recently, more general tensor networks have been considered, where the maximally entangled states on edges are replaced by multipartite entangled states on plaquettes. Both the structure of the underlying graph and the dimensionality of the entangled states influence the computational cost of contracting these networks. Using the geometrical properties of entangled states, we provide a method to construct tensor network representations with smaller effective bond dimension. We illustrate our method with the resonating valence bond state on the kagome lattice.

John Gough: How to think of Quantum Markov Models from an Engineering Perspective (slides)

We review the theory of quantum feedback networks and show how it gives a framework for a system theoretic description applicable to quantum engineering. The network rules are presented along with an overview of feedback based control. There are two main approaches: feedback by the observed output signal; and feedback by the actual quantum output itself. We will illustrate this with several current examples from quantum technology, in particular, quantum optics and super-conducting qubits.

Madalin Guta

Talk 1: Fast state tomography with optimal error bounds (slides)

In this talk I will review the quantum tomography problem and discuss an intuitive and numerically cheap technique called Projected Least Squares (PLS) estimation. The method first computes the least-squares estimator (or a linear inversion estimator) and then projects the initial estimate onto the space of states. The main result shows that this point estimator satisfies non-asymptotic concentration bounds in terms of the trace distance, for a variety of measurements, including 2-designs and Pauli measurements. The sample complexity of the estimator is comparable to the strongest convergence guarantees available in the literature and - in the case of measuring the uniform POVM - saturates fundamental lower bounds. The results are derived by reinterpreting the least-squares estimator as a sum of random matrices and applying a matrix-valued concentration inequality. The theory is supported by numerical simulations for mutually unbiased bases, Pauli observables, and Pauli basis measurements.

Talk 2: Local asymptotic normality in quantum statistics (slides)

From IID ensembles to Markovdynamics Abstract: In this talk I will give an introduction to the concept of local asymptotic normality (LAN) and how it can be used to find asymptotically optimal measurement procedures for quantum tomography with IID ensembles, and for the estimation of dynamical parameters of quantum Markov systems. In a nutshell, LAN means that in the limit of large samplesizes (number of systems in the IID case and time in the Markov case) the statistical model of interest can be approximated locally (in the tangent space) around a given paramter, by a more tractable Gaussian shift model consisting of a family of Gaussian states of fixed variance and mean equal to the a linear transoformation of the tangent vector. The transformation between models can be implemented operationally via quantum channels, and leads to asymptotically optimal estimation procedures (map to Gaussian and measure the latter) and Gaussian confidence regions. In the Markovian case, LAN gives rise to an information geometry structure on the space of Markov dynamical systems.

Hans Maassen: Entanglement of symmetric Werner states (slides)

The study of entanglement between more than two systems or particles is complicated by the fact that the number of degrees of freedom of n particles, each with a d-dimensional Hilbert space, increases steeply as a function of n or d. By requiring symmetry both under particle permutation and under joint unitary transformations, we are left with the symmetric Werner states. This "backbone" of states simplifies the analysis considerably, yet retains a rich structure. The barycentric coordinates of symmetric Werner states are given by immanants of positive definite matrices, thus laying a connection with Lieb'sconjecture on these objects. Interpreting a result of Barrett, Hall, and Loewy, we find that the separable symmetric Werner states form a polytope for n=2, 3, and 4, but not for any larger number of particles. Restriction of symmetric Werner states to a smaller number of particles is governed by a transition probability on the Young graph. Christandl, Koenig, Mitchison and Renner showed that extendability of symmetric Werner states to arbitrary particle number implies separability in a strong sense: they must be convex combinations of tensor power states. A norm on state space defined by Arveson characterizes entanglement in a quantitative way.

Joel Klassen: When is a Hamiltonian Stoquastic (slides)

Finding the lowest energy of a Hamiltonian is a hard problem in general, however for many physical systems quantum Monte Carlo methods can often be effectively applied to determine the lowest energy of a Hamiltonian, and it is commonly understood that the absence of a sign problem is a requisite condition for the success of these methods. The notion of stoquastic Hamiltonians was introduced with the aim of categorizing those Hamiltonians which do not suffer from the sign problem. Indeed, the study of stoquastic Hamiltonians in the context of computational complexity theory has lent support to the notion that stoquastic Hamiltonians are somehow ?simpler? than generic Hamiltonians. Importantly, the property of being stoquastic makes itself manifest only in a particular local basis choice. In this work we explore how hard it is, from a computational complexity perspective, to find such a choice of basis. I will present an outline of an efficient algorithm for deciding if a 2-local Hamiltonian, with no 1-local terms, is stoquastic in some local basis.

Robert König: Quantum advantage with noisy shallow circuits in 3D

Prior work has shown that there exists a relation problem which can be solved with certainty by a constant-depth quantum circuit composed of geometrically local gates in two dimensions, but cannot be solved with high probability by any classical constant depth circuit composed of bounded fan-in gates. Here we provide two extensions of this result. Firstly, we show that a separation in computational power persists even when the constant-depth quantum circuit is restricted to geometrically local gates in one dimension. The corresponding quantum algorithm is the simplest we know of which achieves a quantum advantage of this type. It may also be more practical for future implementations. Our second, main result, is that a separation persists even if the shallow quantum circuit is corrupted by noise. We construct a relation problem which can be solved with near certainty using a noisy constant-depth quantum circuit composed of geometrically local gates in three dimensions, provided the noise rate is below a certain constant threshold value. On the other hand, the problem cannot be solved with high probability by a noise-free classical circuit of constant depth. A key component of the proof is a quantum error-correcting code which admits constant-depth logical Clifford gates and single-shot logical state preparation. We show that the surface code meets these criteria. To this end, we provide a protocol for single-shot logical state preparation in the surface code which may be of independent interest.This is joint work with Sergey Bravyi, David Gosset and Marco Tomamichel.

Burkhard Kümmerer: Scattering Theory for Markov Processes - An Interplay between Classical and Quantum Probability

The structure of a typical quantum Markov chain suggests to study also an alternative construction for classical Markov chains and to look at both from the point of view of scattering theory. We demonstrate how this "quantum point of view" leads to new insights when spezialized to classical Markov chains, which in turn suggest a second look at the quantum case, and the techniques developed here are crucial for our analysis of classical Markov chains with countable state space ... a story which has not yet come to an end.

Pieter Naaijkens: Capacity of quantum channels from subfactors (slides)

Consider a subfactor, i.e. a unital inclusion of von Neumann algebras with trivial centre. From the work of Jones (and generalisations by Kosaki and Longo) one can assign an index to such a subfactor, which says something about the relative size of the two algebras. In this talk I will argue that this setting naturally leads to a quantum (wiretapping) channel, with classical capacity given by the index. A key step in passing from operator algebra to quantum information is using the Pimsner-Popa formulation of the index in terms of Araki relative entropies. This provides new operator algebraic tools to study quantum information tasks in systems with infinitely many degrees of freedom, such as conformal field theory of Kitaev's toric code on an infinite plane.

Michal Oszmaniec: TBA

Jonas Helsing: TBA

David Pérez-Garcia: Spectral gap in PEPS

Quantum information theory and the theory of quantum many body systems are inextricably connected. An important part of this connection is mediated through the so called Projected Entangled Pair States (PEPS), variational families of states which mimic the entanglement structure present in ground states and thermal states of quantum many body systems Each PEPS comes together with an associated ?parent? Hamiltonian. Proving whether this Hamiltonian is gapped or gapless remains an important open problem. In this talk I will review some recent progress in this problem. (joint work with M. Kastoryano, A. Lucia and A. Pérez.)

William Slofstra

Talk 1: Approximate representation theory and non-local games: stability

Approximate representation theory is a fledgling research area which studies "approximate representations" of algebras (for several different notions of approximate representation). One of the central questions in approximate representation theory is stability: for which algebras are approximate representations close to actual representations? Approximate representation theory arises naturally in the theory of non-local games. In this talk, I'll give an overview of this connection, focusing on the connection between stability androbust self-testing.

Talk 2: Approximate representation theory and non-local games:Tsirelson problems and entanglement requirements

In this talk, I'll continue with the connection between approximate representation theory and nonlocal games, focusing on Tsirelson problems and entanglement requirements for games.

Stanislaw Szarek: On the discrepancy between norms on tensor products of normed spaces (slides)

The projective and injective norms are extreme ones among natural tensor products of normed spaces. An obvious question is "How much do they differ?" This question was considered by Grothendieck and Pisier (respectively in the 1950s and 1980s), but - surprisingly - no quantitative analysis of the finite-dimensional case was ever made. As explained in the talk of G. Aubrun, this last question comes up naturally in the context of generalized probabilistic theories (GPTs), where it can be restated as "How powerful are global strategies compared to local ones?"We will show that the discrepancy between the projective and injective norms on a tensor product of two finite-dimensional normed spaces E and F is always lower-bounded by the power of the (smaller) dimension, with the exponent depending on the generality of the setup (e.g., E = F or dim E = dim F). Some of the results are essentially optimal, but other can be likely improved. The methods involve a wide range of techniques from geometry of Banach spaces and random matrices.Based on joint work with G. Aubrun, L. Lami, C. Palazuelos, and A. Winter.

Michael Walter: Quantum marginals, invariants, and non-commutative optimization (slides)

Given a vector in a representation, can it be distinguished from zero by an invariant polynomial? Remarkably, this simple question captures many interesting problems in quantum information, computational complexity, algebra, and analysis, as we will see in several examples (including the quantum marginal problem). I will explain how the general question can be usefully thought of as an optimization problem over non-commutative groups, discuss the underlying geometry, and present rigorous algorithms for solving it. Mathematically, these are algorithms for minimizing moment maps (a non-commutative version of the gradient) and testing membership in moment polytopes (a vast class of polytopes that arise in this setting).

Jeroen Zuiddam: The theory of asymptotic spectra

The Shannon capacity of a graph is the rate of growth of the independence number under taking the strong power, or in different words, it is the maximum rate at which information can be transmitted over a noisy communication channel. We give a dual description of the Shannon capacity as a minimization over the "asymptotic spectrum of graphs", which unifies previous results and naturally gives rise to new questions.Besides a gentle introduction to this topic we discuss the general idea of "asymptotic spectra". The theory of asymptotic spectra of Strassen is a theory about properties of large powers of objects, which, besides the Shannon capacity of graphs, helps us understand quantum versions of Shannon capacity (joint work with Yinan Li), the matrix multiplication exponent and asymptotic slocc (stochastic local operations and classical communication) protocols (joint work with Matthias Christandl and Péter Vrana), and more.