PaperlayerView exact revision on arXiv

Source-linked AI summary

There and back again: A circuit extraction tale

Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski, John van de Wetering

arXiv:2003.01664v3quant-ph

TL;DR

Circuit and measurement-pattern representations support different optimization goals, while work on gflow has largely focused on XY-plane measurements. The paper develops a ZX-calculus-based extraction and simplification procedure for extended-gflow patterns, including measurements in multiple planes. It provides the first such multi-plane extraction algorithm without ancillae and rewrite rules that can remove Pauli-measured qubits while preserving gflow.

  • Problem

    Circuit and measurement-pattern representations offer different optimization goals, motivating translations between them.

    Source: §1 · p. 3

  • Method

    The paper uses ZX-calculus rewrites to simplify multi-plane measurement patterns while tracking extended gflow, then extracts a circuit.

    Source: §6 · p. 47

  • Results

    The paper presents the first circuit-extraction algorithm for patterns with measurements in multiple planes and extended gflow, and it uses no ancillae.

    Source: §6 · p. 47

  • Takeaways & Limitations

    The rewrite rules can reduce measurement-pattern qubits, including by eliminating all qubits measured in a Pauli basis while preserving extended gflow.

    Source: §6 · p. 47

    Resynthesizing CNOT gates can increase their count for some input circuits.

    Source: §6 · p. 47

Abstract

from arXiv · show

Translations between the quantum circuit model and the measurement-based one-way model are useful for verification and optimisation of quantum computations. They make crucial use of a property known as gflow. While gflow is defined for one-way computations allowing measurements in three different planes of the Bloch sphere, most research so far has focused on computations containing only measurements in the XY-plane. Here, we give the first circuit-extraction algorithm to work for one-way computations containing measurements in all three planes and having gflow. The algorithm is efficient and the resulting circuits do not contain ancillae. One-way computations are represented using the ZX-calculus, hence the algorithm also represents the most general known procedure for extracting circuits from ZX-diagrams. In developing this algorithm, we generalise several concepts and results previously known for computations containing only XY-plane measurements. We bring together several known rewrite rules for measurement patterns and formalise them in a unified notation using the ZX-calculus. These rules are used to simplify measurement patterns by reducing the number of qubits while preserving both the semantics and the existence of gflow. The results can be applied to circuit optimisation by translating circuits to patterns and back again.

1 Introduction

Circuit and one-way measurement models offer different ways to implement and optimize quantum computations, but research on measurement patterns has focused mostly on XY-plane measurements. This paper extends circuit extraction and pattern simplification to computations with measurements in multiple planes and gflow.

1 Introduction

  • For one-way computations, gflow is necessary and sufficient for deterministic implementability, whereas causal flow is sufficient when all measurements are in the XY-plane.Extended gflow covers labelled open graphs with measurements in all three planes.Source: §1 · p. 3

1.1 Our contributions

  • The paper presents the first circuit-extraction algorithm for measurement patterns with extended gflow, including measurements in multiple planes, and the extracted circuits use no ancillae.The ZX-calculus approach also applies to ZX-diagrams satisfying the algorithm’s conditions.Source: §1.1 · p. 3
  • The authors derive ZX-calculus rewrite rules that track how graph transformations change gflow, preserving deterministic implementability while simplifying measurement patterns.The rules can remove non-input qubits measured in a Pauli basis, relating the number of measured qubits needed to the computation’s non-Clifford operations.Source: §1.1 · p. 4
  • The paper generalizes focused and maximally delayed gflow to measurements in multiple planes; its focused-gflow definition differs from three proposals by Hamrit and Perdrix.The authors say the applications motivate a unique generalization.Source: §1.1 · p. 4
  • Translating a circuit into a measurement pattern, simplifying it, and extracting a circuit again can reduce the circuit’s T-gate count.The procedure uses the ZX-calculus to transform the circuit into a diagram corresponding to a pattern before simplification and re-extraction.Source: §1.1 · p. 4

2 Preliminaries

This section establishes the ZX-calculus and MBQC formalisms and their diagrammatic correspondence, then introduces MBQC+LC diagrams, rewrite operations, and gflow’s role in deterministic measurement patterns. It also gives the focused-gflow equivalence for XY-plane measurements and notes a consequence of prior proofs that was not explicitly stated in the cited paper.

2.1 The ZX-calculus

  • ZX-diagrams compose and tensor spiders to represent linear maps, and the calculus is universal; circuits are defined as a special class of ZX-diagrams.The paper chooses a universal gate set with convenient spider representations for its circuit translations.Source: §2.1 · pp. 5–7

2.2 Measurement-based quantum computation

  • MBQC consumes an entangled graph state through adaptive single-qubit measurements, typically restricted to the XY, XZ, or YZ planes.Measurement outcomes can require corrections, so deterministic computations must adapt their instructions to earlier outcomes.Source: §2.2 · pp. 8, 10
  • A labelled open graph with measurement angles translates to an MBQC-form ZX-diagram with the same linear map, and the correspondence is one-to-one up to isomorphism.Conversely, each MBQC-form diagram determines such a labelled open graph and angle assignment.Source: §2.2 · pp. 11–12
  • An MBQC+LC diagram is an MBQC-form diagram up to arbitrary single-qubit Clifford unitaries on its input and output wires, which are ignored in its underlying graph.MBQC form is the special case with trivial input and output unitaries.Source: §2.2 · p. 12

2.3 Graph-theoretic rewriting

  • Local complementation toggles edges between a vertex’s neighbours, pivoting composes three local complementations, and identity removal deletes a degree-two vertex while fusing its nonadjacent neighbours.Identity removal corresponds in the ZX-calculus to replacing a zero-phase spider with two incident wires by an identity wire.Source: §2.3 · pp. 12–13
  • The ZX-calculus expresses local complementation and pivoting as graph-state diagram equalities involving Clifford phase shifts.The cited equalities concern underlying graphs related by local complementation or pivoting, with vertices outside the affected neighbourhood unchanged.Source: §2.3 · p. 14

2.4 Generalised flow

  • Preserving the existence of gflow preserves uniform, strong, stepwise determinism, and the paper extends a constructive XY-plane gflow algorithm to find extended gflow for all three measurement planes.The relevant invariant is existence of some gflow, not preservation of the particular gflow.Source: §2.4 · pp. 15, 17
  • The earlier gflow condition (4) can accept a graph whose pattern implements a rank-2, noninvertible map, so that condition does not guarantee determinism.The example satisfies conditions (g1), (4), and (g3)–(g5), but fails revised condition (g2) and is therefore not a gflow under the revised definition.Source: §2.4 · pp. 16–17
  • Gflow is necessary and sufficient for uniformly, strongly, stepwise deterministic patterns, and unlike causal flow it applies to measurements in all three planes.The sufficiency result also guarantees a runnable pattern realizing the associated linear map; the converse says such a pattern’s labelled open graph has gflow.Source: §2.4 · pp. 15, 17

2.5 Focusing gflow for XY plane measurements

  • For XY-only labelled open graphs, gflow exists if and only if focused gflow exists; with equal input and output counts, focused gflow also reverses when inputs and outputs are swapped.The reversed correction set for an input consists of the outputs whose original correction sets contain it.Source: §2.5 · p. 19
  • The result follows immediately from Ref. [44, Theorems 3–4], although that paper does not state it explicitly.Source: §2.5 · p. 21

3 Rewriting while preserving the existence of gflow

This section develops graph rewrites that preserve gflow, extends polynomial-time gflow finding to all three measurement planes, and constructs focused extended gflow with plane-dependent correction constraints. It also shows that every non-input vertex has at least two neighbors, so an XY-plane-measured vertex in a unitary MBQC-form ZX-diagram with gflow has at least two incident wires besides its measurement-effect wire.

3.1 Graph operations that preserve the existence of gflow

  • Local complementation, including at output vertices, and pivoting preserve the existence of gflow in labelled open graphs.Pivot preservation follows by applying the local-complementation result three times.Source: §3.1 · pp. 21–22
  • Deleting a vertex measured outside XY preserves gflow, whereas deleting an XY vertex can destroy it; a conditional arity-2 removal also preserves gflow.The arity-2 result requires the specified adjacent vertices to be labelled outside YZ.Source: §3.1 · pp. 22–23
  • Adding an XY-measured vertex before an input or in place of an output preserves gflow.For an output replacement, the original output becomes XY-measured and a new adjacent output takes its place.Source: §3.1 · p. 23

