Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Applied Sciences

Estimating Algorithmic Information Using Quantum Computing for Genomics Applications

Aritra Sarkar, Zaid Al-Ars, Koen Bertels

Published Mar 17, 2021• 38 citations
Publisher

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.

DOI
10.3390/app11062696

Related papers

Quantum Accelerated Estimation of Algorithmic Information.

Aritra Sarkar, Zaid Al-Ars, Koen Bertels

In this research we present a quantum circuit for estimating algorithmic information metrics like the universal prior distribution. This accelerates inferring algorithmic structure in data for discovering causal generative models. The computation model is restricted in time and space resources to make it computable in approximating the target metrics. A classical exhaustive enumeration is shown for a few examples. The precise quantum circuit design that allows executing a superposition of automata is presented. As a use-case, an application framework for experimenting on DNA sequences for meta-biology is proposed. To our knowledge, this is the first time approximating algorithmic information is implemented for quantum computation. Our implementation on the OpenQL quantum programming language and the QX Simulator is copy-left and can be found on this https URL.

•Jun 1, 2020•3 citations

ACSS-q: Algorithmic complexity for short strings via quantum accelerated approach

Aritra Sarkar, Koen Bertels

In this research we present a quantum circuit for estimating algorithmic complexity using the coding theorem method. This accelerates inferring algorithmic structure in data for discovering causal generative models. The computation model is restricted in time and space resources to make it computable in approximating the target metrics. The quantum circuit design based on our earlier work that allows executing a superposition of automata is presented. As a use-case, an application framework for protein-protein interaction ontology based on algorithmic complexity is proposed. Using small-scale quantum computers, this has the potential to enhance the results of classical block decomposition method towards bridging the causal gap in entropy based methods.

arXiv:2009.08866•Sep 18, 2020•0 citations

Quantum circuit design for universal distribution using a superposition of classical automata

Aritra Sarkar, Zaid Al-Ars, Koen Bertels

In this research, we present a quantum circuit design and implementation for a parallel universal linear bounded automata. This circuit is able to accelerate the inference of algorithmic structures in data for discovering causal generative models. The computation model is practically restricted in time and space resources. A classical exhaustive enumeration of all possible programs on the automata is shown for a couple of example cases. The precise quantum circuit design that allows executing a superposition of programs, along with a superposition of inputs as in the standard quantum Turing machine formulation, is presented. This is the first time, a superposition of classical automata is implemented on the circuit model of quantum computation, having the corresponding mechanistic parts of a classical Turing machine. The superposition of programs allows our model to be used for experimenting with the space of program-output behaviors in algorithmic information theory. Our implementations on OpenQL and Qiskit quantum programming language is copy-left and is publicly available on GitHub.

arXiv:2006.00987•Jun 1, 2020•0 citations

Quantum Computing for Genomics: Conceptual Challenges and Practical Perspectives

Aurora Maurizio, Guglielmo Mazzola

We assess the potential of quantum computing to accelerate computation of central tasks in genomics, focusing on often-neglected theoretical limitations. We discuss state-of-the-art challenges of quantum search, optimization, and machine learning algorithms. Examining database search with Grover's algorithm, we show that the expected speedup vanishes under realistic assumptions. For combinatorial optimization prevalent in genomics, we discuss the limitations of theoretical complexity in practice and suggest carefully identifying problems genuinely suited for quantum acceleration. Given the competition from excellent classical approximate solvers, quantum computing could offer a speedup in the near future only for a specific subset of hard enough tasks in assembly, gene selection, and inference. These tasks need to be characterized by core optimization problems that are particularly challenging for classical methods while requiring relatively limited variables. We emphasize rigorous empirical validation through runtime scaling analysis to avoid misleading claims of quantum advantage. Finally, we discuss the problem of trainability and data-loading in quantum machine learning. This work advocates for a balanced perspective on quantum computing in genomics, guiding future research toward targeted applications and robust validation.

arXiv:2507.04111•PRX Life•Oct 1, 2025•8 citations

Title: Bio-Information Quantum Algorithm

Jincheng Zhang

This paper explores the potential of quantum algorithms to revolutionize bioinformatics, particularly in genomic analysis, protein structure prediction, and drug discovery. The core concept centers on leveraging the inherent information richness within biological datasets – specifically, DNA sequences and protein structures – to create novel quantum computational approaches. We propose a new algorithmic framework based on constructing quantum circuits directly from biological data structures, aiming to significantly accelerate computationally intensive tasks. The study emphasizes the transformative impact of this approach, focusing on the unique advantages conferred by biological information within the quantum realm. This research addresses the limitations of existing quantum computing approaches by integrating biological data into the core algorithm design.

•Aug 29, 2026•0 citations

Based Bioinformatics Prediction of Quantum Algorithm Design

Jincheng Zhang

