Consider caching dense layout result between executions of SabreLayout

[mtreinish]

What should we add?

In SabreLayout one of the trials we run is started by using the output of the dense layout algorithm to find the most connected subgraph in the coupling graph to use as a starting point for sabre's algorithm to improve the layout from. This calculation is always the same for a given pass manager as it depends solely on the target and the number of circuit qubits. For current sized backends the dense layout algorithm is quite fast but when the backend gets > 900 qubits the time is more noticeable, especially when routing small circuits on large backends.

We should be able to cache the dense layout result so we avoid recomputing it for every run of a pass manager as long as the number of dag qubits does not change between multiple executions. We should investigate the scaling characteristics of dense layout and determine if caching is worth the overhead in this case and implement it if we think the tradeoff in extra code complexity and memory to store the partial layout is worth it. Especially considering the frequency of use for multiple runs on a reused pass manager vs a single pass manager execution (I expect the former is more common).

[mtreinish]

We also should investigate reviving: Qiskit/rustworkx#635 maybe in the Qiskit rust code instead of as a rustworkx function if the scaling for dense layout can be improved.