Preparing a superposition state modulo $k$

Question

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

Answer 1

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.

Answer 2

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.