一句话：提出延迟迹的图语言构造，将任意可丢弃图语言扩展为有限内存计算语言，并给出流语义及完备性结果。
图语言（如量子线路、ZX-calculus）擅长表示有限量子比特上的无记忆量子计算，而延迟迹可在经典笛卡尔数据类型中以图形方式表示流上的有限内存计算。本文融合两者，提出通用构造：只要图语言具备丢弃概念，就能扩展为有限内存计算的图语言。为覆盖 ZX-calculus 这类对后选择量子力学完备的情形，作者将延迟迹推广到非因果情形，细化流变换器的因果性，并基于有状态态射序列给出流语义。在若干假设下，证明了框架的通用性与完备性，并讨论了其与笛卡尔数据类型、信号流图及带记忆量子信道的联系。
Graphical languages, like quantum circuits or ZX-calculus, have been successfully designed to represent (memoryless) quantum computations acting on a finite number of qubits. Meanwhile, delayed traces have been used as a graphical way to represent finite-memory computations on streams, in a classical setting (cartesian data types). We merge those two approaches and describe a general construction that extends any graphical language, equipped with a notion of discarding, to a graphical language of finite memory computations. In order to handle cases like the ZX-calculus, which is complete for post-selected quantum mechanics, we extend the delayed trace formalism beyond the causal case, refining the notion of causality for stream transformers. We design a stream semantics based on stateful morphism sequences and, under some assumptions, show universality and completeness results. Finally, we investigate the links of our framework with previous works on cartesian data types, signal flow graphs, and quantum channels with memories.
DOI 原文 ·
@inproceedings{paperbot6205,
title = {Graphical Language with Delayed Trace: Picturing Quantum Computing with Finite Memory},
author = {Titouan Carette and Marc de Visme and Simon Perdrix},
booktitle = {LICS},
year = {2021},
doi = {10.1109/lics52264.2021.9470553}
}