Séminaire APR

Compiling Higher-Order Bayesian Networks

Tuesday, March 17, 2026
Gabriele Vanoni (IRIF, Université Paris Cité)

A fascinating connection has recently been exposed [Low et al. 2014] between quantum circuits and Bayesian Networks [Pearl 1988], the latter being a prominent tool for probabilistic reasoning. Such a line of research exploits the power of quantum computing to accelerate Bayesian inference over Bayesian Networks. To do so, Bayesian Networks are encoded into quantum circuits, where each boolean random variable is represented by a qubit. A quantum version of the rejection sampling algorithm [Ozols et al. 2013] yields a quadratic speed-up. Our goal is to exploit this body of research to accelerate inference in *higher-order* probabilistic programs. We present the first steps in the development of an end-to-end methodology that would allow users to write stochastic models in a functional higher-order probabilistic programming language, and that produces as output the quantum circuit ready to be used for quantum rejection sampling. The goal is to leverage both the expressiveness of a fully-fledged probabilistic language and the speedup brought by the quantum technology. The main challenge is that the target of the compilation—a quantum circuit—can only handle a finite amount of information. To deal with this issue, we integrate resource-awareness in the compilation scheme, relying on techniques rooted in linear logic and abstract machines.

Antoine.Mine (at) nulllip6.fr