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 Symposium on Multiple-Valued Logic (ISMVL)

Analysis of Reversible and Quantum Finite State Machines Using Homing, Synchronizing and Distinguishing Input Sequences

M. Lukac, Michitaka Kameyama, Marek A. Perkowski, Paweł Kerntopf

Published May 1, 2013• 2 citations
Publisher

Abstract

We present an analysis of the Reversible and Quantum Finite State Machines (QFSM) realized as Quantum Circuits using the three well known sequences applied in the analysis of the classical Finite State Machines (FSM). The synchronizing, the homing and the distinguishing sequences are applied to both strictly Reversible FSM (RFSM) and QFSM in order to determine the power of these new techniques in the above mentioned new models of sequential devices. In particular, care is taken to demonstrate these classical techniques on the RFSM and the one-way QFSMs. We show certain properties of the RFSM/QFSM with respect to these sequences and we show what are the restrictions and advantages.

DOI
10.1109/ismvl.2013.15

Related papers

Quantum finite state machines - A circuit based approach

Martin Lukáč, Michitaka Kameyama, Marek A. Perkowski

We present a model of Quantum Finite State Machines (QFSM) based on the quantum circuit representation. In this model, properties of quantum bits are exploited in order to implement Quantum Finite State Machines without an explicit external memory. We show that because of the the natural ability of quantum systems to retain the quantum state, quantum circuits can be directly used to implement some classes of the quantum finite state machines. In particular, the circuit model allows to remove the logic-memory distinction as it is used in the classically established model of finite state machines. Rather, the quantum register implementing the QFSM as a circuit is alternatively used as memory and as logic. In order to allow such behavior the quantum circuit (processor) is controlled by a classical circuit that provides the necessary timing of the quantum operations as well as the interface between the quantum and the classical world. Moreover, additional mechanism for preserving unknown quantum qubit state is used and a novel computational protocol allowing the implementation of the QFSM is proposed. This framework is is called the Classically Controlled Quantum Computer (CCQC). The CCQC thus combines a quantum processor with a classical controller in such manner that computation is carried from the classical inputs, through quantum processing to classical outputs. We discuss a high level synthesis approach to quantum sequence detection based on the synthesis of quantum sequential circuits. Such machines can find many applications for instance in robotics; for example a robot is required to recognize certain sequences of input sensor values.

International journal of unconventional computing•May 1, 2013•4 citations

Quantum Finite State Machines as Sequential Quantum Circuits

Martin Lukáč, Marek A. Perkowski

In this paper we present the synthesis process of quantum finite state machines for sequence detection based on the synthesis of quantum sequential circuits. Such machines have many applications for instance in robotics. We show the relation between the quantum circuit and the natural ability of quantum systems to retain the quantum state. We consider cases where a single qubit in a circuit represents a quantum state and another is used as the input qubit. We analyze some of the well known circuits as sequence detectors and describe their behaviors. We show that the standard quantum logic synthesis can be used for both the synthesis of quantum circuits as well as for quantum finite state machines used as sequence detectors.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•Jan 1, 2009•16 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

Equivalence Checking of Sequential Quantum Circuits

Qisheng Wang, Riling Li, Mingsheng Ying

We define a formal framework for equivalence checking of sequential quantum circuits. The model we adopt is a quantum state machine, which is a natural quantum generalization of Mealy machines. A major difficulty in checking quantum circuits (but not present in checking classical circuits) is that the state spaces of quantum circuits are continuums. This difficulty is resolved by our main theorem showing that equivalence checking of two quantum Mealy machines can be done with input sequences that are taken from some chosen basis (which are finite) and have a length quadratic in the dimensions of the state Hilbert spaces of the machines. Based on this theoretical result, we develop an (and to the best of our knowledge, the first) algorithm for checking equivalence of sequential quantum circuits with running time$\mathcal {O}(2^{3m+5l}(2^{3m}{\,+\,}2^{3l}))$, where$m$and$l$denote the numbers of input and internal qubits, respectively. The complexity of our algorithm is comparable with that of the known algorithms for checking classical sequential circuits in the sense that both are exponential in the number of (qu)bits. Several case studies and experiments are presented.

arXiv:1811.07722•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 5, 2021•22 citations

Superiority of one-way and realtime quantum machines and new directions

Abuzer Yakaryılmaz

In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QFAs augmented with counters or stacks. Moreover, to our knowledge, there is no result related to QFAs having more than one input head. In this paper, we focus on such generalizations of QFAs whose input head(s) operate(s) in one-way or realtime mode and present many superiority of them to their classical counterparts. Furthermore, we propose some open problems and conjectures in order to investigate the power of quantumness better. We also give some new results on classical computation.

arXiv:1102.3093•NCMA•Feb 15, 2011•2 citations

A quantum model for synchronizing finite state transition systems

Martin Lukac, Khaled El-Fakih, Uraz Turker

