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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Algorithm to build quantum circuit from classical description of DFSM

Varun Puram, Dingyi Kang, K. M. George, Johnson P. Thomas

Published Sep 1, 2022• 2 citations
Publisher

Abstract

There are several papers that define quantum finite automaton analogous to classical finite automaton. Some papers describe the power of quantum automaton. In general, in quantum automata unitary matrices are associated to input symbols. Even though quantum circuits (or unitary matrices) are shown in specific cases, there is no general method given to construct a circuit or unitary matrix is found in the literature. This research focuses on construction of unitary matrices for each input symbol from the classical definition of a Deterministic Finite State Machine (DFSM). An algorithm is developed to associate a quantum circuit to an input symbol which considered as a mapping of classical DFSM states. IBM quantum composer is used to design circuits and build examples.

DOI
10.1109/qce53715.2022.00104

Related papers

Quantum Representation for Deterministic Push-Down Automata

Varun Puram, K. M. George, Johnson P. Thomas

Abstract There are many papers presenting quantum computing models. The definitions parallel the classical definitions of finite state automata, push down automata, context-free grammars etc. Classical computing model definitions define languages precisely. We can state that a string belongs to a language or does not belong to it with no room for error. Quantum definitions do not possess this certainty. Sacrificing the certainty and adopting a quantum definition of a computing model does not appear to provide any concrete power to the model. Therefore, the path of this paper is to begin from the classical definition and end in a quantum circuit. In this paper we start from a Deterministic Push-Down Automaton (DPDA). We present circuit for state transition and stack operations. The circuits presented can be viewed as independent algorithms. As an example, the approach used to construct the circuit for state transition can be utilized to build the circuit for a function presented as a Boolean matrix.

Electronics•Nov 18, 2024•0 citations

Quantum circuits from non-unitary sparse binary matrices

Krishnageetha Karuppasamy, Varun Puram, K. M. George +1 more

Quantum computing leverages unitary matrices to perform reversible computations while preserving probability norms. However, many real-world applications involve non-unitary sparse matrices, posing a challenge for quantum implementation. This paper introduces a novel method for transforming a class of non-unitary sparse binary matrices into higher-dimensional permutation matrices, ensuring unitarity. Our approach is efficient in both space and time, ensuring practical applicability to large-scale problems. We demonstrate the utility of this transformation in constructing quantum gates and apply the method to model quantum finite state machines (QFSMs) derived from classical deterministic finite automata (DFAs). This work offers a practical pathway for integrating non-unitary transformations into quantum systems, with implications for the many applications that are based on sparse, non-unitary matrices. The significance of this work for automata theory and quantum computation is outlined.

Scientific Reports•Jul 1, 2025•2 citations

A Framework for Quantum Finite-State Languages with Density Mapping

SeungYeop Baik, Sicheol Sung, Yo-Sub Han

A quantum finite-state automaton (QFA) is a theoretical model designed to simulate the evolution of a quantum system with finite memory in response to sequential input strings. We define the language of a QFA as the set of strings that lead the QFA to an accepting state when processed from its initial state. QFAs exemplify how quantum computing can achieve greater efficiency compared to classical computing. While being one of the simplest quantum models, QFAs are still notably challenging to construct from scratch due to the preliminary knowledge of quantum mechanics required for superimposing unitary constraints on the automata. Furthermore, even when QFAs are correctly assembled, the limitations of a current quantum computer may cause fluctuations in the simulation results depending on how an assembled QFA is translated into a quantum circuit. We present a framework that provides a simple and intuitive way to build QFAs and maximize the simulation accuracy. Our framework relies on two methods: First, it offers a predefined construction for foundational types of QFAs that recognize special languages MOD and EQU. They play a role of basic building blocks for more complex QFAs. In other words, one can obtain more complex QFAs from these foundational automata using standard language operations. Second, we improve the simulation accuracy by converting these QFAs into quantum circuits such that the resulting circuits perform well on noisy quantum computers. Our framework is available at https://github.com/sybaik1/qfa-toolkit.

arXiv:2407.02776•Jul 3, 2024•0 citations

Quantum state transition diagram: a bridge from classical computing to quantum computing

Loyd R. Hook, Sam Lee

