🐛 Timeout for test on MacOS when `TwoQubitMultiplicity` is `unordered_map` in HeuristicMapper

mqt.qmap version

mqt.qmap==2.1.4

OS

macOS 12.6.3

Python version

No response

C++ compiler

AppleClang 14.0.0.140000

Additional environment information

No response

Description

When implementing TwoQubitMultiplicity in the heuristic mapper as an std::unordered_map instead of the current ordered std::map using the following custom hash function for the Edge keys:

struct PairHash {
  template <class T1, class T2>
  std::size_t operator()(const std::pair<T1, T2>& p) const {
    auto h1 = std::hash<T1>{}(p.first);
    auto h2 = std::hash<T2>{}(p.second);

    if constexpr (sizeof(size_t) >= 8) {
      return h1 ^ (h2 + 0x517cc1b727220a95 + (h2 << 6) + (h2 >> 2));
    }
    return h1 ^ (h2 + 0x9e3779b9 + (h2 << 6) + (h2 >> 2));
  }
};

using TwoQubitMultiplicity =
    std::unordered_map<Edge, std::pair<std::uint16_t, std::uint16_t>, PairHash>;

The test Heuristic/HeuristicTest16Q.Disjoint2qBlocks/ising_model_10 fails consistently because of a timeout in the Github CI job C++/Tests macos-latest (Ubuntu and Windows pass without too much difference in mapping time between both implementations)

Has not yet been tested with a local macOS system.

Expected behavior

Any use of TwoQubitMultiplicity in the heuristic mapper should be agnostic of the specific map implementation used (apart from negligible performance differences).

How to Reproduce

1. change the line HeuristicMapper.hpp:21 in the source from

using TwoQubitMultiplicity = std::map<Edge, std::pair<std::uint16_t, std::uint16_t>>;

to

struct PairHash {
  template <class T1, class T2>
  std::size_t operator()(const std::pair<T1, T2>& p) const {
    auto h1 = std::hash<T1>{}(p.first);
    auto h2 = std::hash<T2>{}(p.second);

    if constexpr (sizeof(size_t) >= 8) {
      return h1 ^ (h2 + 0x517cc1b727220a95 + (h2 << 6) + (h2 >> 2));
    }
    return h1 ^ (h2 + 0x9e3779b9 + (h2 << 6) + (h2 >> 2));
  }
};

using TwoQubitMultiplicity =
    std::unordered_map<Edge, std::pair<std::uint16_t, std::uint16_t>, PairHash>;

2. run the Github CI on the altered source (or probably also possible to compile using equivalent local macOS system)
3. Heuristic/HeuristicTest16Q.Disjoint2qBlocks/ising_model_10 fails with a timeout

Start at HeuristicMapper.hpp:21 and inspect how TwoQubitMultiplicity is used in the heuristic mapper. Reproduce the change on macOS or in the C++/Tests macos-latest CI job, then run Heuristic/HeuristicTest16Q.Disjoint2qBlocks/ising_model_10; done means the test no longer times out when the map implementation is changed.