# Estimating Algorithmic Information Using Quantum Computing for Genomics Applications
## 4 Experimental Use Cases
### Estimation of Algorithmic Complexity  
In [13], the coding theorem method is used to estimate the algorithmic complexity of short strings. This forms the classical kernel that we accelerate with our quantum formulation. Estimation of the algorithmic complexity of sequences is actively researched by [PERSON] and been applied to diverse fields such as evaluations of structures in genomics [27], psychometrics [28], cellular automata [29; 30], graph theory, economic time series [31; 32], and complex networks [28]. It is thus promising to develop a quantum computing approach, as any benefit will be magnified by the wide applicability of this technique. In this use case, we explore the possibility to accelerate the estimation of algorithmic (Kolmogorov) complexity. As defined formally in Equation (1), this is an absolute measure of the information content of a string. A seminal result in estimating AC [33] via Experimental Algorithmic Information Theory (EAIT)-based approach considers the property that many of the algorithmic metrics are semi-computable and converges in the limit. This is crucial, as otherwise, any hope of approximating these quantities with computing models would not be possible. An important distinction can be made with 'quantum Kolmogorov complexity' which deals with the metrics to define the complexity of a specific quantum state and its preparation process using quantum gate. Our focus in this research is on 'quantum computing approaches for estimation of the algorithmic complexity of classical sequences'. Estimating the complexity of real-world data needs a scalable approach for long data streams or graphs. The complexity of long strings can be estimated using the block decomposition method as defined in Equation (7). The estimation of complexity by BDM is compatible with lossless compression algorithms but can go beyond the scope of Shannon entropy-based methods, which are widely used to estimate AC. Entropy=based techniques can capture simple statistical patterns (repetitions), while algorithmic patterns (such as 12345... or 246810...), are characterized as having maximum randomness and the highest degree of incompressibility by these methods. These methods are not invariant to language choice and are therefore not robust enough to measure complexity or randomness as for AIT-based methods. In contrast, techniques based on algorithmic metrics can detect causal gaps in entropy-based methods (e.g., Shannon entropy or compression algorithms). BDM is a smooth transition between the Kolmogorov entropy and Shannon entropy, depends respective on whether the size of \(s_{i}\) is same as \(s\) or \(1\). Calculating the CTM value gets exponentially difficult with string size, thus the BDM is the method of choice for using algorithmic metrics for causal inferences. However, for longer data such as real-world use cases, BDM starts getting less effective (for a fixed block size) and fails to find causal links beyond the block size. To maintain the advantage over the simpler data-driven approaches we need to have an application motivated block size, e.g., how far in a genome can one gene affect the other. This motivates our research in using quantum-acceleration to extend the lookup table of the Algorithmic Complexity of Short Strings (ACSS) [34] built using the CTM technique. The quantum technique is not to supplant the BDM but to power it with the resources from the quantum-accelerated CTM. The ACSS database is constructed by approximating the output frequency distribution for Turing machines with 5 states and 2 symbols generating the algorithmic complexity of strings of size \(\leq 12\) over \(\approx 500\) iterations. These numbers of 5, 2, 12 and 500 are arbitrary from the BDM application perspective and fixed based on the computational resource.