HomeWork20252d

HomePage | Memberswill go by tor | RecentChanges | Join |

Let b=0,1b =0,1 then

H(b⟩)=12∑ x=0,1(−1) bxx⟩H({b}\rangle) = \frac{1}{\sqrt{2}} \sum_{x=0,1} {(-1)^{b x} {x}\rangle}

Initially nn qbit 0⋯0⟩{0 \cdots 0 }\rangle

Apply H⊗⋯⊗HH \otimes \cdots \otimes H to nn qbit

H(0⟩)⊗⋯⊗H(0⟩)=(12∑ b 1=0,1b 1⟩)⊗⋯⊗(12∑ b n=0,1b n⟩)=12 n2∑ b 1,⋯,b n∈{0,1}b 1⋯b n⟩H({0}\rangle) \otimes \cdots \otimes H({0}\rangle) = \left(\frac{1}{\sqrt{2}} \sum_{b_1 = 0,1} {b_1}\rangle \right) \otimes \cdots \otimes \left(\frac{1}{\sqrt{2}} \sum_{b_n =0,1} {b_n}\rangle \right)=\frac{1}{2^{\frac{n}{2}}}\sum_{b_1, \cdots, b_n \in \{0,1\}} {b_1 \cdots b_n}\rangle

Apply O fO_f

O f(12 n2∑ b 1,⋯,b n∈{0,1}b 1⋯b n⟩)=12 n2∑ b 1,⋯,b n∈{0,1}O f(b 1⋯b n⟩)=12 n2∑ b 1,⋯,b n∈{0,1}(−1) f(b 1⋯b n)b 1⋯b n⟩O_f\left(\frac{1}{2^{\frac{n}{2}}} \sum_{b_1,\cdots,b_n \in \{0,1\}} {b_1 \cdots b_n}\rangle \right)= \frac{1}{2^{\frac{n}{2}}} \sum_{b_1,\cdots,b_n \in \{0,1\}} O_f\left({b_1 \cdots b_n}\rangle \right)= \frac{1}{2^{\frac{n}{2}}} \sum_{b_1,\cdots,b_n \in \{0,1\}} (-1)^{f(b_1 \cdots b_n)} {b_1 \cdots b_n}\rangle

Apply H⊗⋯⊗HH \otimes \cdots \otimes H to nn qbit

12 n2∑ b 1,⋯,b n∈{0,1}(−1) f(b 1⋯b n)H(b 1⟩)⊗⋯⊗H(b n⟩) =12 n2∑ b 1,⋯,b n∈{0,1}(−1) f(b 1⋯b n)(12∑ x 1=0,1(−1) b 1x 1x 1⟩)⊗⋯⊗(12∑ x n=0,1(−1) b nx nx n⟩) =12 n∑ b1,⋯,b n=0,1∑ x 1,⋯,x n=0,1(−1) f(b 1⋯b n)(−1) b 1x 1⋯(−1) b nx nx 1⋯x n⟩ =12 n∑ x1,⋯,x n=0,1∑ b 1,⋯,b n=0,1(−1) f(b 1⋯b n)(−1) b 1x 1⋯(−1) b nx nx 1⋯x n⟩\begin{aligned}&\frac{1}{2^{\frac{n}{2}}} \sum_{b_1,\cdots,b_n \in \{0,1\}} (-1)^{f(b_1 \cdots b_n)} H({b_1}\rangle) \otimes \cdots \otimes H({b_n}\rangle)\\&=\frac{1}{2^{\frac{n}{2}}} \sum_{b_1,\cdots,b_n \in \{0,1\}} (-1)^{f(b_1 \cdots b_n)} \left(\frac{1}{\sqrt{2}} \sum_{x_1=0,1} (-1)^{b_1 x_1} {x_1}\rangle \right) \otimes \cdots \otimes \left(\frac{1}{\sqrt{2}} \sum_{x_n=0,1} (-1)^{b_n x_n} {x_n}\rangle \right)\\&=\frac{1}{2^n} \sum_{b1,\cdots,b_n=0,1} \sum_{x_1,\cdots,x_n=0,1} (-1)^{f(b_1 \cdots b_n)} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle\\&=\frac{1}{2^n} \sum_{x1,\cdots,x_n=0,1} \sum_{b_1,\cdots,b_n=0,1} (-1)^{f(b_1 \cdots b_n)} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle \end{aligned}