3.2 Finding extended gflow

  • A polynomial-time algorithm decides whether a labelled open graph has extended gflow and returns a maximally delayed gflow when one exists.The procedure works backwards from outputs and maximally delays measurements, yielding gflow of minimal depth.Source: §3.2 · p. 24

3.3 Focusing extended gflow

  • A maximally delayed gflow can be focused so correction sets contain only XY-measured qubits, while correction side-effects do not affect XY-measured qubits.The construction is polynomial in the number of vertices; the detailed proof gives O(n^4) operations.Source: §3.3 · p. 26
  • Deleting all XZ- or YZ-measured vertices preserves gflow, and when |I| = |O| an internal XY vertex must have at least two neighbours.Source: §3.3 · pp. 26–27
  • Every non-input vertex v has at least two neighbors: |N_G(v)| ≥ 2.Assuming fewer neighbors leads to a contradiction with (g3) after reversing the focused gflow when |I| = |O|.Source: §3.3 · p. 27
  • In a unitary MBQC-form ZX-diagram with gflow, every XY-plane-measured vertex has at least two incident wires, plus its measurement-effect wire.An input vertex in the labelled open graph is connected to an input wire in the ZX-diagram.Source: §3.3 · p. 27

4 Simplifying measurement patterns

This section develops ZX-calculus rewrites and polynomial-time transformations that simplify measurement patterns and MBQC+LC diagrams while preserving computation and gflow, with the aim of reducing qubit count. It extends simplification to measurements in all three planes, including Clifford-qubit removal and reduction from phase-gadget form, and gives an operation count for the removal process.

4 Simplifying measurement patterns

  • The rules remove Clifford qubits rather than merely compressing them, cover measurements in three planes, and preserve gflow and deterministic realisability.The section presents these as extensions beyond earlier results restricted to XY-plane measurements.Source: §4 · p. 28

4.1 Transforming local Cliffords into measurements

  • Local Clifford gates can be converted into measurements with at most 2p + 4q added qubits, while preserving gflow.Here p and q are the input and output counts; the resulting MBQC-form diagram has at most n + 2p + 4q qubits.Source: §4.1 · p. 29

4.2 Local complementation and pivoting on patterns

  • Local complementation and pivot rewrites return patterns to MBQC+LC form and preserve gflow, including when complementing an input via an equivalent construction.For non-input vertices, local complementation changes the underlying graph by local complementation; pivoting is handled for neighboring non-input vertices.Source: §4.2 · pp. 30–31

4.3 Removing Clifford vertices

  • Local complementation and pivoting enable removal of non-input Clifford vertices across several measurement planes and angles, including some vertices connected only to boundary vertices.The removal rewrites preserve semantics and gflow; the boundary-connected case requires the pattern to have gflow.Source: §4.3 · pp. 32–33
  • A polynomial-time algorithm removes every non-input Clifford vertex from an equivalent MBQC+LC diagram while preserving gflow.The algorithm uses at most O(n^3) elementary graph operations.Source: §4.3 · p. 34
  • At most n + 8q measurements suffice for a uniformly deterministic pattern implementing the same unitary, with q inputs and n non-Clifford measured qubits.The construction takes polynomially many steps.Source: §4.3 · pp. 34–35
  • The process for constructing P′ from D′′ uses O(|G|^3) graph operations overall.Its stages construct D from P, D′ from D, D′′ from D, and P′ from D′′.Source: §4.3 · p. 35

4.4 Phase-gadget form

  • An equivalent MBQC+LC diagram in phase-gadget form with gflow can be found in polynomial time.Phase-gadget form excludes XZ-measured vertices and adjacent pairs of YZ-measured vertices; the form is not guaranteed to be unique.Source: §4.4 · pp. 35–36

