Optimizing circuits via Graphopt

This plugin is based on Automated optimization of large quantum circuits with continuous parameters by Nam and al.

The algorithm implemented is a light version of the one introduced in the paper. The optimization relies on two different techniques:

• pattern rewriting (an ad hoc version of the mecanics implemented in qat.pbo)
• phase polynomial optimization (described below)

Step by step walkthrough

The algorithm starts by rewriting gates in order to express the circuit in a particular gate set containing only CNOTs, H, and RZ.

In order to have an idea of the patterns used during this first rewriting, one can use the expandonly parameter to limit the algorithm to this first stage:

from qat.lang.AQASM import *

p_toffoli = Program()
qbits = p_toffoli.qalloc(3)
p_toffoli.apply(CCNOT, qbits)
toffoli = p_toffoli.to_circ()

p_cph = Program()
qbits = p_cph.qalloc(2)
p_cph.apply(PH(0.5).ctrl(), qbits)
cph = p_cph.to_circ()

from qat.plugins import Graphopt
from qat.core import Batch
plugin = Graphopt(expandonly=True)
batch = Batch(jobs=[toffoli.to_job(), cph.to_job()])
compiled = plugin.compile(batch, None)
toffoli_split = compiled.jobs[0].circuit
cph_split = compiled.jobs[1].circuit
print(">>>> Toffoli expansion:")
toffoli.display()
toffoli_split.display()
print(">>>> Controled phase expansion:")
cph.display()
cph_split.display()

>>>> Toffoli expansion:

>>>> Controled phase expansion:

Of course the resulting circuits are larger than the original ones, but also more realistics in terms of practical gate sets.

Once all the gates are expanded, the optimizer alternate between pattern rewriting and phase polynomial reductions.

To illustrate the different patterns used in the first stage, lets consider the following circuit:

from qat.core.simutil import optimize_circuit
prog = Program()
qbits = prog.qalloc(1)
prog.apply(H, qbits)
prog.apply(S, qbits)
prog.apply(H, qbits)
circuit = prog.to_circ()
optimized_circuit = optimize_circuit(circuit, Graphopt())
circuit.display()
optimized_circuit.display()

The main idea is to reduce the number of H gates in order to build large, Hadamard free, subcircuits.

There are 6 different identities that help achieve this same goal:

prog = Program()
qbits = prog.qalloc(1)
prog.apply(H, qbits)
prog.apply(S.dag(), qbits)
prog.apply(H, qbits)
circuit = prog.to_circ()
optimized_circuit = optimize_circuit(circuit, Graphopt())
print("===== Second pattern:")
circuit.display()
optimized_circuit.display()

prog = Program()
qbits = prog.qalloc(2)
for qb in qbits:
    prog.apply(H, qb)
prog.apply(CNOT, qbits)
for qb in qbits:
    prog.apply(H, qb)
circuit = prog.to_circ()
optimized_circuit = optimize_circuit(circuit, Graphopt())
print("===== Third pattern")
circuit.display()
optimized_circuit.display()

prog = Program()
qbits = prog.qalloc(2)
prog.apply(H, qbits[1])
prog.apply(S, qbits[1])
prog.apply(CNOT, qbits)
prog.apply(S.dag(), qbits[1])
prog.apply(H, qbits[1])
circuit = prog.to_circ()
optimized_circuit = optimize_circuit(circuit, Graphopt())
print("===== Fourth pattern")
circuit.display()
optimized_circuit.display()

prog = Program()
qbits = prog.qalloc(2)
prog.apply(H, qbits[1])
prog.apply(S.dag(), qbits[1])
prog.apply(CNOT, qbits)
prog.apply(S, qbits[1])
prog.apply(H, qbits[1])
circuit = prog.to_circ()
optimized_circuit = optimize_circuit(circuit, Graphopt())
print("===== Fifth pattern")
circuit.display()
optimized_circuit.display()

prog = Program()
qbits = prog.qalloc(1)
prog.apply(H, qbits)
prog.apply(H, qbits)

circuit = prog.to_circ()
optimized_circuit = optimize_circuit(circuit, Graphopt())
print("===== Last pattern")
circuit.display()
optimized_circuit.display()

===== Second pattern:

===== Third pattern

===== Fourth pattern

===== Fifth pattern

===== Last pattern

Notice how all these patterns reduce the Hadamard count of the circuit.

Once the Hadamard count is reduced, the optimizer uses phase polynomial identities to reduce the Rz count.

To illustrate this technique consider the following CNOT + Rz circuit and its optimized version:

prog = Program()
qbits = prog.qalloc(3)
prog.apply(PH(0.3), qbits[2])
prog.apply(CNOT, qbits[0], qbits[1])
prog.apply(CNOT, qbits[1], qbits[2])
prog.apply(CNOT, qbits[2], qbits[1])
prog.apply(PH(0.4), qbits[1])
circuit = prog.to_circ()
optimized_circuit = optimize_circuit(circuit, Graphopt())

circuit.display()
optimized_circuit.display()

By tracking how PH gates contribute to the phase of the circuit, the optimizer can merge them when possible, thus reducing the PH/RZ count of the circuit.

Overall optimization

Lets see how the optimizer behave on a QFT-based adder:

from qat.lang.AQASM.qftarith import add
from qat.core.util import statistics
prog = Program()
qbits = prog.qalloc(8)
prog.apply(add(4, 4), qbits)
circuit = prog.to_circ(inline=True)

circuit = optimize_circuit(circuit, Graphopt(expandonly=True))
optimized_circuit = optimize_circuit(circuit, Graphopt())
circuit.display()
print(statistics(circuit))
optimized_circuit.display()
print(statistics(optimized_circuit))

{'nbqbits': 8, 'size': 118, 'gates': {'custom gate': 0, 'H': 8, 'T': 15, 'CNOT': 44, 'PH': 43, 'S': 8}, 'measurements': 0, 'resets': 0, 'logic': 0, 'breaks': 0, 'remaps': 0, 'gate_size': 118}

{'nbqbits': 8, 'size': 87, 'gates': {'custom gate': 0, 'H': 8, 'CNOT': 44, 'PH': 29, 'T': 4, 'S': 2}, 'measurements': 0, 'resets': 0, 'logic': 0, 'breaks': 0, 'remaps': 0, 'gate_size': 87}

As you can notice, the number of RZ/PH/T/S gates is indeed lower after optimization. Of course, this type of circuits is not representative, since it is already quite optimized. One can try, for instance to concatecate two of those circuits:

circuit = circuit + circuit
optimized_circuit = optimize_circuit(circuit, Graphopt())
circuit.display()
print(statistics(circuit))
optimized_circuit.display()
print(statistics(optimized_circuit))

{'nbqbits': 8, 'size': 236, 'gates': {'custom gate': 0, 'H': 16, 'T': 30, 'CNOT': 88, 'PH': 86, 'S': 16}, 'measurements': 0, 'resets': 0, 'logic': 0, 'breaks': 0, 'remaps': 0, 'gate_size': 236}

{'nbqbits': 8, 'size': 59, 'gates': {'custom gate': 0, 'H': 12, 'T': 3, 'PH': 21, 'CNOT': 20, 'S': 2, 'Z': 1}, 'measurements': 0, 'resets': 0, 'logic': 0, 'breaks': 0, 'remaps': 0, 'gate_size': 59}

Here the gain is much larger!