If you have two registers in the state $\frac{1}{2^{n/2}} \sum_{x = 0}^{2^{n/2} - 1} |x\rangle |0\rangle$, how could you construct a gate that produces a superposition of states $|x\rangle|1\rangle$ when some integer $r$ divides $x$, and $|x\rangle|0\rangle$ otherwise, for each input?

I.e. a unitary quantum gate that replicates the function $f(x) = \begin{cases} 1 \text{ if } r \text{ divides } x\\ 0 \text{ otherwise} \end{cases}$

  • $\begingroup$ Do you mean for the second to be $r|x$ cast to 0 or 1. X is being summed over, not a free variable. $\endgroup$
    – AHusain
    Oct 20, 2018 at 20:09
  • $\begingroup$ Yes, second register cast to a superposition of states $|0\rangle$ and $|1\rangle$, based on whether the first register is a multiple of $r$. First register is an equal superposition of all states. $\endgroup$
    – nikojpapa
    Oct 20, 2018 at 20:28
  • $\begingroup$ @AHusain Ah, I see what you mean. Does it make more sense after the edit? $\endgroup$
    – nikojpapa
    Oct 20, 2018 at 21:07
  • 1
    $\begingroup$ Also what is your gate set? Is $r$ arbitrary? $\endgroup$
    – AHusain
    Oct 20, 2018 at 21:12
  • $\begingroup$ Just the standard single-bit quantum gates, H, Paulis, $\pi/8$, etc. I'm using Q#. And yes, $r$ is arbitrary. $\endgroup$
    – nikojpapa
    Oct 20, 2018 at 21:15

1 Answer 1


The simplest way would be to do a long division to compute the remainder, toggle the target bit if there is a non-zero remainder, then uncompute the long division.

Here is an example $r=3$, $N < 16$ circuit in Quirk:

mod 3 != 0 circuit

Note the displays on the right hand side, which show that conditioning on the output qubit (the bottom one) leaves only values divisible by 3 in the input register (the top 4 qubits).

The basic idea is to keep track of the maximum value $m$ that could possibly be in the input register $i$, then iteratively pick the largest $k$ such that $r^k \leq m$ and subtract $r^k$ out of $i$ if $i \geq r^k$. This reduces $m$ by $r^k$. Repeat this until $m < r$, then toggle your output bit if $i=0$. Then uncompute all the conditional subtractions to restore $i$.

A proper construction would not require $r$ subtractions for each value of $k$ as this one does, and a proper construction would expand the comparison and addition circuits into their full form, but I think this construction gets the right idea across.


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.