RowCol Algorithm

Korbinian Kottmann

Compilation/
RowCol Algorithm

RowCol Algorithm

On this page, we are going to first briefly introduce the parity matrix intermediate representation that is used in the RowCol algorithm and show how one can perform a Gauss-Jordan elimination using CNOT gates. Then we show the two building blocks of the RowCol algorithm: Eliminating a row and eliminating a column of a parity matrix, potentially under restricted connectivity. Finally, all these components are put together in the RowCol algorithm in its formal definition. An easy way to fully grasp the algorithm is by going through a full example, which we will do at the end of the page.

Parity Matrix
Gauss-Jordan elimination
Eliminating a column under restricted connectivity
Eliminating a row under restricted connectivity
RowCol algorithm
Example

Parity matrix

The parity matrix describes the action of a CNOT circuit. The action of a CNOT gate on a computational basis state $|x_0 x_1\rangle$ with $x_i \in \{0, 1\}$ is simply

$\text{CNOT}_{x_0 x_1} |x_0, x_1\rangle = |x_0, x_0 \oplus x_1\rangle.$

In circuit form, this is the following:


x_0: ─╭●─┤  x_0
x_1: ─╰X─┤  x_0 ⊕ x_1

The corresponding parity matrix $P$ is

P = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}.

In particular, a computational basis input state $\boldsymbol{x} = (x_0, x_1)$ is mapped to $P \boldsymbol{x}$ .

Row j corresponds to the bit-wise addition of the input qubit values, i.e. $x_1 = x_0 \oplus x_1$ . One way to interpret this is to say that $\text{CNOT}_{x_\text{control} x_\text{target}}$ corresponds to adding the row of the control qubit to the row of the target qubit in the parity matrix. We will sometimes use the shorthand notation $x_\text{control} \rightarrow x_\text{target}$ for that.

We can then describe a whole CNOT circuit with this logic by means of its action on arbitrary computational basis states $|x_0 x_1 .. x_{n-1}\rangle$ . Take, for example, the following circuit.


x_0: ────╭●───────╭X─╭●─┤  x_0 ⊕ x_3
x_1: ────│──╭X────│──│──┤  x_0 ⊕ x_1 ⊕ x_2 ⊕ x_3
x_2: ─╭X─╰X─╰●─╭X─│──╰X─┤  x_2 ⊕ x_3
x_3: ─╰●───────╰●─╰●────┤  x_3

The corresponding parity matrix is given by

\begin{pmatrix} 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1\end{pmatrix}.

Gauss-Jordan elimination

The general idea of RowCol and similar algorithms is to transform the parity matrix $P$ to the identity matrix via Gauss-Jordan elimination restricted to row additions. In particular, adding a row $i$ to row $j$ corresponds to a $\text{CNOT}_{ij}$ gate.

This is easiest understood with an example. Let us take the circuit


x_0: ─╭●─╭●────╭X─┤  x_0 ⊕ (x_2 ⊕ x_0) = x_2 
x_1: ─╰X─│──╭X─│──┤  x_1 ⊕ x_0 ⊕ (x_2 ⊕ x_0) = x_1 ⊕ x_2 
x_2: ────╰X─╰●─╰●─┤  x_2 ⊕ x_0

and its parity matrix

P = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}.

We can retrieve the identity matrix by performing row additions in the following manner,

\begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \stackrel{2 \rightarrow 0}{=} \begin{pmatrix} \color{blue}1 & \color{blue}0 & \color{blue}0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \stackrel{2 \rightarrow 1}{=} \begin{pmatrix} 1 & 0 & 0 \\ \color{blue}1 & \color{blue}1 & \color{blue}0 \\ 1 & 0 & 1 \end{pmatrix} \stackrel{0 \rightarrow 1}{=} \begin{pmatrix} 1 & 0 & 0 \\ \color{blue}0 & \color{blue}1 & \color{blue}0 \\ 1 & 0 & 1 \end{pmatrix} \stackrel{0 \rightarrow 2}{=} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \color{blue}0 & \color{blue}0 & \color{blue}1 \end{pmatrix}.

The synthesized circuit is obtained by going through the elimination steps backwards and writing down the corresponding CNOT gates. In particular, we obtain


x_0: ─╭●─╭●────╭X─┤  x_2
x_1: ─│──╰X─╭X─│──┤  x_1 ⊕ x_2
x_2: ─╰X────╰●─╰●─┤  x_2 ⊕ x_0

This circuit is equivalent to the original input circuit. You can see this by commuting the first two operations. We could have also performed the first two row additions in the opposite order.

