# Estimating Algorithmic Information Using Quantum Computing for Genomics Applications
## 4 Experimental Use Cases
### Estimation of Algorithmic Complexity
Thus, if a quantum algorithm could perform approximate counting in polynomial time, then that would imply that \(NP\subseteq BQP\), which is implausible. However, quantum computing might provide a polynomial speedup in solving counting problems with respect to classical computers. The quantum counting algorithm, boson sampling and post-selection are three ways that hold promise in this direction. We discuss the later two possibilities before evaluating the quantum counting approach. Postselection is the process of ignoring all outcomes of a computation in which an event did not occur, selecting specific outcomes after (post) the computation. However, postselection is not considered to be a feature that a realistic computer (classical or quantum)would possess, but nevertheless are interesting to study from a theoretical perspective. The complexity class \(PostBQP\), is the class \(BQP\) with postselection. It was shown [38] that \(BQP\subseteq PostBQP=PP\), and as a corollary \(PH\subseteq P^{PostBQP}\), as \(P^{PostBQP}=P^{\sharp P}\). This means that if there was an efficient way to postselect with a quantum computer, we would be able to solve many of the problems which are intractable classically, including exact counting. However, it is not clear how to practically design such an algorithm. Boson sampling [39] is a proposed (non-universal) model of quantum computation which involves sampling from a probability distribution of non-interacting bosons. Sampling from bosonic or fermionic distributions can be done in polynomial time [40] using a universal quantum computer. For this it is required to calculate the permanent of a matrix encoding the state probabilities of the bosonic system. Calculating the permanent of a matrix, or even approximating it, is a _#P-hard_ problem. The existence of a classical algorithm which could efficiently compute exact (or approximate) boson sampling would imply that the polynomial hierarchy collapses to the third level, which is unlikely. Thus, large boson sampling computers would allow us to solve hard problems such as the exact or approximate counting. Recently, quantum supremacy [41] was demonstrated using boson sampling; however, feasibility of practical applications are yet to be explored. The quantum counting approach is more malleable for concrete circuit design for gate-based quantum computing. This was proposed [14] for accelerating the speed prior, another important AIT metric. Efficient approximations of Solomonoff prior would provide a powerful form of compression and prediction, for example from the artificial general intelligence agent perspective. The speed prior, as defined in Equation (8), accounts for the running time of each program on a UTM, in contrast to running each program until it halts, as in the Solomonoff prior. The speed prior, \(S\), is an approximation, yet takes time scaling exponentially in the length of the largest program. Computing \(S\) essentially involves counting the number of programs of given length that runs in polynomial time. Thus, this is an NP problem, and the counting is _#P_. It was conjectured that \(S\) is _#P-hard_, such that if there did exist a quantum algorithm which could solve \(S\) in polynomial time, then the polynomial hierarchy would collapse. However, a fixed length speed prior can yield a quadratic speedup using quantum computing compared to the classical method. The speedup of both the CTM and speed prior depends on the quantum counting algorithm. Here, we present the algorithm for the quantum-accelerated CTM. ```
1 Given string \(s\);
2 for\(i<t\)do
3 Run QPULBA step;
4 end for
5\(num_{s}:=QCount(tape=s)\);
6 for\(i<t\)do
7 Run QPULBA step;
8 end for
9\(num_{h}:=QCount(state=halt)\);
10 Result:\(CTM(s):=-log_{2}(num_{s}/num_{h})\)
```  
**Algorithm 1**Quantum counting CTM algorithm  
Please note that we need to run the superposition of automata twice, since the quantum state collapses on measurement.