Parity Quantum Computing as YZ-Plane Measurement-Based Quantum Computing

Abstract

We show that universal parity quantum computing employing a recently introduced constant depth decoding procedure is equivalent to measurement-based quantum computation (MBQC) on a bipartite graph using only YZ-plane measurements. We further show that any unitary MBQC using only YZ-plane measurements must occur on a bipartite graph.

In the present era of pre-fault-tolerant quantum computation [1], there exists an array of theoretical proposals for computation that display certain advantages and differing levels of suitability for implementation on current physical devices.

Parity quantum computation [2, 3, 4, 5, 6, 7] refers to one such proposal, initially based on quantum annealing [2]. The universal parity computing framework [3] leverages the properties of a certain type of quantum state encoding, the parity encoding. This encoding maps an $n$-qubit logical state onto $n(n+1)/2$ physical qubits, some of which obtain parity information related to subsets of logical qubits. Consequently, certain rotations acting locally on these parity qubits translate to multi-qubit logical rotations on the corresponding subset [3]. The parity code is in particular a stabiliser code [8, 9] and many of the properties of the code are well understood using the stabiliser formalism.

Stabiliser states and stabiliser codes are known to have a canonical form, namely graph states [10, 11] and graph codes [12, 13, 14] respectively. Graph states form an important class of highly entangled states that support measurement-based quantum computation (MBQC) [15, 16, 17, 18, 19, 20]. MBQC is a well-known alternative to the quantum circuit model driven by single qubit projective measurements instead of unitary gates.

Recently, a proposal for measurement-based encoding and decoding procedures were put forward for the parity computing regime [21], demonstrating beneficial properties in terms of their computational depth. Due to the close connection between stabiliser codes and graph codes, an investigation of the potential connections to MBQC is warranted, which we initiate in this work.

After presenting the required background, we demonstrate that every parity code is local Clifford equivalent to a bipartite graph code (1). Consequently, we show that parity quantum computation with the measurement-based decoding is MBQC where all measurements are from the YZ-plane of the Bloch sphere, and where re-entanglement and some local operations are allowed (1). We further show that any MBQC using only YZ-plane measurements and with input and output sets of equal size must use bipartite graph states (2). To conclude, we briefly outline some consequences of these results for both computing paradigms.

I Background

Parity Quantum Computing - A parity quantum computation commences by encoding the computational input state using the LHZ architecture [2] (see Figure 0(a)). The computation proceeds by applying unitaries from a native gate set for the parity encoding, such as that outlined in [3], which largely consists of local rotations. To finish, a decoding procedure returns the computational output. Presently, we will focus on the parity encoding procedure and universal gate set presented in [3] in combination with the measurement-based decoding procedure outlined in [21].

The parity encoding procedure maps a state on $n$ logical qubits to a state on $n(n+1)/2$ physical qubits. Following [3], we consider an LHZ layout where $n$ physical qubits (the ‘data’ qubits) directly correspond to the $n$ logical qubits. The remaining $N=n(n-1)/2$ qubits will be referred to as ‘parity’ qubits. We denote the sets of data and parity qubits by $I$ and $V\setminus I$ respectively.

Encoding consists of applying a sequence of CNOTs to an input state $\ket{\psi}$ and the parity qubits, which are all initialised to $\ket{0}$. Letting $C$ represent the set of control-target pairs, the encoded state is:

$$\ket{LHZ_{\psi}}=U_{\text{enc}}\ket{0}^{\otimes N}\ket{\psi}=\prod_{(c,t)\in C}\text{CNOT}_{(c,t)}\ket{0}^{\otimes N}\ket{\psi}.$$ (1)

Different constraint sets $C$ can produce the same encoded state. For example, $C$ could contain only pairs where every control is a data qubit and every target a parity qubit, which may involve non-nearest neighbour interactions for a given physical layout. Equivalently, it is possible to take $C$ to contain only nearest-neighbour CNOTs, where now some control qubits are parity qubits (see e.g., Figure 0(a)). The compilation of a given parity code into a nearest-neighbour layout is an interesting optimisation problem and a topic of ongoing research [7, 6, 5].

