Estimating Algorithmic Information Using Quantum Computing for Genomics Applications

Sarkar, A.; Al-Ars, Z.; Bertels, K.L.M.

doi:10.3390/app11062696

Estimating Algorithmic Information Using Quantum Computing for Genomics Applications

Title

Estimating Algorithmic Information Using Quantum Computing for Genomics Applications

Author

Sarkar, A. (TU Delft Computer Engineering)
Al-Ars, Z. (TU Delft Computer Engineering)
Bertels, K.L.M. (Universidade do Porto)

Date

2021

Abstract

Inferring algorithmic structure in data is essential for discovering causal generative models. In this research, we present a quantum computing framework using the circuit model, for estimating algorithmic information metrics. The canonical computation model of the Turing machine is restricted in time and space resources, to make the target metrics computable under realistic assumptions. The universal prior distribution for the automata is obtained as a quantum superposition, which is further conditioned to estimate the metrics. Specific cases are explored where the quantum implementation offers polynomial advantage, in contrast to the exhaustive enumeration needed in the corresponding classical case. The unstructured output data and the computational irreducibility of Turing machines make this algorithm impossible to approximate using heuristics. Thus, exploring the space of program-output relations is one of the most promising problems for demonstrating quantum supremacy using Grover search that cannot be dequantized. Experimental use cases for quantum acceleration are developed for self-replicating programs and algorithmic complexity of short strings. With quantum computing hardware rapidly attaining technological maturity, we discuss how this framework will have significant advantage for various genomics applications in meta-biology, phylogenetic tree analysis, protein-protein interaction mapping and synthetic biology. This is the first time experimental algorithmic information theory is implemented using quantum computation. Our implementation on the Qiskit quantum programming platform is copy-left and is publicly available on GitHub.

Subject

Algorithmic information theory
Genomics
Kolmogorov complexity
Meta-biology
Quantum Turing machine
Quantum algorithms
Quantum circuit model
Universal distribution
Viral genomics

To reference this document use:

http://resolver.tudelft.nl/uuid:d02cb3f8-6207-4d24-9698-7522735191e7

DOI

https://doi.org/10.3390/app11062696

ISSN

2076-3417

Source

Applied Sciences, 11 (6), 1-25

Part of collection

Institutional Repository