5
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ What is quantum about that? $\endgroup$ Jan 25 at 10:55
  • 1
    $\begingroup$ 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? $\endgroup$
    – Carlo
    Jan 25 at 21:03
  • 1
    $\begingroup$ 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? $\endgroup$
    – Mark S
    Jan 25 at 21:14
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Mark S
    Jan 25 at 21:19
  • 2
    $\begingroup$ @Carlo Please focus on one question, and add the clarifications to the question. $\endgroup$ Jan 25 at 23:02
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.