I am trying to implement the quantum k-means algorithm proposed in https://arxiv.org/pdf/1909.04226.pdf.

In the equation (8) of the manuscript we need to implement a state $|\psi\rangle = \frac{1}{\sqrt{2}}\left[|0\rangle \otimes |X_i\rangle + |1\rangle \otimes |X_j\rangle\right]$ like the one shown in the title, where $X_i$, $X_j$ are normalised vectors.

One solution proposed in the paper for implementing the $|\psi\rangle$ state is to use Hadamard and CSWAP gates. Assuming that $X_i$ and $X_j$ can be prepared with one qubit each, if one apply a Hadamard gate to the first qubit and afterwards a CSWAP gate, we would have the state $|\gamma\rangle = \frac{1}{\sqrt{2}}\left[|0\rangle \otimes |X_i\rangle \otimes |X_j\rangle + |1\rangle \otimes |X_j\rangle \otimes |X_i\rangle \right]$. So I need to somehow "get rid" of the leftmost qubit. Here are some of the things I have tried/thought about until now:

  • As the $|\gamma\rangle$ state is not separable, we can't use the partial trace or just reset the leftmost qubit.
  • We can apply a SWAP gate between the leftmost qubit and a new qubit q3, because then equation (9) of the manuscript wouldn't hold.

Any ideas on how to encode the $|\psi\rangle$ state with or without using the mentioned procedure ?

  • 1
    $\begingroup$ If you can prepare a state $X_i$ you can remove it by running the inverse algorithm. Just control it off your first qubit! $\endgroup$
    – DaftWullie
    Commented Oct 13, 2023 at 15:18

1 Answer 1


Suppose that $U_i$ prepares the state $\left|X_i\right\rangle$. Start by applying an Hadamard gate on the first qubit: $$\frac{1}{\sqrt{2}}\left(|00\rangle+|10\rangle\right)$$ Then apply $U_j$ controlled off the first qubit: $$\frac{1}{\sqrt{2}}\left(|00\rangle+|1\rangle\otimes\left|X_j\right\rangle\right)$$ Apply an $X$ gate on the first qubit: $$\frac{1}{\sqrt{2}}\left(|10\rangle+|0\rangle\otimes\left|X_j\right\rangle\right)$$ Apply $U_i$ controlled off the first qubit: $$\frac{1}{\sqrt{2}}\left(|1\rangle\otimes\left|X_i\right\rangle+|0\rangle\otimes\left|X_j\right\rangle\right)$$ And finally reapply an $X$ gate on the first qubit to obtain the state you're looking for.


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.