The complexity of compatible measurements

Measurement incompatibility is one of the basic aspects of quantum theory. Here we study the structure of the set of compatible -- i.e. jointly measurable -- measurements. We are interested in whether or not there exist compatible measurements whose parent is maximally complex, in the sense of requiring a number of outcomes exponential in the number of measurements, and related questions. Although we show this to be the case in a number of simple scenarios, we show that generically it cannot happen, by proving an upper bound on the number of outcomes of a parent measurement that is linear in the number of compatible measurements. We discuss why this doesn't trivialise the problem of finding parent measurements, but rather shows that a trade-off between memory and time can be achieved. Finally, we also investigate the complexity of extremal compatible measurements in regimes where our bound is not tight, and uncover rich structure.