Double categories for adaptive quantum computation
Abstract
Quantum computation can be formulated through various models, each highlighting distinct structural and resource-theoretic aspects of quantum computational power. This paper develops a unified categorical framework that encompasses these models and their interrelations using the language of double categories. We introduce double port graphs, a bidirectional generalization of port graphs, to represent the quantum (horizontal) and classical (vertical) flows of information within computational architectures. Quantum operations are described as adaptive instruments, organized into a one-object double category whose horizontal and vertical directions correspond to quantum channels and stochastic maps, respectively. Within this setting, we capture prominent adaptive quantum computation models, including measurement-based and magic-state models. To analyze computational power, we extend the theory of contextuality to an adaptive setting through the notion of simplicial instruments, which generalize simplicial distributions to double categorical form. This construction yields a quantitative characterization of computational power in terms of contextual fraction, leading to a categorical formulation of the result that non-contextual resources can compute only affine Boolean functions. The framework thus offers a new perspective on the interplay between adaptivity, contextuality, and computational power in quantum computational models.