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

Issue:
Teleportation sometimes fails
The teleportation functionality is flaky and fails with some initial placements.


Discussion / hints:

Fix patch:
diff --git a/README.md b/README.md
index d6a55554e..9f22954cf 100644
--- a/README.md
+++ b/README.md
@@ -91,7 +91,7 @@ Params:
     layering – Circuit layering strategy to use (*individual_gates* | disjoint_qubits | odd_qubits | qubit_triangle)
     use_teleportation - Use teleportation in addition to swaps
     teleportation_fake - Assign qubits as ancillary for teleportation but don't actually use them
-    teleportation_seed - Fix a seed for the initial ancilla placement (0 means no fixed seed)
+    teleportationSeed - Fix a seed for the initial ancilla placement (0 means no fixed seed)
     save_mapped_circuit – Include .qasm string of the mapped circuit in result
     csv – Create CSV string for result
     statistics – Print statistics
@@ -106,7 +106,7 @@ def compile(circ, arch: Union[str, Arch],
             layering: LayeringStrategy = LayeringStrategy.individual_gates,
             use_teleportation: bool = False,
             teleportation_fake: bool = False,
-            teleportation_seed: int = 0,
+            teleportationSeed: int = 0,
             save_mapped_circuit: bool = False,
             csv: bool = False,
             statistics: bool = False,
diff --git a/apps/heuristic_app.cpp b/apps/heuristic_app.cpp
index b882ff172..2fc790a1b 100644
--- a/apps/heuristic_app.cpp
+++ b/apps/heuristic_app.cpp
@@ -104,9 +104,9 @@ int main(int argc, char** argv) {
 	ms.verbose = vm.count("verbose") > 0;
 
     if (vm.count("teleportation")) {
-        ms.teleportation_qubits = std::min((arch.getNqubits() - qc.getNqubits()) & ~1u, 8u);
-        ms.teleportation_seed = vm["teleportation"].as<unsigned long long int>();
-        ms.teleportation_fake = vm.count("teleportation_fake") > 0;
+        ms.teleportationQubits = std::min((arch.getNqubits() - qc.getNqubits()) & ~1u, 8u);
+        ms.teleportationSeed = vm["teleportation"].as<unsigned long long int>();
+        ms.teleportationFake = vm.count("teleportationFake") > 0;
     }
 
     mapper.map(ms);
diff --git a/include/Architecture.hpp b/include/Architecture.hpp
index 6bcb7af33..e763923e3 100644
--- a/include/Architecture.hpp
+++ b/include/Architecture.hpp
@@ -54,7 +54,7 @@ class Architecture {
 
 public:
 
-	struct CalibrationData {
+    struct CalibrationData {
 		unsigned short qubit = 0;
 		double t1 = 0.0; // [ms]
 		double t2 = 0.0; // [ms]
@@ -105,6 +105,9 @@ class Architecture {
 	CouplingMap& getCurrentTeleportations() {
 		return current_teleportations;
 	}
+    std::vector<std::pair<short, short>>& getTeleportationQubits() {
+        return teleportationQubits;
+    }
 
 	const Matrix& getDistanceTable() const {
 		return distanceTable;
@@ -175,6 +178,7 @@ class Architecture {
 	CouplingMap current_teleportations = {};
 	bool isBidirectional = true;
 	Matrix distanceTable = {};
+    std::vector<std::pair<short, short>> teleportationQubits{};
 
 	std::vector<CalibrationData> calibrationData = {};
 	Matrix fidelityTable = {};
diff --git a/include/MappingResults.hpp b/include/MappingResults.hpp
index 2776bfc19..596770873 100644
--- a/include/MappingResults.hpp
+++ b/include/MappingResults.hpp
@@ -97,7 +97,7 @@ struct MappingResults {
 		out << "\t\t\"singlequbitgates\": " << input_singlequbitgates << ",\n";
 		out << "\t\t\"cnots\": " << input_cnots << ",\n";
 		out << "\t\t\"layers\": " << input_layers << ",\n";
-		out << "\t\t\"teleportation_qubits\": " << input_teleportation_qubits << "\n";
+		out << "\t\t\"teleportationQubits\": " << input_teleportation_qubits << "\n";
 		out << "\t},\n";
 		out << "\t\"mapped_circuit\": {\n";
 		out << "\t\t\"name\": \"" << output_name << "\",\n";
@@ -107,7 +107,7 @@ struct MappingResults {
 		out << "\t\t\"cnots\": " << output_cnots << ",\n";
 		out << "\t\t\"swaps\": " << output_swaps << ",\n";
 		out << "\t\t\"teleportations\": " << output_teleportations << ",\n";
-		out << "\t\t\"teleportation_qubits\": " << output_teleportation_qubits << ",\n";
+		out << "\t\t\"teleportationQubits\": " << output_teleportation_qubits << ",\n";
 		out << "\t\t\"teleportation_fake\": " << output_teleportation_fake << ",\n";
 		out << "\t\t\"direction_reverse\": " << output_direction_reverse << "\n";
 		out << "\t}";
@@ -156,7 +156,7 @@ struct MappingResults {
 		mapped_circuit["cnots"] = output_cnots;
 		mapped_circuit["swaps"] = output_swaps;
         mapped_circuit["teleportations"] = output_teleportations;
-        mapped_circuit["teleportation_qubits"] = output_teleportation_qubits;
+        mapped_circuit["teleportationQubits"] = output_teleportation_qubits;
         mapped_circuit["teleportation_fake"] = output_teleportation_fake;
 		mapped_circuit["direction_reverse"] = output_direction_reverse;
 
diff --git a/include/MappingSettings.hpp b/include/MappingSettings.hpp
index 374782586..9d8231342 100644
--- a/include/MappingSettings.hpp
+++ b/include/MappingSettings.hpp
@@ -78,9 +78,9 @@ struct MappingSettings {
 
 	bool lookahead = true;
 	int nrLookaheads = 15;
-    int teleportation_qubits = 0;
-    unsigned long long teleportation_seed = 0;
-    bool teleportation_fake = false;
+    int teleportationQubits = 0;
+    unsigned long long teleportationSeed = 0;
+    bool teleportationFake = false;
 	double firstLookaheadFactor = 0.75;
 	double lookaheadFactor = 0.5;
 
diff --git a/include/heuristic/HeuristicMapper.hpp b/include/heuristic/HeuristicMapper.hpp
index 98e70078a..4729a472a 100644
--- a/include/heuristic/HeuristicMapper.hpp
+++ b/include/heuristic/HeuristicMapper.hpp
@@ -49,38 +49,61 @@ class HeuristicMapper: public Mapper {
 
             if(arch.getCouplingMap().find(swap) != arch.getCouplingMap().end() || arch.getCouplingMap().find(Edge {swap.second, swap.first}) != arch.getCouplingMap().end()) {
                 swaps.back().emplace_back(swap.first, swap.second, qc::SWAP);
-                //std::clog << "SWAP " << swap.first << " <--> " << swap.second << "\n";
             } else {
-                unsigned short middle_anc = std::numeric_limits<decltype(middle_anc)>::max();
-                for(const auto& t : arch.getCurrentTeleportations()) {
-                    if (t.first == swap.first || t.first == swap.second) {
-                        middle_anc = t.second;
-                        break;
-                    } else if (t.second == swap.first || t.second == swap.second) {
-                        middle_anc = t.first;
-                        break;
-                    }
-                }
+                throw QMAPException("Something wrong in applySWAP.");
+            }
+        }
+
+        void applyTeleportation(const Edge& swap, Architecture& arch) {
+            short q1 = qubits.at(swap.first);
+            short q2 = qubits.at(swap.second);
+
+            qubits.at(swap.first) = q2;
+            qubits.at(swap.second) = q1;
+
+            if (q1 != -1) {
+                locations.at(q1) = swap.second;
+            }
+            if (q2 != -1) {
+                locations.at(q2) = swap.first;
+            }
 
-                if (middle_anc == std::numeric_limits<decltype(middle_anc)>::max()) {
-                    throw QMAPException("Teleportation between seemingly wrong qubits: " + std::to_string(swap.first) + " <--> " + std::to_string(swap.second));
-                }
 
-                unsigned short source = std::numeric_limits<decltype(source)>::max();
-                unsigned short target = std::numeric_limits<decltype(target)>::max();
-                if(arch.getCouplingMap().find({swap.first, middle_anc}) != arch.getCouplingMap().end()
-                    || arch.getCouplingMap().find({middle_anc, swap.first}) != arch.getCouplingMap().end()) {
-                    source = swap.first;
-                    target = swap.second;
-                } else {
-                    source = swap.second;
-                    target = swap.first;
+            unsigned short middle_anc = std::numeric_limits<decltype(middle_anc)>::max();
+            for(const auto& qpair : arch.getTeleportationQubits()) {
+                if (swap.first == qpair.first) {
+                    middle_anc = qpair.second;
+                } else if (swap.first == qpair.second) {
+                    middle_anc = qpair.first;
+                } else if (swap.second == qpair.first) {
+                    middle_anc = qpair.second;
+                } else if (swap.second == qpair.second) {
+                    middle_anc = qpair.first;
                 }
+            }
 
-                swaps.back().emplace_back(source, middle_anc, target, qc::Teleportation);
-                //std::clog << "TELE " << source << " -(" << middle_anc << ")-> " << target << "\n";
+            if (middle_anc == std::numeric_limits<decltype(middle_anc)>::max()) {
+                throw QMAPException("Teleportation between seemingly wrong qubits: " + std::to_string(swap.first) + " <--> " + std::to_string(swap.second));
             }
-		}
+
+            unsigned short source = std::numeric_limits<decltype(source)>::max();
+            unsigned short target = std::numeric_limits<decltype(target)>::max();
+            if(arch.getCouplingMap().find({swap.first, middle_anc}) != arch.getCouplingMap().end()
+               || arch.getCouplingMap().find({middle_anc, swap.first}) != arch.getCouplingMap().end()) {
+                source = swap.first;
+                target = swap.second;
+            } else {
+                source = swap.second;
+                target = swap.first;
+            }
+
+            if (source == middle_anc || target == middle_anc) {
+                std::clog << "FAIL: TELE " << source << " -(" << middle_anc << ")-> " << target << "\n";
+                throw QMAPException("Overlap between source/target and middle ancillary in teleportation.");
+            }
+
+            swaps.back().emplace_back(source, target, middle_anc, qc::Teleportation);
+        }
 
 		void updateHeuristicCost(const Architecture& arch, const Gate& gate, bool admissibleHeuristic) {
 			auto cost = arch.distance(locations.at(gate.control), locations.at(gate.target));
diff --git a/jkq/qmap/bindings.cpp b/jkq/qmap/bindings.cpp
index bbd3932fa..5a4413b9d 100644
--- a/jkq/qmap/bindings.cpp
+++ b/jkq/qmap/bindings.cpp
@@ -70,9 +70,9 @@ nl::json map(const py::object& circ, const py::object& arch, const nl::json& jso
 	}
 
     if (jsonConfig.contains("use_teleportation")) {
-        ms.teleportation_qubits = std::min((architecture.getNqubits() - qc.getNqubits()) & ~1u, 8u);
-        ms.teleportation_seed = jsonConfig["teleportation_seed"].get<unsigned long long>();
-        ms.teleportation_fake = jsonConfig["teleportation_fake"].get<bool>();
+        ms.teleportationQubits = std::min((architecture.getNqubits() - qc.getNqubits()) & ~1u, 8u);
+        ms.teleportationSeed = jsonConfig["teleportationSeed"].get<unsigned long long>();
+        ms.teleportationFake = jsonConfig["teleportation_fake"].get<bool>();
     }
 
 
diff --git a/src/Mapper.cpp b/src/Mapper.cpp
index d58f59291..987848857 100644
--- a/src/Mapper.cpp
+++ b/src/Mapper.cpp
@@ -14,7 +14,7 @@ void Mapper::initResults() {
 	results.output_qubits = architecture.getNqubits();
 	results.layeringStrategy = settings.layeringStrategy;
 	results.initialLayoutStrategy = settings.initialLayoutStrategy;
-	qcMapped.addQubitRegister(architecture.getNqubits());
+	qcMapped.addQubitRegister(architecture.getNqubits()+settings.teleportationQubits);
 }
 
 Mapper::Mapper(qc::QuantumComputation& quantumComputation, Architecture& arch): qc(quantumComputation), architecture(arch) {
diff --git a/src/heuristic/HeuristicMapper.cpp b/src/heuristic/HeuristicMapper.cpp
index 70f8a6541..52ed93750 100644
--- a/src/heuristic/HeuristicMapper.cpp
+++ b/src/heuristic/HeuristicMapper.cpp
@@ -19,7 +19,7 @@ void HeuristicMapper::map(const MappingSettings& ms) {
 
 	createLayers();
 	if (ms.verbose) {
-        std::clog << "Teleportation qubits: " << ms.teleportation_qubits << "\n";
+        std::clog << "Teleportation qubits: " << ms.teleportationQubits << "\n";
 		printLayering(std::clog);
 	}
 
@@ -182,31 +182,31 @@ void HeuristicMapper::initResults() {
 	Mapper::initResults();
 	results.method = Method::Heuristic;
 
-	results.seed = settings.teleportation_seed;
-	results.input_teleportation_qubits = settings.teleportation_qubits;
-	results.output_teleportation_qubits = settings.teleportation_qubits;
-	results.output_teleportation_fake = settings.teleportation_fake;
+	results.seed = settings.teleportationSeed;
+	results.input_teleportation_qubits = settings.teleportationQubits;
+	results.output_teleportation_qubits = settings.teleportationQubits;
+	results.output_teleportation_fake = settings.teleportationFake;
 }
 
 void HeuristicMapper::createInitialMapping() {
 	if (layers.empty())
 		return;
 
-	if (settings.teleportation_qubits > 0) {
+	if (settings.teleportationQubits > 0) {
         std::mt19937_64 mt;
-        if (settings.teleportation_seed == 0) {
+        if (settings.teleportationSeed == 0) {
             std::array<std::mt19937_64::result_type, std::mt19937_64::state_size> random_data{};
             std::random_device rd;
             std::generate(std::begin(random_data), std::end(random_data), [&rd]() { return rd(); });
             std::seed_seq seeds(std::begin(random_data), std::end(random_data));
             mt.seed(seeds);
         } else {
-            mt.seed(settings.teleportation_seed);
+            mt.seed(settings.teleportationSeed);
         }
 
         std::uniform_int_distribution<> dis(0, architecture.getNqubits() - 1);
 
-        for (int i = 0; i < settings.teleportation_qubits; i += 2) {
+        for (int i = 0; i < settings.teleportationQubits; i += 2) {
             Edge e;
             do {
                 auto it = std::begin(architecture.getCouplingMap());
@@ -217,12 +217,11 @@ void HeuristicMapper::createInitialMapping() {
             locations[qc.getNqubits() + i + 1] = e.second;
             qubits[e.first] = qc.getNqubits() + i;
             qubits[e.second] = qc.getNqubits() + i + 1;
-            //std::clog << "initial teleportation pair: " << e.first << ", " << e.second << "\n";
         }
 
-        if (settings.teleportation_fake) {
-            settings.teleportation_qubits = 0;
-            results.output_teleportation_qubits = settings.teleportation_qubits;
+        if (settings.teleportationFake) {
+            settings.teleportationQubits = 0;
+            results.output_teleportation_qubits = settings.teleportationQubits;
         }
     }
 
@@ -300,21 +299,34 @@ void HeuristicMapper::mapUnmappedGates(long layer, HeuristicMapper::Node& node,
 					possibleEdges.emplace(edge);
 				}
 			}
+            std::pair<unsigned short, unsigned short> chosenEdge;
 
 			if (possibleEdges.empty()) {
-				throw QMAPException("Could not map logical qubits to physical qubits. No suitable edge found.");
+                double bestScore = std::numeric_limits<int>::max();
+
+                for(int i=0; i < architecture.getNqubits(); i++) {
+                    for (int j = i + 1; j < architecture.getNqubits(); j++) {
+                        if (qubits.at(i) == DEFAULT_POSITION && qubits.at(j) == DEFAULT_POSITION) {
+                            double dist = architecture.distance(i, j);
+                            if (dist < bestScore) {
+                                bestScore = dist;
+                                chosenEdge = std::make_pair(i, j);
+                            }
+                        }
+                    }
+                }
+			} else {
+                chosenEdge = *possibleEdges.begin();
 			}
-
 			// TODO: Consider fidelity here if available. The best available edge should be chosen
-			auto& chosenEdge = *possibleEdges.begin();
-			locations.at(gate.control) = chosenEdge.first;
-			locations.at(gate.target) = chosenEdge.second;
-			qubits.at(chosenEdge.first) = gate.control;
-			qubits.at(chosenEdge.second) = gate.target;
-			qc::QuantumComputation::findAndSWAP(gate.control, chosenEdge.first, qcMapped.initialLayout);
-			qc::QuantumComputation::findAndSWAP(gate.target, chosenEdge.second, qcMapped.initialLayout);
-			qc::QuantumComputation::findAndSWAP(gate.control, chosenEdge.first, qcMapped.outputPermutation);
-			qc::QuantumComputation::findAndSWAP(gate.target, chosenEdge.second, qcMapped.outputPermutation);
+            locations.at(gate.control) = chosenEdge.first;
+            locations.at(gate.target) = chosenEdge.second;
+            qubits.at(chosenEdge.first) = gate.control;
+            qubits.at(chosenEdge.second) = gate.target;
+            qc::QuantumComputation::findAndSWAP(gate.control, chosenEdge.first, qcMapped.initialLayout);
+            qc::QuantumComputation::findAndSWAP(gate.target, chosenEdge.second, qcMapped.initialLayout);
+            qc::QuantumComputation::findAndSWAP(gate.control, chosenEdge.first, qcMapped.outputPermutation);
+            qc::QuantumComputation::findAndSWAP(gate.target, chosenEdge.second, qcMapped.outputPermutation);
 		} else if (controlLocation == DEFAULT_POSITION) {
 			mapToMinDistance(gate.target, gate.control);
 		} else if (targetLocation == DEFAULT_POSITION) {
@@ -382,7 +394,9 @@ void HeuristicMapper::expandNode(const std::vector<unsigned short>& consideredQu
 
     std::set<Edge> perms = architecture.getCouplingMap();
     architecture.getCurrentTeleportations().clear();
-    for(int i = 0; i < settings.teleportation_qubits; i+=2) {
+    architecture.getTeleportationQubits().clear();
+    for(int i = 0; i < settings.teleportationQubits; i+=2) {
+        architecture.getTeleportationQubits().emplace_back(node.locations[qc.getNqubits() + i], node.locations[qc.getNqubits() + i + 1]);
         Edge e;
         for(auto const& g : architecture.getCouplingMap()) {
             if(g.first == node.locations[qc.getNqubits() + i] && g.second != node.locations[qc.getNqubits() + i + 1]) {
@@ -434,14 +448,22 @@ void HeuristicMapper::expand_node_add_one_swap(const Edge &swap, Node& node, lon
 
 	Node new_node = Node(node.qubits, node.locations, node.swaps);
 	new_node.nswaps++;
-	if (architecture.bidirectional()) {
-        new_node.costFixed = node.costFixed + COST_BIDIRECTIONAL_SWAP;
-	} else {
-        new_node.costFixed = node.costFixed + COST_UNIDIRECTIONAL_SWAP;
-	}
 
 	new_node.swaps.emplace_back();
-	new_node.applySWAP(swap, architecture);
+	if(architecture.getCouplingMap().find(swap) != architecture.getCouplingMap().end() ||
+	    architecture.getCouplingMap().find(Edge {swap.second, swap.first}) != architecture.getCouplingMap().end()) {
+
+	    if (architecture.bidirectional()) {
+            new_node.costFixed = node.costFixed + COST_BIDIRECTIONAL_SWAP;
+        } else {
+            new_node.costFixed = node.costFixed + COST_UNIDIRECTIONAL_SWAP;
+        }
+
+        new_node.applySWAP(swap, architecture);
+    } else {
+        new_node.costFixed = node.costFixed + COST_TELEPORTATION;
+	    new_node.applyTeleportation(swap, architecture);
+	}
     new_node.costTotal = new_node.costFixed;
     new_node.done = true;
 


Test patch:
diff --git a/test/test_heuristic.cpp b/test/test_heuristic.cpp
index 62d518cb7..f01554968 100644
--- a/test/test_heuristic.cpp
+++ b/test/test_heuristic.cpp
@@ -161,12 +161,43 @@ TEST_P(HeuristicTest20Q, Dynamic) {
     SUCCEED() << "Mapping successful";
 }
 
-/*TEST_P(HeuristicTest20Q, Teleportation) {
+
+
+class HeuristicTest20QTeleport: public testing::TestWithParam<std::tuple<unsigned long long, std::string>> {
+protected:
+
+    std::string test_example_dir = "../../examples/";
+    std::string test_architecture_dir = "../../extern/architectures/";
+
+    qc::QuantumComputation qc{};
+    Architecture arch{};
+    HeuristicMapper tokyo_mapper{qc, arch};
+
+    void SetUp() override {
+        qc.import(test_example_dir + std::get<1>(GetParam()) + ".qasm");
+        arch.loadCouplingMap(test_architecture_dir + "ibmq_tokyo_20qubit.arch");
+    }
+};
+
+INSTANTIATE_TEST_SUITE_P(HeuristicTeleport, HeuristicTest20QTeleport,
+                         testing::Combine(
+                                testing::Values(1, 2, 3, 1337, 1338, 3147),
+                                testing::Values("ising_model_10", "rd73_140", "cnt3-5_179",  "qft_16", "z4_268")
+                         ),
+                         [](const testing::TestParamInfo<HeuristicTest20QTeleport::ParamType>& info) {
+                             std::string name = std::get<1>(info.param);
+                             std::replace( name.begin(), name.end(), '-', '_');
+                             std::stringstream ss{};
+                             ss << name << "_seed" << std::get<0>(info.param);
+                             return ss.str();});
+
+TEST_P(HeuristicTest20QTeleport, Teleportation) {
     MappingSettings settings{};
     settings.initialLayoutStrategy = InitialLayoutStrategy::Dynamic;
-    settings.teleportation_qubits = std::min((arch.getNqubits() - qc.getNqubits()) & ~1u, 8u);
+    settings.teleportationQubits = std::min((arch.getNqubits() - qc.getNqubits()) & ~1u, 8u);
+    settings.teleportationSeed = std::get<0>(GetParam());
     tokyo_mapper.map(settings);
-    tokyo_mapper.dumpResult(GetParam() + "_heuristic_tokyo_teleport.qasm");
+    tokyo_mapper.dumpResult(std::get<1>(GetParam()) + "_heuristic_tokyo_teleport.qasm");
     tokyo_mapper.printResult(std::cout, true);
     SUCCEED() << "Mapping successful";
-}*/
+}
\ No newline at end of file