Very few papers have been written on the topic of a quantum version of the finite state machine, (or finite state automata). Furthermore, these papers only serve to define what a quantum finite state machine might be in the mathematical sense using the early languages of Turing machines. This paper seeks to further develop the notion of a quantum finite state machine (FSM) using constructs developed for the classical FSM and utilized for classical FSM design. In particular the quantum state transition diagram (QSTD) is constructed to further the understanding and realization of quantum finite state machines and quantum computers.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Mar 25, 2010•3 citations

Automata-Based Quantum Circuit Design Patterns Identification: A Novel Approach and Experimental Verification

Francisco P. Romero, José A. Cruz-Lemus, Sergio Jiménez-Fernández +1 more

This paper introduces a strategy for identifying design patterns in quantum circuits. The foundation of this approach relies on using the information procured from both the segmentation and the analysis of these circuits as primary data. The approach of the methodology is based on the novel interpretation of quantum circuit components through the lens of an automaton. Additionally, the method entails the generation of input symbols for this finite automaton. The symbols are derived from the matching process between design patterns and components of quantum circuits. Two tool prototypes, QPainter and QCDPDTool, have been developed to represent quantum circuits graphically and automatically detect quantum patterns. Using them, the primary reasoning process is carried out by an automaton that can manage representations of quantum circuit components. A suite of experiments on a set of quantum circuit sequences reveals promising results and offers empirical support for our approach. Furthermore, we explore how these experimental findings can be leveraged to improve the efficacy of design pattern identification in quantum circuits.

International Journal of Software Engineering and Knowledge Engineering•Jul 19, 2024•2 citations

Chapter 8 Quantum computing in automata theory

G. Ignisha Rajathi, R. Vedhapriyavadhana, R. Niranjana +2 more

In the contemporary era we dwell in, every now and then, new technologies are developed by master brains such as researchers and scientists. This also paves the way to discover replacements to classical computers. One such progression among the great inventions is the essence of quantum computing. They are brought to light for the purpose of solving problems and scenarios solved by classical computers but in a more effective way and in the least span of time. The study of quantum computing focuses on finding new ways to compute by using quantum physics phenomena. A qubit, in contrast to a typical computer bit, can be either 0 or 1, or it can be a superposition of both 0 and 1. Quantum theory commemorates with automata theory, thereby formulating quantum finite automata. Quantum finite automaton, or basically a deterministic finite automaton, is one of the simplest models of computation, which is an input-driven model, which takes an input, and according to the input, we just read the machine, and it changes its state. This proves that any quantum finite automata are completely capable of recognizing languages like Tally with given cut point too. Such languages recognized by a cut point, by quantum finite automata, are called stochastic languages. It further collaborates with the chemical industry with its qubit power over molecular collide, interactive models, and collaborative string processing using nonregular languages.

