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:quant-ph/9807026

Simulation of finite state machines in a quantum computer

Michael R. Dunlavey

Published Jul 9, 1998• 4 citations
arXivHTMLPDF

Abstract

A construction is given for simulating any deterministic finite state machine (FSM) on a quantum computer in a space-efficient manner. By constructing a superposition of input strings of lengths K or less, questions can be asked about the FSM, such as the inputs that reach particular nodes, and the answers can be found using a search algorithm such as Grover's. This has implications for the eventual utility of quantum computers for software validation.

DOI
10.48550/arxiv.quant-ph/9807026

Related papers

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

A quantum algorithm for automata encoding

Edison Tsai, Marek A. Perkowski

Encoding of finite automata or state machines is critical to modern digital logic design methods for sequential circuits. Encoding is the process of assigning to every state, input value, and output value of a state machine a binary string, which is used to represent that state, input value, or output value in digital logic. Usually, one wishes to choose an encoding that, when the state machine is implemented as a digital logic circuit, will optimize some aspect of that circuit. For instance, one might wish to encode in such a way as to minimize power dissipation or silicon area. For most such optimization objectives, no method to find the exact solution, other than a straightforward exhaustive search, is known. Recent progress towards producing a quantum computer of large enough scale to surpass modern supercomputers has made it increasingly relevant to consider how quantum computers may be used to solve problems of practical interest. A quantum computer using Grover?s well-known search algorithm can perform exhaustive searches that would be impractical on a classical computer, due to the speedup provided by Grover?s algorithm. Therefore, we propose to use Grover?s algorithm to find optimal encodings for finite state machines via exhaustive search. We demonstrate the design of quantum circuits that allow Grover?s algorithm to be used for this purpose. The quantum circuit design methods that we introduce are potentially applicable to other problems as well.

Facta universitatis - series Electronics and Energetics•Jan 1, 2020•6 citations

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

A Quantum Algorithm for Software Engineering Search

Robert J. Hall

Quantum computers can solve a few basic problems, such as factoring an integer and searching a database, much faster than classical computers. However, the complexity of software artifacts, and the types of questions software engineers ask about them, pose significant challenges for applying existing quantum approaches to software engineering search (SES) problems. This paper first describes a new quantum search algorithm, IDGS-FA, whose design is motivated by the characteristics of SES problems. Next, it describes how to apply quantum searching to three SES problems: FSM property checking, software test generation, and library-based software synthesis. Next, the paper gives the main ideas in QSAT, a novel toolkit supporting efficient simulation of the algorithms and applications discussed. Finally, it concludes with a substantial simulation-based study of IDGS-FA, showing that it improves both the reliability and speed of other approaches.

IEEE/ACM International Conference on Automated Software Engineering (ASE)•Nov 1, 2009•4 citations

Quantum State Machines

Yorick Hardy, Willi-Hans Steeb

In this chapter we introduce the quantum state machine [80,119].The quantum state machine is an extension of classical finite state machines used to represent the computations possible in quantum computing. Quantum state machines introduce amplitudes for transitions between states to represent the parallelism available.

Birkhäuser Basel eBooks•Jan 1, 2001•0 citations

Space-efficient simulation of quantum computers

Michael P. Frank, Uwe H. Meyer-Baese, I. Chiorescu +2 more

Traditional algorithms for simulating quantum computers on classical ones require an exponentially large amount of memory, and so typically cannot simulate general quantum circuits with more than about 30 or so qubits on a typical PC-scale platform with only a few gigabytes of main memory. However, more memory-efficient simulations are possible, requiring only polynomial or even linear space in the size of the quantum circuit being simulated. In this paper, we describe one such technique, which was recently implemented at FSU in the form of a C++ program called SEQCSim, which we releasing publicly. We also discuss the potential benefits of this simulation in quantum computing research and education, and outline some possible directions for further progress.

arXiv:0812.3675•ACM Southeast Regional Conference (ACMSE)•Mar 19, 2009•9 citations
A construction is given for simulating any deterministic finite state machine (FSM) on a quantum computer in a space-efficient manner. By constructing a superposition of input strings of lengths K or less, questions can be asked about the FSM, such as the inputs that reach particular nodes, and the answers can be found using a search algorithm such as Grover's. This has implications for the eventual utility of quantum computers for software validation.
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.
Encoding of finite automata or state machines is critical to modern digital logic design methods for sequential circuits. Encoding is the process of assigning to every state, input value, and output value of a state machine a binary string, which is used to represent that state, input value, or output value in digital logic. Usually, one wishes to choose an encoding that, when the state machine is implemented as a digital logic circuit, will optimize some aspect of that circuit. For instance, one might wish to encode in such a way as to minimize power dissipation or silicon area. For most such optimization objectives, no method to find the exact solution, other than a straightforward exhaustive search, is known. Recent progress towards producing a quantum computer of large enough scale to surpass modern supercomputers has made it increasingly relevant to consider how quantum computers may be used to solve problems of practical interest. A quantum computer using Grover?s well-known search algorithm can perform exhaustive searches that would be impractical on a classical computer, due to the speedup provided by Grover?s algorithm. Therefore, we propose to use Grover?s algorithm to find optimal encodings for finite state machines via exhaustive search. We demonstrate the design of quantum circuits that allow Grover?s algorithm to be used for this purpose. The quantum circuit design methods that we introduce are potentially applicable to other problems as well.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
Quantum computers can solve a few basic problems, such as factoring an integer and searching a database, much faster than classical computers. However, the complexity of software artifacts, and the types of questions software engineers ask about them, pose significant challenges for applying existing quantum approaches to software engineering search (SES) problems. This paper first describes a new quantum search algorithm, IDGS-FA, whose design is motivated by the characteristics of SES problems. Next, it describes how to apply quantum searching to three SES problems: FSM property checking, software test generation, and library-based software synthesis. Next, the paper gives the main ideas in QSAT, a novel toolkit supporting efficient simulation of the algorithms and applications discussed. Finally, it concludes with a substantial simulation-based study of IDGS-FA, showing that it improves both the reliability and speed of other approaches.
Traditional algorithms for simulating quantum computers on classical ones require an exponentially large amount of memory, and so typically cannot simulate general quantum circuits with more than about 30 or so qubits on a typical PC-scale platform with only a few gigabytes of main memory. However, more memory-efficient simulations are possible, requiring only polynomial or even linear space in the size of the quantum circuit being simulated. In this paper, we describe one such technique, which was recently implemented at FSU in the form of a C++ program called SEQCSim, which we releasing publicly. We also discuss the potential benefits of this simulation in quantum computing research and education, and outline some possible directions for further progress.