One Rig to Control Them All
Chris Heunen, Robin Kaarsgaard, Louis Lemonnier
摘要
Controlled commands -- computations whose execution depends on a separate input -- play a central role in reversible Boolean circuits and quantum circuits. However, existing formalisms typically treat control only implicitly, entangled with other aspects of computation. From a semantic perspective, control is most naturally expressed in semisimple rig categories, which -- unlike standard circuit models such as props -- support both parallel and conditional composition. We present a construction that freely adjoins an explicit syntactic notion of control to a circuit theory specified as a suitable prop, subject to eight universally quantified equations. Our main result is that these equations are sound and complete for the intended semantics of control: the resulting theory satisfies a universal property, identifying it exactly as the circuit subtheory of the free semisimple rig completion. The proof combines coherence for rig categories with a new method based on induction over Gray codes. We illustrate the usefulness of the framework by showing that it simplifies several existing sound and complete axiomatisations of quantum circuits, isolating a small and conceptually clean set of generators and equations. In addition, the same equations yield a sound and complete axiomatisation of the multiply controlled Toffoli gate set, that is universal for reversible Boolean circuits.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
引用它的顶会 Paper1
问问它们各自怎么用它它引用的顶会 Paper6
- A Complete Equational Theory for Quantum CircuitsAlexandre Clément, Nicolas Heurtel, Shane Mansfield, Simon Perdrix 等LICS 2023 · 被引用 14 次
- With a Few Square Roots, Quantum Computing Is as Easy as PiJacques Carette, Chris Heunen, Robin Kaarsgaard, Amr SabryPOPL 2024 · 被引用 7 次
- Minimal Equational Theories for Quantum CircuitsAlexandre Clément, Noé Delorme, Simon PerdrixLICS 2024 · 被引用 3 次
- Quantum information effectsChris Heunen, Robin KaarsgaardPOPL 2022 · 被引用 1 次
- Hadamard-Pi: Equational Quantum ProgrammingWang Fang, Chris Heunen, Robin KaarsgaardPOPL 2026
相关 Paper
- Complete ω-Regular Supermartingale CertificatesAlessandro Abate, Mirco Giacobbe, Sergey Ichtchenko, Diptarko RoyLICS 2026
- Symmetries in reversible programming: from symmetric rig groupoids to reversible programming languagesVikraman Choudhury, Jacek Karwowski, Amr SabryPOPL 2022 · 被引用 10 次
- Optimal Synthesis of Multi-Controlled Qudit GatesWei Zi, Qian Li, Xiaoming SunDAC 2023 · 被引用 7 次
- Linear Dependent Type Theory for Quantum Programming Languages: Extended AbstractPeng Fu, Kohei Kishida, Peter SelingerLICS 2020 · 被引用 23 次
- Verification of Recursively Defined Quantum CircuitsMingsheng Ying, Zhicheng ZhangPLDI 2026
