arXiv:2009.08866

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

Aritra Sarkar, Koen Bertels

Published Sep 18, 2020• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2009.08866

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, 20203 citations

Estimating Algorithmic Information Using Quantum Computing for Genomics Applications

Aritra Sarkar, Zaid Al-Ars, Koen Bertels

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.

Applied SciencesMar 17, 202138 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.00987Jun 1, 20200 citations

Title: Quantum Entanglement-Based Computational Complexity

Jincheng Zhang

Quantum entanglement, a peculiar phenomenon in quantum mechanics, offers a fundamentally different approach to computation than classical systems. This research explores the potential of leveraging entanglement as a core building block for computational complexity, proposing a novel method for quantifying the difficulty of algorithms through the development of an entanglement metric. The core claim is that certain computational tasks exhibit inherent complexity that cannot be adequately explained by classical complexity theory, and that this approach could lead to a deeper understanding of the limits of computation. The paper details the creation of an entanglement metric, a mathematical framework designed to directly relate entanglement properties to computational resource requirements, and demonstrates its ability to accurately estimate the complexity of specific algorithms. This work represents a significant step towards a more rigorous and predictive analysis of computational challenges, potentially uncovering previously unrecognized limitations within the realm of algorithmic complexity.

Sep 1, 20260 citations

Quantum Computation Complexity Theory Based on Quantum Information Entropy

Jincheng Zhang

This paper explores the application of quantum information entropy to the theory of computational complexity. We posit that quantum information entropy can serve as a novel metric for quantifying the complexity of quantum algorithms and their associated resource requirements. The core argument is that traditional measures of computational complexity, such as circuit depth or quantum gate count, often fail to fully capture the inherent challenges posed by quantum systems. By leveraging entropy, we aim to provide a more nuanced and potentially more accurate assessment of the difficulty of quantum computations. This work introduces a framework for analyzing quantum algorithms through the lens of information entropy, exploring relationships between algorithmic complexity, entropy generation, and the resources needed to execute these algorithms. Specifically, we examine how entropy can be used to characterize the 'quantumness' of an algorithm and its impact on the overall computational cost. The ultimate goal is to develop a more robust and predictive model for quantum computation, leading to improved algorithm design and resource allocation. ---

Aug 31, 20260 citations

Title: Quantum-Enhanced Statistical Inference – Leveraging Quantum Algorithms for Data Analysis

Jincheng Zhang

Quantum-enhanced statistical inference represents a significant advancement in data analysis, leveraging the unique properties of quantum mechanics to surpass the limitations of classical approaches. This paper investigates the design and implementation of a novel statistical inference algorithm, incorporating a quantum algorithm, designed to enhance accuracy and efficiency, particularly when dealing with large datasets. We explore the potential of quantum computation to accelerate computationally intensive tasks critical to statistical analysis, focusing on the application of a modified Grover's algorithm to estimate expected values. The core mechanism centers around exploiting quantum phenomena to reduce computational complexity and improve the reliability of statistical results. This work presents a comprehensive theoretical analysis and practical implementation demonstrating a substantial improvement over existing classical methods, particularly for large datasets, and lays the groundwork for a new paradigm in statistical data processing. The research culminates in a detailed discussion of the algorithm's performance characteristics and potential applications across diverse statistical domains.

Sep 4, 20260 citations