Abstract

A sequential model is a type of causal network that describes the (discrete) time evolution of a system’s external output, as well as its internal state, and can be regarded as a generalization of a Markov decision process. At each time-step, the system transitions from one internal state to the next through a known equation of motion, which depends on the current state of the system and: (a) unobserved evolution parameters, the same for all times; (b) a number of uncontrolled (and unobserved) variables at each time; and (c) optionally, the (observed) input or policy of an agent interacting with the system. The (observed) output of the system, which can be regarded as a penalty, depends in a known way on all the afore-mentioned variables, the systems’ current internal state and the time. In this talk, I will argue that many tasks in quantum information, but also in other fields, such as mathematical epidemiology, can be formulated as the maximization of the cumulative penalty of a sequential model over variables of type (a) and (b). Next I will introduce general mathematical tools to upper bound this quantity. We will use these tools to bound the maximum probability that a probabilistic finite-state automata generates a specific (finite) sequence of bits and to devise new protocols for entanglement detection in many-body systems. Finally, I will introduce a heuristic to minimize upper bounds on the penalty over all allowed policies. Given any sequential model, the heuristic will generate policies with an acceptable proven worst-case performance with a computational cost comparable to that of establishing the upper bound.

Video Recording