Improve RemoveCupsRewriter

[dimkart]

Description

Some of the syntax-based diagrams in lambeq, such as pregroup diagrams, include cups that indicate syntactic interactions between the words in the sentence. For example, in the diagram:

John       gave      Mary    a    flower                                                                                            
────  ─────────────  ────  ─────  ──────
 n    n.r·s·n.l·n.l   n    n·n.l    n
 ╰─────╯  │  │   ╰────╯    │  ╰─────╯
          │  ╰─────────────╯

cups are indicated by ╰─╯ links. These operations are expensive, since they introduce post-selections which increase exponentially the number of the required circuit executions. lambeq addresses this problem with RemoveCupsRewriter, which attempts to remove as many cups as possible while retaining the same connections as the original diagram.

The goal of this task is to improve RemoveCupsRewriter, or to create a new rewriter class, so that the new implementation:

1. is more effective than the old one concerning the number of cups removed from a diagram
2. keeps the rewriting speed in acceptable ranges

Notes

• A robust implementation of a related diagram rewriting routine can be found here.
• The PRs should be accompanied with some proof-of-concept benchmarks of the new implementation and comparisons with the old one, with regard to both effectiveness and performance, as these were defined above.

References

• Remove cups implementation in discopro
• lambeq rewriting tutorial