MS Quantum Katas - Measurements Task 2.3 - problems in understanding the solution

Question

I am referring to the MS Quantum Katas, Measurements, 2.3 Peres/Wootters game I have big problems to understand the solution. The task is defined as:

--begin

Input: A qubit which is guaranteed to be in one of the three states:

• $|A\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle + |1\rangle \big)$,
• $|B\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle + \omega |1\rangle \big)$,
• $|C\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle + \omega^2 |1\rangle \big)$,

Here $\omega = e^{2i \pi/ 3}$.

Output:

• 1 or 2 if the qubit was in the $|A\rangle$ state,
• 0 or 2 if the qubit was in the $|B\rangle$ state,
• 0 or 1 if the qubit was in the $|C\rangle$ state.

You are never allowed to give an incorrect answer. Your solution will be called multiple times, with one of the states picked with equal probability every time.

The state of the qubit at the end of the operation does not matter.

--end

The solution is described as:

Solution

The task is a simple game inspired by a quantum detection problem due to Holevo^[1] and Peres/Wootters^[2]. In the game, a player A thinks of a number (0,1 or 2) and the opponent, player B, tries to guess any number but the one chosen by player A.

Classically, if you just made a guess, you'd have to ask two questions to be right $100\%$ of the time. If instead, player A prepares a qubit with 0, 1, or 2 encoded into three single qubit states that are at an angle of 120 degrees with respect to each other and then hands the state to the opponent, then player B can apply a Positive Operator Valued Measure (POVM) consisting of 3 states that are perpendicular to the states chosen by player A. It can be shown that this allows B to be right $100\%$ of the time with only 1 measurement, which is something that is not achievable with a von Neumann measurement on 1 qubit. See also Peres^{[3, chapter 9.6]} for a nice description of the optimal POVM.

Next, we address how we can implement the mentioned POVM by way of a von Neumann measurement, and then how to implement said von Neumann measurement in Q#. First, we note that the POVM elements are given by the columns of the following matrix:

$$M = \frac{1}{\sqrt{2}}\left(\begin{array}{rrr} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \end{array} \right)$$

where $\omega = e^{2 \pi i/3}$ denotes a primitive $3$rd root of unity. Our task will be to implement the rank 1 POVM given by the columns of $M$ via a von Neumann measurement. This can be done by "embedding" $M$ into a larger unitary matrix (taking complex conjugates and transposed):

$$M' = \frac{1}{\sqrt{2}}\left(\begin{array}{cccc} 1 & -1 & 1 & 0 \\ 1 & -\omega^2 & \omega & 0 \\ 1 & -\omega & \omega^2 & 0 \\ 0 & 0 & 0 & -i \end{array} \right)$$

Notice that applying $M'$ to input states given by column $i$ of $M$ (padded with two zeros to make it a vector of length $4$), where $i=0, 1, 2$ will never return the label $i$ as the corresponding vectors are perpendicular.

We are therefore left with the problem of implementing $M'$ as a sequence of elementary quantum gates. Notice that

$$M' \cdot {\rm diag}(1,-1,1,-1) = M' \cdot (\mathbf{1}_2 \otimes Z) = \frac{1}{\sqrt{2}}\left(\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 1 & \omega^2 & \omega & 0 \\ 1 & \omega & \omega^2 & 0 \\ 0 & 0 & 0 & i \end{array} \right)$$

...
--end

I have several questions / problems here.

1. What exactly is a "von-Neumann" measurement? Is it just a measurement in the standard basis?

2. I understand how to get M:
   A POVM M with ${E_0, E_1, E_2}, E_k = |\psi_k\rangle\langle\psi_k|, |\psi_k\rangle=1/sqrt(2)(|0\rangle+\omega^k|1\rangle)$ results in $M=(\psi_0 \psi_1 \psi_2) = \frac{1}{\sqrt{2}}\left(\begin{array}{rrr} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \end{array}\right)$

Next step is

Our task will be to implement the rank 1 POVM given by the columns of M via a von Neumann measurement. This can be done by "embedding" M into a larger unitary matrix (taking complex conjugates and transposed)

What does this embedding mean exactly, what is the math behind? I only found one article about "Emdedded Transforms" (https://books.google.de/books?id=pefvCAAAQBAJ&pg=PA104&lpg=PA104&dq=embedding+matrix+into+larger+unitary+matrix&source=bl&ots=2apFdXFYNd&sig=ACfU3U3JCtj7GgJimx5cgCcKE_FrMUx_4Q&hl=de&sa=X&ved=2ahUKEwjo-K3EipHpAhW8UxUIHVuyDtYQ6AEwCXoECAgQAQ#v=onepage&q=embedding%20matrix%20into%20larger%20unitary%20matrix&f=false), but this is valid only for square matrices.

3. The next step in the solution is:

Notice that applying $M'$ to input states given by column $i$ of $M$ (padded with two zeros to make it a vector of length $4$), where $i=0, 1, 2$ will never return the label $i$ as the corresponding vectors are perpendicular. We are therefore left with the problem of implementing $M'$ as a sequence of elementary quantum gates.

What does this mean? I don't understand the sense of this.

Thanks in advance, Markus

Answer 1

Von Neumann measurement is a measurement that corresponds to an orthonormal basis, not necessary standard. Though it's related to the standard by a unitary transformation.

As for the solution, at first you need to construct a POVM from the vectors orthogonal to those $|A\rangle, |B\rangle, |C\rangle$. For example, you can take $$ |E_0\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle - |1\rangle \big), $$ $$ |E_1\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle - \omega |1\rangle \big), $$ $$ |E_2\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle - \omega^2 |1\rangle \big). $$

You can verify that it's indeed a POVM, i.e. $\sum_i |E_i\rangle\langle E_i| = \frac{3}{2}I$. Not any set of vectors is suitable for a POVM.

So, if the result of the corresponding POVM measurement is $E_1$ (label 1), then the input state certainly wasn't $|B\rangle$ and you return 1 as an answer $-$ this will satisfy the output requirement.

The corresponding POVM matrix is
$$ M = \frac{1}{\sqrt{3}}\left(\begin{array}{rrr} 1 & 1 & 1 \\ -1 & -\omega & -\omega^2 \end{array} \right) $$ Notice that we've renormalized vectors, i.e. $|E_i'\rangle = \sqrt{\frac{2}{3}}|E_i\rangle$, to satisfy $\sum_i |E_i'\rangle\langle E_i'| = I$.

To construct von Neumann measurement we must find "embedding" of this $M$ into some unitary matrix $M^\prime$. Embedding means that $M$ is just a submatrix of the matrix $M^\prime$.

You can take $$ M' = \frac{1}{\sqrt{3}}\left(\begin{array}{cccc} 1 & 1 & 1 & 0 \\ -1 & -\omega & -\omega^2 & 0 \\ 1 & \omega^2 & \omega & 0 \\ 0 & 0 & 0 & \sqrt{3} \end{array} \right) $$ Here the embedding is obvious - $M$ is the top left corner.

In a unitary matrix columns form an orthonormal basis - this is our von Neumann measurement. Our embedding means that the input state to this measurement is $|\psi\rangle \otimes |0\rangle$, where $|\psi\rangle$ is the given state which is either $|A\rangle,|B\rangle$ or $|C\rangle$.

How it corresponds to a POVM measurement $M$? In this case trivially $-$ label $i$ of $M'$ corresponds to the label $i$ of $M$ if $i=0,1,2$. The result labelled $i=3$ can't happen because $|\psi\rangle \otimes |0\rangle$ is orthogonal to $|11\rangle$.