LazySynthesis: quantum circuit compilation
The base algorithm/plugin
The qat.plugins.LazySynthesis plugin uses in-house meta-heuristics that strictly generalize the standard SWAP insertion techniques in order to generate connectivity compliant circuit.
It works by lazily synthesizing pieces of linear boolean operators using sub-circuits matching the hardware connectivity.
The algorithm itself is detailed in [MdB20].
Additionally, since it is a Plugin, LazySynthesis is able to skip the synthesis of the final CNOTs and store the final linear operator
in order to post-process samples or alter the compiled job’s observable to an equivalent one.
This feature might save up a large number of CNOTs depending on the connectivity and/or the circuit.
In practice, everything happens inside the Plugin and is transparent for the user.
Note
The purpose of this plugin is by no means, to replace the Nnizer plugin. SWAP insertion plugins might behave better for some type of circuits. A good rule of thumb is the density of Clifford gates in the initial quantum circuit.
If the circuit contains very few Clifford gates, Nnizer might behave better. On the contrary, for large Clifford densities the LazySynthesis plugin will probably even prune some gates during the compilation, leading to a shorter, architecture compliant circuit.
Additional features
The main algorithm inside the CliffordNormalizer plugin works by rewriting a quantum circuit \(U\) into a new circuit \(U'\) and a Clifford operator \(C\) such that:
Having access to such a black box, one can perform several direct and reverse passes on a quantum circuit in order to rewrite it as
where \(C_1\) and \(C_2\) are Clifford operators. One can then deal with \(C_1\) and \(C_2\) by performing stabilizer states synthesis.
This concept is described through the concept CliffordNormalizer
that is implemented by LazySynthesis.
This means that any construction argument of the CliffordNormalizer can also be passed to the CliffordNormalizer plugin.
We list here the few features that this CliffordNormalizer provides.
Bidirectional Clifford re-normalization
Bidirectional normalization (in this setting of Clifford based synthesis) consists in iterating several time forward and backward passes of LazySynthesis calls.
These passes might change operators \(C_1\), \(C_2\), and \(U'\) in the formula above, and thus their entangling gates requirements.
In this meta-heuristics, we simply iterate the passes several times and pick the iteration that led to the least number of entangling gates.
from qat.plugins import LazySynthesis
from qat.lang.AQASM import *
prog = Program()
qbits = prog.qalloc(10)
for i in range(9):
CNOT(qbits[i], qbits[i+1])
RZ(0.2311)(qbits[9])
for i in range(9):
CNOT(qbits[i], qbits[i+1])
circuit = prog.to_circ()
job = circuit.to_job()
from qat.devices import LineDevice
print("Without renormalization:")
new_job, _ = LazySynthesis(bidirectional=False).compile_job(job, LineDevice(10))
for gate in new_job.circuit.iterate_simple():
print(gate)
print("With renormalization:")
new_job, _ = LazySynthesis(bidirectional=True, max_iter=3).compile_job(job, LineDevice(10))
for gate in new_job.circuit.iterate_simple():
print(gate)
Without renormalization:
('CNOT', [], [9, 8])
('CNOT', [], [8, 7])
('CNOT', [], [7, 6])
('CNOT', [], [6, 5])
('CNOT', [], [5, 4])
('CNOT', [], [4, 3])
('CNOT', [], [3, 2])
('CNOT', [], [2, 1])
('CNOT', [], [1, 0])
('RZ', [0.2311], [0])
('H', [], [0])
('H', [], [1])
('H', [], [2])
('H', [], [3])
('H', [], [4])
('H', [], [5])
('H', [], [6])
('H', [], [7])
('H', [], [8])
('H', [], [9])
('H', [], [0])
('H', [], [1])
('H', [], [2])
('H', [], [3])
('H', [], [4])
('H', [], [5])
('H', [], [6])
('H', [], [7])
('H', [], [8])
('H', [], [9])
With renormalization:
('H', [], [9])
('H', [], [8])
('H', [], [7])
('H', [], [6])
('H', [], [5])
('H', [], [4])
('H', [], [3])
('H', [], [2])
('H', [], [1])
('H', [], [0])
('H', [], [9])
('H', [], [8])
('H', [], [7])
('H', [], [6])
('H', [], [5])
('H', [], [4])
('H', [], [3])
('H', [], [2])
('H', [], [1])
('H', [], [0])
('RZ', [0.2311], [0])
('H', [], [0])
('H', [], [1])
('H', [], [2])
('H', [], [3])
('H', [], [4])
('H', [], [5])
('H', [], [6])
('H', [], [7])
('H', [], [8])
('H', [], [9])
('H', [], [0])
('H', [], [1])
('H', [], [2])
('H', [], [3])
('H', [], [4])
('H', [], [5])
('H', [], [6])
('H', [], [7])
('H', [], [8])
('H', [], [9])
In this example, the renormalization process basically stripped all Clifford gates out of the circuit. This is of course an extreme example. In any case, this optimization can never degrade the entangling count performance of the main synthesis algorithm.
Initial gate optimization
One can ask CliffordNormalizer (or LazySynthesis) to simplify the start of the output quantum circuit.
This optimization assumes that the quantum computation starts in state \(|0\rangle\).
from qat.plugins import LazySynthesis
from qat.lang.AQASM import *
prog = Program()
qbits = prog.qalloc(2)
CNOT(qbits)
RZ(0.2311)(qbits[1])
CNOT(qbits)
circuit = prog.to_circ()
job = circuit.to_job()
new_job, _ = LazySynthesis(optimize_initial=True, verbose=True).compile_job(job, None)
for gate in new_job.circuit.iterate_simple():
print(gate)
<<<<<<<<< Plugin configuration >>>>>>>>>
bidirectional renormalization: False
bidirectional iterations: 20
initial rotation optim.: True
codiag. backend: syndrome
normalization backend: LazySynthesis
<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>
🚀️ Starting compilation 🚀️
=======================================================================
Initial circuit CNOT-equivalent count: 2
Attempting to remove useless rotations...
initial rotation count: 1
new rotation count after pruning: 0
Final circuit CNOT-equivalent count: 0
('H', [], [0])
('H', [], [1])
('H', [], [0])
('H', [], [1])
Indeed, in this example, the circuit does strictly nothing when applied to state \(|0\rangle\) (since it contains a single ZZ rotations, and operator ZZ stabilizes \(|0\rangle\)).
A CliffordNormalizer is able to notice that and remove the rotation, leaving an (almost) empty circuit.