If ff is constant 0,

12 n∑ x1,⋯,x n=0,1∑ b 1,⋯,b n=0,1(−1) f(b 1⋯b n)(−1) b 1x 1⋯(−1) b nx nx 1⋯x n⟩ =12 n∑ x1,⋯,x n=0,1∑ b 1,⋯,b n=0,1(−1) b 1x 1⋯(−1) b nx nx 1⋯x n⟩\begin{aligned}&\frac{1}{2^n} \sum_{x1,\cdots,x_n=0,1} \sum_{b_1,\cdots,b_n=0,1} (-1)^{f(b_1 \cdots b_n)} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle\\&= \frac{1}{2^n} \sum_{x1,\cdots,x_n=0,1} \sum_{b_1,\cdots,b_n=0,1} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle \end{aligned}

The quantum prob of x 1⋯x n⟩{x_1 \cdots x_n}\rangle is

12 n∑ b 1,⋯,b n=0,1(−1) b 1x 1⋯(−1) b nx n\frac{1}{2^n} \sum_{b_1,\cdots,b_n= 0 , 1} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n}

If some x k=1x_k = 1

∑ b 1,⋯,b n=0,1(−1) b 1x 1⋯(−1) b nx nx 1⋯x n⟩ =∑ b 1,⋯,b k−1,b k+1,⋯b n=0,1∑ b k=0,1(−1) b 1x 1⋯(−1) b kx k⋯(−1) b nx nx 1⋯x n⟩ =∑ b 1,⋯,b k−1,b k+1,⋯b n=0,1∑ b k=0,1(−1) b 1x 1⋯(−1) b k⋯(−1) b nx nx 1⋯x n⟩ =∑ b 1,⋯,b k−1,b k+1,⋯b n=0,1(−1) b 1x 1⋯(1+(−1))⋯(−1) b nx nx 1⋯x n⟩ =∑ b 1,⋯,b k−1,b k+1,⋯b n=0,1(−1) b 1x 1⋯0⋯(−1) b nx nx 1⋯x n⟩ =0\begin{aligned}&\sum_{b_1,\cdots,b_n=0,1} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle\\&=\sum_{b_1, \cdots, b_{k-1}, b_{k+1}, \cdots b_n=0,1} \sum_{b_k=0,1} (-1)^{b_1 x_1} \cdots (-1)^{b_k x_k} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle\\&=\sum_{b_1, \cdots, b_{k-1}, b_{k+1}, \cdots b_n=0,1} \sum_{b_k=0,1} (-1)^{b_1 x_1} \cdots (-1)^{b_k} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle\\&=\sum_{b_1, \cdots, b_{k-1}, b_{k+1}, \cdots b_n=0,1} (-1)^{b_1 x_1} \cdots \left(1+(-1)\right) \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle\\&=\sum_{b_1, \cdots, b_{k-1}, b_{k+1}, \cdots b_n=0,1} (-1)^{b_1 x_1} \cdots 0 \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle \\&=0\end{aligned}

Therefore

12 n∑ x 1,⋯,x n=0,1∑ b 1,⋯,b n=0,1(−1) b 1x 1⋯(−1) b nx nx 1⋯x n⟩ =12 n∑ b 1,⋯,b n=0,1(−1) 0⋯(−1) 00⋯0⟩ =12 n∑ b 1,⋯,b n=0,10⋯0⟩ =0⋯0⟩\begin{aligned}&\frac{1}{2^n} \sum_{x_1,\cdots,x_n=0,1} \sum_{b_1,\cdots,b_n=0,1} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle \\&= \frac{1}{2^n} \sum_{b_1,\cdots,b_n =0,1} (-1)^0 \cdots (- 1)^0 {0 \cdots 0}\rangle \\&= \frac{1}{2^n} \sum_{b_1,\cdots,b_n=0,1} {0 \cdots 0}\rangle \\&= {0 \cdots 0}\rangle\end{aligned}

