Mapping: steiner vs swap - 100 times slower

[DevelopDaily]

Thanks for the previous fix. Now, I start to run bigger circuits.

Here is a test case to show steineris 100 times slower than swap.

shor.zip

Though I don't characterize that as a bug yet, it looks unusual.

Would you please comment on the issue?

I run these:

time ./staq -S   -O1   -d   tokyo -m  -M  steiner   -l   bestfit   -f   qasm   -o shor_staq.qasm shor.qasm

real    2m54.130s
user    2m52.265s
sys 0m0.375s

time ./staq   -S   -O1   -d   tokyo -m  -M  swap   -l   bestfit   -f   qasm   -o shor_staq.qasm shor.qasm 

real    0m1.782s
user    0m1.534s
sys 0m0.058s

[meamy]

We are aware of this issue. It arises because we do an additional layout optimization before the steiner mapping, but it can be disabled:

time ./staq -S -O1 -d tokyo -m -M steiner -l bestfit -f qasm -o shor_staq.qasm shor.qasm 

real    1m55.443s
user    1m55.293s
sys 0m0.144s

time ./staq --disable-layout-optimization -S -O1 -d tokyo -m -M steiner -l bestfit -f qasm -o shor_staq.qasm shor.qasm 

real    0m1.615s
user    0m1.615s
sys 0m0.000s

Basically after we generate an initial layout, we do a "hill climb" by repeatedly swapping two qubits in the layout and running a simulation of the steiner mapping algorithm. This gets quite expensive for a lot of qubits, so we have an option to disable it. We only did this for the steiner mapping as the initial layout seems to have a greater effect on the final cx counts for this algorithm than for swap.

We're hoping to go back to this problem and find a more scalable solution, but that's getting into active research. The layout optimization was a nice stop-gap that gave a boost of performance for small circuits where the scaling isn't an issue.

[DevelopDaily]

Very nice. Thanks.