Lookahead swap mapper has excessive runtime for larger width circuits

[nonhermitian]

Information

• Qiskit Terra version: master
• Python version:
• Operating system:

What is the current behavior?

Using the lookahead swap mapper on a 20q QV circuit does not complete on my machine within at least 30min. The others take 2-4 seconds.

Steps to reproduce the problem

Try to use routing_method='lookahead' on a 20q QV circuit.

What is the expected behavior?

Suggested solutions

[nonhermitian]

I gave up waiting, but here is timings at smaller widths:

[mrvee-qC]

Update for Santa:elf:- QGoGP

ℹ️ Could OP test out their code with the new qiskit-experiments module to see if the behavior still holds for the QuantumVolume class in ignis is now deprecated? Also an MWE would help a lot for the scenario OP is testing. I transpiled it for FakeManhattan for QV = 4 and confirm that setting routing_method = lookahead adds a significant delay

routing_method = None -> Walltime 376ms
routing_method = "basic" -> Walltime 275ms
routing_method = "sabre" -> Walltime 265ms
routing_method = "stochastic" -> Walltime 394ms
routing_method = "lookahead" -> Walltime 28500ms

The code I tried -

from qiskit_experiments.library import QuantumVolume
from qiskit import Aer
from qiskit.providers.aer import AerSimulator

# For simulation
from qiskit.test.mock import FakeManhattan
backend = AerSimulator.from_backend(FakeManhattan())

%%time
qv_exp = QuantumVolume(4, seed=13) # Random seed fixed for reproducablity
qv_exp.set_transpile_options(routing_method='lookahead',optimization_level=3)
qv_exp.set_experiment_options(trials=1)

experiment = qv_exp.run(backend)

Will update comment/add more comments if cause is found/fixed!

Python version 3.9.7
qiskit-terra version: 0.19.1

[jakelishman]

I'm going to close this as stale now. The LookaheadSwap algorithm as described in the transpiler pass is inherently ~quartic in width (which ups to $n^8$ for volumetric circuits) because of its scoring requirements - the alternative is to pivot it to effectively just be Sabre with some lookahead of its own. That's a direction we are interested in looking at for Sabre, but not for a mostly unused transpiler pass that generally has worse performance characteristics than the full Sabre.

(Technically the squaring of the complexity for volumetric circuits can be removed by using a similar relative-scoring approach as we took for Sabre in #9012, but the general gist of what I said remains.)