# How to construct a quantum gate producing 1 if r divides x, 0 otherwise?

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}$$

• Do you mean for the second to be $r|x$ cast to 0 or 1. X is being summed over, not a free variable. – AHusain Oct 20 '18 at 20:09
• 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. – nikojpapa Oct 20 '18 at 20:28
• @AHusain Ah, I see what you mean. Does it make more sense after the edit? – nikojpapa Oct 20 '18 at 21:07
• Also what is your gate set? Is $r$ arbitrary? – AHusain Oct 20 '18 at 21:12
• Just the standard single-bit quantum gates, H, Paulis, $\pi/8$, etc. I'm using Q#. And yes, $r$ is arbitrary. – nikojpapa Oct 20 '18 at 21:15

Here is an example $$r=3$$, $$N < 16$$ circuit in Quirk:
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.