There was a problem at the Winter 2019 Q# codeforces contest (that is now over), which I cannot find a mathematical solution for.

The problem goes like this: You are given 3 qubits that can be in one of the following states:

$$|ψ_0⟩=\frac{1}{\sqrt 3}\left(|100⟩+ω|010⟩+ω^2|001⟩\right)$$


$$|ψ_1⟩=\frac{1}{\sqrt 3}\left(|100⟩+ω^2|010⟩+ω|001⟩\right)$$

where $ω=e^{2iπ/3}$.

Build a function that determines in which of the 2 states are the 3 qubits.

My question is, how could you solve this problem in linear algebra (bra-kets notation) and the normal quantum logic gates? I figured out you have to somehow measure the coefficients, but I don't know quite how. If you could include a "code algorithm proof of concept" that would be great, but I am mainly interested in understanding the algebra part. After understanding it, implementing would be just a problem of translating the operations/gates.

If I got something wrong, please correct me. I am new-ish to the whole quantum computing scene.


The idea is to apply a unitary transformation which will map these states to a different pair of orthogonal states which are easy to distinguish by measuring in computational basis.

Let's construct a unitary $U$ which prepares $|\psi_0\rangle$ starting from $|000\rangle$ state.

The first step is to prepare a $W_3 = \frac{1}{\sqrt{3}}\left(|100\rangle + |010\rangle + |001\rangle\right)$ state, as described in this question.

After that you just have to apply the $\omega$ and $\omega^2$ phases to the states $|010\rangle$ and $|001\rangle$ - this can be done using rotation gates. Depending on the primitives you have, you can do it using R1 gate, like the authors' solution, using Rz gate if you're ok with some accumulating some global phase, or using zero-controlled Rz.

Now, what happens if you take the states $|\psi_0\rangle$ and $|\psi_1\rangle$ and apply the adjoint of the transformation $U$ to them? You know that the state $|\psi_0\rangle$ will be transformed to $|000\rangle$, and the state $|\psi_1\rangle$ will be transformed to some other state. It doesn't really matter what state it is, it's enough to know that it is orthogonal to $|000\rangle$. So to distinguish these states you can measure all qubits after applying $U^\dagger$ - if you get all zeroes, you know it was $|\psi_0\rangle$, otherwise it was $|\psi_1\rangle$.

You can find a more detailed explanation and the code for this problem in the contest editorial.

  • $\begingroup$ Thanks for the answer! it was exactly what I was looking for. Do you think you can give me an example of a rotation gate that will apply the w phase just to |010>, but not to the others? After this, I'll gladly mark the question as answered, since it's exactly what I needed. $\endgroup$ – Tudor Mar 14 at 12:27
  • $\begingroup$ @Tudor I've edited the answer with the examples of the gates. $\endgroup$ – Mariia Mykhailova Mar 14 at 15:44
  • $\begingroup$ @Tudor Please let me know if you need more details :-) $\endgroup$ – Mariia Mykhailova Mar 15 at 16:57

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.