Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

SabreSwap can reorder or throw away operations near conditions #8675

Closed
jakelishman opened this issue Sep 5, 2022 · 0 comments · Fixed by #8727
Closed

SabreSwap can reorder or throw away operations near conditions #8675

jakelishman opened this issue Sep 5, 2022 · 0 comments · Fixed by #8727
Assignees
Labels
bug Something isn't working Rust This PR or issue is related to Rust code in the repository
Milestone

Comments

@jakelishman
Copy link
Member

Environment

  • Qiskit Terra version: main @ a4cf148
  • Python version: 3.10
  • Operating system: macOS

What is happening?

Randomised testing turned up a case in SabreSwap (since the merge of #8388) where it appeared to throw away a measurement gate: see #2645 (comment). Tweaking the qubits and conditionals there results in different parts of the circuit being dropped.

It seems to be related to conditionals, but I'm not 100% sure.

How can we reproduce the issue?

For example,

import qiskit
from qiskit.converters import circuit_to_dag, dag_to_circuit
from qiskit.transpiler import CouplingMap
from qiskit.transpiler.passes import SabreSwap
qc = qiskit.QuantumCircuit(3, 1)
qc.cx(0, 2).c_if(0, 0)
qc.measure(1, 0)
qc.h(2).c_if(0, 0)
out = SabreSwap(CouplingMap.from_line(3)).run(circuit_to_dag(qc))
dag_to_circuit(out).draw()

gives

q_0: ────────■────────────────
           ┌─┴─┐      ┌───┐
q_1: ─X────┤ X ├──────┤ H ├───
      │    └─╥─┘      └─╥─┘
q_2: ─X──────╫──────────╫─────
        ┌────╨────┐┌────╨────┐
c: 1/═══╡ c_0=0x0 ╞╡ c_0=0x0 ╞
        └─────────┘└─────────┘

while changing the cx(0, 2) to cx(0, 1) and the h(2) to h(0) causes the circuit to be invalidly re-ordered:

                   ┌───┐
q_0: ─────■────────┤ H ├──────
        ┌─┴─┐      └─╥─┘   ┌─┐
q_1: ───┤ X ├────────╫─────┤M├
        └─╥─┘        ║     └╥┘
q_2: ─────╫──────────╫──────╫─
     ┌────╨────┐┌────╨────┐ ║
c: 1/╡ c_0=0x0 ╞╡ c_0=0x0 ╞═╩═
     └─────────┘└─────────┘ 0

(mathematically that re-ordering is technically valid, since we assume qubits start in | 0 so the clbit can ideally never be 1, but Sabre doesn't know that at this point, so it's doing something wrong.)

What should happen?

Classical wire ordering should be respected as well, even if the wires are only in conditions.

Any suggestions?

Looks like the Rust-ified version of Sabre is back to its old tricks of not correctly respecting wires in conditions, somehow or another. We fixed similar issues in #7952 and #8041, so something similar might be up again (though not exactly the same, since those added regression tests). Dropping inputs has previously meant that the wire predecessor / successor counts aren't being handled correctly.

@jakelishman jakelishman added bug Something isn't working Rust This PR or issue is related to Rust code in the repository labels Sep 5, 2022
@jakelishman jakelishman added this to the 0.22 milestone Sep 5, 2022
@mtreinish mtreinish self-assigned this Sep 12, 2022
mtreinish added a commit to mtreinish/qiskit-core that referenced this issue Sep 12, 2022

Verified

This commit was signed with the committer’s verified signature.
mtreinish Matthew Treinish
In Qiskit#8388 we moved all of the SabreSwap pass's processing into rust. To
facilitate that we had to create a rust DAG data structure to represent
the data flow graph solely in Rust to enable analyzing the DAG structure
in rust code without having to callback to python. To do this the
DAGCircuit (which has a nearly identical representation in python) would
export a list of nodes and the bits (both quantum and classical) that
they operated on. This information is then used to create the SabreDAG
used in the rust code. However, in this process an edge case was missed
with classical condtions. If a condition was specified solely as a
property of the operation and not in cargs list the SabreDAG would not
know about the classical bit dependency between any subsequent
operations involving that classical bit. This would cause incorrect
output because the ndoes would not get processed as they were in the
circuit. This commit fixes this issue by explicitly checking if there is
a condition on the operation and there are no cargs and if so adding the
carg bits to the SabreDAG directly. This fixes the incorrect
representation in SabreDAG.

Fixes Qiskit#8675
@mergify mergify bot closed this as completed in #8727 Sep 16, 2022
mergify bot added a commit that referenced this issue Sep 16, 2022

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
* Fix handling of conditions in SabreDAG creation

In #8388 we moved all of the SabreSwap pass's processing into rust. To
facilitate that we had to create a rust DAG data structure to represent
the data flow graph solely in Rust to enable analyzing the DAG structure
in rust code without having to callback to python. To do this the
DAGCircuit (which has a nearly identical representation in python) would
export a list of nodes and the bits (both quantum and classical) that
they operated on. This information is then used to create the SabreDAG
used in the rust code. However, in this process an edge case was missed
with classical condtions. If a condition was specified solely as a
property of the operation and not in cargs list the SabreDAG would not
know about the classical bit dependency between any subsequent
operations involving that classical bit. This would cause incorrect
output because the ndoes would not get processed as they were in the
circuit. This commit fixes this issue by explicitly checking if there is
a condition on the operation and there are no cargs and if so adding the
carg bits to the SabreDAG directly. This fixes the incorrect
representation in SabreDAG.

Fixes #8675

* Fix handling of instructions with condition and cargs

This commit fixes the logic for handling instructions that have both
cargs and conditions set. The previous commit fixed the behavior only if
cargs was mutually exclusive with having classical arguments. However,
the same bug this PR is fixing would persist for instructions with clbit
arguments and a condition. This fixes the behavior to correctly
represent the data dependency in SabreDAG for these cases.

* Improve efficiency of condition handling

This commit improves the efficiency of the condition handling on
SabreDAG creation that was added in the previous commit. Previously, it
was potentially expensive to loop over the list of cargs and condition
bits as for instructions with a large number of both the repeated
duplicate searches would get quite expensive. This commit fixes that by
converting the cargs data structure to be a set to prevent adding
duplicates. Since the order isn't significant for the cargs in sabre as
it's only used to represent data dependency between instructions we can
convert it to internally use a set in python and a HashSet in rust. This
also removes storing of cargs for each node in the SabreDAG as this was
never used and just wasted memory by storing the list and never using
it.

Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working Rust This PR or issue is related to Rust code in the repository
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants