WernerStateEntanglement: swapping fidelity error

[yoursunny]

It's been noticed that there are potential errors in WernerStateEntanglement fidelity calculation, if one of the EPRs involved in a swapping operation is itself the outcome of a swapping operation.
This issue is to investigate and fix this error.

[yoursunny]

scenario for consideration

I'm starting with a failing test case for the following scenario.

Suppose the memory coherence time is 1 second, and we start with the following elementary entanglements:

1. e1 is generated at t=1000us with initial fidelity 0.99
2. e2 is generated at t=2000us with initial fidelity 0.99
3. e3 is generated at t=3000us with initial fidelity 0.99

Then we do two swaps:

1. ne1 is created by successfully swapping e1 and e2 at t=2500us
2. ne2 is created by successfully swapping ne1 and e3 at t=3500us

reference code

I'm given the following reference code and results for the above scenario.

import numpy as np

f2w = lambda f: (4*f - 1)/3 # Fidelity --> Werner
w2f = lambda w: (1 + 3*w)/4 # Werner --> Fidelity

T_coh = 1 # dephasing time of each memory
r_dph = 2/T_coh # dephasing rate of a pair (worst-case)

dephase = lambda dt: np.exp(-r_dph * dt) # dephasing function

t1_init, t2_init, t3_init  = [1e-3, 2e-3, 3e-3]
f_init = [0.99]*3 # can have different values
w1_init, w2_init, w3_init  = [f2w(f) for f in f_init]

# ne1
t = 2.5e-3
print('\nAt t=',t)

print('\tbefore swp: ') 
w1 = w1_init*dephase(t-t1_init) 
w2 = w2_init*dephase(t-t2_init)
print(f'\tw1: {w1:.9f}\tw_2: {w2:.9f}')

print('\tafter  swp:')
w12_init = w1*w2
t12_init = t*1
print(f'\tw12: {w12_init:.9f} \t f12: {w2f(w12_init):.9f}')

# ne2
t = 3.5e-3
print('\nAt t=',t)

print('\tbefore swp: ') 
w12 = w12_init*dephase(t - t12_init)
w3  = w3_init *dephase(t - t3_init)
print(f'\tw12: {w12:.9f}\tw3: {w3:.9f}')

print('\tafter  swp:')
w123_init = w12*w3
print(f'\tw123: {w123_init:.9f} \t f123: {w2f(w123_init):.9f}')

At t= 0.0025
	before swp: 
	w1: 0.983711102	w_2: 0.985680493
	after  swp:
	w12: 0.969624844 	 f12: 0.977218633

At t= 0.0035
	before swp: 
	w12: 0.967687533	w3: 0.985680493
	after  swp:
	w123: 0.953830724 	 f123: 0.965373043

logic errors in existing code

In comparison with the reference, I found two errors in MQNS logic.

decoherence time and decoherence rate

The concepts of decoherence time and decoherence rate are ambiguous.
In QuantumMemory.init, the semantics of decoherence rate parameter isn't clearly defined, but its inverse is used for calculating when a stored qubit should be deleted due to decoherence, i.e. the memory's decoherence time.

mqns/mqns/entity/memory/memory.py

Lines 74 to 75 in de03247

	decoherence_rate: decoherence rate passed to `QuantumModel.store_error_model()`.
	0 means the memory will never lose coherence.

mqns/mqns/entity/memory/memory.py

Lines 96 to 99 in de03247

	self.decoherence_delay = None if self.decoherence_rate == 0.0 else 1 / self.decoherence_rate
	"""
	Inverse of `decoherence_rate`, i.e. duration between EPR creation time and decoherence time in seconds.
	"""

However, decoherence rate of an EPR is 2 / T_coh as in the reference code, which differs from the inverse of the memory's decoherence time.

swapped EPR creation time

In WernerStateEntanglement.swapping, the new EPR's creation_time is set as the oldest between the two EPRs:

mqns/mqns/models/epr/werner.py

Line 115 in de03247

ne.creation_time = min(self.creation_time, epr.creation_time)

Consequently, when ne1 is subsequently swapped to produce ne2, the Werner parameter update on ne1 would be using a have a longer than expected dephasing time.
Effectively, the dephasing period of [1000us,2500us] is applied twice.

[yoursunny]

I'm validating the fidelity calculation and found potential errors with parallel swapping.
Hence, this issue is reopened.

[yoursunny]

I have some ideas on what's wrong with parallel swapping.

Consider this scenario:

• linear topology S-R1-R2-D
• every link has same length and delay
• LinkArch notifies both sides at the same time, such as DIM
• ASAP swap order

Suppose the elementary entanglement arrives in this order:

1. epr_S_R1
2. epr_R2_D
3. epr_R1_R2

When the third elementary entanglement arrives, both repeaters will attempt to swap their two entanglements at the same time.
Let's also assume the discrete event simulator executes R1's swap before R2's swap, and the swaps are successful.