Quantum computing holds immense potential for revolutionizing various fields, particularly in scientific research and data analysis. However, the development of practical quantum algorithms is a complex and challenging endeavor. This paper proposes a novel approach to quantum algorithm design, leveraging bioinformatics to predict algorithm performance and efficiency. We outline a method that utilizes genomic data and protein structure analysis to create a predictive model, aiming to streamline the algorithm design process and accelerate discovery. The core mechanism centers around analyzing genetic sequences and protein interactions to identify patterns and correlations that correlate with algorithm performance. This will allow for a more focused and efficient exploration of potential quantum algorithms. The paper presents a framework for integrating biological data with traditional quantum algorithm development, demonstrating its potential for enhancing the overall design process. The research explores the application of specific bioinformatics tools and techniques for generating predictive models. The focus is on providing a robust, data-driven approach to guide algorithm optimization and reduce reliance on purely theoretical calculations. This work contributes to the growing field of bio-inspired quantum computing, offering a new avenue for accelerating the advancement of quantum technologies.

•Aug 31, 2026•0 citations
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.
In this research we present a quantum circuit for estimating algorithmic information metrics like the universal prior distribution. This accelerates inferring algorithmic structure in data for discovering causal generative models. The computation model is restricted in time and space resources to make it computable in approximating the target metrics. A classical exhaustive enumeration is shown for a few examples. The precise quantum circuit design that allows executing a superposition of automata is presented. As a use-case, an application framework for experimenting on DNA sequences for meta-biology is proposed. To our knowledge, this is the first time approximating algorithmic information is implemented for quantum computation. Our implementation on the OpenQL quantum programming language and the QX Simulator is copy-left and can be found on this https URL.
In this research we present a quantum circuit for estimating algorithmic complexity using the coding theorem method. This accelerates inferring algorithmic structure in data for discovering causal generative models. The computation model is restricted in time and space resources to make it computable in approximating the target metrics. The quantum circuit design based on our earlier work that allows executing a superposition of automata is presented. As a use-case, an application framework for protein-protein interaction ontology based on algorithmic complexity is proposed. Using small-scale quantum computers, this has the potential to enhance the results of classical block decomposition method towards bridging the causal gap in entropy based methods.
In this research, we present a quantum circuit design and implementation for a parallel universal linear bounded automata. This circuit is able to accelerate the inference of algorithmic structures in data for discovering causal generative models. The computation model is practically restricted in time and space resources. A classical exhaustive enumeration of all possible programs on the automata is shown for a couple of example cases. The precise quantum circuit design that allows executing a superposition of programs, along with a superposition of inputs as in the standard quantum Turing machine formulation, is presented. This is the first time, a superposition of classical automata is implemented on the circuit model of quantum computation, having the corresponding mechanistic parts of a classical Turing machine. The superposition of programs allows our model to be used for experimenting with the space of program-output behaviors in algorithmic information theory. Our implementations on OpenQL and Qiskit quantum programming language is copy-left and is publicly available on GitHub.
We assess the potential of quantum computing to accelerate computation of central tasks in genomics, focusing on often-neglected theoretical limitations. We discuss state-of-the-art challenges of quantum search, optimization, and machine learning algorithms. Examining database search with Grover's algorithm, we show that the expected speedup vanishes under realistic assumptions. For combinatorial optimization prevalent in genomics, we discuss the limitations of theoretical complexity in practice and suggest carefully identifying problems genuinely suited for quantum acceleration. Given the competition from excellent classical approximate solvers, quantum computing could offer a speedup in the near future only for a specific subset of hard enough tasks in assembly, gene selection, and inference. These tasks need to be characterized by core optimization problems that are particularly challenging for classical methods while requiring relatively limited variables. We emphasize rigorous empirical validation through runtime scaling analysis to avoid misleading claims of quantum advantage. Finally, we discuss the problem of trainability and data-loading in quantum machine learning. This work advocates for a balanced perspective on quantum computing in genomics, guiding future research toward targeted applications and robust validation.
This paper explores the potential of quantum algorithms to revolutionize bioinformatics, particularly in genomic analysis, protein structure prediction, and drug discovery. The core concept centers on leveraging the inherent information richness within biological datasets – specifically, DNA sequences and protein structures – to create novel quantum computational approaches. We propose a new algorithmic framework based on constructing quantum circuits directly from biological data structures, aiming to significantly accelerate computationally intensive tasks. The study emphasizes the transformative impact of this approach, focusing on the unique advantages conferred by biological information within the quantum realm. This research addresses the limitations of existing quantum computing approaches by integrating biological data into the core algorithm design.
Quantum computing holds immense potential for revolutionizing various fields, particularly in scientific research and data analysis. However, the development of practical quantum algorithms is a complex and challenging endeavor. This paper proposes a novel approach to quantum algorithm design, leveraging bioinformatics to predict algorithm performance and efficiency. We outline a method that utilizes genomic data and protein structure analysis to create a predictive model, aiming to streamline the algorithm design process and accelerate discovery. The core mechanism centers around analyzing genetic sequences and protein interactions to identify patterns and correlations that correlate with algorithm performance. This will allow for a more focused and efficient exploration of potential quantum algorithms. The paper presents a framework for integrating biological data with traditional quantum algorithm development, demonstrating its potential for enhancing the overall design process. The research explores the application of specific bioinformatics tools and techniques for generating predictive models. The focus is on providing a robust, data-driven approach to guide algorithm optimization and reduce reliance on purely theoretical calculations. This work contributes to the growing field of bio-inspired quantum computing, offering a new avenue for accelerating the advancement of quantum technologies.