Quantum finite state machines - A circuit based approach

Martin Lukac, Michitaka Kameyama, Marek Perkowski

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)267-301
Number of pages35
JournalInternational Journal of Unconventional Computing
Issue number3-4
Publication statusPublished - 2013 May 1

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Quantum finite state machines - A circuit based approach'. Together they form a unique fingerprint.

Cite this