SabreSwap can reorder operations that depend on the same classical bit

[jakelishman]

Environment

• Qiskit Terra version: main @ ef997f9
• Python version: any
• Operating system: any

What is happening?

SabreSwap can re-order measurement operations (and probably classically conditioned gates) that write to the same classical bits. This affects optimisation level 3 by default, since it uses sabre to route if nothing else is provided.

I am 95% sure this is the cause of the failures we're seeing in the randomised test suite currently.

Expand for logs of recent failed randomised run

Hypothesis failure at commit 618e0ea, in file `test/randomized/test_transpile_equivalence.py`

Falsifying example:
state = QCircuitMachine()
state.qasm()
(v1,) = state.add_creg(n=1)
state.qasm()
v2, v3, v4 = state.add_qreg(n=3)
state.qasm()
state.add_3q_gate(gate=qiskit.circuit.library.standard_gates.x.CCXGate, qargs=[v4, v3, v2])
state.qasm()
state.add_1q1c_gate(carg=v1, gate=qiskit.circuit.measure.Measure, qarg=v3)
state.qasm()
state.add_1q2p_gate(gate=qiskit.circuit.library.standard_gates.u2.U2Gate, params=[0.0, 0.0], qarg=v4)
state.qasm()
state.add_1q1c_gate(carg=v1, gate=qiskit.circuit.measure.Measure, qarg=v4)
state.qasm()
Evaluating circuit at level 3 on fake_ourense:
OPENQASM 2.0;
include "qelib1.inc";
qreg q35069[3];
creg c1656[1];
ccx q35069[2],q35069[1],q35069[0];
measure q35069[1] -> c1656[0];
u2(0,0) q35069[2];
measure q35069[2] -> c1656[0];

state.equivalent_transpile(backend=<FakeOurense('fake_ourense')>, opt_level=3)
state.teardown()

You can reproduce this example by temporarily adding @reproduce_failure('6.43.2', b'AXicY2Bk5GFgYGDkZWBiYARCIBPIYmAE8thAbEYOBkwAkgKSrEBlzAALaABL') as a decorator on your test case

How can we reproduce the issue?

Given a circuit:

import qiskit

qc = qiskit.QuantumCircuit(3, 1)
qc.ccx(2, 1, 0)
qc.h(0)
qc.measure(0, 0)
qc.measure(1, 0)

which has a drawing

     ┌───┐┌───┐┌─┐
q_0: ┤ X ├┤ H ├┤M├───
     └─┬─┘└───┘└╥┘┌─┐
q_1: ──■────────╫─┤M├
       │        ║ └╥┘
q_2: ──■────────╫──╫─
                ║  ║
c: 1/═══════════╩══╩═
                0  0

Clearly the output of the circuit should always be 0, because qubit 1 is never altered, and is measured second.

If we transpile it with a special coupling map that essentially only has one valid routing for the default decomposition of ccx, the orders of the measurements get flipped, which Aer confirms:

transpiled = qiskit.transpile(qc, coupling_map=[[(0, 2), (2, 0), (1, 2), (2, 1)]], routing_method="sabre")
backend = qiskit.Aer.get_backend("aer_simulator")
print(backend.run(qc, shots=1024).result().get_counts())
print(backend.run(transpiled, shots=1024).result().get_counts())

This produces, for example:

{'0': 1024}
{'1': 503, '0': 521}

but the second dictionary should be the same as the first.

(It's too long to draw transpiled here, but if you do it locally, you can see the measurements are swapped.)

What should happen?

Sabre should take into account the topological ordering of measurements (and other clbits). In the above examples, the counts should both be {'0': 1024} (which they are for any other routing method).

Any suggestions?

In both SabreSwap._successors and ._is_resolved, only the quantum bits are accounted for. My very very rough intuition for what's going on makes it feel like it should account for all successors, not just qubits.

[mtreinish]

I think you're correct here. The other routing passes work over the dag in topological order directly (well typically they either use dag.layers() or dag.serial_layers() which the first step is to do a topological sort and iterate over that) which will respect classical wire edges in the dag. Since sabre does the layer generation as it iterates over the dag we should be looking at successor nodes over both quantum and classical wires to ensure we get the correct ordering.