Ex7 6
$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\def\tr{\mathord{\mbox{tr}}}\mathbf{Exercise\ 7.6}$
Show directly that, in the distributed computation algorithm of section 7.5.4, when $u = v$, $\abs{\braket{x,y}{\psi}}^2 = 0$ for all $x \ne y$.
page revision: 0, last edited: 18 Nov 2012 19:32
In the Distributed Computation algorithm it was shown that if $u=v$ then with probability 1 Alice measures $x$ and Bob measures $y$ such that $x=y$. In fact, it can be shown directly that $x \neq y$ is measured with probability 0.
By the Measurement Postulate the probability of measuring the state $\ket{\psi}$ to be $\ket{x,y}$ is $|P_{xy}\ket{\psi}|^2$ where $P_{xy} = \ket{xy}\bra{xy}$ is the projection. The probability is then the square of the amplitude of $\ket{x,y}$ in $\ket{\psi}$:
(1)We have from the Distributed Computation algorithm that
(2)If $u=v$ this becomes
(3)If $x\neq y$ then at least in one bit position $x$ and $y$ have different bit values in the binary representation. Let's say they differ in the $k$'th bit. Then we can split the sum into two parts where the $k$'th bit is either 1 or 0 (& is bitwise AND):
(4)Since the bits $x_k \neq y_k$ we have
(5)and $\braket{xy}{\psi} = 0$. The same argument goes for any other bit position that differs in $x$ and $y$.