Completeness for flow-preserving rewrite rules

• URL: http://arxiv.org/abs/2608.13035v1
• Date: Thu, 13 Aug 2026 10:03:31 GMT
• Title: Completeness for flow-preserving rewrite rules
• Abstract summary: Recent applications of the ZX-calculus have made use of the close correspondence between ZX-diagrams and computations.<n>We extend the set of flow-preserving rules appearing in the literature with a few new rules and extensions of existing rules.<n>We show that the resulting rule set is complete for all flow-preserving translations between ZX-diagrams of appropriate form.
• Score: 2.406359246841227
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Complete sets of graphical rewrite rules enable fully graphical reasoning about quantum computations and have been an area of active research for more than a decade. Many recent applications of the ZX-calculus have made use of the close correspondence between ZX-diagrams and computations in the one-way model of measurement-based quantum computation. In this model, various kinds of flow properties ensure deterministic implementability; for ZX-diagrams, these same properties allow efficient translation into quantum circuits (a problem that is known to be #P-hard in general). Therefore, flow-preserving ZX-calculus rewrite rules are of strong interest. Here, we extend the set of flow-preserving rules appearing in the literature with a few new rules and extensions of existing rules. We then show that the resulting rule set is complete for all flow-preserving translations between ZX-diagrams of appropriate form. The proof employs a manifestly flow-preserving equivalent of circuit extraction, where a diagram with gflow is transformed, using only flow-preserving rewrite rules, into a diagram with causal flow.

Related papers

• Generating one-way computations with flow: flow-preserving rewriting that ignores the interpretation [2.8427946758947304]
  One-way quantum computation is made deterministic overall by modifying later measurements depending on the outcomes of earlier ones.<n>Existing approaches to flow-preserving rewriting are used for compilation or optimisation.<n>We show that a family of just three flow-preserving rewrite rules suffices to generate any diagram with flow from a trivial diagram with the desired number of inputs and outputs.
  arXiv  Detail & Related papers  (2026-07-03T12:10:32Z)
• ZX-Flow: A Flexible Criterion for Deterministic Computation with ZX-Diagrams [0.0]
  We introduce a new flow criterion called ZX-flow, formulated using a new type of decoration of a ZX-diagram we call Pauli semiwebs.<n>We show that ZX-flow is straightforwardly preserved by all Clifford rewrites and furthermore that a ZX-diagram has ZX-flow if and only if it is Clifford-equivalent to a graph-like ZX-diagram with Pauli flow.
  arXiv  Detail & Related papers  (2026-03-10T12:26:09Z)
• Bridging wire and gate cutting with ZX-calculus [45.200826131319815]
  We show how decompositions of ideal, global unitaries can be obtained diagrammatically using ZX-calculus expanding.<n>We obtain improved decompositions for multi-qubit controlled-Z (MCZ) gates with $1$-norm equal to $3$ for any number of qubits and any partition.
  arXiv  Detail & Related papers  (2025-03-14T15:20:47Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Equivalence Classes of Quantum Error-Correcting Codes [49.436750507696225]
  Quantum error-correcting codes (QECC's) are needed to combat the inherent noise affecting quantum processes. We represent QECC's in a form called a ZX diagram, consisting of a tensor network.
  arXiv  Detail & Related papers  (2024-06-17T20:48:43Z)
• Tempered Calculus for ML: Application to Hyperbolic Model Embedding [70.61101116794549]
  Most mathematical distortions used in ML are fundamentally integral in nature. In this paper, we unveil a grounded theory and tools which can help improve these distortions to better cope with ML requirements. We show how to apply it to a problem that has recently gained traction in ML: hyperbolic embeddings with a "cheap" and accurate encoding along the hyperbolic vsean scale.
  arXiv  Detail & Related papers  (2024-02-06T17:21:06Z)
• ChatRule: Mining Logical Rules with Large Language Models for Knowledge Graph Reasoning [107.61997887260056]
  We propose a novel framework, ChatRule, unleashing the power of large language models for mining logical rules over knowledge graphs. Specifically, the framework is initiated with an LLM-based rule generator, leveraging both the semantic and structural information of KGs. To refine the generated rules, a rule ranking module estimates the rule quality by incorporating facts from existing KGs.
  arXiv  Detail & Related papers  (2023-09-04T11:38:02Z)
• Flow-preserving ZX-calculus Rewrite Rules for Optimisation and Obfuscation [0.0]
  We introduce several ZX-calculus rewrite rules that increase the number of qubits and preserve the existence of Pauli flow. We also give the first flow-preserving rewrite rule that allows measurement angles to be changed arbitrarily.
  arXiv  Detail & Related papers  (2023-04-17T11:28:47Z)
• Simple qudit ZX and ZH calculi, via integrals [0.0]
  ZX calculus and ZH calculus use diagrams to denote quantum operations, using rewrite rules' to transform between diagrams which denote the same operator through a functorial semantic map. We describe semantic maps for ZX and ZH diagrams, well-suited to analyse unitary circuits and measurements on qudits of any fixed dimension D>1 as a single ZXH-calculus' We demonstrate rewrite rules for the stabiliser fragment' of the ZX calculus and a multicharacter fragment' of the ZH calculus.
  arXiv  Detail & Related papers  (2023-04-06T18:00:31Z)
• Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
  We present a quantum circuit compiler that prepares an algorithm-specific graph state from quantum circuits described in high level languages. The computation can then be implemented using a series of non-Pauli measurements on this graph state.
  arXiv  Detail & Related papers  (2022-09-15T14:52:31Z)
• Simplification Strategies for the Qutrit ZX-Calculus [0.0]
  The ZX-calculus is a graphical language for suitably represented tensor networks, called ZX-diagrams. The ZX-calculus has found applications in reasoning about quantum circuits, condensed matter systems, quantum algorithms, quantum error codes, and counting problems.
  arXiv  Detail & Related papers  (2021-03-11T19:17:28Z)
• There and back again: A circuit extraction tale [0.0]
  We give the first circuit-extraction algorithm to work for one-way computations containing measurements in all three planes. The algorithm is efficient and the resulting circuits do not contain ancillae. We bring together several known rewrite rules for measurement patterns and formalise them in a unified notation using the ZX-calculus.
  arXiv  Detail & Related papers  (2020-03-03T17:45:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.