In the current code, the following happens, all in the same time slot:

1. r1_fw.do_swapping() calls Entanglement.swap(epr_S_R1,epr_R1_R2,ps=0.5), which returns epr_S_R2. epr_S_R1 and epr_R1_R2 are released from its memory.
2. R1 deposits epr_S_R2 into r1_fw.parallel_swappings (along with epr_S_R1), s_fw.remote_swapped_eprs, and r2_fw.remote_swapped_eprs.
3. R1 transmits SWAP_UPDATE message to both S and R2, stating that epr_S_R1 and epr_R1_R2 has been swapped into epr_S_R2.
4. r2_fw.do_swapping() calls Entanglement.swap(epr_R1_R2,epr_R2_D,ps=0.5), which returns epr_R1_D. epr_R1_R2 and epr_R2_D are released from its memory.
5. R2 deposits epr_R1_D into r2_fw.parallel_swappings (along with epr_R2_D), r1_fw.remote_swapped_eprs, and d_fw.remote_swapped_eprs.
6. R2 transmits SWAP_UPDATE message to both R1 and D, which states that epr_R1_R2 and epr_R2_D has been swapped into epr_R1_D.

The first round SWAP_UPDATE messages reach neighbor nodes several time slots later:

1. S pops epr_S_R2 from its remote_swapped_eprs, and then calls _su_sequential to write it into the memory, overwriting epr_S_R1 in the same slot.
2. D pops epr_R1_D from its remote_swapped_eprs, and then calls _su_sequential to write it into the memory, overwriting epr_R2_D in the same slot.
3. R1 pops epr_R1_D from its remote_swapped_eprs but notices epr_R1_R2 is no longer in its memory.
4. R1 retrieves epr_S_R1 from its parallel_swappings and stitches it with epr_R1_D via Entanglement.swap(epr_S_R1,epr_R1_D,ps=1.0), which returns epr_S_D_1.
5. R1 deposits epr_S_D_1 into s_fw.remote_swapped_eprs, and then transmits SWAP_UPDATE message to S.
6. R2 pops epr_S_R2 from its remote_swapped_eprs but notices epr_R1_R2 is no longer in its memory.
7. R2 retrieves epr_R2_D from its parallel_swappings and stitches it with epr_S_R2 via Entanglement.swap(epr_S_R2,epr_R2_D,ps=1.0), which returns epr_S_D_2.
8. R2 deposits epr_S_D_2 into d_fw.remote_swapped_eprs, and then transmits SWAP_UPDATE message to D.

The second round SWAP_UPDATE messages reach S and D several time slots later:

1. S pops epr_S_D_1 from its remote_swapped_eprs and consumes it.
2. D pops epr_S_D_2 from its remote_swapped_eprs and consumes it.

Crucially, in the first round SWAP_UPDATE processing, R1 and R2 have formed two separate end-to-end entanglements.
They have the same name because EPR name is generated by digesting the elementary entanglement names, but they are not the same entanglement object instance because each Entanglement.swap() would return a new instance.
While this does not affect the eventual throughput statistics, having two instances can likely cause fidelity computation errors in more complex error models.

I inserted some id(epr) into logs (just after "ENTANGLED" and "SWAP_SUCC" and "consume EPR") and can see this bug in action:

