TeamGraphix
"Direct" implementations for `standardize` and `shift_signals`
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) |
@thierry-martinez Thanks! Me and @masa10-f think it's time to deprecate localpattern.
@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?
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.
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.
@thierry-martinez LGTM!
@shinich1 @masa10-f Could you check the code correctly implements the measurement calculus?
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)
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?
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.
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 ?
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.
I made two substantial changes yesterday that may warrant additional reviews:
- I made
standardize_directandshift_signals_directmore 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_directto correctly commuteCcommands within the pattern. Previous implementations of standardize ignoredCcommands.
You can verify this by checking the disassembly: string literal statements are compiled into NOP in the bytecode.
I checked it. You're right!
@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 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
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.
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
@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.
@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.
@thierry-martinez just looked through again and this looks ready to go. please squash and merge!