Unreasonable time taken on optimization level 3 transpilation

[adamglos92]

if a combination of these 3 arguments is provided (backed, initial layout, optimization level 3), the transpilation process with VF2PostLayout is added to pass manager with no time limit. Because of this, especially for simple circuits the pass takes unreasonable time.

To reproduce:

from time import perf_counter

from qiskit import QuantumCircuit, transpile
from qiskit_ibm_runtime.fake_provider.fake_provider import FakeGuadalupeV2

backend = FakeGuadalupeV2()
for q in range(16):
    qc = QuantumCircuit(q)
    qc.measure_all()
    t = perf_counter()
    qc = transpile(qc, backend, optimization_level=3, initial_layout=list(range(q)))
    print(f"{perf_counter() - t} seconds for {q} qubits.")

gives

2.134571125999855 seconds for 1 qubits.
0.006853208000165978 seconds for 2 qubits.
0.034131333000004815 seconds for 3 qubits.
0.6500858340000377 seconds for 4 qubits.
6.656475377999982 seconds for 5 qubits.
73.66349649099993 seconds for 6 qubits.

I was not able to get the next time measure in reasonable time.

Probably the origin of the problem is in OptimizationPassManager.

I'm using qiskit 2.1.1

[jakelishman]

If we're ever calling the VF2 passes without limits, that would be a bug, though at O3, I think in theory we budgeted the calls to VF2 with the intention of them being allowed to take up to a minute each. (c.f. 10s for O2 and 1s for O1, though both those levels only use VF2 twice, not three times at O3.)

That said, the reason your "simple circuit" takes so long is because it doesn't use any 2q gates at all, so every possible layout is possible, which is $16^{16}$ in this case. We should have some better logic for catching this kind of thing and stopping it growing unbounded. In VF2Layout and VF2PostLayout(strict_direction=False), which are used in O1 and O2, there is extra logic used to avoid exponential explosion from huge amounts of 1q gates. We're not able to reliably use that with 1q gates in VF2PostLayout(strict_direction=True) though (used in O3), which is why dummy circuits like this will be having trouble.

While we do want to fix this, is there a reason you're using O3? It's explicitly documented as taking a long time for no guaranteed improvement over O2.

[adamglos92]

Hi @jakelishman! I'm using mostly for consistent transpilation of circuits of various sizes. In my cases I oftenly have a few qubits which are not interacted with other ones, which caused the effect.

I'm perfectly fine with O3 taking more time, however I do believe it is as you're saying that in this particular case limits are not set at all, so it is looking for all possible combinations as you're saying (except I believe it is 16! except of 16^16). At least when I was printing the time/call-limiting attributed of the class instantiation, it was set to None for all

[adamglos92]

Actually why this pass is even being run if I'm specifying initial layout myself?

[jakelishman]

Oh yeah, I hadn't even spotted that you'd set a layout explicitly. This is almost certainly a bug in how VF2PostLayout(strict_direction=True) was added at the end of the O3 optimisation-loop pass manager - it shouldn't be a candidate to run if the layout was fixed by the user. The immediate fix will be to sort that bit out, and to set limits if they aren't already.

The harder follow-up is to find a good way of having something like #9148 work for the exact-match VF2PostLayout(strict_direction=True) form, which is what's causing the timing explosion here. The trouble is that, especially in the case of heterogeneous Targets, it's hard to satisfy both the "graph-structure" and the "1q semantics" constraints of a potential interaction graph, unless we take both into account simultaneously (otherwise we might fail to find a valid mapping because the "structure" bit used a necessary physical qubit, etc). Having the 1q bit inside the VF2 algorithm is what causes the factorial explosion, though.

except I believe it is 16! except of 16^16

yeah you're right sorry - I wasn't thinking much while typing on my phone

[adamglos92]

@jakelishman I fully agree, eventually having separable qubits will be anyway causing a decrease in quality, and might cause too much focus on finding good physical qubits for those in contrast to the more involved part.
I also agree with the first part, to be more concrete about possible fixes:

• raise error whenever limits are requested and layout is set, or set the call limit to 0
• skip adding layout in that case at all

[jakelishman]

I opened #14867 to track the issue around VF2PostLayout running when it shouldn't, since that's a backportable bugfix, but the further performance-improvement issues around allocation of isolated single-qubit gates is something that I think is worth considering for the future.

Fwiw, I just now posted a pretty large PR series that significantly improves how VF2 (regular and post) do their scoring, and this pushes back the frontier for "unreasonable" by a couple of qubits. As of #14864, my timings for your script went to:

0.031039667999721132 seconds for 0 qubits.
0.009948544000508264 seconds for 1 qubits.
0.007904162001068471 seconds for 2 qubits.
0.009038442000019131 seconds for 3 qubits.
0.009920108001097105 seconds for 4 qubits.
0.01863158400010434 seconds for 5 qubits.
0.04455086699817912 seconds for 6 qubits.
0.32249035600034404 seconds for 7 qubits.
2.4385544680008024 seconds for 8 qubits.
17.2389362310023 seconds for 9 qubits.
144.517077728 seconds for 10 qubits.

(and then I killed it)

It's not a complete solution at all, but it helps a little.