Graph-theoretic simplification of quantum circuits with the ZX-calculus

Duncan, Ross and Kissinger, Aleks and Perdrix, Simon and van de Wetering, John (2020) Graph-theoretic simplification of quantum circuits with the ZX-calculus. Quantum, 4. 279. ISSN 2521-327X

[img]
Preview
 Text (Duncan-etal-Quantum-2020-Graph-theoretic-simplication-of-quantum-circuits-with-the-ZX-calculus)
Duncan_etal_Quantum_2020_Graph_theoretic_simplication_of_quantum_circuits_with_the_ZX_calculus.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (1MB)| Preview

    Abstract

    We present a completely new approach to quantum circuit optimisation, based on the ZX-calculus. We first interpret quantum circuits as ZX-diagrams, which provide a flexible, lower-level language for describing quantum computations graphically. Then, using the rules of the ZX-calculus, we give a simplification strategy for ZX-diagrams based on the two graph transformations of local complementation and pivoting and show that the resulting reduced diagram can be transformed back into a quantum circuit. While little is known about extracting circuits from arbitrary ZX-diagrams, we show that the underlying graph of our simplified ZX-diagram always has a graph-theoretic property called generalised flow, which in turn yields a deterministic circuit extraction procedure. For Clifford circuits, this extraction procedure yields a new normal form that is both asymptotically optimal in size and gives a new, smaller upper bound on gate depth for nearest-neighbour architectures. For Clifford+T and more general circuits, our technique enables us to to `see around' gates that obstruct the Clifford structure and produce smaller circuits than naïve `cut-and-resynthesise' methods.

    Creators(s): Duncan, Ross ORCID logoORCID: https://orcid.org/0000-0001-6758-1573, Kissinger, Aleks, Perdrix, Simon and van de Wetering, John;
    Item type:Article
    ID code:73158
    Keywords:quantum science, ZX-calculus, quantum circuits, ZX-diagrams, graph, Electronic computers. Computer science, Computational Theory and Mathematics
    Subjects:Science > Mathematics > Electronic computers. Computer science
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:09 Jul 2020 15:05
    Last modified:22 Sep 2020 02:52
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/73158
    Export data:
    CORE (COnnecting REpositories)