[Bug]: `minimize_space` can increase `max_space`

[thierry-martinez]

This is a longstanding bug but I just realized it had not been properly reported yet.

The following example provides a family of patterns where max_space is larger after calling minimize_space than before. sz = 4 and depth = 3 are the minimum values for which the problem occurs, but the gap between max_space before and after increases as these values grow (and the initial max_space depends only on sz, not on depth).

from graphix import Pattern, command
from graphix.measurements import Measurement

sz = 4
depth = 3
block = Pattern(input_nodes=range(sz))
block.extend(command.N(sz + i) for i in range(sz))
for i in range(1, sz):
    block.extend(command.E((j, sz + i)) for j in range(sz))
    block.extend(command.E((sz + j, sz + i)) for j in range(1, i))
block.extend(command.M(i) for i in range(sz))
p, _ = block.compose(block, {i: o for i, o in zip(block.input_nodes, block.output_nodes, strict=True)})
for _ in range(depth):
    p, _ = p.compose(block, {i: o for i, o in zip(block.input_nodes, p.output_nodes, strict=True)})
print(f"Before minimize_space: {p.max_space()=}")
p.minimize_space()
print(f"After minimize_space: {p.max_space()=}")

These patterns have X measurements; therefore they do not have causal flows, so that minimize_space uses the heuristics implemented in _measurement_order_space (selecting nodes with minimum degree first).

[emlynsg]

Noting this is also true, but to a lesser degree, for the jcz transpiler.

[mgarnier59]

Thanks! X measurements don't preclude causal flow since they are XY plane measurements with angle 0. Do they have a gflow or Pauli flow?