Heuristic and Optimal Synthesis of CNOT and Clifford Circuits

Understand

Efficiently implementing Clifford circuits is crucial for quantum error correction and quantum algorithms.

• Linear reversible circuits, equivalent to circuits composed of CNOT gates, have important applications in classical computing.
• In this work we present methods for CNOT and general Clifford circuit synthesis which can be used to minimise either the entangling two-qubit gate count or the circuit depth.
• We present three families of algorithms - optimal synthesis which works on small circuits, A* synthesis for intermediate-size circuits and greedy synthesis for large circuits.