# Does applying the transformation $\sum\alpha_{jk}|j,f(k)\rangle\mapsto\sum\omega_N^{-jk}\alpha_{jk}|j,f(k)\rangle$ require computing $f^{-1}$?

Suppose that I have a bijective function $$f: \mathbb{Z}_N → Y$$ where $$Y$$ is a finite set. Suppose that $$f$$, but not its inverse, can be computed efficiently classically.

I would like to apply the following diagonal unitary transformation:

$$\sum_{j,k \in \mathbb{Z}_N} \alpha_{j,k} \vert j, f(k) \rangle \mapsto \sum_{j,k \in \mathbb{Z}_N} \omega_N^{-jk} \alpha_{j,k} \vert j, f(k) \rangle.$$

Here, $$\omega_N = e^{\frac{2 \pi i}{N}}$$.

My question is: if I want to apply this transformation, does that require $$f$$ to be inverted classically, or is that not needed because my sum goes over $$j$$ and $$k$$?

• What is quantum about that? Jan 25 at 10:55
• Okay, so more concretely, i have a quantum superposition: $$\sum_{x_1, x_2 \in X} \alpha_{x_1,x_2} \vert x_1, f(x_2) \rangle$$ And I want to apply a diagonal unitary transformation to get: $$\sum_{x_1, x_2 \in X} \varphi(x_1,x_2) \alpha_{x_1,x_2} \vert x_1, f(x_2) \rangle$$ My question is, does applying that transformation require inverting the function f classically? Jan 25 at 21:03
• Before application of the second unitary, there is no entanglement between $x_1$ and $x_2$ in the state $\vert x_1, f(x_2)\rangle$, right? Jan 25 at 21:14
• It may depend very much on what's known about $\phi(x_1,x_2)$. For example if $\phi(x_1,x_2)$ is solely dependent on $x_1$, then no need to invert $f(x_2)$. Jan 25 at 21:19
• @Carlo Please focus on one question, and add the clarifications to the question. Jan 25 at 23:02

In order to apply the conditional rotation by $$\omega_{N}^{-jk}$$, you will need to know $$k$$, therefore you will need to have access to both $$k$$ (for the phase) and $$f(k)$$ (for the basis vector).
An easier way to see that is to set $$N=2$$ and let $$\alpha_{j,k}$$ be $$1/2$$ for all $$i,j$$. There are only two bijective functions $$f$$ - the identity, or the inverse.
You end up with two different states, depending on whether $$f$$ is the identity or the inverse.