For each $\ket{\psi}$, $\ket{LHZ_{\psi}}$ is a state in the parity codespace for the given architecture. The stabilizer of the parity code is generated by operators of the form

$$K^{\prime}_{(ij...k)}:=Z_{(ij...k)}\otimes Z_{i}\otimes Z_{j}\otimes...\otimes Z_{k}$$ (2)

where the single subscripts $i$, $j$, etc. indicate data qubits and the subscript $(ij...k)$ indicates the parity qubit that encodes the parity information of data qubits $i$, $j$ and so on. The operators $K^{\prime}_{(ij...k)}$ for all parity qubits are mutually independent and generate the codespace. Note that often each parity qubit is taken to encode the parity of just two data qubits.

A benefit of this encoding consists in the ability to implement diagonal multi-qubit logical operations via single qubit physical rotations. For example, applying a local $Z$-rotation to a parity qubit $(ij)$ effectively applies a logical $Z_{i}\otimes Z_{j}$-rotation, from which a controlled-phase gate between logical qubits $i$ and $j$ can be obtained via local $Z$-rotations on the corresponding data qubits [3]. For full universal quantum computation, in conjunction with $Z$-rotations and controlled-phase gates, it suffices to be able to implement a logical $X$-rotation. For a data qubit $i$, this can be done via a decoding sequence of CNOTs along all parity qubits containing parity information about $i$, a local $X$-rotation at data qubit $i$, and a re-encoding sequence of CNOTs (see [3] for more details).

Until recently, the typical parity decoding procedures involved applying the encoding sequence of CNOT gates in reverse. In [21], an equivalent decoding procedure was proposed involving local $X$-measurements on parity qubits followed by local $Z$-operations conditional on measurement outcomes. One benefit of this approach is that full and partial decoding can be performed in constant-depth regardless of the size of the architecture.

For this gate set and measurement-based decoding, a unitary $U$ applied to input state $\ket{\psi}$ in the parity regime can be decomposed into a series of layers, where each layer involves parity qubit rotations followed by decoding. For notational simplicity, we consider full decoding in each layer. Denoting the set of layers by $L$, the set of data qubits by $I$ and the set of parity qubits by $V\setminus I$, the computation can be written as:

$$U\ket{\psi} =\prod_{l=1}^{L}\left(U_{\text{data}}^{(l)}(\bm{\alpha}^{(l)},\bm{\phi}^{(l)})D_{\text{dec}}^{(l)}(\bm{\theta}^{(l)})U_{\text{enc}}\ket{0}^{\otimes N}\right)\ket{\psi}$$ (3)

where $U_{\text{enc}}$ acts on both the ancilla $\ket{0}^{\otimes N}$ as well as the qubits in $I$, $D_{\text{dec}}^{(l)}(\bm{\theta}^{(l)})$ is the operator involving parity qubit rotations and decoding for layer $l$ given by

$$D_{\text{dec}}^{(l)}(\bm{\theta}^{(l)}):=\bigotimes_{(ij...k)\in V\setminus I}\bra{+_{(ij...k)}}R_{Z_{(ij...k)}}(\theta_{(ij...k)}^{(l)})$$ (4)

and $U_{\text{data}}^{(l)}(\bm{\alpha}^{(l)},\bm{\phi}^{(l)})$ is the product of local rotation on data qubits for layer l given by:

$$U_{\text{data}}^{(l)}(\bm{\alpha}^{(l)},\bm{\phi}^{(l)}):=\bigotimes_{i\in I}R_{X_{i}}(\alpha_{i}^{(l)})R_{Z_{i}}(\phi_{i}^{(l)}).$$ (5)

