Online-ICCHA2021

Online International Conference on
Computational Harmonic Analysis


September 13-17, 2021

"Convergent SDP-hierarchies for causal optimization"

Gross, David

A causal structure is a description of the functional dependencies between random variables. A distribution is compatible with a given causal structure if it can be realized by a process respecting these dependencies. Deciding whether a distribution is compatible with a structure is a practically and fundamentally relevant, yet very difficult problem. Only recently has a general class of algorithms been proposed: These so-called inflation techniques associate to any causal structure a hierarchy of efficiently solvable convex optimization problems. Remarkably, it has been shown that if causal influences are realized by the exchange of classical messages, this hierarchy is complete in the sense that each non-compatible distribution will be detected at some level of the hierarchy. We establish completeness results also for the case where quantum messages can be exchanged. The talk will focus on an introduction of the classical and quantum problem formulations and the necessary mathematical tools. Indeed, from a technical point of view, convergence proofs are built on de Finetti Theorems, which show that certain symmetries (which can be imposed in convex optimization problems) imply independence of random variables (which is not directly a convex constraint). A main technical ingredient to our proof is a Quantum de Finetti Theorem that holds for general tensor products of C?-algebras, generalizing previous work that was restricted to minimal tensor products.

« back