LookaheadSwap mapper hangs in some cases

[kdk]

The LookaheadSwap mapper will, for some input circuits and coupling maps, loop infinitely while attempting to build a mapping.

The lookahead algorithm can end up in an effective local minimum where 1) no depth-1 swaps lead to an improvement in score over the current layout, and 2) the swaps required to advance the circuit fall outside of the search width pruning (maybe depending on the order returned by coupling.get_edges()).

The LookaheadSwap has no priority queue or backtracking mechanism beyond the size of search depth, so it will continue to examine the first set of swaps indefinitely. An iteration limit would be an easy way to likely detect and alert users to these cases. Alternately, the algorithm could choose to not prune in cases where there is no clear ranking of swaps, or randomly select a subset to consider further.

e.g.

>>> import qiskit as qk
>>> from qiskit.test.mock import FakeMelbourne
>>> from qiskit.transpiler import CouplingMap
>>> qr = qk.QuantumRegister(14, 'q')
>>> qc = qk.QuantumCircuit(qr)
>>> qc.cx(qr[0], qr[13])
>>> qc.cx(qr[1], qr[13])
>>> qc.cx(qr[1], qr[0])
>>> qc.cx(qr[13], qr[1])
>>> qc.cx(qr[6], qr[7])
>>> qc.cx(qr[8], qr[7])
>>> qc.cx(qr[8], qr[6])
>>> qc.cx(qr[7], qr[8])
>>> qc.cx(qr[0], qr[13])
>>> qc.cx(qr[1], qr[0])
>>> qc.cx(qr[13], qr[1])
>>> qc.cx(qr[0], qr[1])
>>> dag = qk.converters.circuit_to_dag(qc)
>>> cm = CouplingMap(FakeMelbourne().configuration().coupling_map)
>>> qk.transpiler.passes.LookaheadSwap(cm).run(dag)
...
KeyboardInterrupt
>>> qk.transpiler.passes.BasicSwap(cm).run(dag)
<qiskit.dagcircuit.dagcircuit.DAGCircuit object at 0x1220bc668>
>>> qk.transpiler.passes.LegacySwap(cm).run(dag)
<qiskit.dagcircuit.dagcircuit.DAGCircuit object at 0x1220cd2b0>
>>> qk.transpiler.passes.StochasticSwap(cm).run(dag)
<qiskit.dagcircuit.dagcircuit.DAGCircuit object at 0x1220c0ba8>

[1ucian0]

priority: medium because LookaheadSwap is not in any of the preset passmanagers...