Hello sorry if this is a stupid question arising from my ignorance but I have been looking at the modular adder for Shor's algorithm according to this website. Here is what the gate looks like:
The adding gate has a band on the right and the subtraction gate has a band on the left. My confusion comes from the CNOT gate between the ancillary bit and an extra qubit coming from the inverse QFT. This happens again later, although with a NOT gate on either side, presumably to reset the state of the ancillary bit so that it can be used again. As far as I know, there isn't an extra qubit output from inverse QFT, or even an ancillary bit, so where does this qubit come from?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Earlier on that paper, they state that the input to the adders (or subtracters) will have an extra qubit than the ones needed to represent the numerical input. For example, if you want to input $8$, you need $4$ qubits since $8$ in binary is $1000$. So, you will input $5$ qubits to the gates.
They use this extra qubit to look out for overflow. For example if you do $8 + 9$, you will get $17$, which is $10001$ in binary. So, if you were using only the 4 qubits needed to represent $8$, you will not be able to represent $17$ correctly if needed.
This extra qubit is what the $CNOT$s are being controlled by to detect overflow on that register.