Qiskit / qiskit / 24313520567

87%

main: 87%

Build Type

push

github

Committed by web-flow

Commit Message

Convert Sabre's `lookahead` to layer-based tracking (#14911)

* Convert Sabre's `lookahead` to layer-based tracking

The previous Sabre extended set was just the "next N" 2q gates
topologically on from the front layer, where Qiskit reliably used
`N = 20` ever since its introduction.  For small-width circuits (as were
common when the original Sabre paper was written, and when it was first
implemented in Qiskit), this could mean the extended set was reliably
several layers deep.  This could also be the case for star-like
circuits.  For the wider circuits in use now, at the 100q order of
magnitude, the 20-gate limit reliably means that denser circuits cannot
have their entire next layer considered by the lookahead set.

This commit modifies the lookahead heuristic to be based specifically on
layers.  This regularises much of the structure of the heuristic with
respect to circuit and target topology; we reliably "look ahead" by the
same "distance" as far as routing is concerned.  It comes with the
additional benefits:

- we can use the same `Layer` structure for both the front layer and the
  lookahead layers, which reduces the amount of scoring code

- the lookahead score of a swap can now affect at most two gates per
  layer, just like the front-layer scoring, and we can do this
  statically without loops

- we no longer risk "biasing" the lookahead heuristic in either case of
  long chains of dependent gates (e.g. a gate that has 10 predecessors
  weights the score the same as a gate with only 1) or wide circuits
  (some qubits have their next layer counted in the score, but others
  don't because the extended set reached capacity).

- applying a swap to the lookahead now has a time complexity that is
  constant per layer, regardless of the number of gates stored in it,
  whereas previously it was proportional to the number of gates stored
  (and the implementation in the parent of this commit is proportional
  to the number of qubits in the circuit).
... (continued)

Coverage Stats

88 of 98 new or added lines in 5 files covered. (89.8%)

21 existing lines in 5 files now uncovered.

104553 of 119521 relevant lines covered (87.48%)

971651.24 hits per line