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


2 Answers 2


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.

  • $\begingroup$ I can't believe I've overlooked this! $\endgroup$
    – Tristan Nemoz
    Sep 10, 2022 at 13:56

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.