Quantum Computing Asked on February 16, 2021
$newcommand{expectation}[1]{mathop{mathbb{E}} left[ #1 right] }
newcommand{Var}{mathrm{Var}}$ From Nielsen & Chuang 10th edition page 261:
Consider a classical algorithm for the counting problem which samples uniformly and independently $k$ times from the search space, and let $X1, dots, X_k$ be the results of the oracle calls, that is, $X_j = 1$ if the $j$th oracle call revealed a solution to the problem, and $X_j = 0$ if the $j$th oracle call did not reveal a solution to the problem. This algorithm returns the estimate $S equiv N times sum_j X_j/k$ for the number of solutions to the search problem. Show that the standard deviation in $S$ is $bigtriangleup S = sqrt{ M(N − M)/k }$.
The question goes on but I’m already stuck here. To get to the standard deviation first I’m trying to calculate the variance via:
$$
Var(S) = expectation{S^2} – expectation{S}^2 tag1label1
$$
$$
expectation{S} = N times sum_j expectation{X_j}/k = frac{N}{k} sum_{j=1}^k frac{M}{N} = M tag2label2
$$
Therefore $S$ is an unbiased estimator of M.
Now:
$$
expectation{S}^2 = expectation{left( N times sum_j X_j/k right)^2} = frac{N^2}{k^2} expectation{left( sum_j X_j right)^2} = frac{N^2}{k^2} sum_{i=1}^k sum_{j=1}^k expectation{X_i X_j} tag3label3
$$
To calculate $expectation{X_i X_j}$ we need to consider 2 cases:
Case 1 happens $k$ times, therefore case 2 must happen $k^2-k$ times. So we have:
$$
expectation{S}^2 = frac{N^2}{k^2} left( k frac{M}{N} + (k^2 – k) frac{M}{N} frac{M-1}{N-1} right) tag6label6
$$
Putting eqref{2} and eqref{6} together, after some tedious algebra I got:
$$
Var(S) = frac{M}{k} frac{(N-M)(N-k)}{N-1} tag7label7
$$
If $k ll N$, then eqref{7} is close to what is stated in the original question but is not exactly it. Can anyone spot where I made the blunder?
Since the classical algorithm samples "uniformly and independently $?$ times from the search space", equation $(5)$ should be, $P(X_i=1, X_j=1)= P(X_i=1)P(X_j=1)=frac{M^2}{N^2}$ instead. If you substitute $(5)$ with this, you would arrive at the book's standard deviation.
Correct answer by Nan on February 16, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP