karlosz
commented
2 years ago To clarify this issue, the linear in linear reversible circuits is a much stronger condition than the adjective linear as one would expect from linear algebra when considering unitary matrices. linear is a very strong condition on a reversible circuit preserving the linearity over the XOR operation; that is, the action of the circuit is not just determined by the computational basis of size 2^n for an n-(qu)bit circuit; in fact it is determined by a smaller basis of size n where the basis vectors index into the computational basis by 2^i for 0 <= i < n.
This algorithm cannot generalize to what tweedledum does for us, which is the much more general problem of synthesizing any reversible circuit, which requires at least the gates needed to simulate arbitrary multiple control Toffoli gates.
We would still like to investigate how to detect/when we can apply the synthesis algorithm for the much stronger condition of linear reversible circuits.
The paper describes a way to convert linear reversible circuits into CNOT gates. The paper operates over boolean vectors, but the results are extended to quantum just fine. This could be useful in the synthesis of classical logic (e.g., permutation matrices), which the Tweedledum library has done for us. However, the Tweedledum library has gone through several new, incompatible versions, and we haven't maintained the binding.
The goal would be to implement the paper and implement it as a compiler in QUILC.