Unitary Realizations of Synchronizing Automata in Quantum Systems

Jȩdrzej Stempin, Jan Wójcik, Gabriela Banaszak, Andrzej Grudka, Marcin Karczewski, Paweł Kurzyński, Antoni Wójcik · 2026

Read Unitary Realizations of Synchronizing Automata in Quantum Systems by Jȩdrzej Stempin, Jan Wójcik, Gabriela Banaszak, Andrzej Grudka, Marcin Karczewski, Paweł Kurzyński, Antoni Wójcik (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-20432.txt.

Introduction

Stempin and six colleagues build a quantum version of a classical synchronizing automaton, where special input words drive the machine to a fixed state no matter where it starts. Since such resetting looks at odds with quantum unitarity, they add helper qubits encoding the automaton's alphabet, acting through one global unitary step. When the helper register starts in a synchronizing word, the machine lands in a fixed pure state while the register keeps where it began. The team shows how chosen entangled states can be made this way.

Catalog record

CREATORJȩdrzej Stempin, Jan Wójcik, Gabriela Banaszak, Andrzej Grudka, Marcin Karczewski, Paweł Kurzyński, Antoni Wójcik
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43994
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20432

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Unitary Realizations of Synchronizing Automata in Quantum Systems Jȩdrzej Stempin, Jan Wójcik, Gabriela Banaszak, Andrzej Grudka, Marcin Karczewski, Paweł Kurzyński, Antoni Wójcik Abstract We introduce a quantum analogue of a classical synchronizing automaton. In classical case the state of a system evolves according to a set of rules forming an alphabet, and sequences of these rules, called words, govern its evolution. Certain special words, known as synchronizing words, drive the automaton into a predetermined state regardless of its initial configuration. Although such an apparently irreversible process seems incompatible with the unitarity of quantum mechanics, we present a resetting protocol based on quantum synchronizing words by incorporating auxiliary qubits whose states encode the rules of the automaton’s alphabet. These qubits interact with the quantum automaton, whose state is encoded in a qudit, via a global unitary operation. When the qubit register is initially prepared in a state corresponding to a synchronizing word, the automaton evolves into a predetermined pure state independent of its initial state, while the qubit register is transformed into a complex, often entangled, state that encodes information about the automaton’s original configuration. The resulting entanglement depends on both the rule set and the automaton’s initial state, and we show how specific entangled states can be generated within this framework. I Introduction Synchronization is a broad concept that appears in various fields of science. In physics it is mostly considered to be a phenomenon in which two, or more, oscillators evolve towards the same frequency and phase. However, in computer science, particularly in automata theory, synchronization is a process that takes an automaton to a predetermined state, regardless of its initial state 3 ; 12 . Despite apparent differences, both notions of synchronization have one important common feature: it is a process that contracts the allowable state space of the system. To illustrate automata synchronization, consider a robot on a 3×3 grid that can execute only two instructions: a (attempt to move forward one cell; if the square ahead is outside the grid the robot stays put) and b (rotate left 90^{o} ). A robot state is determined by its cell (x,y) (with x=0,1,2 left \rightarrow right and y=0,1,2 top \rightarrow bottom) and its facing (one of N , E , S , W ). A synchronizing word is a finite instruction sequence that, when executed from any initial state, brings every possible robot to the same final state (or — in the weaker version we use in this example — to the same cell, possibly with different facings). The nine-letter word below is a synchronizing word that sends the robot in an arbitrary initial state to the center cell (1,1) (though final facings may differ): aabaababa. (1) Intuitively this sequence funnels robots inward. Because a has no effect at a boundary when the robot faces outward, robots on edges that point outwards are stalled while others move; the interspersed b rotations change facings so that over the whole sequence every robot will at some point face toward the interior and make the inward move. Repeating this pattern of moves-and-left-rotations eliminates the possibility of remaining on the outer ring: after the nine instructions every robot that started anywhere on the board has been moved (or held) in such a way that the only possible final cell is the center. This idea is represented in Fig. 1 . Figure 1: Schematic representation of how synchronizing word aabaababa brings the robot to the center of the grid (clockwise from an arbitrary initial state – top-left). This problem underscores the importance of a synchronization protocol – an algorithmic sequence of a and b (or even more rules) that ensures convergence to a unique final state, irrespective of the initial condition. Such sequences, known as synchronizing words 19 ; 22 ; 3 ; 5 ; 12 , are central to automata theory and have broad applications in control theory, coding, and symbolic dynamics. Contribution In this paper, we further extend the concept of synchronizing words to quantum systems 10 . A natural first approach is to translate classical synchronization schemes into the language of unitary quantum dynamics. However, a fundamental challenge arises: for synchronization to occur, there must exist operations that map multiple initial states to the same final state. This requirement conflicts with the reversibility of unitary evolution, making direct translation impossible. More generally, irreversibility need not be a fundamental obstruction if the automaton is embedded into a suitably enlarged dynamical structure. An instructive example is provided by cellular automata: Conway’s Game of Life 7 is irreversible, while the more structured Critters automaton of Toffoli and Margolus 21 admits reversible evolution. Here, we propose a method for constructing quantum synchronizing automata by introducing an auxiliary system. In particular, the automaton is encoded in a qudit, while the auxiliary system is an n -qubit register. Each of the n qubits can be in one of two orthogonal states, either |a\rangle or |b\rangle . These states encode a specific transition rule that is applied to the qudit. We then introduce a joint qubit–qudit unitary transformation. More precisely, in the i -th step of the joint evolution ( i=1,\ldots,n ), the transformation acts on the i -th qubit and applies the corresponding transition rule to the qudit. Quantum finite automata had been studied before, but not in the context of synchronization. Instead, they were viewed as quantum recognizers driven by a classical input word and yielding an acceptance probability 15 ; 13 ; 2 . Here, apart from introducing a quantum version of a synchronizing automaton, our main contribution in this work is the following proof. We show that although the transition rules a and b are, in general, non-unitary (since they contract the qudit state space), for certain contracting rules it is possible to construct a transformation that is unitary on the joint space. Such a transformation alters the state of the qubit register in a complex manner and, in general, produces non-trivial multi-qubit entanglement. While our construction can be viewed as a unitary embedding of non-unitary dynamics, it differs from a generic Stinespring dilation in an essential way. In standard dilation theory, the environment is typically introduced in an abstract and non-structured manner to reproduce a given quantum channel. In contrast, here the auxiliary system has a clear computational interpretation: it encodes a word over a finite alphabet, and the global unitary is constrained to act sequentially and locally with respect to this encoding. As a result, not every dilation corresponds to a synchronizing automaton, and the existence of such a structured unitary is governed by nontrivial combinatorial constraints, captured by Theorem 1. Our method can be used to map an arbitrary qudit state (mixed or pure) into a preassigned pure state, provided that the initial state of the qubit register is prepared in a state corresponding to a synchronizing word. This ensures reliable state preparation. Moreover, we demonstrate that, by preparing specific qudit states, our protocol can transform the qubit register into various multi-qubit entangled states. This approach naturally extends our previously proposed concept 10 and establishes a robust foundation for the development of new tools for quantum computation. II Preliminaries – Synchronizing Deterministic Finite Automata Deterministic Finite Automaton (DFA) consists of

Read the complete text