论文标题
Toffoli-Hadamard的总计和量子计算的二元片段的完整性
Completeness of Sum-Over-Paths for Toffoli-Hadamard and the Dyadic Fragments of Quantum Computation
论文作者
论文摘要
“总计”形式主义是一种象征性操纵线性图的方式来描述量子系统，并且是用于正式验证此类系统的工具。我们在这里为形式主义提供了一套新的改写规则，并表明它是“ Toffoli-Hadamard”完整的，这是量子力学的最简单通用片段。我们表明，重写正在终止，但不是汇合（这是从碎片的普遍性所期望的）。我们使用总计和图形语言zh-calculus之间的连接，并显示公理化如何转化为后者。最后，我们展示了如何丰富重写系统以达到量子计算的二元片段的完整性 - 通过将$π$的二元倍数添加到toffoli-Hadamard Gate-Set-ate-gate-set中获得 - 尤其是在量子傅立叶变换中使用。
The "Sum-Over-Paths" formalism is a way to symbolically manipulate linear maps that describe quantum systems, and is a tool that is used in formal verification of such systems. We give here a new set of rewrite rules for the formalism, and show that it is complete for "Toffoli-Hadamard", the simplest approximately universal fragment of quantum mechanics. We show that the rewriting is terminating, but not confluent (which is expected from the universality of the fragment). We do so using the connection between Sum-over-Paths and graphical language ZH-Calculus, and also show how the axiomatisation translates into the latter. Finally, we show how to enrich the rewrite system to reach completeness for the dyadic fragments of quantum computation -- obtained by adding phase gates with dyadic multiples of $π$ to the Toffoli-Hadamard gate-set -- used in particular in the Quantum Fourier Transform.
