Can anyone explain this in-place modular addition circuit from the paper "Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms" by Martin Roetteler et. al (https://arxiv.org/pdf/1706.06752.pdf). What does that '>' sign mean in the last circuit component? Also, what do those black arrowheads imply leaving from the circuit components?
They're trying to say this (working quirk link):
In pseudocode it would be this:
# perform y += x (mod R) # the $ operator means to concatenate two quint registers' qubits borrow g = quint(len=1) let c = quint(len=1, val=0) y$c += x y$c$g -= R if c: y$g += R del c = x <= y unborrow g
It's kind of complicated to explain why it works. The key thing to realize is that you can fold a comparison into a subtraction by appending a bit to the high part of the target register, because when a subtraction underflows it flips that bit.
You don't actually need
g for this circuit. Maybe it's filling some underlying purpose (like making the additions be the same size), but if not then the code can be simplified to:
let c = quint(len=1, val=0) y$c += x - R if c: y += R del c = x <= y