"Direct" implementations for `standardize` and `shift_signals`

[thierry-martinez]

This PR proposes more direct implementations for standardize and shift_signals. Here are some benchmarks, with random circuits:

method	global	local	direct
standardize	5.51	0.24 (×23.05)	0.04 (×5.33)
shift_signals	3.37	0.40 (×8.52)	0.11 (×3.61)
standardize_and_shift_signals	9.01	0.44 (×20.56)	0.20 (×2.24)

[shinich1]

@thierry-martinez Thanks! Me and @masa10-f think it's time to deprecate localpattern.

[shinich1]

@thierry-martinez we should also deprecate standardize_and_transpile of Circuit class! I believe it would be good to deprecate LocalPattern and standardize_and_transpile in this PR. could you update this branch?

[thierry-martinez]

I changed shift_signals and standardize to use direct as the default method, and added warnings to other methods as well as to Circuit.standardize_and_transpile, and to Pattern.standardize_and_shift_signals. Without LocalPattern, there is no longer a benefit to perform these operations simultaneously.

[thierry-martinez]

The CI fails on windows-2022 (with all Python versions except 3.8) with the following error:

  .tox\py39\lib\site-packages\matplotlib\cbook.py:32: in <module>
      from matplotlib import _api, _c_internal_utils
  E   ImportError: DLL load failed while importing _c_internal_utils: The specified module could not be found.

I don't think this failure is related to a change in this PR, though.

[EarlMilktea]

@thierry-martinez LGTM!

@shinich1 @masa10-f Could you check the code correctly implements the measurement calculus?

[masa10-f]

By the way, do you intend to use the measurement calculus for non-Untiary case? As far I understand, signal shifting requires correction set to be consistent with a gflow or Pauli flow, otherwise it can destruct the computation. I guess we need to check determinism before.(This can be discussed in another place as it might be out of this PR)

[EarlMilktea]

We may better turn off RUF003... It's going too far that we cannot use Greek letters.

@thierry-martinez Could you kindly add "RUF003" to the ignore section in pyprojec.toml or use # noqa: RUF003 , and then revert the changes?

[thierry-martinez]

Could you kindly add "RUF003" to the ignore section in pyprojec.toml or use # noqa: RUF003 , and then revert the changes?

Done in ad8396f. More precisely, the proof comments are now written as multi-line strings, which enables noqa: RUF001 to be applied to the whole block instead of applying noqa: RUF003 on each single comment line.

[EarlMilktea]

I'm a little against this approach (ad8396f) as it forces python interpreter to evaluate the literal as string, whereas comments are simply discarded. How about using https://docs.astral.sh/ruff/settings/#lint_allowed-confusables ?

[thierry-martinez]

I agree that using allowed-confusables is a better approach, especially since it allows α to appear in other contexts where it can be useful. This has been addressed in commit ceaebaf. However, I don't believe using string literal for comments forces the Python interpreter to evaluate anything. You can verify this by checking the disassembly: string literal statements are compiled into NOP in the bytecode.

[thierry-martinez]

I made two substantial changes yesterday that may warrant additional reviews:

• I made standardize_direct and shift_signals_direct more robust with respect to aliasing by ensuring they instantiate new commands and domains instead of modifying them in-place. These functions are now correct even if some command or domain instances are shared between patterns.
• I updated standardize_direct to correctly commute C commands within the pattern. Previous implementations of standardize ignored C commands.

[EarlMilktea]

You can verify this by checking the disassembly: string literal statements are compiled into NOP in the bytecode.

I checked it. You're right!

[thierry-martinez]

@masa10-f Are you sure that the initial pattern in your example has gflow? I get (None, None) when I run gflow_from_pattern on it.

from graphix.command import E, M, N, X, Z
from graphix.gflow import gflow_from_pattern
from graphix.pattern import Pattern
from graphix.pauli import Plane

pattern = Pattern(input_nodes=[1, 2])
pattern.extend(
    [
        N(node=0),
        N(node=3),
        N(node=4),
        N(node=5),
        N(node=6),
        E(nodes=(0, 1)),
        E(nodes=(0, 3)),
        E(nodes=(0, 4)),
        E(nodes=(1, 3)),
        E(nodes=(2, 4)),
        E(nodes=(3, 4)),
        E(nodes=(3, 5)),
        E(nodes=(4, 6)),
        M(node=1, plane=Plane.XY, angle=0.0, s_domain=set(), t_domain=set()),
        M(node=2, plane=Plane.XY, angle=0.0, s_domain=set(), t_domain=set()),
        M(node=0, plane=Plane.XZ, angle=0.0, s_domain={1, 2}, t_domain={1}),
        M(node=3, plane=Plane.XY, angle=0.0, s_domain={0}, t_domain={0, 1, 2}),
        M(node=4, plane=Plane.XY, angle=0.0, s_domain={2}, t_domain={1}),
        Z(node=6, domain={2}),
        Z(node=5, domain={0}),
        X(node=5, domain={3}),
        X(node=6, domain={4}),
    ]
)

assert gflow_from_pattern(pattern) == (None, None)

[masa10-f]

@masa10-f Are you sure that the initial pattern in your example has gflow? I get (None, None) when I run gflow_from_pattern on it.