Note that the only distinction in the case of partial decoding is that $D_{\text{dec}}^{(l)}$ contains measurements in some subset of $V\setminus I$, the ancilla prepared in $\ket{0}$ in the subsequent layer correspond to the same subset, and the relevant $U_{\text{enc}}$ is replaced by $U_{\text{enc}}^{(l+1)}$ which applies only the appropriate CNOTs to re-encode back to the full LHZ state.

(a) An example of an LHZ architecture.

(b) The equivalent bipartite graph code.

Figure 1: (a) The parity encoding encodes an input state prepared on the data qubits (white circles). The grey circles denote parity qubits prepared in $\ket{0}$ and CNOT gates are applied to data and parity according to the layout as shown. This parity code in is equivalent to a graph code for the bipartite graph shown in (b).

Measurement-Based Quantum Computing - Measurement-based quantum computing (MBQC) [15, 16, 17, 18] consists of three things: (i) a highly entangled graph state [10, 11], (ii) a sequence of single qubit projective measurements in certain planes of the Bloch sphere, and (iii) classical, adaptive corrections of future measurements conditioned on prior measurement outcomes. Despite the indeterminacy of quantum measurements, deterministic computation can be performed, provided the sequence of measurements and underlying graph state satisfy certain properties [22].

Graph states take their name from their connection to mathematical graphs, where vertices correspond to qubits and edges correspond to two-qubit gates. We consider here graph states where a computational input state $\ket{\psi}$ can be prepared on a selected subset of vertices, denoted $I$.

Let $G$ be a graph with vertex set $V$ and edge set $\tilde{E}$. Let $I\subset V$ be a set of distinguished vertices such that $|I|=n$ and $|V\setminus I|=N$. Let $\ket{\psi}$ be a state in the Hilbert space associated to the input vertices, $\mathcal{H}_{I}$. Let $E$ denote the set of edges that are not entirely contained in $I$. The graph state with input is then

$$\ket{G_{\psi}}:=\prod_{\{v,v^{\prime}\}\in E}\text{CZ}_{v,v^{\prime}}\ket{\psi}_{I}\ket{+}^{\otimes N}.$$ (6)

For any input state $\ket{\psi}$, the graph state with input is invariant under the application of any operation in the set $\{K_{v}:v\in V\setminus I\}$ where

$$K_{v}:=X_{v}\otimes Z_{N_{v}^{G}}$$ (7)

with $N_{v}^{G}$ denoting the set of neighbours of vertex $v$ in $G$ and $Z_{N_{v}^{G}}:=\bigotimes_{v^{\prime}\in N_{v}^{G}}Z_{v^{\prime}}$. The $K_{v}$ are all mutually independent and the set $\{K_{v}:v\in V\setminus I\}$ generates a $2^{n}$-dimensional subspace of $\mathcal{H}_{v}$, the graph codespace corresponding to $G$ (see e.g., [12, 14] for further details on graph codes ).

In the measurement-based regime, computation is driven by single-qubit projective measurements restricted to the $XY$-, $XZ$- and $YZ$-planes of the Bloch sphere. A given computation is defined by one specific outcome for each measurement, and the restriction to the given planes allows for the correction of undesired outcomes via an effective application of an appropriate stabiliser element (or products thereof). However, even with these restrictions not every sequence of measurements for a given graph states is possible. The combination of graph state and measurements that do allow for computation are well characterised by a property called gflow (see Appendix A) which is known to be a necessary and sufficient condition for deterministic MBQC [22].

II Results

It is known that every stabiliser code is equivalent to a graph code [13] (see also [24]). The following is an instance of this result using the specific properties exhibited by parity codes.

Proposition 1.

Every parity code is local Clifford equivalent to a bipartite graph code, where all data qubits are contained in one partition.

Proof.

A parity code is defined by a stabiliser generated by the operators $K^{\prime}_{(ij...k)}=Z_{(ij...k)}\otimes Z_{i}\otimes Z_{j}\otimes...\otimes Z_{k}$ for each parity qubit $(ij...k)$. The set of qubits upon which these operators act includes only a single parity qubit. Via conjugation by Hadamards on each parity qubit, we obtain the local Clifford equivalent stabiliser generated by $K_{(ij...)}=X_{(ij...k)}\otimes Z_{i}\otimes Z_{j}\otimes...\otimes Z_{k}$. Since the $K_{(ij...k)}$ are of the form $X_{(ij...k)}\otimes Z_{N_{(ij...k)}^{G}}$ which generate a graph code for a graph $G$ with edges between parity and data qubits. That is, each neighbourhood $N_{(ij...k)}^{G}$ contains only vertices corresponding to data qubits, which enforces a parity qubit-data qubit bipartition. ∎

An example of this correspondence is shown in Figure 0(a) and Figure 0(b). Note that there exist graph codes that are not local Clifford equivalent to bipartite graph codes, and hence are inequivalent to any parity code.

An immediate consequence of 1 is that, for any $\ket{\psi}$, we have

$$\ket{LHZ_{\psi}}=\bigotimes_{v\in V\setminus I}H_{v}\ket{G_{\psi}}$$ (8)

where $G$ denotes the bipartite graph corresponding to the parity code, $I$ denotes the set of vertices corresponding to data qubits and $V$ is the set of all qubits. We will use $V\setminus I$ to denote the set of parity qubits forthwith.

Consider the parity computation $U$ described in Equation 3. For simplicity, let us first consider only the initial layer $l=1$ and drop the parameters $\bm{\alpha}$, $\bm{\phi}$ and $\bm{\theta}$ from the notation since the following holds for all parameter values. Using Equation 8, we get that

$$U_{\text{data}}^{(1)}D_{\text{dec}}^{(1)}U_{\text{enc}}\ket{0}^{\otimes N}\ket{\psi}=U_{\text{data}}^{(1)}D_{\text{dec}}^{(1)}H_{V\setminus I}\ket{G_{\psi}}$$ (9)

where $H_{V\setminus I}$ is shorthand for $\otimes_{v\in V\setminus I}H_{v}$. Both $D_{\text{dec}}^{(1)}$ and $H_{V\setminus I}$ act on the same qubits and can be simplified as:

$$D_{\text{dec}}^{(1)}H_{V\setminus I}=\bigotimes_{v\in V\setminus I}\bra{0_{v}}R_{X_{v}}(\theta_{v}^{(1)}).$$ (10)

The operator $\bra{0_{v}}R_{X_{v}}(\theta_{v}^{(1)})$ is a measurement in the YZ-plane of the Bloch sphere, and hence $D_{\text{dec}}^{(1)}H_{V\setminus I}\ket{G_{\psi}}$ is precisely a measurement-based computation where all measurements are restricted to that plane (the issue of measurement corrections is covered below). Denote the output of the first layer as $\ket{\psi^{(1)}}$, which is the resultant state of applying $U_{\text{data}}^{(1)}$ to the output state of the MBQC. The remaining computation is then given by

$$\prod_{l=2}^{L}\left(U_{\text{data}}^{(l)}D_{\text{dec}}^{(l)}U_{\text{enc}}\ket{0}^{\otimes N}\right)\ket{\psi^{(1)}}$$ (11)

for which the above process can be repeated. We have thus shown the following:

Theorem 1.

Universal parity quantum computing is repeated measurement-based quantum computation using YZ-plane measurements, interleaved with local rotations.

It should be noted that typically, MBQC is done on a fully pre-prepared graph state where input $I$ and output $O$ are distinct. However, proposals for repeated MBQC which de- and re-encode graph codes have been considered previously [25]; see also [20] for a recent perspective.

In light of the above, it is prudent to demarcate the parity computing regime with respect to the MBQC regime. One could reasonably ask if there exist YZ-only measurement-based computations on graphs that are not bipartite. However, the following theorem demonstrates that this in fact not the case. The theorem also takes care of any issues regarding correction of measurements (this is explained further in Appendix A).