Similarly if ff is constant 1,

12 n∑ x 1,⋯,x n=0,1∑ b 1,⋯,b n=0,1(−1) f(b 1⋯b n)(−1) b 1x 1⋯(−1) b nx nx 1⋯x n⟩=−0⋯0⟩\frac{1}{2^n} \sum_{x_1,\cdots,x_n=0,1} \sum_{b_1,\cdots,b_n=0,1} (-1)^{f(b_1 \cdots b_n)} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle = -{0 \cdots 0}\rangle

So if ff is constant then 0⋯0⟩{0 \cdots 0}\rangle is 100% possibility

Let AA be the set of b 1⋯b n⟩{b_1 \cdots b_n}\rangle whose ff is 0. Let BB be the set of b 1⋯b n⟩{b_1 \cdots b_n}\rangle whose ff is 1

12 n∑ x 1,⋯,x n=0,1∑ b 1,⋯,b n=0,1(−1) f(b 1⋯b n)(−1) b 1x 1⋯(−1) b nx nx 1⋯x n⟩ =12 n(∑ x 1,⋯,x n=0,1∑ (b 1,⋯,b n)∈A(−1) b 1x 1⋯(−1) b nx nx 1⋯x n⟩−∑ x 1,⋯,x n=0,1∑ (b 1,⋯,b n)∈B(−1) b 1x 1⋯(−1) b nx nx 1⋯x n⟩)\begin{aligned}&\frac{1}{2^n} \sum_{x_1,\cdots,x_n=0,1} \sum_{b_1,\cdots,b_n=0,1} (-1)^{f(b_1 \cdots b_n)} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle\\&= \frac{1}{2^n} \left( \sum_{x_1,\cdots,x_n=0,1} \sum_{(b_1, \cdots, b_n) \in A} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle - \sum_{x_1,\cdots,x_n=0,1} \sum_{(b_1, \cdots, b_n) \in B} (-1)^{b_1 x_1} \cdots (-1)^{b_n x_n} {x_1 \cdots x_n}\rangle \right)\end{aligned}

Let Count(A)Count(A), Count(B)Count(B) mean the size of the set AA and BB therefore Count(A)+Count(B)=2 nCount(A)+Count(B) = 2^n . The coefficient of 0⋯0⟩{0 \cdots 0}\rangle is

12 n(∑ (b 1,⋯,b n)∈A(−1) b 1⋅0⋯(−1) b n⋅00⋯0⟩−∑ (b 1,⋯,b n)∈B(−1) b 1⋅0⋯(−1) b n⋅00⋯0⟩) =12 n(∑ (b1,⋯,b n)∈A0⋯0⟩−∑ (b1,⋯,b n)∈B0⋯0⟩) =12 n(Count(A)0⋯0⟩−Count(B)0⋯0⟩) =Count(A)−Count(B)2 n0⋯0⟩\begin{aligned}&\frac{1}{2^n} \left( \sum_{(b_1, \cdots, b_n) \in A} (-1)^{b_1 \cdot 0} \cdots (-1)^{b_n \cdot 0} {0 \cdots 0}\rangle - \sum_{(b_1, \cdots, b_n) \in B} (-1)^{b_1 \cdot 0} \cdots (-1)^{b_n \cdot 0} {0 \cdots 0}\rangle \right)\\&=\frac{1}{2^n} \left( \sum_{(b1,\cdots,b_n)\in A} {0 \cdots 0}\rangle-\sum_{(b1,\cdots,b_n)\in B} {0 \cdots 0}\rangle \right)\\&=\frac{1}{2^n} \left( Count(A) {0 \cdots 0}\rangle - Count(B) {0 \cdots 0}\rangle\right)\\&=\frac{Count(A)-Count(B)}{2^n} {0 \cdots 0}\rangle\end{aligned}

So if ff is balance then the coefficient of 0⋯0⟩{0 \cdots 0}\rangle is 0 aka 0% possibility