LayoutTransformation mapping qubits incorrectly between dags

[qci-amos]

I'm not sure I understand what's happening, but I use LayoutTransformation and I recently hit a bug where LayoutTransformation isn't producing the desired output. It's actually non-deterministic, sometimes it works, other times the exact same input does not (if I set a seed, then it becomes deterministic).

I've found that if I replace this line: https://github.com/Qiskit/qiskit-terra/blob/bee5e7f62db400a4c2f6924064413371be0048eb/qiskit/transpiler/passes/routing/layout_transformation.py#L112

with:

        qubits = [dag.qubits[i[0]] for i in perm_circ.inputmap.items()]

(i.e., remove the sorted) then passed all my tests.

I'm not entirely clear why, but one origin seems to be that the order that the qubits are added to the PermutationCircuit is non-deterministic: https://github.com/Qiskit/qiskit-terra/blob/bee5e7f62db400a4c2f6924064413371be0048eb/qiskit/transpiler/passes/routing/algorithms/util.py#L85-L91

I'm not an expert in qiskit dag circuits, but it looks like the argument to compose needs to be sorted in the qubit ordering in the permutation circuit, not the dag passed to run. My hack works because the inputmap dict has, deterministically, the correct sort.

My issue could also be fixed by sorting the nodes object before this line: https://github.com/Qiskit/qiskit-terra/blob/bee5e7f62db400a4c2f6924064413371be0048eb/qiskit/transpiler/passes/routing/algorithms/util.py#L89

The sorted was added in #5281 by @1ucian0

[jakelishman]

Please can you provide a reproducer of your bug? The extra information here is super nice, but I don't actually understand what problem you're having. The normal "bug report" template should have prompted for this, and for version information.

[qci-amos]

$ git diff .
diff --git a/test/python/transpiler/test_layout_transformation.py b/test/python/transpiler/test_layout_transformation.py
index 5fe2fe315..903bcf194 100644
--- a/test/python/transpiler/test_layout_transformation.py
+++ b/test/python/transpiler/test_layout_transformation.py
@@ -15,7 +15,7 @@
 import unittest

 from qiskit import QuantumRegister, QuantumCircuit
-from qiskit.converters import circuit_to_dag
+from qiskit.converters import circuit_to_dag, dag_to_circuit
 from qiskit.test import QiskitTestCase
 from qiskit.transpiler import CouplingMap, Layout
 from qiskit.transpiler.passes import LayoutTransformation
@@ -45,6 +45,25 @@ class TestLayoutTransformation(QiskitTestCase):

         self.assertEqual(circuit_to_dag(expected), output_dag)

+    def test_qubit_ordering(self):
+        v = QuantumRegister(9, "v")  # virtual qubits
+        coupling = CouplingMap.from_grid(3,3)
+        from_layout = Layout({v[0]: 0, v[4]: 1, v[2]: 2, v[3]: 3, v[1]: 4, v[8]: 5, v[6]: 6, v[7]: 7, v[5]: 8})
+        to_layout = Layout({v[i]: i for i in range(9)})
+        ltpass = LayoutTransformation(
+            coupling_map=coupling, from_layout=from_layout, to_layout=to_layout, seed=42
+        )
+        qc = QuantumCircuit(9)  # input (empty) physical circuit
+        dag = circuit_to_dag(qc)
+        output_dag = ltpass.run(dag)
+        print(dag_to_circuit(output_dag))
+
+        expected = QuantumCircuit(9)
+        expected.swap(1,4)
+        expected.swap(5,8)
+        self.assertEqual(circuit_to_dag(expected), output_dag)
+
+
     def test_four_qubit(self):
         """Test if the permutation {0->3,1->0,2->1,3->2} is implemented correctly."""
         v = QuantumRegister(4, "v")  # virtual qubits

It prints this (incorrect) dag:

q_0: ──────

q_1: ────X─
         │
q_2: ────┼─
         │
q_3: ────┼─
         │
q_4: ─X──┼─
      │  │
q_5: ─X──┼─
         │
q_6: ────┼─
         │
q_7: ────┼─
         │
q_8: ────X─

In order to find this one which fails, I did a combinatorial search. I didn't find a smaller from_grid which exhibits the problem.

This particular test was run on 0.18.3, but I believe I checked the latest main too.

[qci-amos]

Oh, and that test passes as written if I remove the sorted from LayoutTransformation as described above.

[qci-amos]

The normal "bug report" template should have prompted for this

This issue was created by selecting a line in the code on GH and then clicking "Reference in new issue" in the context menu. I just confirmed, no issue template is presented to the reporter!

[jakelishman]

Perfect, thanks. That's enough for us to go on, though I'm not sure if we'll have many resources to put into it internally - I wasn't even aware of this pass's existence, and it looks like it was added in #3762 with the intent to use it in #2860, which simply never merged. Nothing else in the library uses it, and there's only been one nontrivial change to it since it merged two years ago (the commit in #5281 you mentioned above).

If you come across for a fix for it, please let us know and we'd be happy to accept a PR (and with the new test case - we're a little lacking in tests for it at the moment!).

---

no issue template is presented to the reporter!

Ah, that's how they get us! A shame, really, though I guess GitHub didn't want to deal with the headache of deciding which field in the report form it should fill that entry into.