Using PennyLane

Release news

Development

API

Internals

  1. Docs
  2. qml.labs
  3. qml.labs.intermediate_reps
  4. qml.labs.intermediate_reps.rowcol

qml.labs.intermediate_reps.rowcol

rowcol(P, connectivity=None, verbose=False)[source]

CNOT routing algorithm ROWCOL.

This algorithm was introduced by Wu et al. and is detailed in the compilation hub, where examples can be found as well.

Parameters:

  • P (np.ndarray) – Parity matrix to implement. Will not be altered

  • connectivity (nx.Graph) – Connectivity graph to route into. If None (the default), full connectivity is assumed.

  • verbose (bool) – Whether or not to print progress of obtained CNOT gates. Default is False.

Returns:

Wire pairs for CNOTs that implement the parity matrix (control first, target second).

Return type:

list[tuple[int]]

Note

This function requires the package galois to be installed. It can be installed via pip install galois, for details see its documentation.

Example

Here we compute the example 1 from Wu et al. in code. We also compute it by hand in the manual example section below.

To start, we have the connectivity graph

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

and define it in code as a networkx.Graph (networkx documentation).

>>> import networkx as nx
>>> G = nx.Graph([(0, 3), (1, 2), (2, 3), (3, 4)])

We would like to find a CNOT circuit implementing the following parity matrix P:

>>> P = np.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],
... ])

We import rowcol and the function parity_matrix that will allow us to check that the computed circuit produces the input parity matrix. Then we run the algorithm:

>>> from pennylane.labs.intermediate_reps import rowcol, parity_matrix
>>> cnots = rowcol(P, G)

The constructed circuit is the one found in the paper as well:

>>> circ = qml.tape.QuantumScript([qml.CNOT(pair) for pair in cnots])
>>> print(qml.drawer.tape_text(circ, wire_order=range(5)))
0: ──────────────────────────────────╭X───────╭X─╭●───────┤
1: ─────────────╭X───────╭X─╭●────╭X─│────────│──│────────┤
2: ────╭X────╭●─╰●────╭X─╰●─╰X─╭●─╰●─│─────╭●─│──│─────╭X─┤
3: ─╭X─╰●─╭X─╰X─╭●─╭X─╰●─╭X────╰X────╰●─╭X─╰X─╰●─╰X─╭●─╰●─┤
4: ─╰●────╰●────╰X─╰●────╰●─────────────╰●──────────╰X────┤

We can confirm that this circuit indeed implements the original parity matrix:

>>> recon_P = parity_matrix(circ, wire_order=range(5))
>>> np.allclose(P, recon_P)
True

Given a parity matrix \(P\) and a connectivity graph \(G(V, E)\), as well as an empty list L to which we will append CNOT gates, the algorithm consists of the following steps:

  1. If \(|V|=1\) (there is a single node), go to step 5. Else, select a vertex \(i\in V\) that is not a cut vertex, i.e. a vertex that we can remove without disconnecting the graph.

  2. Eliminate column P[:, i]

    1. Construct \(S = \{j | P_{ji} \neq 0\} \cup \{i\}\) and find a Steiner tree \(T \supseteq S\).

    2. Post-order traverse the Steiner tree \(T\) starting from \(i\) as root. If P[c, i]=1 for node \(c\) in the traversal and P[p, i]=0 for parent node \(p\) of node \(c\), add row P[c] to row P[p] and append CNOT([c, p]) to L.

    3. Post-order traverse \(T\) again starting from \(i\). For each node \(p\) in the traversal, add row P[p] to row P[c], where \(c\) is the child node of \(p\), and append CNOT([p, c]) to L.

  3. Eliminate row P[i]

    1. Construct \(S'\) such that the corresponding rows of \(P\) add up to the \(i\)th basis vector, \(\sum_{j\in S'} P[j] = e_i\). Find a Steiner tree \(T' \supseteq S'\).

    2. Pre-order traverse the Steiner tree \(T'\) starting from \(i\) and for each node \(c\) in the traversal for which \(c \notin S'\), add row \(P[c]\) to row \(P[p]\), where \(p\) is the parent node of \(c\), and append CNOT([c, p]) to L.

    3. Post-order traverse \(T\) starting from \(i\). For each node \(c\) in the traversal, add row P[c] to row P[p], where \(p\) is the parent node of \(c\), and append CNOT([c, p]) to L.

  4. Delete vertex \(i\) from \(G\) and ignore row and column with index \(i\) in the following. Go to step 1.

  5. Revert the list L of CNOT gates in order to go from the circuit that transforms \(P\) to the identity to the circuit that implements \(P\) starting from the identity.

We walk through example 1 in Wu et al., which was demonstrated in code above, in detail. The steps are numbered according to the algorithm overview above. We restrict ourselves to the following connectivity graph.

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

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 ((0) is not a cut vertex).

\[\begin{split}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}\end{split}\]

Step 1: Pick vertex i=0

Step 2: Eliminate P[:, 0]

Step 2.a: Find \(S\) and \(T\)

All non-zero vertices are S = [0, 2, 3, 4]. A Steiner tree T connecting those vertices is given by

(0) - (3) - (4)
       |
      (2)

Step 2.b: First post-order traversal

We post-order traverse \(T\) from \(0\), giving the ordering \([2, 4, 3, 0]\), and check for nodes \(c\) with parent \(p\) where \(P_{ci}=0\) and \(P_{pi}=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.

Step 2.c: Second post-order traversal

We again post-order traverse the tree and add every vertex to its children, i.e. we get the CNOT operations \(\text{CNOT}_{3 2} \text{CNOT}_{3 4} \text{CNOT}_{0 3}\). Simultaneously, we update the parity matrix with the corresponding row additions (modulo 2).

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

Step 3: Eliminate P[0, :]

Now we eliminate the first row, marked blue below.

\[\begin{split}P = \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}\end{split}\]

Step 3.a: Find \(S'\) and \(T'\)

We see that we can add rows \(S' = \{0, 2, 4\}\) together to obtain the first unit vector \(e_0\). The Steiner tree \(T'\) encapsulating \(S'\) is then

(0) - (3) - (4)
       |
      (2)

where \(3 \notin S'\).

Step 3.b: Pre-order traverse

We pre-order traverse \(T'\) (yielding \([0, 3, 2, 4]\)) and for all \(c \notin S'\), we add them to their parent. In particular, we get an additional \(\text{CNOT}_{3 0}\). 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 3.c: Post-order traverse

Similarly to step 2.c, we post-order traverse \(T'\), but this time adding every node’s row to that of its parent. This yields the same circuit as in step 2.c (because the Steiner trees are the same), but with the roles of target and control qubits reversed.

Step 4: Delete and iterate

We delete vertex \(i=0\) from \(G\) and ignore the first row and column of \(P\) in the following. Then we return to step 1.

Step 1: Pick vertex i=1

Step 2: Eliminate P[:, 1]

We repeat the procedure for the next vertex \(i=1\) from the resulting parity matrix

\[\begin{split}P = \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}.\end{split}\]

Step 2.a: Find \(S\) and \(T\)

The set \(S\) of non-zero entries in column P[:,1] together with \(i\) itself is \(S = [1, 2, 3]\) and the encapsulating Steiner tree \(T\) is simply

(3)
 |
(2)
 |
(1)

Step 2.b: First post-order traversal

We post-order traverse \(T\) from \(1\) (yielding \([3, 2, 1]\)) to check if any parent has \(P_{pi}=0\), which is the case for \(p=1\), so we add \(\text{CNOT}_{2 1}\).

Step 2.c: Second post-order traversal

Once again, add every parent node row to the row of its children while post-order traversing. We additionally get \(\text{CNOT}_{2 3}\text{CNOT}_{1 2}\).

Step 3: Eliminate P[1]

Now we eliminate the second row, marked blue below.

\[\begin{split}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}\end{split}\]

Step 3.a: Find \(S'\) and \(T'\)

We first construct \(S' = [1, 3, 4]\), which labels rows whose sum yields \(e_1\). The encapsulating Steiner tree \(T'\) is

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

where \(2 \notin S'\).

Step 3.b: Pre-order traverse

Add \(2 \notin S'\) to its parent during pre-order traversal (\([1, 2, 3, 4]\)), i.e. add \(\text{CNOT}_{2 1}\).

Step 3.c: Post-order traverse

Post-order traverse the tree (\([4, 3, 2, 1]\)) and add every row to its parent: \(\text{CNOT}_{4 3}\text{CNOT}_{3 2}\text{CNOT}_{2 1}\).

Step 4: Delete and iterate

We delete vertex \(i=1\) from \(G\) and ignore the second row and column of \(P\) in the following. Then we return to step 1.

Remaining operations

At this point, we have covered all the cases. We defer to the compilation hub for a more extensive explanation of this example and here simply list the remaining gates.

Step 1: Select vertex \(i=2\)

Step 2.b: \(\text{CNOT}_{4 3}\)

Step 2.c: \(\text{CNOT}_{3 4}\text{CNOT}_{2 3}\)

Step 3.a: no gate

Step 3.c: \(\text{CNOT}_{4 3}\text{CNOT}_{3 2}\)

Step 4: Delete \(i=2\)

Step 1: Select vertex \(i=3\)

Step 2.b: no gate

Step 2.c: no gate

Step 3.a: no gate

Step 3.c: \(\text{CNOT}_{4 3}\)

Step 4: Delete \(i=3\)

Step 1: \(|V|=|\{4\}|=1\), terminate.

The final circuit is the reverse of the synthesized subcircuits, matching the result from the code example above:

>>> print(qml.drawer.tape_text(circ, wire_order=range(5)))
0: ──────────────────────────────────╭X───────╭X─╭●───────┤
1: ─────────────╭X───────╭X─╭●────╭X─│────────│──│────────┤
2: ────╭X────╭●─╰●────╭X─╰●─╰X─╭●─╰●─│─────╭●─│──│─────╭X─┤
3: ─╭X─╰●─╭X─╰X─╭●─╭X─╰●─╭X────╰X────╰●─╭X─╰X─╰●─╰X─╭●─╰●─┤
4: ─╰●────╰●────╰X─╰●────╰●─────────────╰●──────────╰X────┤
Previous
Next