Qiskit / qiskit / 17434232678

88%

Build Type

push

github

Committed by web-flow

Commit Message

Add on-the-fly score pruning to VF2 (#14856)

This is a complete rewrite of the VF2 codebase, also adding the concept
of "score" to the semantic matchers for nodes and edges.  Nothing in the
current codebase is updated to use the new scoring capabilities in this
patch, though the modifications to how the node-matching functions need
to be supplied are respected.

The on-the-fly scoring is to support the use-case of our `VF2Layout` and
`VF2PostLayout` passes, which are a minimising reduction over all
possible subgraph isomorphisms.  The current logic generates each
isomorphism, keys that to a score, then finds the minimal mapping based
on that key.  The benefits of on-the-fly scoring are:

1. The VF2 search tree can be eagerly pruned as soon as the score of the
   partial mapping exceeds the current known minimal value.  In terms of
   the code structure here, we claim a candidate mapping pair is
   "unfeasible" if it increases the score past the minimum.  This allows
   us to terminate entire branches of the algorithm, potentially with
   many levels of depth still unmapped.  This can be a combinatoric
   improvement on the complete iterator.

2. A given pair of layouts generated "close" together (in terms of the
   loop over isomorphisms) will usually share most of their node
   mappings.  This means that they also share almost all of their score
   calculation.  By tracking the score on-the-fly, and backtracking the
   score to a previous state as we pop pairs out of the mapping, we
   avoid recalculating much of the score.  If there are many available
   subgraph isomorphisms, differing only by small numbers of qubits at
   one end, this can improve the asymptotic complexity of the scoring
   significantly.

The scoring, as implemented here, does come at a cost: if enabled, but
there is _no_ isomorphism, we'll waste time by scoring partial layouts
all the way through, only for the regular structural checks to show that
everything was already imposs... (continued)

Run Details

356 of 572 new or added lines in 3 files covered. (62.24%)

39 existing lines in 6 files now uncovered.

91295 of 103362 relevant lines covered (88.33%)

482189.4 hits per line