A quantum model for synchronizing finite state transition systems
Abstract
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.
Related
- Unitary realizations of synchronizing automata in quantum systems
- Finite-Frequency Boson-Number Bounds Across the Quantum Rabi Transition
- Finite-temperature transition-window weights on a fault-tolerant quantum computer: duplex filtering on a thermal purification
- Correlation and Branching Mechanisms in the Quantum-to-Classical Transition of Interacting Systems
- On the Structure of Quantum Finite-Level Systems: Decoherence-Free Subsystems, Quantum Nondemolition Variables, and Back-Action-Evading Measurements
BibTeX
@misc{lukac2026quantum,
title = {{A quantum model for synchronizing finite state transition systems}},
author = {Martin Lukac and Khaled El-Fakih and Uraz Turker},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.06953},
eprint = {2607.06953},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.06953},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - A quantum model for synchronizing finite state transition systems
AU - Martin Lukac
AU - Khaled El-Fakih
AU - Uraz Turker
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2607.06953
UR - https://arxiv.org/abs/2607.06953
AB - 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.
ER -