As mentioned above, MBQC on a graph state $G$ typically includes specifying an input and output set of vertices, denoted by $I$ and $O$ respectively. For a deterministic MBQC to produce a unitary transformation (as opposed to an isometry), we require $|I|=|O|$.

Theorem 2.

MBQC on a (simple, connected) graph $G$ with $|I|=|O|$ and using only YZ-plane measurements is deterministic if and only if $G$ is bipartite with $I$ forming one partition.

The proof makes use of technical lemmas related to gflow which are proved along with the theorem in Appendix A.

III Discussion

This work has demonstrated that (i) parity codes are local Clifford equivalent to bipartite graph codes, (ii) as a consequence, parity quantum computing can be understood as repeated MBQC where all measurements are made in the YZ-plane, supplemented by local rotations, and (iii) MBQC with equivalent input and output qubits and using only YZ-plane measurements must use a bipartite graph state.

Interestingly, these results demonstrate that the universal parity computing regime has effectively singled out YZ-plane unitary MBQC exactly. To the best of our knowledge, the restriction to having equivalent input and output and only YZ-measurements has not been considered before in the MBQC literature. On the other hand, this is a restriction of the full MBQC framework, which means that there is ample scope for future investigation into what other aspects of MBQC could be brought to bear on the parity computing regime, and vice versa.

There are a number of consequences of these results worth mentioning already here. In [21], it was noted that the parity measurement-based encoding and decoding procedures can be implemented in constant depth regardless of architecture size. Since the decoding procedure corresponds to measuring vertices in one partition of a bipartite graph, it is clear that all measurements can be done simultaneously and corrected for in the other partition. The encoding procedure can be understood as measuring ancilla vertices of a larger graph state in the $X$-basis, which in particular produces the required bipartite graph (see e.g., [10, 11] for a characterisation of graph state deformations under Pauli measurements). It is known that all Pauli-measurements can be performed simultaneously in MBQC [18].

Bipartite graph states have previously received substantial attention in the MBQC literature; see e.g., [26, 27, 28]. The set of bipartite graph states includes both cluster states and GHZ states, which are both known to be useful for computation and communication protocols. There exist multi-particle entanglement purification protocols for bipartite graph states which exhibit favourable error thresholds for realistic scenarios [26, 27, 28]. Similar techniques may be of benefit for error mitigation in the parity regime - an avenue for future work.

Acknowledgements: We would like to thank B. Klaver and A. Messinger for useful discussions. This research was funded in whole or in part by the Austrian Science Fund (FWF) through the DK-ALM W$1259$-N$27$ and the SFB BeyondC F7102. For open access purposes, the authors have applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission. This work was also co-funded by the European Union (ERC, QuantAI, Project No. $101055129$). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

Appendix A Appendix A: Proof of 2

A computation in MBQC is defined by the positive measurement outcomes of a sequence of single qubit projective measurements on a graph state $\ket{G}$. To compute deterministically, a method for effectively correcting for the occurrence of negative outcomes is required. By restricting measurements to the XY-, XZ- or YZ-planes of the Bloch sphere, the positive and negative projections are related by conjugation via $Z$, $XZ$ and $X$ respectively. Since each of these operators features in a tensor factor of some element of the stabiliser for $\ket{G}$, it is possible to correct for a negative outcome by conditionally “completing” that stabiliser element.

The following definition, due to Browne et al. [22], outlines the criteria that a graph $G$, choice of input and output sets $I$ and $O$, and assignment of measurement planes to qubits must satisfy so that any measurement is correctable.

Definition 1.

