3
$\begingroup$

I am referring to the MS Quantum Katas, Measurements, 2.3 Peres/Wooters 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.

  1. 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

$\endgroup$
  • $\begingroup$ This is probably not an official solution because the details have mistakes. For example, $M'$ isn't unitary and $M$ can't be embedded to a unitary because the first row has norm >1. $\endgroup$ – Danylo Y May 4 at 7:09
  • $\begingroup$ Ah, It looks like this is what you were trying to retype here (problem B2) assets.codeforces.com/rounds/1116/contest-editorial.pdf You've missed some essential parts. $\endgroup$ – Danylo Y May 4 at 9:22
  • $\begingroup$ Actually I was referring to (render.githubusercontent.com/view/…), but this is very similar to your link (assets.codeforces.com/rounds/1116/contest-editorial.pdf) except for the normalization factor. Can you outline what I missed? $\endgroup$ – mbuchberger1967 May 4 at 22:33
  • $\begingroup$ Your link isn't working for me. Just read carefully my link. That solution is correct and has all the details. $\endgroup$ – Danylo Y May 4 at 23:25
1
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much for your answer and for taking the time! von_Neumann measurement is clarified now :) Your aswer makes a lot of sense for me, but it raises also some questions: 1. You are choosing $$M = \frac{1}{\sqrt{3}}\left(\begin{array}{rrr}1 & 1 & 1 \\ -1 & -\omega & -\omega^2 \end{array}\right)$$. But in the solution of the MS Kata the POVM is $$ M = \frac{1}{\sqrt{2}}left(\begin{array}{rrr}1 & 1 & 1 \\ 1 & \omega & \omega^2 \end{array}\right) $$ which is quite different. Can both solutions be correct or is only one of them correct? $\endgroup$ – mbuchberger1967 May 3 at 20:56
  • 1
    $\begingroup$ The solution you've presented is correct only in the quoted part. The rest has mistakes. For example, that $M'$ is not unitary at all. The norms of column vectors must be equal to 1. $\endgroup$ – Danylo Y May 3 at 21:18
  • 1
    $\begingroup$ Yes, any remaining values in $M'$ are good if columns are orthogonal and have norms 1. $\endgroup$ – Danylo Y May 3 at 21:19
  • 1
    $\begingroup$ Bra is a conjugate transpose of Ket, not just transpose. E.g. $\langle E_1| = \begin{bmatrix} 1 & -\omega^2\end{bmatrix}$. $\endgroup$ – Danylo Y May 4 at 23:20
  • 1
    $\begingroup$ We did embed it in a 3x3 unitary matrix, but we have to work with qubits, so the dimension must be power of 2. That's why we embed it further into 4x4. $\endgroup$ – Danylo Y May 10 at 7:52

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.