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:2607.06953

A quantum model for synchronizing finite state transition systems

Martin Lukac, Khaled El-Fakih, Uraz Turker

quant-phcs.ETSubmitted Jul 8, 2026• Announced Jul 9, 2026• 0 citations• Revised Sep 15, 2026 (v2)
v1 · Jul 8, 2026v2 · Sep 15, 2026v3 · Sep 18, 2026
arXivHTMLPDF

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.

Comments
13 pages, 7 Figures

Related papers

Simulation of finite state machines in a quantum computer

Michael R. Dunlavey

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.

arXiv:quant-ph/9807026•Jul 9, 1998•4 citations

Quantum synchronizing words

Andrzej Grudka, Marcin Karczewski, Paweł Kurzyński +3 more

Abstract Synchronizing words in classical automata theory provide a mechanism to reset any state of a deterministic automaton to a specific target state via a carefully chosen finite sequence of transition rules. In this work, we extend the concept of synchronizing words to quantum information theory. Specifically, we investigate whether the concatenation of two non-resetting quantum channels can give rise to a resetting channel. While we formulate the problem for general qudits, the complexity of the setting leads us to focus on particular resetting concatenations for qubits and qutrits. Furthermore, we demonstrate that following the reset, any pure real qutrit state can be closely approximated using the same two non-resetting channels. These findings establish a quantum analogue of synchronizing words, highlighting their potential applications in constructing minimal sets of quantum channels capable of both resetting and preparing arbitrary states.

New Journal of Physics•Oct 23, 2025•1 citation

On the Reachability Problem in Quantum Petri Nets

Syed Asad Shah, A. Yavuz Oruc

In this paper, we propose a novel quantum solution to address the problem of reachability in bounded quantum Petri nets (QPNs), an advanced modeling framework that combines the classical Petri net model with quantum mechanical principles. The proposed approach exploits quantum parallelism to construct a superposition over all reachable markings from the initial marking. Grover's amplitude amplification algorithm is then applied to efficiently identify a desired target marking, while ancillary q-tokens used solely for transition control are excluded from the search space, significantly reducing its size. Theoretical analysis shows that our approach achieves a quadratic speed up over classical exhaustive algorithms. Experimental results also confirm the correctness and feasibility of the proposed quantum algorithm for solving the bounded reachability problem in Quantum Petri Nets.

quant-pharXiv:2608.21428•Aug 18, 2026•0 citations

Quantum search algorithm for similar subgraph identification under fixed edge removal

Ruben Kara, Sven Danz, Tobias Stollenwerk +1 more

