Quantum Linear Logic Synthesis Algorithm Based on L-ESOP Reduction

In order to generate quantum linear circuits with minimal gates, we propose a L-ESOP reduction-based logic synthesis algorithm. The proposed algorithm keeps transforming L-ESOP via XOR operationuntil the original L-ESOP of every circuit line is turned into identity form. Each XOR operation used inthe transformation process corresponds to a CNOT gate, and the resulting circuit can be derived by arrangingthese CNOT gates in reverse order. Moreover, we present three look-ahead heuristic rules for the proposedalgorithm to make the gate costs of quantum linear circuit as small as possible. These three rules are employedin three different stages of the algorithm respectively, choosing the best XOR solution according tothe weight of the XOR result, which indicates how many variables of L-ESOP can be reduced successively.The experimental evaluations show that the proposed approach clearly outperforms other optimal algorithms.After employing three look-ahead heuristic rules, the proposed algorithm shows great superiority in terms ofgate count over other optimal approach, and this superiority grows along with the growth of circuit lines,when in 100-line circuit-synthesis cases the average gate count of this algorithm is less than other algorithmsby 21.69% at least. Additionally, this algorithm has a polynomial runtime complexity, the average time needed for 100-line circuit-synthesis is only 71.55 ms.