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 show that with only two quantum channels, it is possible to bring an arbitrary qutrit state close to a designated target state. Furthermore, we demonstrate that following this reset, any pure real qutrit state can be closely approximated using the same two channels. These findings establish a quantum analogue of synchronizing words, highlighting their potential applications in constructing minimal sets of universal quantum gates capable of both resetting and preparing arbitrary states.
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 show that with only two quantum channels, it is possible to bring an arbitrary qutrit state close to a designated target state. Furthermore, we demonstrate that following this reset, any pure real qutrit state can be closely approximated using the same two channels. These findings establish a quantum analogue of synchronizing words, highlighting their potential applications in constructing minimal sets of universal quantum gates capable of both resetting and preparing arbitrary states.
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.
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.
We introduce the quantum Černý complexity qc(w) of a binary word w: the least dimension d for which there exist quantum channels A0,A1 on d×d density matrices and a start state ρ0 such that w is the unique shortest word whose associated channel is constant on the reachable set. We show that 2≤qc(w)≤⌈∣w∣+1⌉ for every nonempty w, a quadratic saving over the classical analogue, and that constant words are extremal: qc(0m)=⌈m+1⌉. In contrast, qc(01n0)=2 for every n≥1, realized by a single qubit whose rotation angle acts as a counter; consequently there is no quantum analogue of the Černý function, and qc is strongly anti-correlated with intuitive notions of descriptive complexity. We further study the variant qcp in which the synchronization target is required to be a pure state. We prove that in dimension 2 no word of length at least 2 can be a unique shortest synchronizing word with pure target, and we exhibit an explicit qutrit instance, combining a coherent rotation with a measure-and-funnel channel, achieving qcp(01n0)=3 with target a computational basis state and with synchronization holding universally over all input states. Thus purity of the reset state costs exactly one dimension on this family. We also observe that qc is computable, by reduction to the first-order theory of the reals.
Quantum computers present a compelling platform for the study of open quantum systems, namely the non-unitary dynamics of a system. Here, we investigate and report digital simulations of Markovian, non-unitary dynamics that converge to a unique steady state. The steady state is programmed as a desired target state, yielding semblance to a quantum state preparation protocol. By delegating ancilla qubits and systems qubits, the system state is driven to the target state by repeatedly performing the following steps: (1) executing a designated system-ancilla entangling circuit, (2) measuring the ancilla qubits, and (3) re-initializing ancilla qubits to known states through active reset. While the ancilla qubits are measured and reinitialized to known states, the system qubits undergo a non-unitary evolution and are steered from arbitrary initial states to desired target states. We show results of the method by preparing arbitrary qubit states and qutrit (three-level) states on contemporary quantum computers. We also demonstrate that the state convergence can be accelerated by utilizing the readouts of the ancilla qubits to guide the protocol in a non-blind manner. Our work serves as a nontrivial example that incorporates and characterizes essential operations such as qubit reuse (qubit reset), entangling circuits, and measurement. These operations are not only vital for near-term noisy intermediate-scale quantum (NISQ) applications but are also crucial for realizing future error-correcting codes.