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?

enter image description here


1 Answer 1


I would use a circuit that looks like:

enter image description here

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.

Please let me know if I can clarify further.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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