[1.002] <qnode n1>: ENTANGLED 140639034381312 MemoryQubit(0, state=ENTANGLED1, ch=l0,1, path=0-R) | EPR(bcd51dc5250343b383d7fc1f1b3f5157, fidelity=0.9900, w=0.9867, fidelity_time=1.001, decohere_time=6.001, src=n1, dst=n2)
[1.002] <qnode n2>: ENTANGLED 140639034381312 MemoryQubit(0, state=ENTANGLED1, ch=l0,1, path=0-L) | EPR(bcd51dc5250343b383d7fc1f1b3f5157, fidelity=0.9900, w=0.9867, fidelity_time=1.001, decohere_time=6.001, src=n1, dst=n2)
[1.003] <qnode n4>: ENTANGLED 140639034192464 MemoryQubit(0, state=ENTANGLED1, ch=l2,3, path=0-L) | EPR(1d8a20922d0949c6a521813d1dd7d864, fidelity=0.9900, w=0.9867, fidelity_time=1.002, decohere_time=6.002, src=n3, dst=n4)
[1.003] <qnode n3>: ENTANGLED 140639034192464 MemoryQubit(1, state=ENTANGLED1, ch=l2,3, path=0-R) | EPR(1d8a20922d0949c6a521813d1dd7d864, fidelity=0.9900, w=0.9867, fidelity_time=1.002, decohere_time=6.002, src=n3, dst=n4)
[1.004] <qnode n2>: ENTANGLED 140639034191504 MemoryQubit(1, state=ENTANGLED1, ch=l1,2, path=0-R) | EPR(4ca64008aa894822b09cfa310f8adea5, fidelity=0.9900, w=0.9867, fidelity_time=1.003, decohere_time=6.003, src=n2, dst=n3)
[1.004] <qnode n2>: SWAP SUCC | [140639034381312, 140639034191504, 140639034396608] | MemoryQubit(0, state=ELIGIBLE, ch=l0,1, path=0-L, purif_rounds=0) x MemoryQubit(1, state=ELIGIBLE, ch=l1,2, path=0-R, purif_rounds=0) = EPR(eeaebd2e8dac77510ffb5cde61d5fb53, fidelity=0.9790, w=0.9720, fidelity_time=1.004, decohere_time=6.001, src=n1, dst=n3, orig_eprs=[bcd51dc5250343b383d7fc1f1b3f5157,4ca64008aa894822b09cfa310f8adea5])
[1.004] <qnode n3>: ENTANGLED 140639034191504 MemoryQubit(0, state=ENTANGLED1, ch=l1,2, path=0-L) | EPR(4ca64008aa894822b09cfa310f8adea5, fidelity=0.9897, w=0.9863, fidelity_time=1.003, decohere_time=6.003, src=n2, dst=n3, ch_index=1)
[1.004] <qnode n3>: SWAP SUCC | [140639034191504, 140639034192464, 140639034397520] | MemoryQubit(0, state=ELIGIBLE, ch=l1,2, path=0-L, purif_rounds=0) x MemoryQubit(1, state=ELIGIBLE, ch=l2,3, path=0-R, purif_rounds=0) = EPR(f86f16a85a50cf7782da3832dd339a77, fidelity=0.9793, w=0.9723, fidelity_time=1.004, decohere_time=6.002, src=n2, dst=n4, orig_eprs=[4ca64008aa894822b09cfa310f8adea5,1d8a20922d0949c6a521813d1dd7d864])
[1.005] <qnode n4>: consume EPR: 140639033916112 EPR(3c3e87c9c92d6977f3359d57a5a7fcc6, fidelity=0.9685, w=0.9580, fidelity_time=1.0045, decohere_time=6.001, src=n1, dst=n4, orig_eprs=[bcd51dc5250343b383d7fc1f1b3f5157,4ca64008aa894822b09cfa310f8adea5,1d8a20922d0949c6a521813d1dd7d864])
[1.005] <qnode n1>: consume EPR: 140639209220816 EPR(3c3e87c9c92d6977f3359d57a5a7fcc6, fidelity=0.9685, w=0.9580, fidelity_time=1.0045, decohere_time=6.001, src=n1, dst=n4, orig_eprs=[bcd51dc5250343b383d7fc1f1b3f5157,4ca64008aa894822b09cfa310f8adea5,1d8a20922d0949c6a521813d1dd7d864])

Note that n1 consumed id=140639209220816 and n4 consumed id=140639209220816.
They have the same name 3c3e87c9c92d6977f3359d57a5a7fcc6 and fidelity (in current simple error model), but are different object instances.

[yoursunny]

Google AI and myself has identified the following solution to the above problem.

In ASAP parallel swapping:

1. R1 swaps epr_S_R1 and epr_R1_R2 into epr_S_R1, and then immediately deposits epr_S_R1 into s_fw.remote_swapped_eprs and r2_fw.remote_swapped_eprs.
2. As R2 becomes ready to swap epr_R1_R2 and epr_R2_D, instead of taking the epr_R1_R2 stored in its memory, it should check its own remote_swapped_eprs data structure, and would notice that epr_R1_R2 is already swapped into epr_S_R1.
3. R2 should physically swap epr_S_R2 (instead of epr_R1_R2) and epr_R2_D into epr_S_D, and then deposit epr_S_D into s_fw.remote_swapped_eprs (replacing epr_S_R1) and d_fw.remote_swapped_eprs.
4. R2 may send SWAP_UPDATE to R1 right away, but cannot send to SWAP_UPDATE to D yet.
5. When R1 and R2 receive SWAP_UPDATE from each other, they can continue sending SWAP_UPDATE to S and D.
6. If MQNS implements gates or gate error models, they will be applied at D.

In sequential swapping (assuming l2r order), remote_swapped_eprs is still used, but R2 would not be checking it until it has received SWAP_UPDATE from R1 and accepts epr_S_R2 into its memory.
Effectively, the memory contains known heralded states, while the remote_swapped_eprs data structure contains "arrived and unverified" states.

To facilitate the above design:

• parallel_swappings is no longer necessary.
• remote_swapped_eprs shall be indexed by old EPR name (e.g. epr_R1_R2) rather than new EPR name (e.g. epr_S_R1).
• It might be necessary to introduce another heralding_map so that when R2 receives SWAP_UPDATE from R1 regarding epr_R1_R2 becoming epr_S_R2, it knows epr_R1_R2 is part of the epr_S_R2 object in memory.

[amar-ox]

remote_swapped_eprs is used here to synchronize the physical state of the EPRs, and it does not seem to violate the realistic coordination principle of MQNS.

