Create circuit from ESOP form

[Quox]

Hello, great work!

I try synthesising the function F = x1x3 ⊕ x1x4 ⊕ x2x3 ⊕ x2x4 ⊕ x5x6. I wrote the following code for it:

module simple(out x0(1), inout x1(1), inout x2(1), inout x3(1), inout x4(1), inout x5(1), inout x6(1))
 x0 ^= (x1 & x3) 
 x0 ^= (x1 & x4)
 x0 ^= (x2 & x3) 
 x0 ^= (x2 & x4)
 x0 ^= (x5 & x6)

However, it led to 5 more gates than expected. Modification to:

x0 ^= (((((x1 & x3) ^ (x1 & x4)) ^ (x2 & x3)) ^ (x2 & x4)) ^ (x5 & x6))

made it even worse (line-aware synthesis failed completely). Is it possible to get the circuit containing 5 standard Toffoli gates?

[burgholzer]

Hey 👋🏼
thanks for reaching out! Unfortunately, I am really blocked at the moment and can't quite say when I'll have time to look into this in more detail. I would have guessed that it should be possible to get the expected 5 Toffoli Circuit, so this might be a bug (or, at least, a missed opportunity).
Maybe @SmaranTum has any idea of what might be happening and whether that is expected.

[burgholzer]

since each line is an irreversible operation, we require an additional lines and additional gates to compute and store the irreversible operation.

Just trying to clarify on this: Isn't c ^= a & b reversible? It "just" translates to a Toffoli with controls a and b and target c. I don't quite see where this would require an additional line.

[SmaranTum]

It is reversible because you are using c as an implicit additional line. SyReC rules does not allow us to use outputs as additional lines.

[burgholzer]

That is not really true though, is it? The statement is reversible no matter the value of c and, theoretically, no matter if c is an input, an output, or both. This is actually shown in Fig 10c of https://doi.org/10.1016/j.vlsi.2015.10.001 and further explained in the text.

[SmaranTum]

In that case, it is a missed opportunities.

[burgholzer]

Note that this is also described at the end of Section 4B in https://www.cda.cit.tum.de/files/eda/2019_iccad_hdl_based_reversible_circuit_synthesis_without_additional_lines.pdf (where you are even a coauthor 😉).