Sudoku on steroids - The combinatorics of causal inference - TC Fraser

The objective of causal inference is to determine whether or not a system of correlated variables is compatible with a provided causal hypothesis; such hypotheses are encoded in directed acyclic graphs called causal networks. Unsurprisingly, the methodology behind causal inference is utilized in a myriad of disciplines including epidemiology, machine learning, policy making, economics and biological systems. Surprisingly, for the vast majority of small causal networks, there is no difference between the sets of compatible classical and quantum correlations, and consequently no opportunity for computational or communicational advantages. It therefore becomes incumbent to find the rare causal networks which have the capacity to support a quantum/classical separation.

In this talk, I will introduce a graphical object called a possible worlds diagram, which transforms the problem of deciding classical causal compatibility into a simple, combinatorial, constraint satisfiability game resembling Sudoku. Using several examples, I will demonstrate how to prove causal incompatibility by playing this game; including an example where no other techniques have made any progress. I will prove this approach forms a complete solution to the possibilistic causal compatibility problem and moreover, if one exploits graphical symmetries and novel consistency constraints, one can implement a hierarchy of necessary compatibility tests for the probabilistic causal compatibility problem which converges to sufficiency. Importantly, these techniques reveal which causal networks have the capacity for quantum/classical separation.