We have proposed DaCSynth, a scalable algorithm for synthesizing shallow linear reversible quantum circuits and we have shown that synthesizing an operator with a divide and conquer algorithm is equivalent to zeroing binary matrices with three elementary operations. This gives a framework that generalizes other works and widens the perspective of finding new techniques.
We have derived an upper bound that improves existing bounds for registers of intermediate sizes and we have used a greedy algorithm to obtain the shallowest possible circuits. In our benchmarks, the circuits produced by the algorithm DaCSynth have a depth which is twice smaller than state-of-the-art algorithms. We have also presented purely greedy algorithms providing close to optimal results for small or simple operators. Applied to the synthesis of a class of reversible functions, we report some substantial savings in the total depth of the circuits while keeping the T-depth as low as possible.
This work represents one step toward the compilation of quantum circuits that can be executed on a quantum hardware in the future. As future work, we will study how to adapt this method to take into account the connectivity constraints between the qubits in real hardware. Another future work will be to extend DaCSynth to Clifford circuits. Syntheses of Clifford circuits through normal forms are possible (see, e.g., [1]}, [2]}, [3]}) but it would also be interesting to see if DaCSynth has an equivalent in the symplectic group \(Sp(2n, \mathbb {F}_2)\)  used to represent Clifford operators with a different set of elementary operations available. An interesting result would be to see if a direct synthesis can produce better depths rather than using normal forms.
