2
$\begingroup$

The sinter.plot_error_rate function handles the plotting of the error rates sampled by sinter. Along with the estimated error rates, it highlights a region within which the true error rate is likely to be found.

The width of the region can be increased through the parameter highlight_max_likelihood_factor whose mathematical impact on the uncertainty is not very explicit in the documentation ("Hypothesis probabilities at most that many times as unlikely as the max likelihood hypothesis will be highlighted").

Papers citing stim are often vague on the interpretation of these regions (e.g. "shaded regions are statistical fit uncertainty" [1]). Papers from stim's author do include some interpretations (e.g. "Highlighted regions correspond to values that the underlying line fit can be forced to imply while increasing its sum of squares error by at most one (in the natural basis)" [2] or "Highlights correspond to hypotheses with a likelihood within a factor of 1000 of the max likelihood hypothesis" [3]) but they do not give much information to someone unfamiliar with statistics.

The base approach to compute estimate uncertainty from Monte Carlo sampling would be with confidence intervals, which from what I have tried look larger than the highlighted regions.

How are computed the highlighted regions given a value for highlight_max_likelihood_factor? How much confidence should I have that a particular data point lies within the highlighted area?


[1] : Logical quantum processor based on reconfigurable atom arrays

[2] : A Fault-Tolerant Honeycomb Memory

[3] : Less Bacon More Threshold

$\endgroup$

1 Answer 1

3
$\begingroup$

After looking in depth through sinter source code, I can offer some answers to my questions.

For each data point, the assumption is made that its value follows a binomial distribution $B(n, p)$ with $n$ the number of samples and $p$ the logical error rate we try to estimate. For large values of $n$, the number of hits $k$ (i.e. the number of logical errors sampled) should be close to the expectation $np$, which explains why the estimate derived from Monte Carlo sampling is $\frac{k}{n}$.

Instead of answering the question: "with these parameters $n$ and $p$ what is the probability we observe $k$ hits?", we want to answer: "given that we hit $k$ times out of $n$ draws, what is the likelihood that $p^{*}$ is the parameter of the underlying binomial distribution?".

To do that, sinter studies the probability density function of the binomial distribution: $$f_{n,k}(p) = \binom{n}{k}p^{k}(1-p)^{(n-k)}$$ as a function of $p$ which peaks at $\frac{k}{n}$. This means that the most likely value for the parameter of the underlying binomial distribution is $\frac{k}{n}$, but does not completely rule out other values for the parameter, as long as the corresponding likelihood given by the pdf is non-zero. The pdf is positive for all $p \in ]0, 1[$ so we still have to decide where to cut.

The range $[p_{low}, p_{high}]$ corresponding to the highlighted region is defined as follows: denoting $l^{*} = f_{n, k}(p^{*})$ the maximum likelihood (reached at $p^{*}=\frac{k}{n}$), define $p_{low}$ (resp. $p_{high}$) the probability $p$ lower (resp. higher) than $p^{*}$ such that $f_{n, k}(p_{low}) = f_{n, k}(p_{high}) = \frac{l^{*}}{h}$ where $h$ is the highlight_max_likelihood_factor argument.

Sinter highlighted regions

The confidence value linked to the interval $[p_{low}, p_{high}]$ is not constant, and most likely depends on $k$ and $n$ as well as $h$, which means each data point has its own confidence value.

I believe the confidence has to be computed for each value through:

$$ \int_{p_{low}}^{p_{high}} f_{n,k}(p)\,\mathrm{d}p $$

unless someone can derived a general expression.

With default value $h=1000$, the above integral numerically came out above 99% for all my tries.

This answer might be a bit handwavy, maybe someone can come with a more rigorous reasoning or point toward relevant statistics content.

$\endgroup$
1
  • 1
    $\begingroup$ This answer is exactly correct. Sinter computes the conditional probability P(hypothesis_probability|data) and highlights the hypothesis probabilities with conditional probabilities within 1000x of P(best_hypothesis|data). In other words, it highlights the region of probabilities where the Bayes factor is less than 1000x. This kind of estimate avoids several potential pitfalls of confidence intervals, such as having them be incorrectly symmetric around the avg near 0 or 1. It also generalizes to more complex situations, like line fit hypotheses. $\endgroup$ Commented Mar 15 at 9:51

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.