Suppose I have an initial state: $$|A\rangle=\dfrac{1}{2^{3l/2}}\sum_{x=0}^{2^l-1}\sum_{y=0}^{2^l-1}\sum_{z=0}^{2^l-1} |x\rangle^{\otimes l}|y\rangle^{\otimes l}|z\rangle^{\otimes l}|0\rangle^{\otimes l}|0\rangle^{\otimes l}|0\rangle^{\otimes l}.$$

Now this state is an equal superposition of all states $\{0....2^l-1\}^3$.

Now I transform this state such that registers $|0\rangle^{\otimes l}|0\rangle^{\otimes l}|0\rangle^{\otimes l}$ contains all the states $\{0....2^l-1\}^3$, but not in the traditional order i.e each state say $(|3\rangle |7\rangle |8\rangle) |0\rangle |0\rangle |0\rangle \to (|3\rangle |7\rangle |8\rangle)|8\rangle|9\rangle|16\rangle$. If I keep doing this to all the initial states then I get all the states just in a permuted manner.

Also since the new permuted states are done obtained using a reversible transform I don't need the first three registers so I want to just make them $0$. Basically what I want is just the permutation of indexes for example I have $1,2,3,4$ then i want $4,1,3,2$. Consider without the $z$ state $$|A\rangle= (|0\rangle|0\rangle ) |0\rangle|0\rangle + (|0\rangle|1\rangle ) |0\rangle|0\rangle + (|1\rangle|0\rangle ) |0\rangle|0\rangle + (|1\rangle|1\rangle ) |0\rangle|0\rangle.$$

Now this state transforms into $$|B\rangle= (|0\rangle|0\rangle ) |0\rangle|1\rangle + (|0\rangle|1\rangle ) |1\rangle|0\rangle + (|1\rangle|0\rangle ) |1\rangle|1\rangle + (|1\rangle|1\rangle ) |0\rangle|0\rangle.$$

The output state that I want is $$ |C\rangle= (|0\rangle|1\rangle ) |0\rangle|0\rangle + (|1\rangle|0\rangle ) |0\rangle|0\rangle + (|1\rangle|1\rangle ) |0\rangle|0\rangle + (|0\rangle|0\rangle ) |0\rangle|0\rangle$$

