2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ The > gate probably compares the top register with the middle register and outputs a $|1\rangle$ on the third register if the first register is greater. I’m not sure about the filled in triangles at the end of some gates- I think this is maybe a carry overflow qubit or something. $\endgroup$
    – Mark S
    Nov 6, 2022 at 13:28
  • $\begingroup$ from the beginning of the seventh page: "We provide circuit diagrams for the modular operations, in which black triangles on the right side of gate symbols indicate qubit registers that are modified and hold the result of the computation" and later on "the black triangles mark the output wire that contains the result." $\endgroup$
    – glS
    Nov 6, 2022 at 15:33

1 Answer 1

1
$\begingroup$

They're trying to say this (working quirk link):

enter image description here

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.