The Quasi-probability Method and Applications for Trace Reconstruction

In the trace reconstruction problem, one attempts to reconstruct a fixed but unknown string $x$ of length $n$ from a given number of traces $\tilde{x}$ drawn iid from the application of a noisy process (such as the deletion channel) to $x$. The best known algorithm for the trace reconstruction from the deletion channel is due to Chase, and recovers the input string whp given $\exp(\tilde{O}(n^{1/5}))$ traces [Cha21b]. The main component in Chase's algorithm is a procedure for k-mer estimation, which, for any marker $w$ in $\{0, 1\}^k$ of length $k$, computes a "smoothed" distribution of its appearances in the input string $x$ [CGL+23, MS24]. Current k-mer estimation algorithms fail when the deletion probability is above $1/2$, requiring a more complex analysis for Chase's algorithm. Moreover, the only known extension of these approaches beyond the deletion channels is based on numerically estimating high-order differentials of a multivariate polynomial, making it highly impractical [Rub23]. In this paper, we construct a simple Monte Carlo method for k-mer estimation which can be easily applied to a much wider variety of channels. In particular, we solve k-mer estimation for any combination of insertion, deletion, and bit-flip channels, even in the high deletion probability regime, allowing us to directly apply Chase's algorithm for this wider class of channels. To accomplish this, we utilize an approach from the field of quantum error mitigation (the process of using many measurements from noisy quantum computers to simulate a clean quantum computer), called the quasi-probability method (also known as probabilistic error cancellation) [TBG17, PSW22]. We derive a completely classical version of this technique, and use it to construct a k-mer estimation algorithm. No background in quantum computing is needed to understand this paper.