Edit: Classically I have three numbers say $x,y,z$ and I want to transform them to $(x'y'z')$ using a function $f$ that is invertible.

$$\begin{eqnarray} x'=f(x,y,z)\\ y'=f(x,y,z)\\ z'=f(x,y,z) \end{eqnarray}$$

So my states $|x\rangle|y\rangle|z\rangle$ is the original and the result $x',y',z'$ is stored in the registers $|0\rangle|0\rangle|0\rangle$.

  • $\begingroup$ So why use additionally registers? Why not just apply the permutation directly? $\endgroup$
    – DaftWullie
    May 25, 2019 at 5:17
  • $\begingroup$ Sir the permutation is not a straightforward one as the permutation of the $x$ and $y$ state depends on the $z$ state and the permutation of the $z$ state depends on the $x$ and $y$ $\endgroup$
    – Upstart
    May 25, 2019 at 6:11
  • $\begingroup$ so while changing the states when i have say a particular state $|x\rangle |y\rangle |z\rangle|0\rangle|0\rangle|0\rangle$ i change it to $|x\rangle |y\rangle |z\rangle|x'\rangle|y'\rangle|z'\rangle$ I cant modify the original registers since its value is necessary to modify the other registers $\endgroup$
    – Upstart
    May 25, 2019 at 6:30

1 Answer 1


To sum up, you have an unitary operation $P$ such that $$ P \ \vert x \rangle \vert y \rangle \vert z \rangle \vert 0 \rangle \vert 0 \rangle \vert 0 \rangle \mapsto \vert x \rangle\vert y \rangle\vert z \rangle\vert 0 \oplus p_1(x, y, z) \rangle\vert 0 \oplus p_2(x, y, z) \rangle\vert 0 \oplus p_3(x, y, z) \rangle $$ with $f$, $p_2$ and $p_3$ already implemented, invertible and you want to create a unitary operation $P'$ such that $$ P' \ \vert x \rangle \vert y \rangle \vert z \rangle \vert 0 \rangle \vert 0 \rangle \vert 0 \rangle\mapsto\vert p_1(x, y, z) \rangle\vert p_2(x, y, z) \rangle\vert p_3(x, y, z) \rangle\vert 0 \rangle \vert 0 \rangle \vert 0 \rangle . $$

This can be achieved easily by using the fact that the XOR ($\oplus$) operation is its self inverse and $S$, defined as the operation that swap the content of the registers given as input: $$ S \vert x_1 \rangle\vert x_2 \rangle\vert x_3 \rangle\vert x_4 \rangle\vert x_5 \rangle\vert x_6 \rangle \mapsto \vert x_4 \rangle\vert x_5 \rangle\vert x_6 \rangle\vert x_1 \rangle\vert x_2 \rangle\vert x_3 \rangle. $$ The $S$ operation can be implemented with CNOT gates.

The gate you are trying to implement is then given by $P' = P^\dagger S P$ (I'm not 100% sure that $P^\dagger$ implements the inverses of $p_1$, $p_2$ and $p_3$, you may need to check that, if it's not the case then replace $P^\dagger$ by the unitary operation inverting $p_1$, $p_2$ and $p_3$):

$$ \begin{split} P^\dagger SP \ \vert x \rangle \vert y \rangle \vert z \rangle \vert 0 \rangle \vert 0 \rangle \vert 0 \rangle &= P^\dagger S \ \vert x \rangle\vert y \rangle\vert z \rangle\vert 0 \oplus p_1(x, y, z) \rangle\vert 0 \oplus p_2(x, y, z) \rangle\vert 0 \oplus p_3(x, y, z) \rangle \\ &= P^\dagger S \ \vert x \rangle\vert y \rangle\vert z \rangle\vert p_1(x, y, z) \rangle\vert p_2(x, y, z) \rangle\vert p_3(x, y, z) \rangle \\ &= P^\dagger \ \vert p_1(x, y, z) \rangle\vert p_2(x, y, z) \rangle\vert p_3(x, y, z) \rangle \vert x \rangle\vert y \rangle\vert z \rangle \\ &= \vert p_1(x, y, z) \rangle\vert p_2(x, y, z) \rangle\vert p_3(x, y, z) \rangle \vert x \oplus x \rangle\vert y \oplus y \rangle\vert z \oplus z \rangle \\ &= \vert p_1(x, y, z) \rangle\vert p_2(x, y, z) \rangle\vert p_3(x, y, z) \rangle\vert 0 \rangle \vert 0 \rangle \vert 0 \rangle \end{split} $$

  • $\begingroup$ since $|A\rangle={2^{3l/2}}\sum_{x=0}^{2^l-1}\sum_{y=0}^{2^l-1}\sum_{z=0}^{2^l-1} |x\rangle^{\otimes l}|y\rangle^{\otimes l}|z\rangle^{\otimes l}|=H^{\otimes 3l}|0\rangle^{\otimes 3l}$ Then can i just appy $H^{\otimes 3l}$ to A to get back $|0\rangle^{\otimes 3l}$? $\endgroup$
    – Upstart
    May 25, 2019 at 20:16
  • $\begingroup$ $H$ is its own inverse so yes, applying $HH$ to a qubit is the same as applying $H^\dagger H = I$ on this qubit. This reasoning can be applyied qubit-wise to your $3l$ qubits. $\endgroup$ May 25, 2019 at 21:30
  • $\begingroup$ so instead of the XOR operation i define the operator say $\rho=I^{\otimes 3l}\otimes H^{\otimes 3l}$ after the swapping is done $\endgroup$
    – Upstart
    May 25, 2019 at 21:42

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.