# Preparing a superposition state modulo $k$

Consider being given the description of a function $$f: \{0, 1\}^n \rightarrow \{0, 1\}^m$$ and the binary representation of an integer $$k$$. Is the state $$\begin{equation} |\psi_{f, k}\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0, 1\}^n} |x\rangle |f(x)~\text{mod}~k\rangle \end{equation}$$

preparable by a polynomial time quantum algorithm?

Note that it is easy to prepare $$\begin{equation} |\psi_{f}\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0, 1\}^n} |x\rangle |f(x)\rangle. \end{equation}$$

But I do not know how to go from there to $$|\psi_{f, k}\rangle$$.

I think you can do it using an ancilla register.

1. Prepare the state $$\left|\psi_f\right\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|f(x)\rangle|0\rangle$$
2. Apply $$\mathcal{O}_k$$ to the second and third registers, where $$\mathcal{O}_k$$ is defined on the basis states as: $$\mathcal{O}_k|x\rangle|y\rangle=|x\rangle|y\oplus (x\text{ mod } k)\rangle$$ This effectively creates the state: $$\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|f(x)\rangle|f(x)\text{ mod }k\rangle$$ Since computing the modulo $$k$$ is classically efficient, then $$\mathcal{O}_k$$ is also efficient (that is, applied in polynomial time).
3. Apply $$U_f$$ a second time on the first and second registers to uncompute the second register.

All in all, this took two applications of $$U_f$$ and one application of $$\mathcal{O}_k$$, both of which are done in polynomial time.

I like what Tristan Nemoz suggested, it shows how to do some interesting acrobatics with quantum registers.

However, in the question, you assumed that $$f(x)$$ is given. $$f(x)$$ is a classical function that eventually converted into $$U_f$$ for quantum computation. Since $$f(x)$$ is given, the most reasonable thing to do is to define $$g(x,k) = f(x) \ \textrm{mod } k$$ and then turn that into $$U_g$$. This way, you create the uniform superposition with one extra register $$|0\rangle$$ and then apply $$U_g$$. Done.

• I can't believe I've overlooked this! Sep 10, 2022 at 13:56