Double categories for adaptive quantum computation

Abstract

Quantum computation admits several models that emphasize different computational primitives and forms of classical control. We develop a unified double categorical framework for describing these models and the conversions between them. The syntax is provided by double port graphs, whose horizontal wires carry quantum information and whose vertical wires carry classical information and control. For each set of port labels, these graphs form a double category, and this construction is functorial in the label set. The semantics is given by the one-object double category of adaptive instruments. Its associated horizontal and vertical monoidal categories recover, respectively, quantum channels and stochastic maps. An assignment of an adaptive instrument to each primitive label therefore extends canonically to a double functor on labeled double port graphs, providing their computational semantics. We apply this framework to prominent models of quantum computation, including the circuit model, measurement-based quantum computation, quantum computation with magic states, and measurement-based Pauli computation. Gadget constructions from quantum computing that implement conversions between these models become double functors. Finally, we show that the interaction between quantum operations and affine classical control in measurement-based Pauli computation realizes every Boolean function in the vertical direction, thereby providing the non-affine classical operations required for its simulation of the circuit model.

47 pages, 2 figure