# Estimating Algorithmic Information Using Quantum Computing for Genomics Applications
## 2 Background
### Algorithmic Information
The algorithmic complexity of these small slices are precomputed and make into a look-up table using CTM. The BDM aggregates this as: \[BDM(s)=\sum_{s_{i}}CTM(s_{i})\] (7) where \(CTM(s_{i})\) is the approximate algorithmic complexity of the string \(s_{i}\) and \(s=\cup_{i}s_{i}\) i.e., the \(s_{i}\) together forms the string \(s\). Small variations on the method of dividing the string into blocks becomes negligible in the limit, e.g., to take a sliding window or blocks. * **Universal distribution:** The universal a priori probability distribution (UD) is the distribution of the algorithmic probability of all strings of a specific size. It can be calculated for all computable sequences. This mathematically formalizes the notion of Occam's razor and [PERSON] principle of multiple explanations using modern computing theory for the Bayesian prediction framework. It explains observations of the world by the smallest computer program that outputs those observations, thus, all computable theories which describe previous observations are used to calculate the probability of the next observation, with more weight put on the shorter computable theories. This is known as [PERSON]'s theory of inductive inference. * **Speed prior:** The universal distribution does not take into account the computing resource (tape and time) required when assigning the probability of certain data. This does not match our intuitive notion of simplicity (Occam's razor). [PERSON] proposed [12] the measure speed prior (SP), derived from the fastest way of computing data. \[SP_{T}(s)=\sum_{z=1}^{\infty}2^{-z}\sum_{p:T(p,z)\to s}2^{-l(p)}\] (8) where program \(p\) generates an output with prefix \(s\) after \(2^{z-l(p)}\) instructions. Thus, it is even more difficult to estimate it as all possible runtimes for all possible programs need to be taken into account. * **Omega number:** The Omega number, also called Chaitin constant or halting probability of a prefix-free TM \(T\) is a real number that represents the probability that a randomly constructed program will halt. \[\Omega_{T}=\sum_{p}2^{-|p|}\] (9)  
While many of the algorithmic metrics discussed here are uncomputable, most of them are either upper or lower semi-computable, i.e., the value of the metric can be approached in the limit from above or below by enumerating the Turing machines [13]. These approximations can further be calculated by time-bounding the TMs for a maximum number of cycles. Though time-bounded algorithmic metrics were researched before for various applications, pragmatically they remain intractable for real-world problem sizes for classical algorithms, motivating this research to explore alternative quantum approaches. It is crucial to highlight that most algorithmic metrics are higher in the computing hierarchy than the more familiar polynomial-time (P) and non-deterministic polynomial time (NP) complexity classes. Since quantum computers are not expected to provide exponential speedup for NP-hard problems, we expect at best a quantum (Grover) search type polynomial speedup. In this research, we explore the possible advantages for some specific cases of the quantum model and their associated applications. Often polynomial speedup between different computing models of the same power are heavily influenced by the formulation of a problem and the model itself. For example, it is highly non-trivial to do a binary search on a Turing machine without a random-access-memory. In this work we ensure that the quantum algorithm formulation retains the speedup. Secondly, for real-world data, often a polynomial speedup is enough in making an application tractable. In the era of small-scale quantum computers, it is thus important to explore polynomial speedups as well and better understand average case complexity and other linear and constant factors in the complexity. Thus, an experimental approach using available small-scale quantum processors or quantum simulators aids in appreciating the exact cost involved in implementing the quantum algorithm in the circuit model.