Linear Boolean operator synthesis

qat.synthopline provides a collection of algorithms able to synthesise circuits implementing a particular set of unitary operators called linear boolean operators. These capture exactly operators that can be implemented using solely CNOT gates.

In practice they can be efficiently represented in a circuit-independent way via a $n\times n$ invertible bit table. For instance the following operator:

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

can be implemented using the following circuit:

from qat.lang.AQASM import Program, CNOT
prog = Program()
qbits = prog.qalloc(3)

CNOT(qbits[2], qbits[1])
CNOT(qbits[1], qbits[2])
CNOT(qbits[0], qbits[1])

circuit = prog.to_circ()
circuit.display()

The method qat.synthopline.linear_synthesis.extract_linear_operator can be used to extract the linear operator underlying a CNOT circuit:

from qat.synthopline.linear_synthesis import extract_linear_operator

table = extract_linear_operator(circuit)
print(table)

[[1 0 0]
 [1 1 1]
 [0 1 0]]

Once we have our linear operator, we can use the qat.synthopline.linear_synthesis.linear_operator_synthesis method to produce a CNOT circuit implementing the operator:

from qat.synthopline.linear_synthesis import linear_operator_synthesis

circuit_bis = linear_operator_synthesis(table)
circuit_bis.display()

In fact, this linear_operator_synthesis methods can call several backend routines to synthesise a circuit. These routines have different behavior and performances.

An exhaustive list of the available routine can be found in the documentation together with references.

To benchmark them, we can try to reduce the size of a large CNOT circuit:

import numpy as np

def large_random_circuit(nbqbits):
    nbcnots = nbqbits ** 2
    prog = Program()
    qbits = prog.qalloc(nbqbits)
    for _ in range(nbcnots):
        CNOT(np.random.choice(qbits, replace=False, size=2))
    return prog.to_circ()

circuit = large_random_circuit(10)
print("Before synthesis:", len(circuit.ops))
table = extract_linear_operator(circuit)
small_circuit = linear_operator_synthesis(table, method="greedy_gauss")
print("After synthesis (greedy_gauss):", len(small_circuit.ops))
small_circuit = linear_operator_synthesis(table, method="gauss")
print("After synthesis (gauss):", len(small_circuit.ops))
small_circuit = linear_operator_synthesis(table, method="pmh", m=3)
print("After synthesis (pmh):", len(small_circuit.ops))

Before synthesis: 100
After synthesis (greedy_gauss): 42
After synthesis (gauss): 55
After synthesis (pmh): 48

For some applications, it can be interesting to minimize the depth of the circuit instead of the CNOT count. That is precisely what the divide_and_conquer routine does:

shallow_circuit = linear_operator_synthesis(table, method="divide_and_conquer", m=3)
print("After synthesis (doc):", len(small_circuit.ops))

def depth(circuit):
    ''' Computes the depth of a circuit '''
    slices = [set()]
    for op in circuit:
        qbits = op.qbits
        insert_in = None
        for index, slic in enumerate(reversed(slices)):
            if all(qb not in slic for qb in qbits):
                continue
            insert_in = index
            break
        if insert_in is None:
            for qb in qbits:
                slices[0].add(qb)
        elif insert_in == 0:
            slices.append(set(qbits))
        else:
            for qb in qbits:
                slices[len(slices) - insert_in].add(qb)
    return len(slices)

print("Depth (doc):", depth(shallow_circuit))
print("Depth (pmh):", depth(small_circuit))

After synthesis (doc): 48
Depth (doc): 21
Depth (pmh): 27

Architecture aware synthesis

One of the routine called by linear_operator_synthesis can take into account a connectivity graph in order to generate an architecture compliant CNOT circuit.

This routine needs a (networkx) graph and an Hamiltonian path of this graph.

For the purpose of demonstration, lets consider a simple line device:

from qat.devices import LineDevice
from qat.synthopline.linear_synthesis import random_linear_operator
device = LineDevice(4)
operator = random_linear_operator(4)
print(device.description)
print(device)
ham_path = [0, 1, 2, 3]
aspen_circuit = linear_operator_synthesis(operator, method="steiner_gauss", graph=device.as_graph(), ham_path=ham_path)
aspen_circuit.display()

A LNN device with 4 qubits
0 -- 1 -- 2 -- 3