# Estimating Algorithmic Information Using Quantum Computing for Genomics Applications
## 2 Background
### Algorithmic Information  
Algorithmic information theory (AIT) [6] allows studying the inherent structure of objects without reference to a generating distribution (often assumed erroneously as the uniform prior in statistical machine learning). The theory originated when [PERSON] [7], [PERSON] [8], and [PERSON] [9] looked at information, probability and statistics through the algorithmic lens. The theory has now become a central part of theoretical computer science [10]. While AIT metrics are ubiquitous, most metrics are uncomputable. Estimating these using approximate methods is often intractable beyond small cases even on classical supercomputers. Thus, while in the field of theoretical computer science, these fundamental concepts are valuable for proofs, their applicability to real-world data and use cases remain very limited. The definitions and applications of some of these AIT metrics that are used in this research, are explained here. * **Algorithmic complexity:** Algorithmic complexity (AC), also called Kolmogorov complexity, is the length of the shortest program that produces a particular output and halts on a specific TM. Formally, it is defined as: \[AC_{T}(s)=\min:\{l(p),T(p)\to s\}\] (1) where \(T\) is a TM, \(p\) is a program, \(l(p)\) is the length of the program, \(s\) is a string, and \(T(p)\to s\) denotes the fact that \(p\) executed on \(T\) outputs \(s\) and halts. AC is not a computable quantity in the general case due to fundamental limits of computations that arise from the halting problem (i.e., it is impossible to determine whether any given program will ever halt without actually running this program, possibly for infinite time). However, it has bounded lower-approximate property, i.e., if we can find a program \(p_{L}\) in a language \(L\) (e.g., Java, Assembly), \(l(p_{L})\geq l(p)\). Since AC depends on the particular model of computation (i.e., the TM and the language), it is always possible to design a language where a particular string \(s\) will have a short encoding no matter how random. However, the invariance theorem guarantees that, there exists a constant additive factor \(c_{T1\to T2}\) independent of \(s\), such that \[AC_{T2}\leq AC_{T1}+c_{T1\to T2}\] (2) This constant is the compiler length for translating any arbitrary program \(p_{T1}\) for \(T1\) to \(p_{T2}\) for \(T2\). * **Algorithmic probability:** Algorithmic probability (AP), also called Solomonoff's probability, is the chance that a randomly selected program will output \(s\) when executed on \(T\). The probability of choosing such a program is inversely proportional to the length of the program. \[AP_{T}(s)=\sum_{p:T(p)\to s}2^{-l(p)}\] (3) Thus, the largest contribution to the term comes from the shortest program that satisfies the condition. It is uncomputable for the same reasons as AC. AP is related to AC via the following law: \[AC_{T}(s)=-log_{2}(AP_{T}(s))+c\] (4) i.e., if there are many programs that generate a dataset, then there has to be also a shorter one. The arbitrary constant is dependent on the choice of a programming language. AP can be approximated by enumerating programs on a TM of a given type and counting how many of them produce a given output and then divide by the total number of machines that halt. When exploring machines with \(n\) symbols and \(m\) states algorithmic probability of a string \(s\) can be approximated as follows: \[D(n,m)(s)=\frac{|T\in(n,m):T\text{ outputs }s|}{|T\in(n,m):T\text{ halts }|}\] (5) The coding theorem method (CTM) [11] approximates the AC as: \[CTM(n,m)(s)=-log_{2}D(n,m)(s)\] (6) Calculating CTM, although theoretically computable, is extremely expensive in terms of computation time. The space of possible Turing machines may span thousands of billions of instances. Block decomposition method (BDM) approximates the CTM value for an arbitrarily large object by decomposing into smaller slices of appropriate sizes for which CTM values are known and aggregated back to a global estimate.