Incorrect Optimization of Swap and Measure Instructions

[p51lee]

Environment

• Qiskit Terra version: 0.45.0
• Python version: 3.10.9
• Operating system: MacOS 13.5 Ventura

What is happening?

Hello, The qiskit.transpile function at optimization_level=3 incorrectly optimizes circuits involving swap and measure instructions. This leads to incorrect possible outcomes when the circuit is executed.

How can we reproduce the issue?

The issue can be replicated using the following Python code:

import qiskit
from qiskit import QuantumCircuit, transpile, Aer

bug_qasm = """OPENQASM 2.0;
include "qelib1.inc";
qreg q[3];
creg c[3];
z q[0];
sx q[0];
swap q[0],q[1];
measure q[1] -> c[2];
measure q -> c;
"""

simulator = Aer.get_backend("aer_simulator")
circ = QuantumCircuit.from_qasm_str(bug_qasm)
original = transpile(circ, backend=simulator, optimization_level=0)
optimized = transpile(circ, backend=simulator, optimization_level=3)

orig_count = simulator.run(original, shots=100000).result().get_counts()
trans_count = simulator.run(optimized, shots=100000).result().get_counts()

keys = set(orig_count.keys()).union(trans_count.keys())

for k in sorted(list(keys)):
    print(f"{k}: {orig_count.get(k, 0):>5} {trans_count.get(k, 0):>5}")

The possible outcomes differ between the original and optimized circuits:

000: 50006 49660
010: 49994     0
100:     0 50340

What should happen?

The optimized circuit should yield only 000 and 010 outcomes, consistent with the original circuit.

Any suggestions?

The potential source of the bug could be in qiskit/transpiler/passes/optimization/optimize_swap_before_measure

[border-b]

I would like to work on this!

[jakelishman]

The bug is in OptimizeSwapBeforeMeasure, which uses DAGCircuit.successors (immediate successors) as opposed to DAGCircuit.descendants (all nodes that are topologically after the given). It should hopefully be an easy fix there, though it'd be good to add a couple more tests, such as when there's multiple swaps before several multiply-measured qubits, just to be sure.

A more minimal reproducer showing the bug:

from qiskit import QuantumCircuit
from qiskit.transpiler.passes import OptimizeSwapBeforeMeasure
pass_ = OptimizeSwapBeforeMeasure()
qc = QuantumCircuit(2, 1)
qc.swap(0, 1)
qc.measure(0, 0)
qc.measure(0, 0)
print(qc.draw())
print(pass_(qc).draw())

This prints

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

but the second circuit should be

q_0: ──────
     ┌─┐┌─┐
q_1: ┤M├┤M├
     └╥┘└╥┘
c: 1/═╩══╩═
      0  0

@border-b: I can assign you, thanks!

[border-b]

@jakelishman, sorry I was a bit busy with work these past couple of weeks. You're right, changing DAGCircuit.successors to DAGCircuit.descendants does seem to solve the issue. I'm gonna try to add some tests.

[mtreinish]

Fixed by: https://github.com/Qiskit/qiskit/pull/11413