[yoursunny]

On my handwritten notes there's a feature request regarding Forwarder.do_swapping:

• Currently, the Entanglement.swap completes instantaneously.
  It should have a configurable delay to match the hardware reality.
• The necessity for this delay, rather than slightly inflating the SWAP_UPDATE signaling timing, is:
  during the swap operation delay, the memory at the swapping node cannot be released.
• The swap operation should also have an error model (e.g. DEPOLAR).

Given this is closely related to the refactoring needed to resolve EPR continuity bug in su_parallel, I plan to address them together.

[yoursunny]

Here's a more detailed design.

Parallel swapping happens in groups.
The self node can identify its group by:

1. Discard nodes with ranks lower than its own rank from fib_entry.route.
   This is called the active route, because nodes with lower ranks have already completed their swaps and are no longer active.
2. The group extends to the left and the right to encompass all nodes with the same rank.

For example, given:

route=[A,B,C,D,E,F,G,H,I,J]
swap =[2,0,0,1,0,0,1,0,0,2]

The groups are: [B,C], [E,F], [H,I], [D,G].

From each group:

• The leftmost node is responsible for heralding the adjacent neighbor to the right on the active route.
• The rightmost node is responsible for heralding the adjacent neighbor to the left on the active route.
• The heralding messages should be sent out of the group only after every node within the group has complete swapping.
• The heralded EPR leaving the group should span from the left adjacent neighbor and right adjacent neighbor (their ranks would be higher than the group's rank).

SwapFailed class represents failed swap, instead of None.
It is like a poison that causes subsequent swaps to also fail.
Failed swap is checked when heralding escapes a group to the higher rank, in which case further sequential swaps are stopped.

Pseudo code of the design

@final
class SwapFailed(Entanglement):
    """
    Sentinel type returned from ``Entanglement.swap()`` to indicate failed swap.
    It has the usual ``src`` and ``dst`` attributes to track its span,
    as well as ``orig_eprs`` attributes to track original elementary entanglements.
    Passing to ``Entanglement.swap()`` would return ``SwapFailed`` too.
    """

# Below functions are methods of `class Forwarder`.

def do_swapping(self, mq0: MemoryQubit, mq1: MemoryQubit, fib_entry: FibEntry):
    """ (PSEUDO-CODE)
    Start swapping between two ELIGIBLE qubits.
    Caller must have confirmed current node has the proper swapping rank to perform the swap,
    which could be either sequential swap or parallel swap.
    """

    # Determine prev/next partner and their swapping rank; load EPRs from memory.
    prev_partner, prev_rank, prev_qubit, prev_epr = ...
    next_partner, next_rank, next_qubit, next_epr = ...
    # (prev|next)_epr are logically confirmed, but they may have been physically swapped elsewhere.

    # Load physical EPRs that have not been confirmed.
    prev_phy_epr = self.remote_swapped_eprs.pop(prev_epr.name, prev_epr)
    next_phy_epr = self.remote_swapped_eprs.pop(next_epr.name, next_epr)

    # Perform the swap.
    # The swap operation is supposed to have a delay, but here we calculate the physical outcome right away,
    # so that parallel swaps can properly extend the chain.
    new_epr: Entanglement = Entanglement.swap(
        prev_phy_epr, next_phy_epr,
        ps=self.ps,
        error=self.swap_error_model,
    )

    # Record that prev_epr and next_epr are swapped/concatenated into new_epr (possibly None),
    # but only if that partner can send SwapUpdate to self node.
    for a_partner, a_rank, a_epr in (prev_partner, ...), (next_partner, ...):
        if a_rank <= fib_entry.own_swap_rank:
            self.heralding_map[a_epr.name] = new_epr

    # Deposit physical swap outcome at physical ends of the chain.
    prev_phy_epr.src.deposit_remote_swapped_epr(prev_phy_epr, new_epr)
    next_phy_epr.dst.deposit_remote_swapped_epr(next_phy_epr, new_epr)
    # Also deposit swap outcome at logical neighbors if they have the same rank.
    for a_partner, a_rank, a_epr in (prev_partner, ...), (next_partner, ...):
        if a_rank == fib.own_swap_rank:
            a_partner.deposit_remote_swapped_epr(a_epr, new_epr)

    # Heralding can start when the swapping outcome is delivered to forwarder software.
    self.simulator.add_event(self.swap_delay, self.after_swap, ...)

def after_swap(self, ...):
    """ (PSEUDO-CODE)
    Event handler after asynchronous physical swapping has succeeded or failed.
    """

    # When using SYNC timing mode but INTERNAL phase is over, qubits are already released.
    if not self.timing.is_internal():
        return

    # Release qubits, as they have collapsed during swapping.
    self.release_qubit(prev_qubit)
    self.release_qubit(next_qubit)

    # Inform neighbors regarding swap outcome.
    # Note that (prev|next)_partner refers to the logical partners based on confirmed heralding,
    # because the forwarder is not supposed to know unconfirmed physical swaps elsewhere.
    for a_partner, a_rank, b_partner, b_rank in (prev_partner, ...), (next_partner, ...):
        if fib_entry.own_swap_rank == b_rank and fib_entry.own_swap_rank < a_rank:
            # Self node is performing a potential parallel swap with b_partner, but not parallel with a_partner.
            # Do not send SwapUpdateMsg to a_partner yet, so that a_partner cannot use the EPR.
            continue
        self.herald_to(a_partner, b_partner, new_epr)

def herald_to(self, a_partner: QNode, b_partner: QNode, new_epr: Entanglement):
    """ (PSEUDO-CODE)
    Send heralding information to one neighbor.

    Args:
        new_epr: extended EPR between a_partner and b_partner.
    """
    # Find elementary EPRs between self.node and a_partner within new_epr,
    # reconstruct the EPR name between these nodes via deterministic hashing.
    old_epr_name: str = ...

    self.send_msg(a_partner, SwapUpdateMsg(
        path_id=fib_entry.path_id,
        swapping_node=self.node.name,
        partner=b_partner.name,
        epr=old_epr_name,
        new_epr=new_epr.name,
        # In a real network, Pauli measurement outcome is included here.
    ))

def deposit_remote_swapped_epr(self, shared_epr: Entanglement, new_epr: Entanglement):
    """ (PSEUDO-CODE)
    Invoked by neighbor nodes to indicate a locally stored EPR has been physically swapped.
    """
    self.remote_swapped_eprs[shared_epr.name] = new_epr

def handle_swap_update(self, msg: SwapUpdateMsg, fib_entry: FibEntry):
    """ (PSEUDO-CODE)
    Process SWAP_UPDATE message received from logical partner.
    """

    # When using SYNC timing mode but INTERNAL phase is over, qubits are already released.
    if not self.timing.is_internal():
        return

    # old_epr_name identifies the EPR between self node and the swapping_node, when swapping_node started swapping.
    # new_epr_name identifies the swapped/extended EPR; it could be "SWAP-FAILED".
    old_epr_name = msg["epr"]
    new_epr_name = msg["new_epr"]
    new_epr = self.remote_swapped_eprs.pop(old_epr_name) or self.heralding_map[old_epr_name]

    if epr_pair := self.memory.read(old_epr_name): # parallel swap did not occur
        self.su_sequential(...)
    else: # parallel swap occurred
        self.su_parallel(...)

def su_sequential(self, ...):
    qubit, old_epr = epr_pair

    # Recursively locate longest EPR after parallel swaps.
    while new_epr.name != new_epr_name:
        new_epr = self.remote_swapped_eprs.pop(new_epr.name)

    if type(new_epr) is SwapFailed or new_epr.decohere_time <= self.simulator.tc:
        # Swap failed at swapping_node, local qubit collapsed.
        # Or, any of the elementary entanglements has reached decoherence time.
        self.release_qubit(qubit)
        return

    # Save extended EPR to memory.
    self.memory.write(qubit.addr, new_epr, replace=True)

    # Start purification, next sequential swap, or consume.
    ...

def su_parallel(self, ...):
    # If self node has performed parallel swapping, old_epr was extended into local_stale_epr, deposited by do_swapping.
    local_stale_epr = self.heralding_map.pop(old_epr_name)
    # Pick the entanglement with longer span.
    # If either input is SwapFailed, the result should be SwapFailed covering the longer span.
    descendant_epr = max(new_epr, local_stale_epr, key=...)

    for a_partner, a_rank, b_partner in (descendant_epr.src, ...), (descendant_epr.dst, ...):
        if fib_entry.own_swap_rank == a_rank:
            # Self node has been performing parallel swap with a_partner.
            # SwapUpdateMsg should have been sent in after_swap().
            continue

        # Determine active route, consisting of nodes who swap in parallel or after self node.
        active_route = clone(fib_entry.route)
        delete_if(active_route, lambda node: fib_entry.find_swap_rank(node) < fib_entry.own_swap_rank)

        if abs(active_route.index(self.node) - active_route.index(a_partner)) == 1:
            # Self node is adjacent to a_partner, so it is responsible for heralding.
            self.herald_to(a_partner, local_stale_epr, b_partner, descendant_epr)

Parallel Swap S-R1-R2-D swap=[1,0,0,1], assumptions:

• Physical swap latency: 1 time unit.
• Classic message latency: 10 time units per hop.
• Swap success or failure does not matter in the parallel segment, failed swap would return SwapFailed object that behaves same as a regular EPR in terms of message flow and timing.

Execution steps of the pseudo code on the above inputs

# t=1000
# R2's logical view:
# * local memory stores epr_R1_R2 and epr_R2_D
# * epr_R1_R2 and epr_R2_D are ready for swapping
R2.do_swapping(mq_R2_R1, mq_R2_D):
    prev_partner, prev_epr = R1, epr_R1_R2
    next_partner, next_epr = D, epr_R2_D
    prev_phy_epr = epr_R1_R2
    next_phy_epr = epr_R2_D
    new_epr = epr_R1_D
    R2.heralding_map["epr_R1_R2"] = epr_R1_D
    R1.remote_swapped_eprs["epr_R1_R2"] = epr_R1_D
    D.remote_swapped_eprs["epr_R2_D"] = epr_R1_D
# Data structures:
# * R2.heralding_map has: epr_R1_R2=epr_R1_D
# * R1.remote_swapped_eprs has: epr_R1_R2=epr_R1_D
# * D.remote_swapped_eprs has: epr_R2_D=epr_R1_D

# t=1000
# R1's logical view:
# * local memory stores epr_S_R1 and epr_R1_R2
# * epr_S_R1 and epr_R1_R2 are ready for swapping
# * epr_S_R1 is alive and ready for swapping
R1.do_swapping(mq_R1_S, mq_R1_R2):
    prev_partner, prev_epr = S, epr_S_R1
    next_partner, next_epr = R2, epr_R1_R2
    prev_phy_epr = epr_S_R1
    next_phy_epr = epr_R1_D # R1.remote_swapped_eprs.pop("epr_R1_R2")
    new_epr = epr_S_D
    R1.heralding_map["epr_R1_R2"] = epr_S_D
    S.remote_swapped_eprs["epr_S_R1"] = epr_S_D
    R2.remote_swapped_eprs["epr_R1_R2"] = epr_S_D
    D.remote_swapped_eprs["epr_R1_D"] = epr_S_D
# Data structures:
# * R1.heralding_map has: epr_R1_R2=epr_S_D
# * R2.heralding_map has: epr_R1_R2=epr_R1_D
# * S.remote_swapped_eprs has: epr_S_R1=epr_S_D
# * R2.remote_swapped_eprs has: epr_R1_R2=epr_S_D
# * D.remote_swapped_eprs has: epr_R2_D=epr_R1_D, epr_R1_D=epr_S_D

# t=1001
R2.after_swap():
    R2.release_qubit(mq_R2_R1) # epr_R1_R2 deleted at R2
    R2.release_qubit(mq_R2_D) # epr_R2_D deleted at R2

    # R2->R1: a_partner=R1, a_rank=0, b_partner=D, b_rank=1, own_rank=0
    R2.send_msg(R1, SwapUpdateMsg("R2", "D", "epr_R1_R2", "epr_R1_D"))
    # R2->D: a_partner=D, a_rank=1, b_partner=R1, b_rank=0, own_rank=0
    # not sending, parallel swap with b_partner but not a_partner

# R2's logical view:
# * local memory is empty
# * R1-D was created, heralded to R1
#
# In-flight SwapUpdate messages:
# * R2->R1, SwapUpdateMsg("R2", "D", "epr_R1_R2", "epr_R1_D"), arriving at 1011

# t=1001
R1.after_swap():
    R1.release_qubit(mq_R1_S) # epr_S_R1 deleted at R1
    R1.release_qubit(mq_R1_R2) # epr_R1_R2 deleted at R1

    # R1->S: a_partner=S, a_rank=1, b_partner=R2, b_rank=0, own_rank=0
    # not sending, parallel swap with b_partner but not a_partner
    # R1->R2: a_partner=R2, a_rank=0, b_partner=S, b_rank=1, own_rank=0
    R1.send_msg(R2, SwapUpdateMsg("R1", "S", "epr_R1_R2", "epr_S_D"))

# R1's logical view:
# * local memory is empty
# * S-R2 was created, heralded to R2
#
# In-flight SwapUpdate messages:
# * R2->R1, SwapUpdateMsg("R2", "D", "epr_R1_R2", "epr_R1_D"), arriving at 1011
# * R1->R2, SwapUpdateMsg("R1", "S", "epr_R1_R2", "epr_S_D"), arriving at 1011

# t=1011, R2 has informed R1 that epr_R1_R2 has been extended to R1-D
R1.handle_swap_update(SwapUpdateMsg("R2", "D", "epr_R1_R2", "epr_R1_D"))
    new_epr = epr_R1_D # R1.remote_swapped_eprs.pop("epr_R1_R2")
    epr_pair = None # R1.memory.read("epr_R1_R2"), deleted in R1.after_swap()
    # parallel swap case
    local_stale_epr = epr_S_D # R1.heralding_map.pop("epr_R1_R2")
    descendant_epr = epr_S_D
    prev_partner = S
    next_partner = D

    # R1->S: a_partner=S, a_rank=1, a_index=0, b_partner=D, own_rank=0, own_index=1
    R1.send_msg(S, SwapUpdateMsg("R1", "D", "epr_S_R1", "epr_R1_D"))

    # R1->D: a_partner=D, a_rank=1, a_index=3, b_partner=S, own_rank=0, own_index=1
    # not sending, active_route index not adjacent

# R1's logical view:
# * local memory is empty
# * S-D was stitched from S-R2 and R1-D (both contain epr_R1_R2), heralded to S and D
#
# In-flight SwapUpdate messages:
# * R1->R2 SwapUpdateMsg("R1", "S", "epr_R1_R2", "epr_S_D"), arriving at 1011
# * R1->S, SwapUpdateMsg("R1", "D", "epr_S_R1", "epr_R1_D"), arriving at 1021
#
# Data structures:
# * R1.heralding_map is empty
# * R2.heralding_map has: epr_R1_R2=epr_R1_D
# * S.remote_swapped_eprs has: epr_S_R1=epr_S_D
# * R1.remote_swapped_eprs is empty
# * R2.remote_swapped_eprs has: epr_R1_R2=epr_S_D
# * D.remote_swapped_eprs has: epr_R2_D=epr_R1_D, epr_R1_D=epr_S_D

# t=1011, R1 has informed R2 that epr_R1_R2 has been extended to S-R2
R2.handle_swap_update(SwapUpdateMsg("R1", "S", "epr_R1_R2", "epr_S_D"))
    new_epr = epr_S_D # R2.remote_swapped_eprs.pop("epr_R1_R2")
    epr_pair = None # R1.memory.read("epr_R1_R2"), deleted in R2.after_swap()
    # parallel swap case
    local_stale_epr = epr_R1_D # R2.heralding_map.pop("epr_R1_R2")
    descendant_epr = epr_S_D
    prev_partner = S
    next_partner = D

    # R2->R1: a_partner=R1, a_rank=0, a_index=1, b_partner=D, own_rank=0, own_index=2
    # not sending, active_route index not adjacent
    # R2->D: a_partner=D, a_rank=1, a_index=3, b_partner=R1, own_rank=0, own_index=2
    R2.send_msg(D, SwapUpdateMsg("R2", "R1", "epr_R2_D", "epr_S_D"))

# R2's logical view:
# * local memory is empty
# * S-D was stitched from S-R2 and R1-D (both contain epr_R1_R2), heralded to D
#
# In-flight SwapUpdate messages:
# * R1->S, SwapUpdateMsg("R1", "D", "epr_S_R1", "epr_S_D"), arriving at 1021
# * R2->D, SwapUpdateMsg("R2", "R1", "epr_R2_D", "epr_S_D"), arriving at 1021
#
# Data structures:
# * R1.heralding_map is empty
# * R2.heralding_map is empty
# * S.remote_swapped_eprs has: epr_S_R1=epr_S_D
# * R1.remote_swapped_eprs is empty
# * D.remote_swapped_eprs has: epr_R2_D=epr_R1_D, epr_R1_D=epr_S_D

# t=1021, R1 has informed S that epr_S_R1 has been extended to epr_S_D
S.handle_swap_update(SwapUpdateMsg("R1", "R2", "epr_S_R1", "epr_S_D"))
    new_epr = epr_S_D # S.remote_swapped_eprs.pop("epr_S_R1")
    # sequential swap case, assuming prior swaps succeeded
    qubit, old_epr = mq_S_R1, epr_S_R1 # S.memory.read("epr_S_R1")
    new_epr = epr_S_D # S.remote_swapped_eprs.pop("epr_S_R1")
    S.memory.write(mq_S_R1.addr, epr_S_D, replace=True)
    S.consume_and_release(epr_S_D)

# In-flight SwapUpdate messages:
# * R2->D, SwapUpdateMsg("R2", "R1", "epr_R2_D", "epr_S_D"), arriving at 1021
#
# Data structures:
# * R1.heralding_map is empty
# * R2.heralding_map is empty
# * S.remote_swapped_eprs is empty
# * R1.remote_swapped_eprs is empty
# * D.remote_swapped_eprs has: epr_R2_D=epr_R1_D, epr_R1_D=epr_S_D

# t=1021: R2 has informed D that epr_R2_D has been extended to epr_S_D
D.handle_swap_update(SwapUpdateMsg("R2", "R1", "epr_R2_D", "epr_R1_D"))
    new_epr = epr_R1_D # D.remote_swapped_eprs.pop("epr_R2_D")
    # sequential swap case, assuming prior swaps succeeded
    qubit, old_epr = mq_D_R2, epr_R2_D # D.memory.read("epr_R2_D")
    new_epr = epr_S_D # D.remote_swapped_eprs.pop("epr_R1_D")
    D.memory.write(mq_D_R2.addr, new_epr, replace=True)
    D.consume_and_release(epr_S_D)

# Data structures: all empty

[amar-ox]

• Maybe I forgot some previous assumptions, but in line:
  R1.send_msg(R2, SwapUpdateMsg("R1", "S", "epr_R1_R2", "epr_S_D"))
  How does R1 know that epr_S_D was created by its swap? it's physically possible via data structure, but R1 didn't receive heralding from R2 yet?
• In line R1.send_msg(S, SwapUpdateMsg("R1", "D", "epr_S_R1", "epr_R1_D")): shouldn't the new epr sent to S be epr_S_D?
• Similarly, in D.handle_swap_update(SwapUpdateMsg("R2", "R1", "epr_R2_D", "epr_R1_D")), D should receive epr_S_D?

[yoursunny]

In line R1.send_msg(S, SwapUpdateMsg("R1", "D", "epr_S_R1", "epr_R1_D")): shouldn't the new epr sent to S be epr_S_D?
Similarly, in D.handle_swap_update(SwapUpdateMsg("R2", "R1", "epr_R2_D", "epr_R1_D")), D should receive epr_S_D?

This is a copy-paste mistake in writing out the execution steps.
R1 to S message should be SwapUpdateMsg("R1", "D", "epr_S_R1", "epr_S_D").
R2 to D message should be SwapUpdateMsg("R2", "S", "epr_R2_D", "epr_S_D").

---

in line R1.send_msg(R2, SwapUpdateMsg("R1", "S", "epr_R1_R2", "epr_S_D"))
How does R1 know that epr_S_D was created by its swap? it's physically possible via data structure, but R1 didn't receive heralding from R2 yet?

R1 does not logically know the name "epr_S_D" represents an entanglement between S and D.
In actual simulator code, this would be an opaque SHA256 digest that does not identify the src and dst of this entanglement.
I write the EPR object (e.g. WernerStateEntanglement instance) in variable form, and write the EPR name in string form with quotes.

R1 informs R2 that it has swapped/extended that original epr_R1_R2 into a longer entanglement between partner="S" and R2.
In real network, the message would contain the Pauli measurement outcome from R1 (more generally, the Pauli measurement outcome from every node to the left of R2 in the same group).
In the simulator, it uses the name "epr_S_D" (actually an opaque digest) to represent the Pauli measurement outcomes and simplify lookup code.

When R2 receives this message, it will find it has swapped epr_R1_R2 to create epr_R1_D between R1 and D.
It can then stitch these heralding information together and know the longest entanglement should be epr_S_D between S and D.

[amar-ox]

It seems that the last parameter of SwapUpdateMsg is essentially used to keep consistent naming.
But if it's a placeholder for swapping Pauli results then we have to be careful: at R1, even if epr_S_D actual value does not identify S/D, if the hash includes epr_R2_D then it's equivalent to identifying S/D.

[yoursunny]

at R1, even if epr_S_D actual value does not identify S/D, if the hash includes epr_R2_D then it's equivalent to identifying S/D.

Although the name "epr_S_D" is generated from SHA256("uuid_S_R1-uuid_R1_R2-uuid_R2_D") (gathered from epr.orig_eprs list), none of the forwarder logic depends on this.
However, to prevent confusion and accidental leaks, I plan to address this issue as follows:

SwapUpdateMsg should no longer have new_epr name.
Instead, it would carry a success/failure flag to indicate whether the swaps between recipient and "partner" have succeeded or there are failures.

The sender can only derive the success/failure flag from its local measurement outcomes and heralded information.
Neither the sender nor the parallel recipient peek type(new_epr) is SwapFailed because it was computed from prev_phy_epr and next_phy_epr, which contains unheralded information.
Nevertheless, a sequential recipient may use the type(new_epr) is SwapFailed expression to validate the heralding outcome.

---

In the existing code, Entanglement.swap function has two failure conditions:

        if epr0.is_decoherenced or epr1.is_decoherenced:
            epr0._mark_decoherenced()
            epr1._mark_decoherenced()
            return None

        if ps < 1.0 and rng.random() >= ps:  # swap failed
            epr0._mark_decoherenced()
            epr1._mark_decoherenced()
            return None

The ._mark_decoherenced() calls are wrong, because it leaks information faster than light.
For example in S-R1-R2-D topology, if R2 had a "swap failed" condition (second if block), it would set epr_R1_R1.is_decoherenced = True, which leaks unheralded information to R1 instantly.
Instead, I'm looking to excise ._mark_decoherenced() and .is_decoherenced, and instead maintain such information either as SwapFailed type, which prevents faster-than-light information.

After that, the first if block is gone, and the second if block is a swap failure from "local measurement outcome".

---

new_epr.decohere_time may also contain unheralded information computed from prev_phy_epr and next_phy_epr.
To plug this leak, several of the new_epr.decohere_time <= self.simulator.tc "# oldest pair decohered" checks must be removed.
Instead, the nodes within a parallel group must operate as if the EPRs are unexpired.

I plan to excise .decoherence_time from EPR objects too.
Instead, it could be added to SwapUpdateMsg.

The memory's automatic deletion upon .decoherence_time expiration is still there, but should act upon heralded information learned from MIN(local elementary EPR, heralded decoherence_time along the path), instead of magical global information.