Improve LinearFunction synthesis

[ShellyGarion]

What should we add?

Improving LinearFunction synthesis.

Currently, it may happen that after the synthesis one gets a circuit with more CX gates than before the synthesis. Here is an example:

from qiskit import QuantumCircuit
from qiskit.circuit.library import *
from qiskit.transpiler import PassManager
from qiskit.transpiler.passes.optimization import CollectLinearFunctions
from qiskit.transpiler.passes.synthesis import (
    LinearFunctionsSynthesis,
    LinearFunctionsToPermutations,
)

# linear
n=5 
qc = QuantumCircuit(n)
for i in range(n-1):
    qc.cx(i,i+1)
# print (LinearFunction(qc).linear)
print ("Before LinearFunction:", qc.count_ops())


qc2 = PassManager(CollectLinearFunctions()).run(qc)
qc3 = PassManager(LinearFunctionsSynthesis()).run(qc2)
# print (qc3)
print ("After LinearFunction: ", qc3.count_ops())

outputs:

Before LinearFunction: OrderedDict([('cx', 4)])
After LinearFunction:  OrderedDict([('cx', 6)])

Here are the suggestions to handle this problem and improve LinearFunction synthesis:

1. The transpiler pass of LinearFunctionsSynthesis should not return a circuit if it has more CX gates and/or worse depth than the original circuit.

2. Let A=LinearFunction(qc).linear. Try to decompose the following 4 options and choose the best one (with optimal CX count and/or depth): A, inverse(A), transpose(A) and inverse(transpose(A)). (take the reverse circuit and/or reverse the ctrl and trgt of the CX gate accordingly).

3. Transfer qiskit.transpiler.synthesis.graysynth to qiskit.synthesis.graysynth and add further synthesis algorithms of reversible linear circuits.

[alexanderivrii]

@ShellyGarion , @mtreinish, how would LinearFunctionsSynthesis know if it's supposed to improve gate-count or depth? I might be wrong, but I don't recall seeing the optimization criteria as part of the options to transpile.