Repository: cda-tum/mqt-qmap (language: python)

Issue:
🐛 Sub-optimal computation of exact mapper, heuristic performs better than exact mapper
### mqt.qmap version

mqt-qmap 2.1.1 via pip

### OS

Ubuntu

### Python version

_No response_

### C++ compiler

_No response_

### Additional environment information

_No response_

### Description

See MEW below:
```
from qiskit import QuantumCircuit
from mqt import qmap

circ = QuantumCircuit(4)
circ.cx(1,0)
circ.cx(0,1)
circ.cx(2,1)
circ.cx(1,2)
circ.cx(3,2)

arch = qmap.Architecture(
    5,
    {
        (1, 0),
        (2, 0),
        (2, 1),
        (4, 2),
        (3, 2),
        (3, 4),
    },
)

qc_mapped_exact, res = qmap.compile(circ, arch, method="exact", post_mapping_optimizations=False)
qc_mapped_heu, res = qmap.compile(circ, arch, method="heuristic", post_mapping_optimizations=False)

print(f"Exact: {qc_mapped_exact.count_ops()}") # gives 12 addtional H - sub-optimal but correct
print(f"Heuristic: {qc_mapped_heu.count_ops()}") # gives 8 addtional H - correct + optimal
```

### Expected behavior

- I would assume that the heuristic approach, in contrast to the exact approach, is not better in terms of added number of gates
- The solution of the exact mapper is not the minimal number of addtional H gates

### How to Reproduce

- Run MWE above
- MWE can be computed via pen&paper


Discussion / hints:
Thanks for bringing this up and taking the time to create the minimal reproducer. That certainly looks like a bug and I'll look into it. I'll come back to you once I found something.

Edit: I can reproduce your example on my machine. On it right now.

Fix patch:
diff --git a/src/exact/ExactMapper.cpp b/src/exact/ExactMapper.cpp
index 126c5bb90..3896e6705 100644
--- a/src/exact/ExactMapper.cpp
+++ b/src/exact/ExactMapper.cpp
@@ -724,22 +724,23 @@ number of variables: (|L|-1) * m!
 
   // cost for reversed directions
   if (!architecture.bidirectional()) {
-    cost = LogicTerm(0);
-    for (std::size_t k = 0; k < reducedLayerIndices.size(); ++k) {
+    cost                 = LogicTerm(0);
+    const auto numLayers = reducedLayerIndices.size();
+    for (std::size_t k = 0; k < numLayers; ++k) {
       for (const auto& gate : layers.at(reducedLayerIndices.at(k))) {
         if (gate.singleQubit()) {
           continue;
         }
 
-        auto reverse = LogicTerm(true);
-        for (const auto& edge : rcm) {
-          auto indexFT = x[k][physicalQubitIndex[edge.first]][gate.target];
-          auto indexSC = x[k][physicalQubitIndex[edge.second]]
-                          [static_cast<std::size_t>(gate.control)];
-          reverse = reverse && (!indexFT || !indexSC);
+        auto reverse = LogicTerm(false);
+        for (const auto& [q0, q1] : rcm) {
+          const auto indexFT = x[k][physicalQubitIndex[q0]][gate.target];
+          const auto indexSC = x[k][physicalQubitIndex[q1]]
+                                [static_cast<std::size_t>(gate.control)];
+          reverse = reverse || (indexFT && indexSC);
         }
         cost = cost + LogicTerm::ite(reverse,
-                                     LogicTerm(GATES_OF_DIRECTION_REVERSE),
+                                     LogicTerm(::GATES_OF_DIRECTION_REVERSE),
                                      LogicTerm(0));
       }
     }


Test patch:
diff --git a/test/test_exact.cpp b/test/test_exact.cpp
index 6acc0cd64..45133f408 100644
--- a/test/test_exact.cpp
+++ b/test/test_exact.cpp
@@ -5,7 +5,6 @@
 
 #include "exact/ExactMapper.hpp"
 
-#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 class ExactTest : public testing::TestWithParam<std::string> {
@@ -534,3 +533,26 @@ TEST_F(ExactTest, Test4QCircuitThatUsesAll5Q) {
   const auto& results = mapper.getResults();
   EXPECT_EQ(results.output.swaps, 1);
 }
+
+TEST_F(ExactTest, Test) {
+  // Regression test for https://github.com/cda-tum/qmap/issues/251
+  using namespace qc::literals;
+
+  Architecture      arch;
+  const CouplingMap cm = {{1, 0}, {2, 0}, {2, 1}, {4, 2}, {3, 2}, {3, 4}};
+  arch.loadCouplingMap(5, cm);
+
+  Architecture::printCouplingMap(cm, std::cout);
+
+  qc = qc::QuantumComputation(4);
+  qc.x(0, 1_pc);
+  qc.x(1, 0_pc);
+  qc.x(1, 2_pc);
+  qc.x(2, 1_pc);
+  qc.x(2, 3_pc);
+
+  auto mapper = ExactMapper(qc, arch);
+  mapper.map(settings);
+  EXPECT_EQ(mapper.getResults().output.swaps, 0);
+  EXPECT_EQ(mapper.getResults().output.directionReverse, 2);
+}