How to borrow memory (2021)

Can someone tell me why this doesn’t break entropy laws? Intuitively, it seems like it should (unless ‘incompressible’ is too strong a claim).

Edit: Ah, it requires the host algorithm to be reversible (if I’m reading it right). That seems like at least part of the answer.

this sort of thing gets used in quantum computing, since quantum circuits are reversable. called either borrowed ancilla, or dirty ancilla

usually, ancilla (q) bits are set to 0 at the start of a circuit, and are garbage at the end. if you can change it to allow garbage in, you can borrow instead.

Wow, this is fascinating.

If I understand correctly, there’s an interesting parallel to erasure coding here. Say I store X, Y, and Z=X⊕Y, I can recover all three after losing any one of the three. Here, X is the original value, Z is stored in memory, and instead of storing Y you arrange your program in a way that Y can be recomputed, allowing X to be recovered from Z.