SAT-based linear synthesis

[boschmitt]

Description

This PR includes an initial implementation for a SAT-based linear synthesis method that also works under coupling constraints.

from tweedledum.target import Device
from tweedledum.synthesis import sat_linear_synth

path3 = Device.path(3)
linear_trans = [[1,1,1], 
                [0,1,0], 
                [0,0,1]]
circuit = sat_linear_synth(path3, linear_trans)
print(circuit)

Results:

__q2 : ──●─────────●──
       ╭─┴─╮     ╭─┴─╮
__q1 : ┤ x ├──●──┤ x ├
       ╰───╯╭─┴─╮╰───╯
__q0 : ─────┤ x ├─────
            ╰───╯     

In comparison, stainer_gauss_synth:

__q2 : ───────●─────────●───────
            ╭─┴─╮     ╭─┴─╮     
__q1 : ──●──┤ x ├──●──┤ x ├──●──
       ╭─┴─╮╰───╯╭─┴─╮╰───╯╭─┴─╮
__q0 : ┤ x ├─────┤ x ├─────┤ x ├
       ╰───╯     ╰───╯     ╰───╯

The method guarantees finding an optimum solution. However, It scales horribly on the number of qubits. But should be enough to run some small experiments and be used to understand how to improve stainer_gauss_synth.

Suggested changelog entry:

SAT-based linear synthesis.

[codecov-commenter]

Codecov Report

Merging #157 (e545b8c) into master (fe997be) will decrease coverage by 1.80%. The diff coverage is 50.26%.

@@            Coverage Diff             @@
##           master     #157      +/-   ##
==========================================
- Coverage   74.18%   72.37%   -1.81%     
==========================================
  Files          87       88       +1     
  Lines        4582     4956     +374     
==========================================
+ Hits         3399     3587     +188     
- Misses       1183     1369     +186     

Impacted Files	Coverage Δ
src/Synthesis/sat_linear_synth.cpp	50.00% <50.00%> (ø)
include/tweedledum/Target/Device.h	47.72% <100.00%> (+0.80%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update f155297...e545b8c. Read the comment docs.