I'm sorry for confusing you. It does not have gflow in the current convention, but has in the RHS convention we discussed in the thread. I generated the initial pattern with the following code

graph = nx.Graph()
graph.add_nodes_from([0, 1, 2, 3, 4, 5, 6])  # 0 is XZ gadget
graph.add_edges_from(
    [
        (0, 1),
        (0, 3),
        (0, 4),
        (1, 3),
        (2, 4),
        (3, 4),
        (3, 5),
        (4, 6),
    ]
)
input_nodes = [1, 2]
output_nodes = [5, 6]
meas_planes = {
    0: Plane.XZ,
    1: Plane.XY,
    2: Plane.XY,
    3: Plane.XY,
    4: Plane.XY,
}
meas_angles = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0}
pattern = generate_from_graph(
    graph, meas_angles, input_nodes, output_nodes, meas_planes
)
pattern.standardize()

With the following modification into standardization, because I didn't notice the convention was changed into LHS.

if cmd.plane == Plane.XY:
    if z_cmd := z_dict.pop(cmd.node, None):
        cmd.t_domain ^= z_cmd.domain
    if x_cmd := x_dict.pop(cmd.node, None):
        cmd.s_domain ^= x_cmd.domain
elif cmd.plane == Plane.XZ:
    if z_cmd := z_dict.pop(cmd.node, None):
        cmd.s_domain ^= z_cmd.domain
    if x_cmd := x_dict.pop(cmd.node, None):
        cmd.s_domain ^= x_cmd.domain
        cmd.t_domain ^= x_cmd.domain
elif cmd.plane == Plane.YZ:
    if z_cmd := z_dict.pop(cmd.node, None):
        cmd.s_domain ^= z_cmd.domain
    if x_cmd := x_dict.pop(cmd.node, None):
        cmd.t_domain ^= x_cmd.domain

[thierry-martinez]

By the way, do you intend to use the measurement calculus for non-Untiary case? As far I understand, signal shifting requires correction set to be consistent with a gflow or Pauli flow, otherwise it can destruct the computation. I guess we need to check determinism before.(This can be discussed in another place as it might be out of this PR)

Signal shifting inverts some classical outcomes: if the pattern is not deterministic, the relationship between the measures and the quantic state is affected, as illustrated in test_shift_signals_plane (in this test, the pattern is not deterministic, so has no flow of any kind). I just exposed in my last commit fd8f8c4 the function pattern.shift_outcomes which converts back and forth outcomes between unshifted and shifted patterns.

[masa10-f]

Signal shifting inverts some classical outcomes: if the pattern is not deterministic, the relationship between the measures and the quantic state is affected, as illustrated in test_shift_signals_plane (in this test, the pattern is not deterministic, so has no flow of any kind). I just exposed in my last commit fd8f8c4 the function pattern.shift_outcomes which converts back and forth outcomes between unshifted and shifted patterns.

Thank you for your reply! I found an error when I added an extra Pauli correction on the output in the test case. Is it fixable within this algorithm? I haven't ever tried this approach, so I'll consider it more.

pattern = Pattern(input_nodes=[0])
for i in (1, 2, 3):
    pattern.add(N(node=i))
    pattern.add(E(nodes=[0, i]))
pattern.add(M(node=0, angle=0.5))
pattern.add(M(node=1, angle=0.5))
pattern.add(M(node=2, angle=0.5, plane=plane, s_domain=[0], t_domain=[1]))
pattern.add(Z(node=3, domain=[2])) # <- added

I added the extra Z correction on the output node(X also has error). Then the results are not consistent with standardized ones. I guess the errors are close to Pauli in this case, but it can be more complex in a longer pattern.

FAILED tests/test_pattern.py::TestPattern::test_shift_signals_plane[global-Plane.XY] - assert 1.0007415106216804e-16 == 1 ± 1.0e-06
FAILED tests/test_pattern.py::TestPattern::test_shift_signals_plane[global-Plane.YZ] - assert 0.0 == 1 ± 1.0e-06
FAILED tests/test_pattern.py::TestPattern::test_shift_signals_plane[global-Plane.XZ] - assert 8.326672684688674e-17 == 1 ± 1.0e-06

[thierry-martinez]

@masa10-f Nice catch! The problem you discovered is in the global method: the implementation modifies domains in-place and, therefore, does not support aliasing. The test performed a shallow copy between the reference pattern and the shifted pattern, causing the domain on Z to be modified in both. I fixed the test in 27396fa by making a deep copy instead of a shallow copy. I preferred not to change the implementation of the global method itself since we plan to deprecate it anyway, and I am not sure to what extent we plan to ensure robustness against aliasing.

[masa10-f]

@thierry-martinez Thanks! I apologize for missing that the error only occurs with the global method. I understand that it preserves the operator sum representation in all cases. This PR looks good to merge.

[shinich1]

@thierry-martinez just looked through again and this looks ready to go. please squash and merge!

[thierry-martinez]

Thank you, @EarlMilktea . Are you ok for merging?

[EarlMilktea]

@thierry-martinez LGTM! Thank you for great work!

[thierry-martinez]

Merged! Thanks!