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

arXiv:2006.00987

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

Aritra Sarkar, Zaid Al-Ars, Koen Bertels

Published Jun 1, 2020• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2006.00987

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

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 Sciences•Mar 17, 2021•38 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

Investigating parallel execution of quantum Machine Learning circuits on superconducting hardware

Julien Rauch, Brice Chichereau, Stéphane Vialle +2 more

Quantum Machine Learning algorithms generally rely on hybrid implementation with a classical learning loop running on a CPU and small quantum circuits running on a Quantum Processing Unit (QPU) for serialized processing batches of data. Considering the scarcity of quantum resources, parallelizing the execution of multiple instances of small quantum circuits instead of allocating a single circuit would better use quantum hardware resources. However, exploiting all available qubits in QPUs could result in a noisier operating condition and disrupt or slow the learning mechanism. This paper investigates the parallelization of QML algorithms on QPU for data clustering based on trainable generative models. We design a parallel macro-circuit with the Qiskit framework and measure their performance on an IBM superconducting quantum computer. A theoretical performance model is then proposed to determine the expected level of acceleration. Finally, we measure the impact of the QPU's occupancy on the loss functions of our QML algorithm, enabling us to identify the most reliable and exploitable acceleration range.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•3 citations

Visualizing Quantum Circuit Probability -- estimating computational action for quantum program synthesis

Bao Gia Bach, Akash Kundu, Tamal Acharya +1 more

This research applies concepts from algorithmic probability to Boolean and quantum combinatorial logic circuits. A tutorial-style introduction to states and various notions of the complexity of states are presented. Thereafter, the probability of states in the circuit model of computation is defined. Classical and quantum gate sets are compared to select some characteristic sets. The reachability and expressibility in a space-time-bounded setting for these gate sets are enumerated and visualized. These results are studied in terms of computational resources, universality and quantum behavior. The article suggests how applications like geometric quantum machine learning, novel quantum algorithm synthesis and quantum artificial general intelligence can benefit by studying circuit probabilities.

arXiv:2304.02358•Apr 5, 2023•0 citations

Parameterized quantum circuits as universal generative models for continuous multivariate distributions

Alice Barthe, Michele Grossi, Sofia Vallecorsa +2 more

Parameterized quantum circuits are a key component of quantum machine learning models for regression, classification, and generative tasks. Quantum Circuit Born machines produce discrete distributions over bitstrings whose length is exactly the number of qubits. To allow for distributions on continuous variables, new models have been introduced where classical randomness is uploaded into quantum circuits and expectation values are returned with a dimensionality decoupled from qubit number. While these models have been explored experimentally, their expressivity remains underexplored. In this work, we formalize this family and establish its theoretical foundation. We prove the universality of several variational circuit architectures for generating continuous multivariate distributions and derive tight resource bounds to reach universality using tools related to the Holevo bound. Our results reveal a trade-off between the number of qubits and measurements. We further explore relaxed notions of universality and present a practical use case, outlining potential domains for quantum advantage.

arXiv:2402.09848•npj Quantum Information•Jul 22, 2025•11 citations
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.
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.
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 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.
Quantum Machine Learning algorithms generally rely on hybrid implementation with a classical learning loop running on a CPU and small quantum circuits running on a Quantum Processing Unit (QPU) for serialized processing batches of data. Considering the scarcity of quantum resources, parallelizing the execution of multiple instances of small quantum circuits instead of allocating a single circuit would better use quantum hardware resources. However, exploiting all available qubits in QPUs could result in a noisier operating condition and disrupt or slow the learning mechanism. This paper investigates the parallelization of QML algorithms on QPU for data clustering based on trainable generative models. We design a parallel macro-circuit with the Qiskit framework and measure their performance on an IBM superconducting quantum computer. A theoretical performance model is then proposed to determine the expected level of acceleration. Finally, we measure the impact of the QPU's occupancy on the loss functions of our QML algorithm, enabling us to identify the most reliable and exploitable acceleration range.
This research applies concepts from algorithmic probability to Boolean and quantum combinatorial logic circuits. A tutorial-style introduction to states and various notions of the complexity of states are presented. Thereafter, the probability of states in the circuit model of computation is defined. Classical and quantum gate sets are compared to select some characteristic sets. The reachability and expressibility in a space-time-bounded setting for these gate sets are enumerated and visualized. These results are studied in terms of computational resources, universality and quantum behavior. The article suggests how applications like geometric quantum machine learning, novel quantum algorithm synthesis and quantum artificial general intelligence can benefit by studying circuit probabilities.
Parameterized quantum circuits are a key component of quantum machine learning models for regression, classification, and generative tasks. Quantum Circuit Born machines produce discrete distributions over bitstrings whose length is exactly the number of qubits. To allow for distributions on continuous variables, new models have been introduced where classical randomness is uploaded into quantum circuits and expectation values are returned with a dimensionality decoupled from qubit number. While these models have been explored experimentally, their expressivity remains underexplored. In this work, we formalize this family and establish its theoretical foundation. We prove the universality of several variational circuit architectures for generating continuous multivariate distributions and derive tight resource bounds to reach universality using tools related to the Holevo bound. Our results reveal a trade-off between the number of qubits and measurements. We further explore relaxed notions of universality and present a practical use case, outlining potential domains for quantum advantage.