AND-gates in ZX-calculus: Spider Nest Identities and QBC-completeness

Anthony Munson
(University of Oxford)
Bob Coecke
(Cambridge Quantum Computing Ltd.)
Quanlong Wang
(Cambridge Quantum Computing Ltd.)

In this paper we exploit the utility of the triangle symbol which has a complicated expression in terms of spider diagrams in ZX-calculus, and its role within the ZX-representation of AND-gates in particular. First, we derive spider nest identities which are of key importance to recent developments in quantum circuit optimisation and T-count reduction in particular. Then, using the same rule set, we prove a completeness theorem for quantum Boolean circuits (QBCs) whose rewriting rules can be directly used for a new method of T-count reduction. We give an algorithm based on this method and show that the results of our algorithm outperform the results of all the previous best non-probabilistic algorithms.

In Benoît Valiron, Shane Mansfield, Pablo Arrighi and Prakash Panangaden: Proceedings 17th International Conference on Quantum Physics and Logic (QPL 2020), Paris, France, June 2 - 6, 2020, Electronic Proceedings in Theoretical Computer Science 340, pp. 230–255.
Published: 6th September 2021.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: