Skip to content

SabreLayout does not terminate in some cases #7707

@ajavadia

Description

@ajavadia

Environment

Qiskit version: master
Python version: 3.8.8
OS: Mac OS 12.2

What is happening?

SabreSwap gets stuck in some specific cases and does not make forward progress.

How can we reproduce the issue?

here's an example that runs indefinitely for me. Note that even though I run SabreLayout, internally it is calling SabreSwap and that's where it gets stuck.

from qiskit.circuit.library import QuantumVolume
from qiskit.transpiler import PassManager, CouplingMap
from qiskit.transpiler.passes import SabreLayout

n = 30
coupling_map = CouplingMap.from_line(n)
basis_gates=['cx', 'u']
qv = QuantumVolume(n, seed=983).decompose()
pm = PassManager(SabreLayout(coupling_map, seed=1))
pm.run(qv)

What should happen?

map the circuit and terminate

Any suggestions?

I think the SabreSwap algorithm has a way to score different swap options and to make forward progress, so not sure what's going on.

Metadata

Metadata

Assignees

Labels

bugSomething isn't workinghelp wantedcommunity contributions welcome. For filters like http://github-help-wanted.com/

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions