Suppose Alice and Bob share the $2n$-qubits state $$|\phi _{x,y,b} \rangle = \frac{1}{2}(|x\rangle + (-1)^b |y\rangle)$$

where $x,y$ are $2n$-length strings of $0$ and $1$, $b$ is a bit, and $x \ne y$.

Alice holds the first $n$ qubits, and bob holds the other $n$ qubits, but they do not know what state they are sharing (they don't know $x,y,b$).

Furthermore, there is Charlie who knows $x,y$ but wants to learn $b$.

Alice and Bob can each send one classical message to Charlie.

I want to think about a protocol that helps Charlie learn $b$.

It seems that I can use super-dense coding in some sort of way, but I'm having trouble to understand how.

Help would be appreciated.


1 Answer 1


Get Alice and Bob to measure all their qubits in the $X$ basis, and send the $\pm 1$ results to Charlie. The combined answer is a bit string $w$.

Charlie discards all the results associated with qubits $i$ where $x_i=y_i$. On the remaining $k$ qubits, Alice and Bob shared $$ |\psi\rangle=|z\rangle+(-1)^b|\bar z\rangle $$ for $z\in\{0,1\}^k$. What's the result of an $X$ measurement? \begin{align*} \langle+|^{\otimes k}Z^{w_k}|\psi\rangle&=\langle+|^{\otimes k}Z^{w_k}Z_1^b(|z\rangle+X^{\otimes k}|z\rangle) \\ &=\langle+|^{\otimes k}(I+(-1)^{|w_k|+b}X^{\otimes k})Z^{w_k}Z_1^b|z\rangle \\ &=(-1)^{z\cdot w_k+z_1}\langle+|^{\otimes k}(I+(-1)^{|w_k|+b}X^{\otimes k})|z\rangle \\ &=(-1)^{z\cdot w_k+z_1}\langle+|^{\otimes k}z\rangle(1+(-1)^{|w_k|+b}) \end{align*} You can only get an answer $w_k$ (the relevant $k$ bits of $w$) if $|w_k|+b$ is even. In other words, $b=|w_k|\text{ mod }2$.

For example, imagine that Alice and Bob initially share $$ |0011\rangle+(-1)^b|1101\rangle. $$ and assume they get the answers +++-, which they send to Charlie. Charlie knows $w_k=000$ and $z=001$, ignoring the last bit because they're the same for $x$ and $y$. Since $w_k$ is even, $b=0$. Basically, we're claiming that in this case $$ \langle +++|(|001\rangle-|110\rangle)=0, $$ i.e. we could never have got the +++ answer if $b=1$.

  • $\begingroup$ Isn't there a (vanishingly small) probability that after Hadamarding, all of Alice and Bob's measurements are +1? $\endgroup$ Feb 26 at 16:09
  • $\begingroup$ yes. It shouldn't be a problem. Or at last wouldn't be if I hadn't missed out a term... $\endgroup$
    – DaftWullie
    Feb 26 at 16:20
  • $\begingroup$ Oh! Charlie gets to ignore when $x\oplus y=0$ because he knows $x$ and $y$; he just doesn't know the phase. Unlike in the examples that came to my mind initially, where $x$ and $y$ are not known and one only had access to $d$ such that $d\cdot (x\oplus y)=0$. $\endgroup$ Feb 26 at 17:13
  • $\begingroup$ Could you elaborate on how you calculated $\langle+|^{\otimes k}Z^{w_k}|\psi\rangle$, because I'm not sure I understand. $\endgroup$
    – Gabi G
    Feb 27 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.