Does applying the transformation $sumalpha_{jk}|j,f(k)ranglemapstosumomega_N^{-jk}alpha_{jk}|j,f(k)rangle$ require computing $f^{-1}$?

Question

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$?
Thanks in advance.

Mark S · Answer

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.

Does applying the transformation $sumalpha_{jk}|j,f(k)ranglemapstosumomega_N^{-jk}alpha_{jk}|j,f(k)rangle$ require computing $f^{-1}$?

One Answer

Add your own answers!

Ask a Question