De Gruyter eBooks•Aug 7, 2023•2 citations
There are several papers that define quantum finite automaton analogous to classical finite automaton. Some papers describe the power of quantum automaton. In general, in quantum automata unitary matrices are associated to input symbols. Even though quantum circuits (or unitary matrices) are shown in specific cases, there is no general method given to construct a circuit or unitary matrix is found in the literature. This research focuses on construction of unitary matrices for each input symbol from the classical definition of a Deterministic Finite State Machine (DFSM). An algorithm is developed to associate a quantum circuit to an input symbol which considered as a mapping of classical DFSM states. IBM quantum composer is used to design circuits and build examples.
Abstract There are many papers presenting quantum computing models. The definitions parallel the classical definitions of finite state automata, push down automata, context-free grammars etc. Classical computing model definitions define languages precisely. We can state that a string belongs to a language or does not belong to it with no room for error. Quantum definitions do not possess this certainty. Sacrificing the certainty and adopting a quantum definition of a computing model does not appear to provide any concrete power to the model. Therefore, the path of this paper is to begin from the classical definition and end in a quantum circuit. In this paper we start from a Deterministic Push-Down Automaton (DPDA). We present circuit for state transition and stack operations. The circuits presented can be viewed as independent algorithms. As an example, the approach used to construct the circuit for state transition can be utilized to build the circuit for a function presented as a Boolean matrix.
Quantum computing leverages unitary matrices to perform reversible computations while preserving probability norms. However, many real-world applications involve non-unitary sparse matrices, posing a challenge for quantum implementation. This paper introduces a novel method for transforming a class of non-unitary sparse binary matrices into higher-dimensional permutation matrices, ensuring unitarity. Our approach is efficient in both space and time, ensuring practical applicability to large-scale problems. We demonstrate the utility of this transformation in constructing quantum gates and apply the method to model quantum finite state machines (QFSMs) derived from classical deterministic finite automata (DFAs). This work offers a practical pathway for integrating non-unitary transformations into quantum systems, with implications for the many applications that are based on sparse, non-unitary matrices. The significance of this work for automata theory and quantum computation is outlined.
A quantum finite-state automaton (QFA) is a theoretical model designed to simulate the evolution of a quantum system with finite memory in response to sequential input strings. We define the language of a QFA as the set of strings that lead the QFA to an accepting state when processed from its initial state. QFAs exemplify how quantum computing can achieve greater efficiency compared to classical computing. While being one of the simplest quantum models, QFAs are still notably challenging to construct from scratch due to the preliminary knowledge of quantum mechanics required for superimposing unitary constraints on the automata. Furthermore, even when QFAs are correctly assembled, the limitations of a current quantum computer may cause fluctuations in the simulation results depending on how an assembled QFA is translated into a quantum circuit. We present a framework that provides a simple and intuitive way to build QFAs and maximize the simulation accuracy. Our framework relies on two methods: First, it offers a predefined construction for foundational types of QFAs that recognize special languages MOD and EQU. They play a role of basic building blocks for more complex QFAs. In other words, one can obtain more complex QFAs from these foundational automata using standard language operations. Second, we improve the simulation accuracy by converting these QFAs into quantum circuits such that the resulting circuits perform well on noisy quantum computers. Our framework is available at https://github.com/sybaik1/qfa-toolkit.
Very few papers have been written on the topic of a quantum version of the finite state machine, (or finite state automata). Furthermore, these papers only serve to define what a quantum finite state machine might be in the mathematical sense using the early languages of Turing machines. This paper seeks to further develop the notion of a quantum finite state machine (FSM) using constructs developed for the classical FSM and utilized for classical FSM design. In particular the quantum state transition diagram (QSTD) is constructed to further the understanding and realization of quantum finite state machines and quantum computers.
This paper introduces a strategy for identifying design patterns in quantum circuits. The foundation of this approach relies on using the information procured from both the segmentation and the analysis of these circuits as primary data. The approach of the methodology is based on the novel interpretation of quantum circuit components through the lens of an automaton. Additionally, the method entails the generation of input symbols for this finite automaton. The symbols are derived from the matching process between design patterns and components of quantum circuits. Two tool prototypes, QPainter and QCDPDTool, have been developed to represent quantum circuits graphically and automatically detect quantum patterns. Using them, the primary reasoning process is carried out by an automaton that can manage representations of quantum circuit components. A suite of experiments on a set of quantum circuit sequences reveals promising results and offers empirical support for our approach. Furthermore, we explore how these experimental findings can be leveraged to improve the efficacy of design pattern identification in quantum circuits.
In the contemporary era we dwell in, every now and then, new technologies are developed by master brains such as researchers and scientists. This also paves the way to discover replacements to classical computers. One such progression among the great inventions is the essence of quantum computing. They are brought to light for the purpose of solving problems and scenarios solved by classical computers but in a more effective way and in the least span of time. The study of quantum computing focuses on finding new ways to compute by using quantum physics phenomena. A qubit, in contrast to a typical computer bit, can be either 0 or 1, or it can be a superposition of both 0 and 1. Quantum theory commemorates with automata theory, thereby formulating quantum finite automata. Quantum finite automaton, or basically a deterministic finite automaton, is one of the simplest models of computation, which is an input-driven model, which takes an input, and according to the input, we just read the machine, and it changes its state. This proves that any quantum finite automata are completely capable of recognizing languages like Tally with given cut point too. Such languages recognized by a cut point, by quantum finite automata, are called stochastic languages. It further collaborates with the chemical industry with its qubit power over molecular collide, interactive models, and collaborative string processing using nonregular languages.