We introduce a novel quantum algorithm for similar subgraph identification in form of an NP-hard cardinality-constrained binary quadratic optimization problem. Given a weighted reference graph with Laplacian $\boldsymbol{B}$, our algorithm determines the subgraph featuring Laplacian $\boldsymbol{B'}$ on the same vertex set, but $x$ out of $N$ inactive edges, minimizing the Frobenius distance $||\boldsymbol{B} - \boldsymbol{B'}||_\mathrm{F}^2$. We represent the $\binom{N}{x}$ graph topologies by an equal-weight superposition in form of a Dicke state, enabling controlled transformations applied to the quantum state associated with the vectorized Laplacian of the reference graph. Combined with amplitude estimation and a minimum finding approach, our algorithm provides a polynomial speed up $\mathcal{O}(\sqrt{N^{x}/x!}N\log\log N)$ compared to $\mathcal{O}(N^{x+1}/x!)$ of classical brute-force search algorithms. We demonstrate the application of our method on standard test cases, which represent electric power grids, by reconstructing $||\boldsymbol{B} -\boldsymbol{B'}||_\mathrm{F}^2$ from measurements and show how our approach can be additionally used to calculate energy functional like quadratic forms of the Laplacians with respect to a given vector.

quant-pharXiv:2604.02027•Apr 3, 2026•0 citations

Dynamic Programming for Quantum State Preparation

Jincheng Zhang

Quantum state preparation is a critical component in many quantum algorithms, yet its complexity scales exponentially with the number of qubits and the desired state's complexity. This work presents a novel approach to quantum state preparation utilizing dynamic programming. We demonstrate that dynamic programming can efficiently determine optimal sequences of quantum gates to realize a target quantum state, significantly reducing the computational burden compared to exhaustive search methods. The core of our method lies in formulating the problem as a state-space optimization task, where each state represents a partial quantum state and the transition between states corresponds to applying a quantum gate. We detail the algorithm and provide a theoretical analysis of its performance, highlighting its potential to mitigate the exponential scaling issues inherent in traditional quantum state preparation techniques. This approach offers a practical and scalable solution for preparing complex quantum states, representing a significant advancement in the field.

•Sep 6, 2026•0 citations

Analysis of mathematical models of quantum parallelism

Petro A. Kravets

This article analyzes mathematical models of quantum parallelism based on the transfer of a quantum system into a superposition state. The principles of quantum parallelism and its mathematical foundations are substantiated. To demonstrate the quantum advantage, mathematical models of fundamental quantum algorithms Deutsch-Joža and Grover are analyzed, which illustrate the efficiency of quantum computing compared to classical methods. The Deutsch-Joshy algorithm is considered, which generalizes the problem of determining the type of a binary function by extending it to a set of arguments written in a quantum register. This algorithm allows determining whether a function is constant or balanced in a single quantum call, while in classical calculations this requires exponential time. It is noted that although the Deutsch-Joshy algorithm demonstrates the possibilities of parallel quantum computing, it is of mainly theoretical importance. Grover’s algorithm implements quantum parallel computing for the practical problem of searching for an element in an unordered database. It is based on iterative amplification of the amplitude of the state corresponding to the searched element and provides quadratic speedup compared to classical algorithms. In addition to database search, Grover’s algorithm can be adapted to solve other optimization problems. The work of the considered algorithms is illustrated by numerical examples, which simplifies the understanding of their principles and contributes to the further methodological development of parallel quantum computing. The article also outlines the advantages of quantum parallelism over classical computing and identifies the prospects for the application of parallel quantum algorithms.

Vìsnik Nacìonalʹnogo unìversitetu Lʹvìvsʹka polìtehnìka Serìâ Ìnformacìjnì sistemi ta merežì•Jun 1, 2025•2 citations
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.
Abstract Synchronizing words in classical automata theory provide a mechanism to reset any state of a deterministic automaton to a specific target state via a carefully chosen finite sequence of transition rules. In this work, we extend the concept of synchronizing words to quantum information theory. Specifically, we investigate whether the concatenation of two non-resetting quantum channels can give rise to a resetting channel. While we formulate the problem for general qudits, the complexity of the setting leads us to focus on particular resetting concatenations for qubits and qutrits. Furthermore, we demonstrate that following the reset, any pure real qutrit state can be closely approximated using the same two non-resetting channels. These findings establish a quantum analogue of synchronizing words, highlighting their potential applications in constructing minimal sets of quantum channels capable of both resetting and preparing arbitrary states.
In this paper, we propose a novel quantum solution to address the problem of reachability in bounded quantum Petri nets (QPNs), an advanced modeling framework that combines the classical Petri net model with quantum mechanical principles. The proposed approach exploits quantum parallelism to construct a superposition over all reachable markings from the initial marking. Grover's amplitude amplification algorithm is then applied to efficiently identify a desired target marking, while ancillary q-tokens used solely for transition control are excluded from the search space, significantly reducing its size. Theoretical analysis shows that our approach achieves a quadratic speed up over classical exhaustive algorithms. Experimental results also confirm the correctness and feasibility of the proposed quantum algorithm for solving the bounded reachability problem in Quantum Petri Nets.
We introduce a novel quantum algorithm for similar subgraph identification in form of an NP-hard cardinality-constrained binary quadratic optimization problem. Given a weighted reference graph with Laplacian B\boldsymbol{B}B, our algorithm determines the subgraph featuring Laplacian B′\boldsymbol{B'}B′ on the same vertex set, but xxx out of NNN inactive edges, minimizing the Frobenius distance ∣∣B−B′∣∣F2||\boldsymbol{B} - \boldsymbol{B'}||_\mathrm{F}^2∣∣B−B′∣∣F2​. We represent the (Nx)\binom{N}{x}(xN​) graph topologies by an equal-weight superposition in form of a Dicke state, enabling controlled transformations applied to the quantum state associated with the vectorized Laplacian of the reference graph. Combined with amplitude estimation and a minimum finding approach, our algorithm provides a polynomial speed up O(Nx/x!Nlog⁡log⁡N)\mathcal{O}(\sqrt{N^{x}/x!}N\log\log N)O(Nx/x!​NloglogN) compared to O(Nx+1/x!)\mathcal{O}(N^{x+1}/x!)O(Nx+1/x!) of classical brute-force search algorithms. We demonstrate the application of our method on standard test cases, which represent electric power grids, by reconstructing ∣∣B−B′∣∣F2||\boldsymbol{B} -\boldsymbol{B'}||_\mathrm{F}^2∣∣B−B′∣∣F2​ from measurements and show how our approach can be additionally used to calculate energy functional like quadratic forms of the Laplacians with respect to a given vector.
Quantum state preparation is a critical component in many quantum algorithms, yet its complexity scales exponentially with the number of qubits and the desired state's complexity. This work presents a novel approach to quantum state preparation utilizing dynamic programming. We demonstrate that dynamic programming can efficiently determine optimal sequences of quantum gates to realize a target quantum state, significantly reducing the computational burden compared to exhaustive search methods. The core of our method lies in formulating the problem as a state-space optimization task, where each state represents a partial quantum state and the transition between states corresponds to applying a quantum gate. We detail the algorithm and provide a theoretical analysis of its performance, highlighting its potential to mitigate the exponential scaling issues inherent in traditional quantum state preparation techniques. This approach offers a practical and scalable solution for preparing complex quantum states, representing a significant advancement in the field.
This article analyzes mathematical models of quantum parallelism based on the transfer of a quantum system into a superposition state. The principles of quantum parallelism and its mathematical foundations are substantiated. To demonstrate the quantum advantage, mathematical models of fundamental quantum algorithms Deutsch-Joža and Grover are analyzed, which illustrate the efficiency of quantum computing compared to classical methods. The Deutsch-Joshy algorithm is considered, which generalizes the problem of determining the type of a binary function by extending it to a set of arguments written in a quantum register. This algorithm allows determining whether a function is constant or balanced in a single quantum call, while in classical calculations this requires exponential time. It is noted that although the Deutsch-Joshy algorithm demonstrates the possibilities of parallel quantum computing, it is of mainly theoretical importance. Grover’s algorithm implements quantum parallel computing for the practical problem of searching for an element in an unordered database. It is based on iterative amplification of the amplitude of the state corresponding to the searched element and provides quadratic speedup compared to classical algorithms. In addition to database search, Grover’s algorithm can be adapted to solve other optimization problems. The work of the considered algorithms is illustrated by numerical examples, which simplifies the understanding of their principles and contributes to the further methodological development of parallel quantum computing. The article also outlines the advantages of quantum parallelism over classical computing and identifies the prospects for the application of parallel quantum algorithms.