Seadog panics with dynamic matchers

[mariagg-quantinuum]

Seadog panics when using dynamic matchers (specifically with Squash3Gadget), resulting in NotConvex errors. Static matchers work as a workaround but limit optimization capabilities.

When Seadog is tested with the Squash3Gadget, it consistently panics with NotConvex errors:

Could not construct PersistentHugr from walker, skipping potentially valid commit combinations
Could not construct PersistentHugr from walker, skipping potentially valid commit combinations
Could not construct PersistentHugr from walker, skipping potentially valid commit combinations
Could not construct PersistentHugr from walker, skipping potentially valid commit combinations

thread '<unnamed>' panicked at tket-py/src/protocol/circuit_replacer.rs:104:1:
called `Result::unwrap()` on an `Err` value: NotConvex
stack backtrace:
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
Caught panic: called `Result::unwrap()` on an `Err` value: NotConvex
Caught panic: called `Result::unwrap()` on an `Err` value: NotConvex

thread '<unnamed>' panicked at tket-py/src/protocol/circuit_replacer.rs:104:1:
called `Result::unwrap()` on an `Err` value: NotConvex
stack backtrace:
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
Caught panic: called `Result::unwrap()` on an `Err` value: NotConvex

The same circuits work fine with other gadgets that use different matchers:

[CX q[0], q[2]; CX q[2], q[0]; CX q[0], q[1]; CX q[2], q[0]; CX q[0], q[1]; CX q[0], q[2]; CX q[1], q[2]; CX q[0], q[2]; ]

[CX q[0], q[1]; CX q[4], q[2]; CX q[0], q[1]; CX q[3], q[2]; CX q[3], q[4]; CX q[3], q[0]; CX q[4], q[1]; CX q[4], q[2]; ]

[CX q[3], q[2]; CX q[2], q[0]; CX q[3], q[1]; CX q[1], q[3]; CX q[3], q[1]; CX q[0], q[1]; CX q[3], q[2]; CX q[3], q[2]; CX q[1], q[2]; ]

[CX q[0], q[2]; CX q[1], q[0]; CX q[1], q[2]; CX q[0], q[2]; CX q[0], q[1]; ]

[CX q[2], q[1]; CX q[0], q[1]; CX q[0], q[1]; CX q[0], q[1]; CX q[2], q[1]; CX q[1], q[0]; ]

[CX q[0], q[1]; CX q[0], q[1]; CX q[0], q[4]; CX q[3], q[1]; CX q[1], q[4]; CX q[1], q[2]; CX q[1], q[0]; ]

The main difference between gadgets are the matchers. The 3Squash matcher handles matching state progression (which affects whether the optimizer can find convex regions to rewrite) more loosely by expanding the qubit set until it reaches a 4th qubit. It can also start on non-CX gates.

Seadog really seems to hate this. The errors can be circumvented by using a static set of expected_qs generated at each CX but that by default will reduce all of our matches to 2 qubits. I still see optimisations occurring in that setting, but I expect it to miss things, as it will no longer see the 3 qubits. (Just forcing it to start on CX gates without the static qubit assignment doesn’t resolve it unfortunately). This will be used as an interim solution, but the incompatibility between seadog and dynamic allocation should be addressed. This does not occur with badger.