# Circuit construction for execution of conditional statements using least significant bit

Suppose I have integers and encode them as binary strings for example: $$|0\rangle=|00\rangle,|1\rangle= |01\rangle,|2\rangle=|10\rangle,|3\rangle=|11\rangle.$$

Now an $$n$$ bit integer, say $$x$$, is encoded as a state $$|x_0x_1....x_{n-1}\rangle$$ with $$x_0$$ being the most significant bit. To check the remainder by $$4$$ we only care about the two least significant bit i.e. $$x_{n-2}x_{n-1}$$. If the remainder is $$0$$ or $$2$$ then the least significant bit is $$0$$, and hence for a controlled operation that executes whether the remainder is $$2$$ or $$0$$ can be triggered only by the least significant bit being $$0$$. But my question is if I want to execute a controlled operation conditioned on the remainder being $$3$$ or $$1$$ what should be done? Since $$|3\rangle=|11\rangle$$ and $$|0\rangle=|00\rangle$$, should this be the circuit for the control?

Where $$|0\rangle$$ is an ancillary output bit. Assume the initial state of the system is in the standard basis.
Here, the first $$\land_2(X)$$ (CCNOT) applies the $$X$$ gate to the target qubit for all states that have their two least significant bits set to 1. Note that if none of the states have $$|x_{n-1}\rangle=|1\rangle$$ and $$|x_{n-2}\rangle=|1\rangle$$ then the $$X$$ gate is never applied to the ancilla.
We then negate both of the control bits, so that if they were previously 1 they are then set to 0, and vice versa. This results in the next $$\land_2(X)$$ gate only being applied if originally, $$|x_{n-1}\rangle=|0\rangle$$ and $$|x_{n-2}\rangle=|0\rangle$$. The final two $$X$$ gates uncompute the original negation, so that the original states of the two least significant bits are preserved.
Therefore, the only states that will have the ancillary bit set to $$|1\rangle$$, are those for which the two least significant bits were either $$|00\rangle$$ or $$|11\rangle$$. Satisfying the requirements of your question.