How to measure superposition coefficients to determine state?

Question

There was a problem at the Winter 2019 Q# codeforces contest, which I cannot find a mathematical solution for. It goes like this:

You are given 3 qubits that can be in one of the following states: $$|\psi_0\rangle=\frac{1}{\sqrt 3}\left(|100\rangle+\omega|010\rangle+\omega^2|001\rangle\right)$$ or $$|\psi_1\rangle=\frac{1}{\sqrt 3}\left(|100\rangle+\omega^2|010\rangle+\omega|001\rangle\right)$$ where $\omega=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.

Answer 1

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.