🐛 Missmatches in current implmentation to publication

[jeanlyc]

mqt.qmap version

mqt-qmap 2.1.2 via pip

OS

Ubuntu

Python version

No response

C++ compiler

No response

Additional environment information

No response

Description

Please find below an (incomplete) list of benchmarks where the current implementation of the exact mapping algorithm shows differences when reproducing the results of Wille et al. (IBM QX4 arch):

• 3_17_13.qasm
• 4gt11_83.qasm
• 4mod5-v0_19.qasm
• alu-v3_34.qasm

Expected behavior

I would expect the same results as mentioned in the paper.

How to Reproduce

Run listed benchmarks above with exact mapper for arch graph resembling IBM QX4 (asymmetric) connectivity and compare with results of publication.

[burgholzer]

Thanks for opening this issue. I'll try to look into it in more detail over the next couple of days.
A note on that right away: Since the original publication, QMAP as a tool has evolved quite a bit. So I wouldn't be too surprised, if the results it produces changed over time.
If the results got better, I'd even go as far and say that's desirable.

Could you provide me with a little more context on the difference in results you are seeing?
Is it final gate count, number of SWAPs, number of direction reverses? Is it better or worse?

[jeanlyc]

I checked against the original publication, and I find the following differences based on the benchmarks shown on the publication.
I count the total number of gates after mapping (as in the publication).
The format below is:
{benchmark name}: {optimal results from publication} vs. {qmap_exact}

3_17_13.qasm: 59 vs. 60
4gt11_83.qasm: 49 vs. 50
4mod5-v0_19.qasm: 64 vs. 69
alu-v3_34.qasm: 90 vs. 91
mod5mils_65.qasm: 64 vs. 65
rd32-v0_66.qasm: 63 vs. 73
rd32-v1_68.qasm: 65 vs. 75

I currently see no reason to argue that the results in the publication are not correct. Maybe there is a bug in the permutation function that SWAPs some qubits even though that is not necessary for physical connectivity reasons?

[burgholzer]

Thanks for the details. Now that I see the numbers, I think I remember the cause for the difference.
IIRC, it comes down to a very subtle difference in the coupling map shown in the paper and the real coupling map of the IBM QX4 device (as it can be seen in https://arxiv.org/abs/1808.05661 and exposed through QMAP).

In the paper, the coupling map for the IBM QX4 device shown in Figure 2 is:

[[1, 0], [2, 0], [2, 1], [3, 2], [3, 4], [4, 2]]

whereas AvailableArchitecture::IbmQx4 in QMAP is defined as:

[[1, 0], [2, 0], [2, 1], [3, 2], [3, 4], [2, 4]]

Note the reversed direction of the last edge of the coupling map.

The results in the paper were generated based on the coupling map shown in the paper. This can also be seen in the original code repository at https://github.com/iic-jku/minimal_ibm_qx_mapping/blob/e41de077a1c1096be74a9bcdd9ced35228bd69d5/minimal_ibm_qx_mapping/main.cpp#L79-L86.
The coupling map error has since been corrected in QMAP (see above), but there is no way we could update the publication.

If you are using the Python interface of QMAP, using the old Architecture is as easy as

from mqt import qmap

circ = ...
arch = qmap.Architecture(
    5,
    {
        (1, 0),
        (2, 0),
        (2, 1),
        (3, 2),
        (3, 4),
        (4, 2)
    },
)
qc_mapped, res = qmap.compile(qc, arch, method="exact")

Please let us know if you can replicate the results based on the above suggestions.

[jeanlyc]

I already included that "mismatch", however, results are still not the optimal ones as in the publication.
Note that is actually used
qmap.compile(circ, arch, method="exact", post_mapping_optimizations=False)
I will have a look at the rd32-* circuits, as here the difference seems to be the largest. Frome these circuits, I will try to derive a smaller circuit as a MVE and potentially create an example where qmap (in excact mode) does not find the minimal solution (and provide this minimal solution independently). Hopefully this will help to narrow down if there really is an issue or not...

[jeanlyc]

I constructed a MVE as follows:

`
from qiskit import QuantumCircuit
from mqt import qmap

n_qubits = 4
circ = QuantumCircuit(n_qubits)
circ.cx(0,1) # first cx(0,1)
circ.cx(3,0)
circ.cx(1,3)
circ.cx(1,0)
circ.cx(3,0)
circ.cx(1,3)
circ.cx(0,1) # last cx(0,1)
circ.cx(1,2)

arch = qmap.Architecture(
5,
{
(1, 0),
(2, 0),
(2, 1),
(3, 2),
(3, 4),
(4, 2), # coupling as in the publication
},
)

qmap.compile(circ, arch, method="exact", post_mapping_optimizations=False)
`
The exact mapper adds 12 additional H gates to the original circuit (total number of gates after mapping: 20). Mapping is: q0->0, q1->2, q2->3,q3->1.

However, there is a valid solution that adds 11 gates and therefore the mapped circuit has 19 gate operations in total after mapping.
Here. the mapping is: q0->2, q1->3, q2->0,q3->4. In this solution 4 additional H are required "to get the first CNOT right", and a SWAP opertation of the physical qubits 2 and 3 (+7 gate ops) is necessary before the last circ.cx(0,1).
Note that this solution is only optimal w.r.t. total gate number after mapping (and, e.g., not if you do not want to add addtional two-qubit gates).

Is this all correct and helps?

[burgholzer]

Thanks for the effort. That certainly helps. I added the circuit you found as an additional regression test to #264.
As of now, it looks like I was able to fix half of the problem. I still need to figure out why the other half of the tests is failing.

[burgholzer]

This problem should be fixed now that #264 is merged. The PR description also contains a detailed description of what has been fixed. Could you maybe confirm that this fixes your problems by trying out the latest main branch?

[jeanlyc]

I will check on Monday.
Will there be or is there a new version also on pip?

[burgholzer]

I'll release a new version probably tomorrow or on Monday the latest. Still want to get in #268 before the next release.