Eliminating a column under restricted connectivity

Consider the parity matrix with arbitrary elements outside our target column 0,

P = \begin{pmatrix} \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}0 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \end{pmatrix}.

Our goal is to eliminate the first column highlighted in blue. In particular, we want it to be the first column of the identity matrix. If there were no connectivity constraints, one way to achieve that is by simply adding $1 \rightarrow 3$ followed by $0 \rightarrow 1$ . But let us further assume that only neighboring qubits are connected. In particular, the connectivity graph is


(0) - (1) - (2) - (3)

The only way to remove the element $P_{3,0} = 1$ is to go through row 2. We say that (0) - (1) - (2) - (3) is the minimal tree that encapsulates all non-zero vertices S = [0, 1, 3] (a so-called Steiner tree). Identifying these elements is step i.1.1 in the RowCol algorithm below.

Since vertex (2) is 0, we first need to create a $1$ in $P_{2,0}$ , which can be achieved by $3 \rightarrow 2$ . Then we get

P = \begin{pmatrix} \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \end{pmatrix}.

This is step i.1.2 in the RowCol algorithm below. This sets up step i.1.3, where we just walk backwards through the rows from (3) to (0), adding each row to the one below it. In graph theory terms, this is called a postorder traversal with respect to the target row/vertex and we add vertices to their children.

The overall step i.1 is then the following:

\begin{pmatrix} \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}0 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \end{pmatrix} \stackrel{3 \rightarrow 2}{\stackrel{\text{create } \color{red}(2)}{=}} \begin{pmatrix} \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \color{red}1 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \end{pmatrix} \stackrel{2 \rightarrow 3}{\stackrel{\text{del } \color{red}(3)}{=}} \begin{pmatrix} \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \color{red}0 & \cdot & \cdot & \cdot \\ \end{pmatrix} \stackrel{1 \rightarrow 2}{\stackrel{\text{del } \color{red}(2)}{=}} \begin{pmatrix} \color{blue}1 & \cdot & \cdot & \cdot \\ \color{blue}1 & \cdot & \cdot & \cdot \\ \color{red}0 & \cdot & \cdot & \cdot \\ \color{blue}0 & \cdot & \cdot & \cdot \\ \end{pmatrix} \stackrel{0 \rightarrow 1}{\stackrel{\text{del } \color{red}(1)}{=}} \begin{pmatrix} \color{blue}1 & \cdot & \cdot & \cdot \\ \color{red}0 & \cdot & \cdot & \cdot \\ \color{blue}0 & \cdot & \cdot & \cdot \\ \color{blue}0 & \cdot & \cdot & \cdot \\ \end{pmatrix}.

Eliminating a row under restricted connectivity

Similarly, we can eliminate a row of a parity matrix

\begin{pmatrix} 1 & \color{blue}0 & \color{blue}1 & \color{blue}0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ \end{pmatrix}.

The process is slightly different because we are restricted to row operations. In this case, we look for the rows required to eliminate the rest of row 0. Specifically, we need rows S' = [0, 1, 3] to achieve an all-zero state by performing $3 \rightarrow 1$ followed by $1 \rightarrow 0$ . This is again a postorder traversal, but this time adding rows to their parents (step i.2.3 in RowCol below).

The general procedure here is to collect the rows S' that cancel each other out. When there are connectivity constraints and we traverse via rows in the encapsulating Steiner tree T' but not in S', we are making a mistake that we need to correct for. Assuming the same connectivity restriction as above, i.e. nearest-neighbors (0) - (1) - (2) - (3), which is again equal to the corresponding Steiner tree, we additionally get row 2 in the addition. We have to correct for it by adding it to its parent, i.e. $2 \rightarrow 1$ (step i.2.2). All these steps correspond to the steps in i.2 in the RowCol algorithm below. In particular, we get

\begin{pmatrix} 1 & \color{blue}0 & \color{blue}1 & \color{blue}0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ \end{pmatrix} \stackrel{2 \rightarrow 1}{\stackrel{\text{i.2.2}}{=}} \begin{pmatrix} 1 & \color{blue}0 & \color{blue}1 & \color{blue}0 \\ 0 & \color{red}1 & \color{red}1 & \color{red}0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ \end{pmatrix} \stackrel{3 \rightarrow 2}{\stackrel{\text{i.2.3}}{=}} \begin{pmatrix} 1 & \color{blue}0 & \color{blue}1 & \color{blue}0 \\ 0 & 1 & 1 & 0 \\ 0 & \color{red}1 & \color{red}0 & \color{red}0 \\ 0 & 1 & 0 & 1 \\ \end{pmatrix} \stackrel{2 \rightarrow 1}{\stackrel{\text{i.2.3}}{=}} \begin{pmatrix} 1 & \color{blue}0 & \color{blue}1 & \color{blue}0 \\ 0 & \color{red}0 & \color{red}1 & \color{red}0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ \end{pmatrix} \stackrel{2 \rightarrow 1}{\stackrel{\text{i.2.3}}{=}} \begin{pmatrix} 1 & \color{red}0 & \color{red}0 & \color{red}0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ \end{pmatrix}.

`RowCol` algorithm

RowCol consecutively eliminates columns and rows of the parity matrix under restricted connectivity, as shown above. We give a formal definition of the algorithm below, taken from [1] and modified for better readability. A cut vertex is defined as a vertex of a connected graph whose removal would destroy the connectivity property of the remaining graph. In principle, any non-cut vertex can be chosen for initial elimination.

To fully grasp the algorithm, we recommend going through the full example that we show below.

Algorithm RowCol

Input: Parity matrix $P$ , connectivity graph $G(V, E)$

Output: Row additions to transform $P$ into $\mathbb{I}$ .

for i ∈ V which is not a cut vertex do

Step i.1: (eliminate column P[:, i])

Construct $S = \{j | P_{ji} \neq 0\} \cup \{i\}$ and Steiner tree $T \supseteq S$ .
Postorder traverse $T$ from $i$ . If the parity of the child row is 1 and the parity of the parent row is 0, add the child row to the parent row.
Postorder traverse $T$ from $i$ . Add every row to its children when reached.

Step i.2: (eliminate row P[i])

Construct S' such that adding up the corresponding rows in S' eliminates the row P[i] (except for P[i, i]=1). Find a Steiner tree $T' \supseteq S'$ .
Preorder traverse $T'$ from $i$ and add each $j \notin S'$ to its parent.
Postorder traverse $T'$ from $i$ and add every row to its parent.

delete vertex $i$

end for loop.

Example

We walk through example 1 from [1] in detail below.

We restrict ourselves to the following connectivity graph.


(1) - (4) - (5)
       |       
      (3)
       |
      (2)

We look at a CNOT circuit with the following parity matrix. The first column is highlighted as we are going to start by eliminating it.

P = \begin{pmatrix} \color{blue}1 & 1 & 0 & 1 & 1 \\ \color{blue}0 & 0 & 1 & 1 & 0 \\ \color{blue}1 & 0 & 1 & 0 & 1 \\ \color{blue}1 & 1 & 0 & 1 & 0 \\ \color{blue}1 & 1 & 1 & 1 & 0 \end{pmatrix}

Vertex i=1

Step 1.1

We pick the first index i=1 and aim to eliminate the first column. Step 1.1.1: All non-zero vertices are S = [1, 3, 4, 5]. A Steiner tree T connecting those vertices is given by


(1) - (4) - (5)
       |       
      (3)

In step 1.1.2, we first postorder traverse the tree and check for instances where the value of $P_i=0$ while the parent's value is $1$ . This can only happen when we have elements in $T$ that are not in $S$ or when the vertex $i$ itself has a value $0$ . Neither is the case here; therefore, no action is required.

In step 1.1.3, we again postorder traverse the tree and add every vertex to its children, i.e. we get the CNOT operations $\text{CNOT}_{4 3} \text{CNOT}_{4 5} \text{CNOT}_{14}$ . This first time, we perform each operation separately to show the path:

P = \begin{pmatrix} \color{blue}1 & 1 & 0 & 1 & 1 \\ \color{blue}0 & 0 & 1 & 1 & 0 \\ \color{blue}1 & 0 & 1 & 0 & 1 \\ \color{blue}1 & 1 & 0 & 1 & 0 \\ \color{blue}1 & 1 & 1 & 1 & 0 \end{pmatrix} \stackrel{4 \rightarrow 3}{=} \begin{pmatrix} 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ \color{blue}0 & \color{blue}1 & \color{blue}1 & \color{blue}1 & \color{blue}1 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{pmatrix} \stackrel{4 \rightarrow 5}{=} \begin{pmatrix} 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ \color{blue}0 & \color{blue}0 & \color{blue}1 & \color{blue}0 & \color{blue}0 \end{pmatrix} \stackrel{1 \rightarrow 4}{=} \begin{pmatrix} 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ \color{blue}0 & \color{blue}0 & \color{blue}0 & \color{blue}0 & \color{blue}1 \\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}.

The shorthand notation $i \rightarrow j$ is a convenient way to indicate a $\text{CNOT}_{i j}$ gate, particularly as it indicates the addition of row $i$ to row $j$ .

The corresponding synthesized subcircuit is shown below.


circ = qml.tape.QuantumScript([
    qml.CNOT((4, 3)),
    qml.CNOT((4, 5)),
    qml.CNOT((1, 4)),
], [])

print(qml.drawer.tape_text(circ, wire_order=range(1, 5+1), show_all_wires=True))


1: ───────╭●─┤  
2: ───────│──┤  
3: ─╭X────│──┤  
4: ─╰●─╭●─╰X─┤  
5: ────╰X────┤

Step 1.2

Now we eliminate the first row.

\begin{pmatrix} \color{blue}1 & \color{blue}1 & \color{blue}0 & \color{blue}1 & \color{blue}1 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}

Step 1.2.1: We see that we can add rows S' = [1, 3, 5] to eliminate the remainder of the first row. The Steiner tree T' encapsulating S' is then


(1) - (4) - (5)
       |       
      (3)

where $(4) \notin S'$ .

Step 1.2.2: For all $j \notin S'$ , we add them to their parents as we preorder traverse T'. In particular, we get an additional $\text{CNOT}_{4 1}$ . This is necessary because we are going to traverse through this node in the next step and we need to undo this step again to eliminate the targeted row.

Step 1.2.3: Similarly to step 1.1.3, we postorder traverse $T'$ once again, but this time adding every row to its parent. This yields the same circuit as in 1.1.3, but with the roles of target and control qubits reversed. Overall, the added synthesized circuit is the following.


circ = qml.tape.QuantumScript([
    qml.CNOT((4, 1)),
    qml.CNOT((3, 4)),
    qml.CNOT((5, 4)),
    qml.CNOT((4, 1)),
], [])

print(qml.drawer.tape_text(circ, wire_order=range(1, 5+1), show_all_wires=True))


1: ─╭X───────╭X─┤  
2: ─│────────│──┤  
3: ─│──╭●────│──┤  
4: ─╰●─╰X─╭X─╰●─┤  
5: ───────╰●────┤

Vertex 2

Step 2.1

We repeat the procedure for the next vertex i=2 from the resulting parity matrix

\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & \color{blue}0 & 1 & 1 & 0 \\ 0 & \color{blue}1 & 1 & 1 & 1 \\ 0 & \color{blue}1 & 0 & 1 & 0 \\ 0 & \color{blue}0 & 1 & 0 & 0 \end{pmatrix}.

Step 2.1.1: The set S of non-zero entries in column $P_{i=2}$ together with $i$ itself is S = [2, 3, 4] and the encapsulating Steiner tree T is simply


(4)
 |       
(3)
 |
(2)

Step 2.1.2: We postorder traverse T to check if any parent has 0, which is the case for (2), so we add $\text{CNOT}_{3 2}$ .

Step 2.1.3: Once again, add every row to its children and additionally get $\text{CNOT}_{3 4}\text{CNOT}_{2 3}$ . The overall circuit then reads


circ = qml.tape.QuantumScript([
    qml.CNOT((3, 2)),
    qml.CNOT((3, 4)),
    qml.CNOT((2, 3)),
], [])

print(qml.drawer.tape_text(circ, wire_order=range(1, 5+1), show_all_wires=True))


1: ──────────┤  
2: ─╭X────╭●─┤  
3: ─╰●─╭●─╰X─┤  
4: ────╰X────┤  
5: ──────────┤

Step 2.2

The resulting parity matrix is

P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & \color{blue}1 & \color{blue}0 & \color{blue}0 & \color{blue}1 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}

and we continue to eliminate the marked row.

Step 2.2.1: We first construct S' = [2, 4, 5], which labels rows whose sum yields all zeros (except for the value in $P_{ii} = 1$ ). The encapsulating Steiner tree T' is


(4) - (5)
 |       
(3)
 |
(2)

Step 2.2.2: Add $3 \notin S'$ to its parent during preorder traversal, i.e. add $\text{CNOT}_{3 2}$ .

Step 2.2.3: Postorder traverse the tree and add every row to its parent: $\text{CNOT}_{5 4}\text{CNOT}_{4 3}\text{CNOT}_{3 2}$ . Overall we get the following subcircuit.


circ = qml.tape.QuantumScript([
    qml.CNOT((3, 2)),
    qml.CNOT((5, 4)),
    qml.CNOT((4, 3)),
    qml.CNOT((3, 2)),
], [])

print(qml.drawer.tape_text(circ, wire_order=range(1, 5+1), show_all_wires=True))


1: ──────────┤  
2: ─╭X────╭X─┤  
3: ─╰●─╭X─╰●─┤  
4: ─╭X─╰●────┤  
5: ─╰●───────┤

Vertex 3

At this point, we have covered all the cases. Let us write down S, T and $P$ at each step.

Step 3.1

P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & \color{blue}1 & 1 & 1 \\ 0 & 0 & \color{blue}0 & 0 & 1 \\ 0 & 0 & \color{blue}1 & 0 & 0 \end{pmatrix}


Step 3.1.1:
S = [3, 5]
T = (3) - (4) - (5)
Step 3.1.2: 5 -> 4
Step 3.1.3: 4 -> 5; 3 -> 4

1: ──────────┤  
2: ──────────┤  
3: ───────╭●─┤  
4: ─╭X─╭●─╰X─┤  
5: ─╰●─╰X────┤

Step 3.2

P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & \color{blue}1 & \color{blue}1 & \color{blue}1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}


Step 3.2.1:
S' = [3, 4, 5]
T' = (3) - (4) - (5)
Step 3.2.2: -
Step 3.2.3: 5 -> 4; 4 -> 3

1: ───────┤  
2: ───────┤  
3: ────╭X─┤  
4: ─╭X─╰●─┤  
5: ─╰●────┤

Vertex 4

Step 4.1

P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & \color{blue}1 & 1 \\ 0 & 0 & 0 & \color{blue}0 & 1 \end{pmatrix}


Step 4.1.1:
S = [4]
T = (4)
Step 4.1.2: -
Step 4.1.3: -

1: ───┤  
2: ───┤  
3: ───┤  
4: ───┤  
5: ───┤

Step 4.2

P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & \color{blue}1 & \color{blue}1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}


Step 4.2.1:
S' = [4, 5]
T' = (4) - (5)
Step 4.2.2: -
Step 4.2.3: 5 -> 4

1: ────┤  
2: ────┤  
3: ────┤  
4: ─╭X─┤  
5: ─╰●─┤

The final circuit is the reverse of the synthesized subcircuits. The following list of CNOTs is given in the order in which we added them in the algorithm above. The reverse of this list is the final circuit.


CNOTs = [
    [4, 3],
    [4, 5],
    [1, 4],
    [4, 1],
    [3, 4],
    [5, 4],
    [4, 1],
    [3, 2],
    [3, 4],
    [2, 3],
    [3, 2],
    [5, 4],
    [4, 3],
    [3, 2],
    [5, 4],
    [4, 5],
    [3, 4],
    [5, 4],
    [4, 3],
    [5, 4],
]

circ = qml.tape.QuantumScript([qml.CNOT(pair) for pair in CNOTs[::-1]], [])

print(qml.drawer.tape_text(circ, wire_order=range(1, 5+1), show_all_wires=True))


1: ──────────────────────────────────╭X───────╭X─╭●───────┤  
2: ─────────────╭X───────╭X─╭●────╭X─│────────│──│────────┤  
3: ────╭X────╭●─╰●────╭X─╰●─╰X─╭●─╰●─│─────╭●─│──│─────╭X─┤  
4: ─╭X─╰●─╭X─╰X─╭●─╭X─╰●─╭X────╰X────╰●─╭X─╰X─╰●─╰X─╭●─╰●─┤  
5: ─╰●────╰●────╰X─╰●────╰●─────────────╰●──────────╰X────┤

We can confirm that this is indeed the original parity matrix by constructing it.


def compute_parity_matrix(circ):
    wires = circ.wires
    P = np.eye(len(wires), dtype=int)
    for op in circ.operations:
        control, target = op.wires
        P[target-1] = P[target-1] + P[control-1]

    return P % 2

circ = qml.tape.QuantumScript([qml.CNOT(pair) for pair in CNOTs[::-1]], [])

compute_parity_matrix(circ)


array([[1, 1, 0, 1, 1],
       [0, 0, 1, 1, 0],
       [1, 0, 1, 0, 1],
       [1, 1, 0, 1, 0],
       [1, 1, 1, 1, 0]])

This is equal to the parity matrix we started from,

P = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{pmatrix}.

Why PennyLane

Getting Started

Documentation

Ecosystem

RowCol Algorithm

Parity matrix

Gauss-Jordan elimination

Eliminating a column under restricted connectivity

Eliminating a row under restricted connectivity

`RowCol` algorithm

Example

RowCol Algorithm

Parity matrix

Gauss-Jordan elimination

Eliminating a column under restricted connectivity

Eliminating a row under restricted connectivity

RowCol algorithm

Example

`RowCol` algorithm