We propose a quantum model for finding a resetting input sequence (RS) which can take a finite state transition system (FA), to particular state independent of its current state. The complexity of finding such sequences for various types of FA can be NP-Hard or even PSPACE-Complete. To this end, we represent the FA states, inputs, and transition function in quantum space. Accordingly, we propose a model to represent the execution of an input sequence of a particular length $l$ starting form an initial FA state. The model is extended considering the application in superposition of all input sequences of length $l$ to an initial state of the FA. The model is further extended considering the application of all input sequences to all initial states of the FA capturing for every input sequence the collection (ordered list) of states reached by applying the sequence to all states of the FA. The amplitude amplification algorithm is then used as it combines similar collections of reached states while preserving all input sequences that reach these collections. A Grover search for a reached collection where its elements correspond to the same FA state provides a RS for the FA. Our approach offers a quadratic gain over the exponential complexity of traditional brute-force method, which is the only method that can be applied to a general FA class.

quant-pharXiv:2607.06953•Jul 9, 2026•0 citations
We present an analysis of the Reversible and Quantum Finite State Machines (QFSM) realized as Quantum Circuits using the three well known sequences applied in the analysis of the classical Finite State Machines (FSM). The synchronizing, the homing and the distinguishing sequences are applied to both strictly Reversible FSM (RFSM) and QFSM in order to determine the power of these new techniques in the above mentioned new models of sequential devices. In particular, care is taken to demonstrate these classical techniques on the RFSM and the one-way QFSMs. We show certain properties of the RFSM/QFSM with respect to these sequences and we show what are the restrictions and advantages.
We present a model of Quantum Finite State Machines (QFSM) based on the quantum circuit representation. In this model, properties of quantum bits are exploited in order to implement Quantum Finite State Machines without an explicit external memory. We show that because of the the natural ability of quantum systems to retain the quantum state, quantum circuits can be directly used to implement some classes of the quantum finite state machines. In particular, the circuit model allows to remove the logic-memory distinction as it is used in the classically established model of finite state machines. Rather, the quantum register implementing the QFSM as a circuit is alternatively used as memory and as logic. In order to allow such behavior the quantum circuit (processor) is controlled by a classical circuit that provides the necessary timing of the quantum operations as well as the interface between the quantum and the classical world. Moreover, additional mechanism for preserving unknown quantum qubit state is used and a novel computational protocol allowing the implementation of the QFSM is proposed. This framework is is called the Classically Controlled Quantum Computer (CCQC). The CCQC thus combines a quantum processor with a classical controller in such manner that computation is carried from the classical inputs, through quantum processing to classical outputs. We discuss a high level synthesis approach to quantum sequence detection based on the synthesis of quantum sequential circuits. Such machines can find many applications for instance in robotics; for example a robot is required to recognize certain sequences of input sensor values.
In this paper we present the synthesis process of quantum finite state machines for sequence detection based on the synthesis of quantum sequential circuits. Such machines have many applications for instance in robotics. We show the relation between the quantum circuit and the natural ability of quantum systems to retain the quantum state. We consider cases where a single qubit in a circuit represents a quantum state and another is used as the input qubit. We analyze some of the well known circuits as sequence detectors and describe their behaviors. We show that the standard quantum logic synthesis can be used for both the synthesis of quantum circuits as well as for quantum finite state machines used as sequence detectors.
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.
We define a formal framework for equivalence checking of sequential quantum circuits. The model we adopt is a quantum state machine, which is a natural quantum generalization of Mealy machines. A major difficulty in checking quantum circuits (but not present in checking classical circuits) is that the state spaces of quantum circuits are continuums. This difficulty is resolved by our main theorem showing that equivalence checking of two quantum Mealy machines can be done with input sequences that are taken from some chosen basis (which are finite) and have a length quadratic in the dimensions of the state Hilbert spaces of the machines. Based on this theoretical result, we develop an (and to the best of our knowledge, the first) algorithm for checking equivalence of sequential quantum circuits with running timeO(23m+5l(23m + 23l))\mathcal {O}(2^{3m+5l}(2^{3m}{\,+\,}2^{3l}))O(23m+5l(23m+23l)), wheremmmandllldenote the numbers of input and internal qubits, respectively. The complexity of our algorithm is comparable with that of the known algorithms for checking classical sequential circuits in the sense that both are exponential in the number of (qu)bits. Several case studies and experiments are presented.
In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QFAs augmented with counters or stacks. Moreover, to our knowledge, there is no result related to QFAs having more than one input head. In this paper, we focus on such generalizations of QFAs whose input head(s) operate(s) in one-way or realtime mode and present many superiority of them to their classical counterparts. Furthermore, we propose some open problems and conjectures in order to investigate the power of quantumness better. We also give some new results on classical computation.
We propose a quantum model for finding a resetting input sequence (RS) which can take a finite state transition system (FA), to particular state independent of its current state. The complexity of finding such sequences for various types of FA can be NP-Hard or even PSPACE-Complete. To this end, we represent the FA states, inputs, and transition function in quantum space. Accordingly, we propose a model to represent the execution of an input sequence of a particular length lll starting form an initial FA state. The model is extended considering the application in superposition of all input sequences of length lll to an initial state of the FA. The model is further extended considering the application of all input sequences to all initial states of the FA capturing for every input sequence the collection (ordered list) of states reached by applying the sequence to all states of the FA. The amplitude amplification algorithm is then used as it combines similar collections of reached states while preserving all input sequences that reach these collections. A Grover search for a reached collection where its elements correspond to the same FA state provides a RS for the FA. Our approach offers a quadratic gain over the exponential complexity of traditional brute-force method, which is the only method that can be applied to a general FA class.