Speed up simplification of CNOTs in BooleanHamiltonian

[tonybruguier]

Description of the issue
During the review of #4386 which reduced the number of CNOT gates produced by BooleanHamiltonian, there was a remark that the functions _simplify_cnots_triplets and _simplify_commuting_cnots can be made faster. As soon as they find a simplification, they return early and then start from scratch again. Maybe continuing would be more efficient.

Cirq version
0.13.0.dev

[yjt98765]

@tonybruguier I have some initial ideas on optimizing the _simplify_commuting_cnots, but I am not sure about the constraints, more specifically, a test case:

        # Can simplify, but violates CNOT ordering assumption
        ([(0, 1), (2, 3), (0, 1)], False, False, [(0, 1), (2, 3), (0, 1)]),

I know that the current algorithm does not simplify this test case, but is it allowed to be simplified? What ordering assumption does it violate? Here says The code does not make any assumption as to the order of the CNOTs. I have also checked the paper but still have no clue. Is _simplify_cnots_triplets less strict as to the order of CNOTs?

[tonybruguier]

So the goal of the issue is simply to speed up the for loops.

The way the code works is to repeatedly be called. If a simplification is found, we apply it and repeat from scratch. If no simplification is found, then we exit.

Instead of restarting from scratch, we could do something smarter. It's not really a quantum problem, but rather a classical algorithmic optimization.

Of course, there could be other optimizations, but that's what the intent of this issue was.

[yjt98765]

Thank you for the quick response. I agree that this issue is not about the quantum part. Can I create a PR only to optimize _simplify_commuting_cnots? I think the PR will produce the same result as the current code, with potentially fewer loops. _simplify_cnots_triplets is somewhat more complex and I am not sure how to improve.

[tonybruguier]

Sounds good. One function at a time seems like a good idea. I could do an initial review, but the final approval would have to be given be an expert.