4.5 Further pattern optimisation

  • Two rewrites remove an interior YZ vertex while preserving equivalence and gflow: fusion with its sole XY neighbour, or merging a pair of YZ vertices with identical neighbourhoods.When gflow exists, distinct interior XY vertices cannot have identical neighbourhoods.Source: §4.5 · pp. 37–38
  • With gflow and equal numbers of inputs and outputs, an equivalent reduced diagram with gflow can be found in polynomially many steps, with total complexity O(n^4).A reduced diagram has no internal Clifford vertices, no internal vertex with only one neighbour, and distinct neighbourhoods for vertices measured in the same plane; YZ vertices connect only to XY vertices.Source: §4.5 · pp. 38–39

5 Circuit extraction

This section extends ZX-calculus circuit extraction to gflow measurement patterns with measurements in multiple planes, describing a procedure that progressively converts them into equivalent ancilla-free circuits while preserving gflow. The practical algorithm does not explicitly calculate a gflow and has the stated worst-case runtime bound.

5 Circuit extraction

  • The extraction algorithm handles measurements in multiple planes by extending Ref. [26], and its correctness proof uses focused gflow and lemmas about extended gflow.Earlier circuit-extraction procedures included ancilla-free extraction for flow patterns [17] and XY-plane gflow patterns [26].Source: §5 · p. 39

5.1 General description of the algorithm

  • The algorithm extracts maximal vertices from a frontier: XY vertices are isolated using CNOT row operations, while connected maximal YZ vertices are pivoted to XY before extraction.The gflow selects maximal vertices, and the chosen transformations preserve gflow in the remaining unextracted diagram.Source: §5.1 · pp. 43–44
  • The general algorithm terminates in polynomial time and produces a circuit implementing the same unitary as the starting pattern.Each iteration reduces the lexicographic pair of unextracted-vertex count and unextracted YZ-vertex count; each step uses polynomially many graph operations.Source: §5.1 · p. 45

5.2 A more practical algorithm

  • The practical shortcut uses Gaussian elimination over Z2 on the frontier-neighbour biadjacency matrix; singleton rows identify XY neighbours that can be extracted after implementing the row operations as CNOTs.The single-neighbour condition follows from Lemma 5.3.Source: §5.2 · pp. 45–46
  • The extraction algorithm does not need to calculate a gflow explicitly; gflow is used to establish correctness and guaranteed termination.Pseudocode for the algorithm is provided in Appendix D.Source: §5.2 · p. 46
  • A pattern with n inputs and outputs, k total qubits, and gflow can be converted in O(n^2k^2 + k^3) time into an equivalent n-qubit circuit with no ancillae.The runtime bound accounts for Gaussian elimination and graph pivots, each of which may be needed for every vertex.Source: §5.2 · p. 46
  • When k ≥ O(n^2), the runtime bound becomes O(k^3), though the authors do not expect this worst case in practice because pivots and elimination toggle connectivity.The worst-case bound would require the graph to remain almost fully connected throughout.Source: §5.2 · p. 46

6 Conclusions and Future Work

The paper presents an ancilla-free circuit-extraction algorithm for measurement patterns with extended gflow, including measurements in multiple planes. Its rewrite rules also reduce pattern qubits, while implementation and routing choices affect the resulting circuits.

6 Conclusions and Future Work

  • The extraction algorithm handles patterns with extended gflow and multiple measurement planes, without ancillae; it is also the most general known procedure for extracting circuits from ZX-diagrams.Source: §6 · p. 47
  • Rewrite rules for all three measurement planes transform extended gflow and can reduce pattern qubits, including by eliminating qubits measured in a Pauli basis.Source: §6 · p. 47
  • The implemented pattern-optimisation and extraction algorithms matched the state-of-the-art reduction in non-Clifford gates for ancilla-free circuits at the time of development.Source: §6 · p. 47
  • CNOT resynthesis can substantially decrease or increase a circuit's two-qubit gate count, depending on the input circuit.Source: §6 · p. 47
  • The extraction algorithm's Gaussian elimination assumes two-qubit gates can connect any pair of qubits, whereas current and near-term devices may restrict those connections.Source: §6 · p. 47

A Gflow and determinism

This section develops the notation and proof framework for showing that gflow guarantees determinism of one-way measurement patterns. It establishes that gflow supports runnable, strongly and stepwise deterministic patterns, with uniform determinism across measurement angles.

