PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus

Ross Duncan, Aleks Kissinger, Simon Perdrix, John van de Wetering

arXiv:1902.03178v6quant-phcs.LOmath.CO

TL;DR

Quantum-circuit optimisation lacks broadly flexible methods, and simplified ZX-diagrams are not generally easy to extract back into circuits. This paper uses ZX-calculus rewrites based on local complementation and pivoting, preserving focused gFlow so reduced diagrams can be extracted. The resulting framework gives an asymptotically optimal Clifford normal form and supports stronger simplification of general circuits than naive Clifford partitioning.

  • Problem

    Quantum circuit optimisation is relatively undeveloped, and generic unitary ZX-diagrams lack a known general-purpose efficient procedure for recovering circuits.

  • Method

    The paper rewrites circuit-derived ZX-diagrams using local complementation and pivoting, while preserving focused gFlow for deterministic circuit extraction.

  • Results

    72% of benchmark circuits matched or outperformed the state of the art under a subsequent ancilla-free T-count technique, with reductions up to 50%.

  • Takeaways & Limitations

    The framework yields an asymptotically optimal Clifford normal form and can exploit non-local structure beyond naive cut-and-resynthesise methods.

  • Takeaways & Limitations

    Efficient extraction from general ZX-diagrams remains open, and more aggressive rewrites can make gFlow-based re-extraction problematic.

Abstract

from arXiv · show

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 naive 'cut-and-resynthesise' methods.

1 Introduction

The paper introduces ZX-calculus circuit optimisation as a more flexible alternative to circuit-level rewrites, while addressing the difficulty of extracting circuits from simplified diagrams.

  • Quantum circuit optimisation remains relatively undeveloped and commonly relies on gate substitutions, special-family normal forms, or phase-polynomial optimisation.
  • ZX-diagrams provide a lower-level, deformable representation with a rich equational theory for simplifying quantum computations.
  • Generic unitary ZX-diagrams lack a known general-purpose efficient circuit-extraction procedure, so optimisation must preserve extractable structure.
  • The proposed strategy uses local complementation and pivoting to delete generators, producing GS-LC form for Clifford circuits and supporting extraction for non-Clifford circuits.
  • 72% of tested benchmark circuits matched or outperformed the state of the art under a subsequent ancilla-free T-count reduction technique, with reductions up to 50%.

2 The ZX-calculus and quantum circuits

The ZX-calculus represents quantum computations as composable diagrams of spiders and wires, with rewrite rules that support circuit descriptions and simplification.

  • ZX-diagrams consist of wires and Z- or X-spiders, and support composition and tensor products of linear maps.
  • A diagram with m inputs and n outputs represents a linear map from (C2)⊗m to (C2)⊗n, while input-free diagrams represent unnormalised quantum states.
  • The ZX-calculus equates diagrams under deformation and additional rewrite rules, with completeness established for Clifford diagrams and extended families.
  • Quantum circuits are defined as ZX-diagrams generated by compositions and tensor products of the chosen gate-diagram generators.
  • Clifford circuits use CNOT, H, and S gates, while adding T gates gives Clifford+T circuits capable of approximating arbitrary n-qubit unitaries.

3 Graph-like ZX-diagrams

Graph-like ZX-diagrams impose a structured form whose underlying open graphs support graph-theoretic reasoning and deterministic circuit extraction via focused gFlow.

  • Graph-like diagrams additionally ensure each input or output connects to at most one Z-spider, yielding an underlying open graph of spiders and Hadamard edges.
  • Graph-like ZX-diagrams generalise graph states by allowing arbitrary phases and interior spiders.
  • Every ZX-diagram can be rewritten into graph-like form, where all spiders are Z-spiders connected only by Hadamard edges without loops or parallel edges.
  • Focused gFlow assigns correction sets and a vertex order that provide the graph-theoretic structure needed for extraction.
  • The graph underlying any graph-like diagram obtained from a circuit admits a focused gFlow.

4 Local complementation and pivoting

Local complementation and pivoting are graph transformations represented by ZX-calculus rewrites; crucially, their permitted deletions preserve gFlow for circuit extraction.

  • Local complementation toggles edges between the neighbours of a selected vertex while leaving other edges unchanged.
  • Pivoting along an edge is defined as three successive local complementations and exchanges the two endpoint vertices.
  • Both transformations correspond to ZX-diagram operations involving local Clifford phases, and pivoting also introduces a vertex swap.
  • Focused gFlow is preserved after local complementation followed by deleting its vertex, or pivoting followed by deleting both endpoint vertices.

5 A simplification strategy for circuits

The paper simplifies graph-like ZX-diagrams by removing interior Clifford and Pauli spiders through local complementation and pivoting, while preserving focused gFlow. For Clifford inputs, the procedure eliminates all interior spiders and supports circuit extraction.

  • Rewrite strategy: The routine repeatedly applies local complementation and pivoting to remove interior Clifford and Pauli spiders from graph-like ZX-diagrams.It targets proper Clifford spiders, adjacent interior Pauli pairs, and interior Pauli spiders adjacent to boundary spiders.
  • Clifford case: For Clifford diagrams, the simplified diagram contains no interior spiders.Graph-like translations of Clifford circuits contain only Clifford spiders, so Theorem 5.4's special case applies.
  • Rewrite strategy: The procedure terminates because every rewrite removes at least one marked node and does not introduce non-Clifford spiders.Its worst-case complexity is O(n3) for n spiders.
  • Extraction guarantee: The simplification preserves focused gFlow, ensuring that the reduced diagram retains the graph-theoretic structure needed for deterministic circuit extraction.The relevant graph transformations preserve focused gFlow, including the input/output extension associated with boundary-spider handling.
  • Non-Clifford case: In circuits with about 2% non-Clifford gates, a 195-gate circuit with 4 non-Clifford gates reduces to a skeleton containing 12 spiders.The remaining interior spiders are non-Clifford or Pauli spiders with only non-Clifford neighbours.

6 Circuit extraction of Clifford circuits

The paper extracts Clifford circuits from the graph-state-with-local-Cliffords form produced by simplification. The resulting normal form has asymptotically optimal size and improves the nearest-neighbour depth bound to 9n −2.

  • Extraction procedure: GS-LC diagrams are extracted by unfusing spiders into local Cliffords and CZ gates, then converting the remaining parity circuit into CNOT gates.The parity portion is implemented using Gaussian elimination over F2.
  • Normal form: The extracted Clifford circuit can be represented in six layers: Local Clifford + CZ + CNOT + H + CZ + Local Clifford.The paper further refines this decomposition into eight layers, H + S + CZ + CNOT + H + CZ + S + H.
  • Optimality: The GS-LC pseudo-normal form has 2n2 + O(n) degrees of freedom, which is asymptotically optimal for n-qubit Clifford unitaries.The comparison is based on the number of Boolean degrees of freedom required to specify all n-qubit Clifford unitaries.
  • Nearest-neighbour depth: 9n −2 is the two-qubit gate-depth bound for mapping the GS-LC normal form to a linear nearest-neighbour architecture.The paper presents this as an improvement over the previously cited 14n −4 bound.

7 Circuit extraction for general circuits

The extraction procedure converts simplified ZX-diagrams into circuits by exploiting focused gFlow and Gaussian elimination, then evaluates the resulting optimisation on random Clifford+T circuits.

  • Extraction procedure: Focused gFlow guarantees that the extraction procedure can progress the frontier from outputs toward inputs until a circuit is obtained.The procedure repeatedly selects an unextracted vertex whose correction set lies in the frontier, performs row operations, and updates the frontier.
  • Extraction procedure: Primitive row operations on the diagram’s biadjacency matrix correspond to CNOT gates while preserving focused gFlow.The matrix transformation adds one row to another modulo 2, and the resulting diagram retains focused gFlow when the original has it.
  • Extraction procedure: The algorithm repeatedly isolates a frontier connection, removes a phaseless degree-two vertex, and unfuses the extracted vertex’s phase into the circuit.After row operations disconnect unwanted frontier neighbours, the designated vertex can be removed and its phase represented as a phase gate.
  • Extraction procedure: The extracted circuit is completed by realizing the remaining permutation of frontier vertices with SWAP gates.The frontier is eventually matched to the inputs up to a permutation.
  • Complexity: O(q^2n^2) bounds extraction complexity, where q is the qubit count and n is the number of spiders.The bound is dominated by repeated Gauss-Jordan elimination on matrices with q rows and at most n columns.
  • Evaluation: The worked example reduces 195 gates to 41 through an intermediate ZX-diagram with 12 spiders.The experiment illustrates the full simplify-and-extract pipeline rather than only a circuit-local rewrite.
  • Evaluation: For random 8-qubit Clifford+T circuits, pyzx outperforms naïve resynthesis near the Clifford regime but becomes less beneficial as T-gate density increases.Naïve optimisation saturates at high T density because Clifford blocks become too small, while pyzx can also increase gate counts when re-synthesizing very small pieces.

8 Conclusions and Future Work

The paper establishes a terminating ZX-diagram simplification and extraction framework, while identifying circuit extraction and topology-aware optimisation as open directions.

  • Conclusions: The rewrite strategy simplifies Clifford circuits to GS-LC form using local complementation and pivoting, and its outputs for non-Clifford circuits can be extracted using preserved focused gFlow.This combines the terminating simplification procedure with the graph property needed for deterministic extraction.
  • Limitations: Circuit extraction from a general ZX-diagram remains open, and the authors speculate that the fully general problem may not be tractable.The paper relates this issue to finding an ancilla-free unitary from a circuit containing ancillae, while not ruling out efficiently extractable larger classes.
  • Future work: Future work seeks additional rewrite rules that produce smaller diagrams while retaining efficient circuit extraction.More aggressive simplification can make re-extraction with gFlow problematic, motivating more general extraction procedures involving ancillae or classical control.
  • Future work: Topology-aware extraction is another future direction because near-term devices restrict which qubit pairs can interact.The extraction procedure’s freedom in choosing CNOTs may be adapted to constrained qubit topologies.

A Example derivation

A complete example applies local complementations and pivots to simplify a graph-like ZX-diagram, then extracts a smaller circuit with final gate simplifications.

  • Initial representation: The starting circuit contains 5 two-qubit gates and 19 single-qubit gates after conversion to graph-like form.The graph-like representation enables the subsequent graph transformations.
  • Simplification: Interior Pauli and proper Clifford phases require a sequence of local complementations followed by pivots.The transformations are applied at marked vertices to remove the remaining interior structures.
  • Simplification: After pivoting, a π/2 vertex becomes local Clifford, making a π vertex a boundary vertex and ending simplification.The example then proceeds to circuit extraction.
  • Circuit extraction: Extraction unfuses phases onto gates, moves suitable vertices onto the frontier, and represents an excess connection as a CNOT.The procedure repeats until all vertices have been extracted.
  • Result: The extracted circuit has 4 two-qubit gates and 18 single-qubit gates, reduced to 11 single-qubit gates after input-output simplifications.The final circuit is smaller than the initial example in both gate categories.

B Proofs

The appendix establishes that circuit-derived graph-like ZX-diagrams admit focused gFlow and that local complementation and pivoting preserve it, supporting deterministic extraction after simplification.

  • B.1 Circuits and focused gFlow: Focused gFlow is a graph property equivalent to ordinary gFlow, while causal flow is its singleton-correction special case.The appendix uses the implication from causal flow to focused gFlow and the equivalence between gFlow and focused gFlow.
  • B.1 Circuits and focused gFlow: Causal flow on circuit-derived graph-like ZX-diagrams implies focused gFlow.The proof assigns qubit-line and row numbers, then constructs a causal-flow order and successor function.
  • B.2.1 Local complementation: Local complementation preserves focused gFlow after deleting the complemented vertex.The transformed correction function is defined recursively over the partial order, with the proof establishing order preservation and the focused odd-neighbourhood condition.
  • B.2 Preservation of focused gFlow: Pivoting preserves focused gFlow after deleting its two pivot vertices.The proof tracks how pivoting changes odd neighbourhoods using closed neighbourhoods and defines the new correction sets by removing the pivot vertices.
  • B.2 Preservation of focused gFlow: Local complementation can normalize local Clifford labels on inputs and outputs into specified finite sets.The GS-LC form can be transformed until inputs use {Sn, H, ZH} and outputs use {Sn, H, HZ}.

C Pseudo-code for extraction algorithm

The extraction procedure converts a graph-like ZX-diagram into a circuit by processing output-frontier vertices, reducing frontier connectivity, and applying the resulting gate operations.

  • Initialization: The algorithm initializes the circuit, extracts the underlying graph, and sets the outputs as the initial frontier.It then removes output-adjacent Hadamard edges and emits phase gates for non-zero phases.
  • Initialization: Frontier edges are translated into CZ gates before frontier updates begin.The procedure removes each processed frontier edge after emitting the corresponding gate.
  • Finalization: After all non-frontier vertices are processed, the algorithm emits input-side Hadamards, performs the required qubit permutation with swaps, and returns the circuit.The final frontier is matched to the input qubits before returning C.
  • Frontier update: Each frontier update computes a biadjacency matrix, performs Gauss reduction, and selects rows with a single nonzero entry for the new frontier.The selected vertices are collected in ws, which becomes the next frontier after row operations are applied.
  • Frontier update: Gauss row operations are emitted as CNOT gates and used to update the diagram.The smaller frontier-to-neighbour matrix determines the row operations and the associated qubit controls and targets.
Loading 1902.03178v6…