Complete Equational Theories for the Sum-Over-Paths with Unbalanced Amplitudes

Abstract

Vilmart recently gave a complete equational theory for the balanced sum-over-paths over Toffoli-Hadamard circuits, and by extension Clifford+Rz(2pi/2^k) circuits. Their theory is based on the phase-free ZH-calculus which crucially omits the average rule of the full ZH-calculus, dis-allowing the local summation of amplitudes. Here we study the question of completeness in unbalanced path sums which naturally support local summation. We give a concrete syntax for the unbalanced sum-over-paths and show that, together with symbolic multilinear algebra and the interference rule, various formulations of the average and ortho rules of the ZH-calculus are sufficient to give complete equational theories over arbitrary rings and fields.

In Proceedings QPL 2023, arXiv:2308.15489

Cited by in corpus (6)

• FeynmanDD: Quantum Circuit Analysis with Classical Decision Diagrams
• Automating Equational Proofs in Dirac Notation
• Rewriting and Completeness of Sum-Over-Paths in Dyadic Fragments of Quantum Computing
• Equivalence Checking of Quantum Circuits via Path-Sum and Weighted Model Counting
• Hybrid Path-Sums for Hybrid Quantum Programs
• Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums