Replacing patterns in a circuit¶

This notebook explains how some patterns can be replaced in a circuit and how some rules can be defined to automatically replace patterns in a circuit.

Replacing pattern once¶

The library pbo (for Pattern Based Optimization) defines some class to replace the first pattern found in a Circuit.

First, we define a circuit. The following circuit is only an example (and does not correspond to a useful program).

In [1]:
# Init a quantum program
from qat.lang.AQASM import *
from qat.lang.AQASM.gates import *

nqbits = 4
prog = Program()
reg = prog.qalloc(nqbits)

# Define a program
prog.apply(H, reg[0])

# Pattern equivalent to CSIGN
prog.apply(H, reg[1])
prog.apply(CNOT, reg[0], reg[1])
prog.apply(H, reg[1])

prog.apply(CNOT, reg[1], reg[3])

# Pattern equivalent to SWAP
prog.apply(CNOT, reg[3], reg[2])
prog.apply(CNOT, reg[2], reg[3])
prog.apply(CNOT, reg[3], reg[2])

# Pattern to remove
prog.apply(H, reg[2])
prog.apply(H, reg[2])

# Pattern equivalent to RZ(-3)
prog.apply(RZ(2), reg[2])
prog.apply(RZ(-3), reg[2])
prog.apply(RZ(-2), reg[2])

# Pattern to remove
prog.apply(CSIGN, reg[0], reg[1])
prog.apply(CSIGN, reg[1], reg[0])

# Generate the corresponding circ
circ = prog.to_circ()

circ.display()
No description has been provided for this image

The purpose of this notebook is to perform local changes on the previous Circuit to reduce the quantum cost (number of gates in the Circuit).

Detect and replace pattern¶

Step 1 : Transform the circuit into a graph

In [2]:
from qat.pbo import GraphCircuit, VAR

# Generate a graph
graph = GraphCircuit()

# Transform the circuit into a graph
graph.load_circuit(circ)

Then, some pattern must be defined

Step 2: Replace a pattern

A pattern is a list of tuples. A tuple is composed of :

  • The gate's name (the name is in the syntax of the gate)
  • The qubit on which the gate is applied
  • The parameters of the gate

For instance :

In [3]:
# Pattern 1
old_pattern = [('CNOT', [0, 1]), ('CNOT', [1, 0]), ('CNOT', [0, 1])]
new_pattern = [('SWAP', [0, 1])]

# Replace pattern
graph.replace_pattern(old_pattern, new_pattern)
Out[3]:
True

The result is True because such a pattern exists. The pattern has been replaced in the circuit. If there are several patterns to replace, a loop could be used.

In [4]:
# Replace all pattern
while graph.replace_pattern(old_pattern, new_pattern):
    continue

The method replace_pattern finds the first pattern to replace it so the order of changes matters. For instance, if two patterns in the circuit are not disjoint, replacing the first pattern will delete the second one.

In [5]:
# Pattern 2
old_pattern_1 = [('H', [0]), ('CNOT', [1, 0]), ('H', [0])]
new_pattern_1 = [('CSIGN',[1, 0])]

# Pattern 3
old_pattern_2 = [('H', [0]), ('CNOT', [0, 1])]
new_pattern_2 = [('H', [1]), ('CSIGN',[0, 1]), ('H', [0]), ('H', [1])]

# Check if the pattern exist
print('Find pattern 1 and 2')
print("Pattern 1 exist ?", graph.count_pattern(old_pattern_1) > 0)
print("Pattern 2 exist ?", graph.count_pattern(old_pattern_2) > 0)

# Replace pattern
print('\nReplace pattern 1 and 2:')
print( graph.replace_pattern(old_pattern_1, new_pattern_1) )
print( graph.replace_pattern(old_pattern_2, new_pattern_2) )

Find pattern 1 and 2
Pattern 1 exist ? True
Pattern 2 exist ? True

Replace pattern 1 and 2:
True
False

Step 3: Remove a pattern

Removing a pattern is equivalent to replacing a pattern by an empty one. An empty pattern is defined by []. For instance :

In [6]:
# Pattern 4
old_pattern = [('H', [0]), ('H', [0])]
new_pattern = []

# Replace pattern
graph.replace_pattern(old_pattern, new_pattern)
Out[6]:
True

Step 4: Undirected gates in pattern

The GraphCircuit may detect multi-qubits and the order of qubits is very important (respecting the order used in AQASM). For instance, the gate ("CNOT", [0, 1]) means that the first qubit is the control one and the second qubit is the target one. Nevertheless, some gates are undirected, which means that the order of qubits does not matter. For instance, a CSIGN gate has no orientation and the undirected pattern CSIGN - CSIGN must be removed. If the order of qubits is not important, qubits must be defined by a set. For instance, a CSIGN gate shall be defined by ("CSIGN", {0, 1}) (if the CSIGN gate acts on qubits 0 and 1).

The replace_pattern method accepts an undirected pattern. The idea is to iterate all the oriented patterns that match the undirected pattern. The old pattern could be defined as : [('CSIGN', {0, 1}), ('CSIGN', {0, 1})]

In fact, since all the oriented patterns will be tested, there are 4 directed patterns. This number could be reduced to 2. In fact, there are two possibilities:

  • Gates have the same orientation
  • Gates have the opposite orientation

So, the following pattern will be used because we only need to generate 2 directed patterns:

[('CSIGN', {0, 1}), ('CSIGN', [0, 1])]

⚠
The new pattern must be oriented.
In [7]:
# Pattern 5
old_pattern = [('CSIGN', {0, 1}), ('CSIGN', [0, 1])]
new_pattern = []

# Replace pattern
graph.replace_pattern(old_pattern, new_pattern)
Out[7]:
True

Step 5: Gate parameters

In our example, a pattern RZ(x) - RZ(y) - RZ(-x) could be replaced by RZ(y). To do so, some abstract variables can be defined

In [8]:
# Abstract var
x = VAR()
y = VAR()

# Pattern 6
old_pattern = [('RZ', [0], -x), ('RZ', [0], y), ('RZ', [0], x)]
new_pattern = [('RZ', [0], y)]

# Replace pattern
graph.replace_pattern(old_pattern, new_pattern)
Out[8]:
True

A parameter must be an instance of VAR. If you want to use constant parameters, use : x.set_value( 2 )

Moreover, you can use any function. For instance :

In [9]:
from math import sqrt

# sqrt( x ) does not work
try:
    z = sqrt( x )
except:
    print("sqrt(x) does not work")
    
# This works
sqrt_var = VAR.add_function( sqrt )
z = sqrt_var( x )

x.set_value( 5**2 )
print("sqrt(x) =", z)

sqrt(x) does not work
sqrt(x) = 5.0

Resulting circuit¶

The graph can be transformed into a circuit

In [10]:
circ_no_pattern = graph.to_circ()
circ_no_pattern.display()
No description has been provided for this image

Custom gates¶

It's possible to insert custom gates in the graph. The custom gate can also be defined after the pattern detection. For instance, we can replace the gate RZ by a gate TEST.

In [11]:
x = VAR()

# Replace a gate by an undefined gate
a = [0]
graph.replace_pattern([('RZ', [0], x)], [('TEST', [0], x)])
Out[11]:
True

Then, we define a gate TEST such that the graph can be transformed into a circuit.

In [12]:
from qat.lang.AQASM import AbstractGate

# Abstract gate: name = 'TEST', take a float as argument, arity is 1
TEST_gate = AbstractGate('TEST', [float], 1)

# Add the custom gate in the circuit
graph.add_abstract_gate(TEST_gate)
circ_with_abstract_gate = graph.to_circ()

circ_with_abstract_gate.display()
No description has been provided for this image