Add backward-propagating flows to crumble

A good starting option might just be a global control to choose whether flows propagate forwards or backwards in time.

A more general version might involve having two or more marker states, such that each marker can choose whether to propagate forwards or backwards, and gives purple bar errors when those states are violated.

[Strilanc]

I think what I want to do is to have some kind of notation, like:

# propagate reset forwards
RX(1,2,t=3) -> ?

# propagate measurement backwards
? -> MX(1,2,t=5)

# propagate free-standing flip forwards (note half integer time)
Y(1,2,t=3.5) -> ?

# try to form a detector, show error otherwise
RX(1,2,t=3) -> MX(1,2,t=5)

# try form a detector; infer the resets
auto -> MX(1,2,t=5) MX(1,2,t=10)

# try form a detector; infer the measurements [somehow]
RX(1,2,t=3) RX(1,2,t=8) -> auto

and once I have a notation for it, I can make a UI for that notation. Like you could pick which ones to show.

That sounds great to me, esp if we can hook in detectors in the circuit for debugging what we're actually making,
esp inferring the resets from the measurements. For inferring the measurements from the resets, we could provide a heuristic like trying to minimize the overall size of the resulting region?

In the meantime, I would appreciate a global flip the propagation direction button, as I'm doing that a reasonable amount by hand by reversing the circuit; how hard would it be to just toggle the direction of the flow mechanics? Any pointers?

[Strilanc]

I think the key method is PropagatedPauliFrames.fromCircuit. If you add a boolean go_backwards to that method, and feed that boolean in from where the method is called from, it should be enough? You'll probably find yourself being dragged into inverting gate flows in order to compute the layer by layer result.

There is, separately, a more performant class in-the-works which is https://github.com/quantumlib/Stim/blob/main/glue/crumble/circuit/pauli_frame.js but it's not integrated yet. Don't get distracted by it.

[shohamjac]

Hi Craig, if I'll implement it as a new button would you consider merging it?

I'm looking for a good place to contribute and thought this might be helpful.

[Strilanc]

I'm open to contributions on this. I'm not sure how much I like a global button for it. The properties I want are:

• Serialized. Must survive Alice copying the URL, sending the URL to Bob, and Bob opening the URL. Otherwise people can't use it to communicate.
• Separable. Should be able to investigate a reversed flow in one part of the circuit without breaking flow annotations elsewhere in the circuit. Maximum flexibility would be if each individual marker could be reversed, but I think that unavoidably has counterintuitive consequences when forward/backward flows meet, so maybe instead each numbered flow as a whole is forwards or backwards.
• Identifiable. User should be able to tell by looking whether a flow is propagating forwards or backwards. Maybe backwards ones are wiggly or something.

If the underlying implementation satisfies those properties, then adding a button to toggle all the flows is a decent first hack at making it available.

[shohamjac]

To address the first two properties, I added an operation REVERSE(i) which reverses the i-th mark.

For example, you can write:

#!pragma MARK(0) 0
#!pragma REVERSE(0)

to reverse the marker with index 0.

For the third property, I tried a few visual cues, and thought the best was to have the backward propagating marks to have saturated colors.

You can try it here.

I did not add any UI for it right now, which I guess is fine for "power users", and we can work something out for UI next.

Let me know what you think, and if you are satisfied, I'll submit a pull request.

---

EDIT: The example in the link no longer works due to the comments below.

[Strilanc]

You should combine MARK and REVERSE into just one thing: #!pragma REVMARK(0) 0. It's odd for the reverse instruction to be a global modifier; other instructions are local in time.

If a number has both forwards and backwards flows (MARK and REVMARK entries), just compute the forwards flows and the backwards flows separately (have them pass through each other). Don't try to make them collide or cancel or interact, unless you can come up with some clever way to make that not incredibly confusing.

[shohamjac]

Sure, I did consider it, but I thought having both forward and backward flows with the same ID might be visually confusing—since the ID also determines the location (and shape) of the flow relative to the timeline. If flows with the same ID move in opposite directions, they can end up overlapping each other.

That said, it’s probably not too bad. I can implement it and let you know.

[Strilanc]

I do think it would be reasonable to have the UI push the user towards only having one direction but, because the user can edit the circuit and insert markers wherever they want, there needs to be a valid interpretation of a mix of forwards and backwards markers.

Alternatively, there would need to be a new object being saved alongside the circuit that tracked non-time-related data, like the reversal state of the flows.

[shohamjac]

Got you.

How is this?

[shohamjac]

I have also added a UI that allows for inserting a REVMARK by pressing shift++<#>:

Alternatively, it is possible to drop the UI and leave it only for power users via the import circuit function.

To further motivate it, here are two example use-cases:

• Visualising how double-check in the cultivation procedure translates to measuring the logical operator twice (with two clicks)

• Checking that an encoding circuit correctly encodes the logical operator by propagating it backward (with one click).

I'll open a PR. Let me know if you want anything done differently.