Qiskit / qiskit

Qiskit is an open-source SDK for working with quantum computers at the level of extended quantum circuits, operators, and primitives.
https://www.ibm.com/quantum/qiskit
Apache License 2.0
5.05k stars 2.33k forks source link

Update `OptimizeSwapBeforeMeasure` to use Rustworkx 0.15 reverse topological order #12128

Open jakelishman opened 5 months ago

jakelishman commented 5 months ago

What should we add?

At the moment, OptimizeSwapBeforeMeasure has an unfortunate complexity where it iterates many times through a circuit, and looks like it even has a worst-case quadratic complexity in checking the descendents for finality. This would be solvable using the new ability to do reverse topological sorting that's coming in Rustworkx 0.15, which could avoid scanning the whole circuit and give us a potential little speed bump in O3, though tbh ElidePermutations (#9523) may well have supplanted this pass by then.

jakelishman commented 5 months ago

Looking more right now, OptimizeSwapBeforeMeasure has several components that are pretty broken, or at least rather unoptimal. DAGCircuit.descendants produces an unordered set (why?), so iterating through that has no particular order, and I don't think it's guaranteed to produce correct results. Similarly, DAGCircuit.op_nodes is not topological, so there's no guarantee that the swaps are visited in the best order, even if reversed.

mtreinish commented 5 months ago

Yeah, my thinking is this pass would be supersceded by ElidePermutations so performance improvements for it shouldn't be critical. Im thinking we'll want to deprecate it in 1.2 for removal in 2.0. But we definitely should try to fix correctness issues for the 1.x branch where we can.

jakelishman commented 5 months ago

I guess the reason it might not be totally supplanted is that this pass might still have worth in a pipeline for a backend that has a native swap - in that case, it might still have value in a post-translation and post-routing optimisation layout, where ElidePermutations would invalidate the coupling constraints. This never invalidates coupling constraints because it's a limited form of swap/permutation elision where it only affects gates that are followed by 1q operations (or other swaps).

That said, we could probably teach ElidePermutations to have a coupling-aware version of itself as well, if we chose.