Let $G=(V,E)$ be a graph, $I$ and $O$ be input and output subsets of $V$ respectively, and $\omega:V\setminus O\rightarrow\{XY,XZ,YZ\}$ be a map assigning measurement planes to qubits (the superscript $c$ denotes set complement). The tuple $(G,I,O,\omega)$ has gflow if there exists a map $g:V\setminus O\rightarrow\mathcal{P}(V\setminus I)$, where $\mathcal{P}$ denotes the powerset, and a partial order over $V$ such that the following hold for all $v\in V\setminus O$:

1. if $v^{\prime}\in g(v)$ and $v^{\prime}\neq v$, then $v<v^{\prime}$;

2. if $v^{\prime}\in\operatorname{Odd}(g(v))$ and $v^{\prime}\neq v$, then $v<v^{\prime}$;

3. if $\omega(v)=XY$, then $v\notin g(v)$ and $v\in\operatorname{Odd}(g(v))$;

4. if $\omega(v)=XZ$, then $v\in g(v)$ and $v\in\operatorname{Odd}(g(v))$;

5. if $\omega(v)=YZ$, then $v\in g(v)$ and $v\notin\operatorname{Odd}(g(v))$;

where $\operatorname{Odd}(K):=\{\tilde{v}\in V:|N_{\tilde{v}}^{G}\cap K|=1\bmod 2\}$ for any $K\subseteq V$.

An intuition for the above definition is as follows. For each $v$, the sets $g(v)$ and $\operatorname{Odd}(g(v))$ specify the stabiliser element for the correction: $g(v)$ is the set of vertices that receive an $X$ and $\operatorname{Odd}(g(v))$ is the set of vertices that receive a $Z$. The first two conditions of the definition stipulate that the measurement corrections must occur in the future of the measurement, and the last three conditions enforce the correcting stabiliser element to have the correct tensor factor at each vertex corresponding to which plane that vertex was measured in. It was shown in Theorems $2$ and $3$ of [22] that the gflow is a necessary and sufficient condition for deterministic MBQC. Accordingly, an equivalent statement to 2 in the main text is:

Theorem 3.

$(G,I,O,\omega\equiv YZ)$ with $|I|=|O|$ has gflow if and only if $G$ is bipartite with $I$ forming one partition.

Before giving the proof of the above theorem, we require the following lemmas:

Lemma 1.

If $(G,I,O,\omega\equiv YZ)$ with $|I|=|O|$ has gflow, then $I=O$.

Proof.

Let $(g,<)$ be a gflow for $(G,I,O,\omega)$ and suppose for a contradiction that $I\neq O$. Since $|I|=|O|$ this means that there exists some $v\in I$ such that $v\notin O$. Accordingly, $v$ is an element of the domain of the map $g$ but not the codomain so $v\notin g(v)$. Via criterion $5$ of 1, this contradicts the assumption that $\omega(v)=YZ$. ∎

Lemma 2.

Let $(G,I,O,\omega)$ with $I=O$ have gflow $(g,<)$ and let $\prec$ denote the partial order obtained by restricting $<$ to $V\setminus I$. Then any maximal element $v$ of $\prec$ must be such that $g(v)=\{v\}$ and hence $\omega(v)=YZ$.

Proof.

Since $I=O$, $g$ maps from $V\setminus I$ to $\mathcal{P}(V\setminus I)$. If $v$ is maximal and $g(v)\neq\{v\}$ then there exists a $v^{\prime}\in g(v)\setminus v$ (no $g(v)$ can be empty otherwise this would contradict criteria $3$, $4$ or $5$ of 1). By criterion $1$ of 1, this would mean that $v<v^{\prime}$ and hence also $v\prec v^{\prime}$, contradicting the maximality of $v$. Hence $g(v)=\{v\}$ and this must mean that $\omega(v)=YZ$ since otherwise this would contradict criteria $3$ or $4$. ∎

It is worth noting that, in the case where $I=O$, the restriction from $<$ to $\prec$ is not a significant one since every $v\in I$ is maximal in $<$.

Lemma 3.

