How do you embed a POVM matrix in a Unitary?

I'm not sure that I agree with what is presented as the solution (although the final answer seems OK). Let me explain what I would do.

That task gives you 3 states $|Arangle$, $|Brangle$ and $|Crangle$. You want a POVM that, for example, cannot give the answer "0" is the state was in $|Arangle$, cannot give the answer "1" if the state was in $|Brangle$ etc. So, the POVM elements are orthogonal to those states. So, let me write $|A^perprangle$ where $langle A|A^perprangle=0$.

So, we will be defining POVM elements $$ E_0=alpha_0|A^perpranglelangle A^perp|,quad E_1=alpha_1|B^perpranglelangle B^perp|,quad E_2=alpha_2|C^perpranglelangle C^perp|. $$ It might help to also have $E_3=I-E_0-E_1-E_2$. All these operators must be non-negative, and we want the $alpha_i$ to be as large as possible. There's actually a certain symmetry here. If you set $alpha_0=alpha_1=alpha_2$ then $$ E_3=I-alphafrac32 I, $$ so $E_3$ is non-negative if $alphaleqfrac23$, so we set $alpha=frac23$.

Now, how do we implement such a measurement. There need to be at least 3 measurement results, and since we're using qubits, the space needs to be $2^kgeq3$ dimensional, i.e. we'll pick $k=2$. This means we'll introduce one ancila, which we'll be able to assume is in a known, fixed state. For simplicity, let that be $|0rangle$.

Now, remember that we want to find a unitary that's going to help us make the measurement. Indeed, each measurement result will have to correspond to an orthogonal state, such as $|00rangle$, $|01rangle $ and $|10rangle$, and the unitary will need to map us to these states. But unitaries map orthogonal states to orthogonal states and our states $|A^perprangle|0rangle$, $|B^perprangle|0rangle$ and $|C^perprangle|0rangle$ are not orthogonal to each other. What we need to do is find components such as $|tilde Arangle$ below: $$ |psi_0rangle=sqrtalpha_0|A^perprangle|0rangle+sqrt{1-alpha_0}|tilde Arangle|1rangle $$ such that all three states are orthogonal.

With this in mind, we can start to specify $U$: $$ U=|00ranglelanglepsi_0|+|01ranglelanglepsi_1|+|10ranglelanglepsi_2|+|11ranglelanglepsi_3|, $$ and so we already know some of the elements: $$ U=frac{1}{sqrt{3}}left(begin{array}{cc} 1 & -1 & ? & ? 1 & -omega^2 & ? &? 1 & -omega & ? &? 0 & 0 & ? & ? end{array}right) $$ You then just have to complete this matrix, however you like, subject to the orthogonality and normalisation conditions of the rows. I'd start by completing the top row with 1,0, at which point everything else falls into place: $$ U=frac{1}{sqrt{3}}left(begin{array}{cc} 1 & -1 & 1 & 0 1 & -omega^2 & omega &0 1 & -omega & omega^2 &0 0 & 0 & 0 & sqrt3 end{array}right) $$ You can put any phase you like on the bottom-right element, such as $-i$. Which one you want will basically be determined by whatever is easiest to implement with a circuit.