# Estimating Algorithmic Information Using Quantum Computing for Genomics Applications
## 4 Experimental Use Cases
### Estimation of Algorithmic Complexity
Quoting the paper \"The calculation presented herein will remain the best possible estimation for a measure of a similar nature with the technology available to date, as an exponential increase of computing resources will improve the length and number of strings produced only linearly if the same standard formalism of Turing machines used is followed.\" This immediately translates to the promise of mapping this exponentially growing states using quantum computation for the Turing machine enumeration. The symbol set of the binary alphabet is justified as the standard used in data encoding in current digital computation due to its simplicity. The argument for 5 state is more directly related to computability restrictions. Being uncomputable, every Turing machine in-principle needs to be run forever to know if it will halt. However, for small Turing machines, it is possible to enumerate and classify every Turing machine as either it halts with a maximum time step of \(B\), called the busy beaver runtime, or goes on forever. This value can be used to stop the computation and declare the enumeration as non-halting if the halt state is not reached in \(B\) steps. The value of \(B\) is known to be 107 for Turing machines with 4 states and 2 symbols. However, for 5 states the value is still unknown as there are too many cases to enumerate (26559922791424) and from partial enumerations so far, we know that the value is \(\geq 47,176,870\) steps. It is intractable to run so many machines for so long iterations. AC can be estimated using a far lower number of iterations when the \(B\) value is unknown, as the number of halting TM decay exponentially [35] with steps using the random variable model, \(P(S=k|S\leq S_{lim})=\alpha e^{-\lambda K}\). For the 5 state, 2 symbol case with \(S_{lim}=500\) it is \(6\times 10^{-173}\), thus can be safely ignored. The run limit should capture on the output tape almost all 12 bit strings thus allowing the calculation of their CTM values. For 13 bits strings, only half of all possible strings were captured in 500 steps, setting the block size limit using this method. The classical technique used various intelligent optimizations such as symmetries, look ahead and patterns, reducing the requirement to only 4/11 of all machines to be enumerated for 500 steps (if they did not halt before). This however still took 18 days on a supercomputer at the Centro Informatico Cientifico de Andalucia, Spain [13]. Analysis Using the QEAIT Framework  
Estimating the algorithmic probability using the CTM requires counting the number of Turing machines that generate a particular output and evolves to a specific state. This requires at the least a 2 symbol 2 state automata to differentiate between fixed-length strings, and the halting state, respectively. Our estimates for the QPULBA-2-2-1 requires over 54 qubits, constraining us from demonstrating the full pipeline on a quantum computing simulator. However, the number of logical qubits required is promisingly low compared to other representative quantum advantage pursuits, for example in cryptography and optimization. We discuss some theoretical results in this application to consolidate our use case. \(\#P\) is the computational complexity class of all problems which can be computed by counting Turing machines of polynomial time complexity [36]. [PERSON]'s theorem states the entire polynomial hierarchy \(PH\) is contained in \(P^{PP}\). Since \(P^{PP}=P^{\#P}\)[37] as a corollary, the entire polynomial hierarchy \(PH\) is also contained in \(P^{\#P}\). This signifies, if there is an efficient classical algorithm which could perform exact counting, then the polynomial hierarchy would collapse. Since we suspect this is not the case, it is unlikely that there exists a classical algorithm which can compute exact counting. Approximate counting can be done probabilistically with a polynomial runtime (with respect to the error and string size) with an _NP-complete_ oracle.