Let $(G,I,O,\omega\equiv YZ)$ with $I=O$ have gflow. Then for every $u,v\in V\setminus I$ and $w\in g(u)$ and $x\in g(v)$, $w\notin N_{x}^{G}$.

Before giving the proof, let us consider some consequences of this lemma. Taking $u=v=x$, we get that $N_{u}^{G}\cap g(u)=\emptyset$. Taking $u=v$ but $x\neq w$, we get that no two elements of $g(u)$ are connected by an edge. Taking $u\neq v$, we get that no element of $g(u)$ is connected to an element of $g(v)$. As a result, there are no edges between any elements in $\bigcup_{v\in V\setminus I}g(v)$, which is used in the proof of the theorem below.

Proof.

Suppose $(g,<)$ is a valid gflow for $(G,I,O,\omega\equiv YZ)$ with $I=O$, which in particular means that $<$ is a valid partial order and criteria $1$, $2$ and $5$ in 1 are satisfied. Pursuant to 2, we make use of the partial order $\prec$ which is the restriction of $<$ to $V\setminus I$.

Let $u,v\in V\setminus I$ and $w\in g(u)$ and $x\in g(v)$. Since $G$ is a simple graph, for $w=x$, $w\notin N_{x}^{G}$ by definition, so we consider $w\neq x$ forthwith. Suppose for a contradiction that $w\in N_{x}^{G}$. If $w\in\operatorname{Odd}(g(x))$ and $x\in\operatorname{Odd}(g(w))$, then a contradiction arises since criterion $2$ requires $w\prec x$ and $x\prec w$. We consider the following two cases in turn: (a) $w\notin\operatorname{Odd}(g(x))$ and $x\in\operatorname{Odd}(g(w))$ or $w\in\operatorname{Odd}(g(x))$ and $x\notin\operatorname{Odd}(g(w))$ and (b) $w\notin\operatorname{Odd}(g(x))$ and $x\notin\operatorname{Odd}(g(w))$.

Case (a): Since the two sub-cases are the same up to swapping $w$ and $x$, we consider without loss of generality the case where $w\notin\operatorname{Odd}(g(x))$ but $x\in\operatorname{Odd}(g(w))$. Since $w\neq x$, the latter gives that $w\prec x$. Since $x\in N_{w}^{G}$ by assumption, there must exist a $x_{1}\in g(x)\setminus x$ such that $x_{1}\in N_{w}^{G}$ in order for $w\notin\operatorname{Odd}(g(x))$ to hold. If $w\in\operatorname{Odd}(g(x_{1}))$, then a contradiction arises since the criteria of gflow would require that $w\prec x\prec x_{1}\prec w$. If $w\notin\operatorname{Odd}(g(x_{1}))$, then there must exist a $x_{2}\in g(x_{1})\setminus x_{1}$ such that $x_{2}\in N_{w}^{G}$. By iterating the above reasoning, a sequence of vertices $x_{1},x_{2},...,x_{l}$ is generated for which $x_{i+1}\in g(x_{i})\setminus x_{i}$, $x_{i+1}\in N_{w}^{G}$, and $w\notin\operatorname{Odd}(g(x_{i+1}))$ for each $i=1,...,l-1$. However, after finitely many steps, this sequence must terminate with some $x_{l+1}$ such that $w\in\operatorname{Odd}(g(x_{l+1}))$: in the worst case, this occurs when $x_{l+1}$ is a maximal element of $\prec$, which from 2 means that $g(x_{l+1})=\{x_{l+1}\}$ and thus $w\in\operatorname{Odd}(g(x_{l+1}))$. The contradiction arises since $w\prec x\prec x_{1}\prec...\prec x_{l}\prec x_{l+1}\prec w$.

Case (b): If $w\notin\operatorname{Odd}(g(x))$ and $x\notin\operatorname{Odd}(g(w))$ but $w\in N_{x}^{G}$, then there must exist $w_{1}\in g(w)\setminus w$ and $x_{1}\in g(x)\setminus x$ such that $x_{1}\in N_{w}^{G}$ and $w_{1}\in N_{x}^{G}$. If $w\in\operatorname{Odd}(g(x_{1}))$ and $x\in\operatorname{Odd}(g(w_{1}))$, then a contradiction arises since $w\prec w_{1}\prec x\prec x_{1}\prec w$. If $w\notin\operatorname{Odd}(g(x_{1}))$ and $x\in\operatorname{Odd}(g(w_{1}))$ or $w\in\operatorname{Odd}(g(x_{1}))$ and $x\notin\operatorname{Odd}(g(w_{1}))$, then we are in a similar situation to Case (a) above. By analogous reasoning, we obtain a sequence of vertices $x_{1}\prec x_{2}\prec...\prec x_{l}$ such that there exists a $x_{l+1}\in g(x_{l})\setminus x_{l}$ for which $w\in\operatorname{Odd}(g(x_{l+1})$, producing a contradiction via $w\prec w_{1}\prec x\prec x_{1}\prec...\prec x_{l+1}\prec w$.

If both $w\notin\operatorname{Odd}(g(x_{1}))$ and $x\notin\operatorname{Odd}(g(w_{1}))$ hold then we are in a scenario similar to that defining Case (b) to begin with. Accordingly, there must exist $w_{2}\in g(w_{1})\setminus w_{1}$ and $x_{2}\in g(x_{1})\setminus x_{1}$ such that $x_{2}\in N_{w}^{G}$ and $w_{2}\in N_{x}^{G}$. By iterating the above splitting into cases and the corresponding reasoning, we obtain sequences of vertices $w\prec w_{1}\prec...\prec w_{l}$ and $x\prec x_{1}\prec...\prec x_{l}$ which must terminate (in the worst case) with either $g(w_{l})\setminus w_{l}$ or $g(x_{l})\setminus x_{l}$ containing a maximal element $w_{l+1}$ or $x_{l+1}$ respectively, and hence $w\in\operatorname{Odd}(g(x_{l+1}))$ or $x\in\operatorname{Odd}(g(w_{l+1}))$. Without loss of generality, suppose that $x\in\operatorname{Odd}(g(w_{l+1}))$. If $w\in\operatorname{Odd}(g(x_{l+1}))$, then we obtain a contradiction via $w\prec w_{1}\prec...\prec w_{l+1}\prec x\prec x_{1}\prec...\prec x_{l+1}\prec w$. If $w\notin\operatorname{Odd}(g(x_{l+1}))$, then we are again in a scenario similar to Case (a), which by analogous reasoning also terminates in a contradiction. ∎

The proof of 3 proceeds as follows:

Proof.

Suppose $G$ is bipartite and denote one partition by $I$. Consider $(g,<)$ where $g$ is defined by $v\mapsto\{v\}$ for all $v\in V\setminus I$ and (ii) $<$ is the coarsest partial order such that the vertices in $V\setminus I$ precede those in $I$. That criteria $1$, $2$ and $5$ in the definition of gflow are satisfied for all $v\in V\setminus I$ can be readily verified, hence $(g,<)$ is a valid gflow for $(G,I,O=I,\omega\equiv YZ)$. Clearly, with this choice of $O$, the requirement that $|I|=|O|$ is satisfied.

For the opposite direction, suppose $(G,I,O,\omega)$ with $\omega\equiv YZ$ and $|I|=|O|$ has gflow $(g,<)$. From 1, we know that $I=O$. From 3, we know that for each $u,v\in V\setminus I$, there are no edges between elements of $g(u)$ and also no edges between elements of $g(u)$ and $g(v)$. Consequently, there are no edges between elements of $g(V\setminus I):=\bigcup_{v\in V\setminus I}g(v)$. Accordingly, we can partition $G$ into those vertices in $g(V\setminus I)\equiv V\setminus I$ and those in $I$. ∎