In the first implementation of ApproxTSFinder, we handle the colored version of the problem, where we first execute the hungarian algorithm. However, the way we were using it didn't make it necessary. So, a faster version of it was created: SimplifiedApproxTSFinder. We basically ignore the unmapped qubits, and only care about the mapped ones (we remove the step where we had to minimum match the unmapped qubits from the source mapping into the closest unmapped ones in the target mapping).
Also, we optimized ApproxTSFinder by preprocessing the graph when it is set. We calculate a list of good vertices for every two pair of vertices. We do it in O(|Q||E|) time.
ysiraichi
commented
6 years ago
In the first implementation of
ApproxTSFinder, we handle the colored version of the problem, where we first execute the hungarian algorithm. However, the way we were using it didn't make it necessary. So, a faster version of it was created:SimplifiedApproxTSFinder. We basically ignore the unmapped qubits, and only care about the mapped ones (we remove the step where we had to minimum match the unmapped qubits from the source mapping into the closest unmapped ones in the target mapping).Also, we optimized
ApproxTSFinderby preprocessing the graph when it is set. We calculate a list of good vertices for every two pair of vertices. We do it in O(|Q||E|) time.