The LGZ algorithm for Topological Data Analysis via computing Betti Numbers is a quantum algorithm that relies on sampling random eigenvalues of an appropriate linear operator. The expected fraction of these eigenvalues that are 0 is equal to the normalised Betti Number.
My question concerns how many samples of random eigenvalues one would need to be confident that the estimator (i.e. the ratio of eigenvalues that are 0 in the sample) is close to its true value (the normalised Betti Number.
Abstracting away all details of quantum algorithms, the problem is effectively the following: Suppose we have a coin with some unknown probability of heads (p).
We make N flips of the coin with the aim of knowing p to within error ±ϵ, and with probability of failure <δ. For a given target of (ϵ,δ), how many flips N do we need to make?