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:2406.11360 · Lecture notes in computer science

A Representative Framework for Implementing Quantum Finite Automata on Real Devices

Aliya Khadieva, Özlem Salehi, Abuzer Yakaryılmaz

Published Jan 1, 2024• 9 citations
arXivHTMLPDF
DOI
10.1007/978-3-031-63742-1_12

Related papers

Implementing Quantum Finite Automata Algorithms on Noisy Devices

Utku Birkan, Özlem Salehi, Viktor Olejár +2 more

arXiv:2105.06184•Lecture notes in computer science•Jan 1, 2021•13 citations

On the Simulation Cost of Quantum Finite Automata

Zeyu Chen, Junde Wu

This paper identifies exact probabilistic simulation cost as the natural quantitative measure of quantum advantage for finite automata under strict cutpoints. It gives sharp simulation laws for two representative models. A one-way finite automaton with $c$ classical states and a $q$-dimensional quantum register has exact probabilistic simulation cost $Θ(cq^2)$, while an $n$-dimensional measure-once one-way quantum finite automaton has worst-case cost $Θ(n^2)$. The proofs develop a prepare--test framework, in which prefixes generate the relevant real operator degrees of freedom and suffixes convert them into strict-cutpoint tests. The same obstruction is recast through finite sign-rank matrices, clarifying the role of Forster's spectral method. Placed beside the surrounding two-way separations, these results give a clean hierarchy of finite-automata quantum advantage.

quant-pharXiv:2605.10682•May 12, 2026•2 citations

Quantum Implementation of Finite State Automata

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

Lecture notes in networks and systems•Jan 1, 2025•0 citations

Models of Quantum Cellular Automata

Carlos A. Pérez-Delgado, Donny Cheung

In this paper we present a systematic view of Quantum Cellular Automata (QCA), a mathematical formalism of quantum computation. First we give a general mathematical framework with which to study QCA models. Then we present four different QCA models, and compare them. One model we discuss is the traditional QCA, similar to those introduced by Shumacher and Werner, Watrous, and Van Dam. We discuss also Margolus QCA, also discussed by Schumacher and Werner. We introduce two new models, Coloured QCA, and Continuous-Time QCA. We also compare our models with the established models. We give proofs of computational equivalence for several of these models. We show the strengths of each model, and provide examples of how our models can be useful to come up with algorithms, and implement them in real-world physical devices.

arXiv:quant-ph/0508164•Aug 23, 2005•15 citations

Simulations of Quantum Finite Automata

Gustaw Lippa, Krzysztof Makieła, Marcin Kuta

Lecture notes in computer science•Jan 1, 2020•0 citations

Verifying Repeat-until-Success Protocols using Automata

Jyun-Ao Lin, Yu‐Fang Chen, Jakub Havlík +4 more

Repeat-until-success (RUS) protocols implement single-qubit unitaries using measurement, classical control, and unbounded looping. Verifying their functional correctness is challenging due to the combination of probabilistic branching, unbounded looping, and the need to reason about all input states. In this paper, we develop a fully automated framework for verifying the functional correctness of these protocols. The framework is based on viewing quantum states as trees and sets of quantum states as sets of trees, which can be represented using tree automata. The particular automata model that we use are level-synchronized tree automata (), in which nondeterminism is labelled by a choice . Since we can map a sequence of choices to a particular tree (and therefore a quantum state) in the language of an LSTA, we can use the choice-sequence semantics to track input-output correspondence (which input quantum state got transformed into which output quantum state) and enable relational verification. To deal with reasoning about infinitely many quantum states, we prove a three-test theorem, which reduces verifying correctness of RUS protocols to testing correctness on finitely many inputs, enabling automatic invariant synthesis and decidable verification. We implemented our approach and identified previously unreported bugs in the RUS literature.

Proceedings of the ACM on Programming Languages•Oct 1, 2026•0 citations
This paper identifies exact probabilistic simulation cost as the natural quantitative measure of quantum advantage for finite automata under strict cutpoints. It gives sharp simulation laws for two representative models. A one-way finite automaton with ccc classical states and a qqq-dimensional quantum register has exact probabilistic simulation cost Θ(cq2)Θ(cq^2)Θ(cq2), while an nnn-dimensional measure-once one-way quantum finite automaton has worst-case cost Θ(n2)Θ(n^2)Θ(n2). The proofs develop a prepare--test framework, in which prefixes generate the relevant real operator degrees of freedom and suffixes convert them into strict-cutpoint tests. The same obstruction is recast through finite sign-rank matrices, clarifying the role of Forster's spectral method. Placed beside the surrounding two-way separations, these results give a clean hierarchy of finite-automata quantum advantage.
In this paper we present a systematic view of Quantum Cellular Automata (QCA), a mathematical formalism of quantum computation. First we give a general mathematical framework with which to study QCA models. Then we present four different QCA models, and compare them. One model we discuss is the traditional QCA, similar to those introduced by Shumacher and Werner, Watrous, and Van Dam. We discuss also Margolus QCA, also discussed by Schumacher and Werner. We introduce two new models, Coloured QCA, and Continuous-Time QCA. We also compare our models with the established models. We give proofs of computational equivalence for several of these models. We show the strengths of each model, and provide examples of how our models can be useful to come up with algorithms, and implement them in real-world physical devices.
Repeat-until-success (RUS) protocols implement single-qubit unitaries using measurement, classical control, and unbounded looping. Verifying their functional correctness is challenging due to the combination of probabilistic branching, unbounded looping, and the need to reason about all input states. In this paper, we develop a fully automated framework for verifying the functional correctness of these protocols. The framework is based on viewing quantum states as trees and sets of quantum states as sets of trees, which can be represented using tree automata. The particular automata model that we use are level-synchronized tree automata (), in which nondeterminism is labelled by a choice . Since we can map a sequence of choices to a particular tree (and therefore a quantum state) in the language of an LSTA, we can use the choice-sequence semantics to track input-output correspondence (which input quantum state got transformed into which output quantum state) and enable relational verification. To deal with reasoning about infinitely many quantum states, we prove a three-test theorem, which reduces verifying correctness of RUS protocols to testing correctness on finitely many inputs, enabling automatic invariant synthesis and decidable verification. We implemented our approach and identified previously unreported bugs in the RUS literature.