A Gflow and determinism

  • A pattern branch fixes each measurement outcome, while determinism compares the linear maps of different branches; strong and stepwise determinism impose stronger branch-consistency conditions.Source: A Gflow and determinism · pp. 51–52
  • For any measurement angles, a labelled open graph with gflow yields a runnable, strongly and stepwise deterministic pattern that realizes the graph's associated linear map.Source: A Gflow and determinism · p. 53
  • The resulting pattern is uniformly deterministic, and its map is a unitary embedding; when input and output counts match, that map is unitary.Source: A Gflow and determinism · p. 53
  • Stepwise determinism follows because removing minimal measured vertices preserves a restricted gflow on the remaining subgraph.Source: A Gflow and determinism · p. 55

B Proofs for Section 3

The proofs show that local complementation preserves gflow when correction sets and measurement-plane labels are updated appropriately. They also establish that local complementation along an edge preserves gflow while changing the endpoint labels as stated.

B Proofs for Section 3

  • The odd neighbourhood of a vertex set changes by symmetric difference with the vertex’s neighbourhood, with the set difference depending on membership in its odd neighbourhood.This identity is used to verify the transformed correction sets.Source: B Proofs for Section 3 · p. 55
  • Local complementation at an output-input vertex preserves gflow when its correction sets and plane labels are transformed by the stated rules.The proof checks the gflow conditions for the complemented vertex and for the other vertices’ correction sets.Source: B Proofs for Section 3 · pp. 55–56
  • Local complementation along an edge between two input-output vertices preserves gflow and changes the endpoint labels according to their original measurement planes.Other output labels remain unchanged.Source: B Proofs for Section 3 · p. 58

C Finding maximally delayed gflow in multiple measurement planes

This appendix extends maximally delayed gflow construction and its supporting characterisations to all three measurement planes. It proves that a polynomial-time algorithm decides whether gflow exists and returns a maximally delayed gflow when it does.

C Finding maximally delayed gflow in multiple measurement planes

  • The appendix generalises earlier results on maximally delayed gflow, including how output layers may be removed and how the first layer is identified across multiple measurement planes.The layer-removal and characterisation results are stated as generalisations of prior lemmas.Source: C Finding maximally delayed gflow in… · pp. 60–61
  • The first maximally delayed layer is characterised by plane-specific odd-neighbourhood tests on subsets of outputs that are also inputs.The XY test gives odd neighbourhood {u}; the XZ test uses K ∪ {u} with odd neighbourhood {u}; the YZ test uses K ∪ {u} with no outputs in its odd neighbourhood.Source: C Finding maximally delayed gflow in… · p. 61
  • The algorithm builds gflow iteratively by finding candidate correction sets through linear systems over F2 and extending the output set by each newly found layer.It reports failure if no layer can be found before all vertices are outputs.Source: C Finding maximally delayed gflow in… · p. 63
  • A polynomial-time algorithm decides whether a labelled open graph has an extended gflow and returns a maximally delayed gflow when one exists.The stated implementation has overall complexity O(n^4), where n is the number of vertices.Source: C Finding maximally delayed gflow in… · pp. 63–64

D Pseudocode for algorithms

The pseudocode specifies an iterative gflow search and a separate circuit-extraction procedure. The extraction procedure processes a frontier of the diagram, updating the circuit as vertices and edges are eliminated.

D Pseudocode for algorithms

  • GFLOW assigns outputs depth zero, searches for plane-specific correction sets, and recursively adds each successful layer to the output set.It returns a maximally delayed gflow when all vertices become outputs, and reports failure if no correction layer can be found.Source: D Pseudocode for algorithms · p. 65
  • Circuit extraction initializes the graph frontier at the outputs, processes frontier Cliffords and edges, and repeats frontier updates until all diagram vertices are processed.The final frontier is checked for input connections via Hadamard gates.Source: D Pseudocode for algorithms · p. 66
  • Frontier updates use Gaussian reduction and row operations to identify vertices with a unique frontier neighbour and add corresponding circuit gates.The pseudocode includes CNOTs for row operations and Hadamard and phase gates when advancing vertices.Source: D Pseudocode for algorithms · p. 66
Loading 2003.01664v3…