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• 7 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•4 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•4 citations

Quantum circuits and parallelism

Pawan Kumar Verma, Mohit Kumar, Saurabh Singhal +1 more

This chapter develops the quantum circuit model as the operational core of gate-based quantum computation, framing circuits as structured compositions of unitary transformations acting on qubits and quantum registers. It begins by formalizing qubits as normalized state vectors in Hilbert space and extends to multi-qubit registers via tensor products, emphasizing the exponential growth of representable basis amplitudes and the resulting capacity for entanglement. Building on these foundations, this chapter details circuit design as an algorithm-engineering discipline that must balance mathematical correctness with resource efficiency under hardware and noise constraints, including circuit depth, gate count, qubit connectivity, control bandwidth, and crosstalk. Circuit construction is presented through sequential composition and parallel execution on disjoint qubit subsets, motivating scheduling methods such as dependency-graph analysis, critical-path identification, and time-slice (layer) formation under platform-imposed concurrency limits. This chapter then addresses quantum circuit decomposition as the bridge from abstract algorithmic operators to implementable gate sets, highlighting universal synthesis principles (including Solovay–Kitaev guarantees) and standard decompositions for single-qubit unitaries (Euler-angle forms) and controlled multi-qubit operations. Finally, quantum parallelism is treated as a distinctly quantum computational resource arising from superposition over 2.

CRC Press eBooks•Nov 6, 2026•0 citations

Quantum Inspired Universal Analog Computation Based on Circuits

Hanxu Zhang, Yifan Sun, Xiangdong Zhang

ABSTRACT Universal quantum computation that consists of producing arbitrary input states and executing universal unitary gates is an important goal for the future information field. However, realizing a device that performs practical universal quantum computation is tricky. This is because it requires a scalable qubit system with long coherence time and good controls, which is harsh for most current platforms. Here, we provide a novel scheme to emulate the universal quantum computer by designing a classical circuit network. In the circuit network, we encode information using correlated electrical signals. The information processing elements that correspond to the universal quantum gate set are designed and embedded into the circuit network, which gives the classical circuit networks processing functions similar to that of universal quantum computation. Taking the analogy of two‐qubit processor as an example, we experimentally verify that our proposal works well. Because classical circuit networks possess good scalability and stability, the present scheme is expected to avoid some problems faced by the quantum schemes. Thus, our findings are advantageous for information processing in the era of big data.

Advanced Quantum Technologies•Nov 28, 2025•1 citation
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 chapter develops the quantum circuit model as the operational core of gate-based quantum computation, framing circuits as structured compositions of unitary transformations acting on qubits and quantum registers. It begins by formalizing qubits as normalized state vectors in Hilbert space and extends to multi-qubit registers via tensor products, emphasizing the exponential growth of representable basis amplitudes and the resulting capacity for entanglement. Building on these foundations, this chapter details circuit design as an algorithm-engineering discipline that must balance mathematical correctness with resource efficiency under hardware and noise constraints, including circuit depth, gate count, qubit connectivity, control bandwidth, and crosstalk. Circuit construction is presented through sequential composition and parallel execution on disjoint qubit subsets, motivating scheduling methods such as dependency-graph analysis, critical-path identification, and time-slice (layer) formation under platform-imposed concurrency limits. This chapter then addresses quantum circuit decomposition as the bridge from abstract algorithmic operators to implementable gate sets, highlighting universal synthesis principles (including Solovay–Kitaev guarantees) and standard decompositions for single-qubit unitaries (Euler-angle forms) and controlled multi-qubit operations. Finally, quantum parallelism is treated as a distinctly quantum computational resource arising from superposition over 2.
ABSTRACT Universal quantum computation that consists of producing arbitrary input states and executing universal unitary gates is an important goal for the future information field. However, realizing a device that performs practical universal quantum computation is tricky. This is because it requires a scalable qubit system with long coherence time and good controls, which is harsh for most current platforms. Here, we provide a novel scheme to emulate the universal quantum computer by designing a classical circuit network. In the circuit network, we encode information using correlated electrical signals. The information processing elements that correspond to the universal quantum gate set are designed and embedded into the circuit network, which gives the classical circuit networks processing functions similar to that of universal quantum computation. Taking the analogy of two‐qubit processor as an example, we experimentally verify that our proposal works well. Because classical circuit networks possess good scalability and stability, the present scheme is expected to avoid some problems faced by the quantum schemes. Thus, our findings are advantageous for information processing in the era of big data.