2
$\begingroup$

I am going through the paper, Solving the graph-isomorphism problem with a quantum annealer, by Hen et. al. In the last line of the second paragraph of the second column of page 2, it says,

Since errors of the various measured quantities are inversely proportional to the square root of the number of measurements, this number will be determined from the needed resolution.

I would like to know the reference of the statement that - errors of the various measured quantities are inversely proportional to the square root of the number of measurements.

Thanks.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ I can't speak to this specific application, but usually such statements can just come from tail bounds like Chernoff or Hoeffding. Let $X \in [0,1]$; let $\bar{X}$ be the average of $n$ independent draws of $X$. For a given "margin of error" $\epsilon$, let $\delta = \Pr[|\bar{X}-\mathbb{E}X| > \epsilon]$. As usually stated, Hoeffding implies that $\delta \leq 2e^{-2n \epsilon^2}$, but often more useful is the restatement $\epsilon \leq \sqrt{\frac{1}{n} \frac{\ln{\frac{2}{\delta}}}{2}}$. $\endgroup$ – usul May 28 '14 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.