A quantum model for synchronizing finite state transition systems

• URL: http://arxiv.org/abs/2607.06953v1
• Date: Wed, 08 Jul 2026 03:27:19 GMT
• Title: A quantum model for synchronizing finite state transition systems
• Abstract summary: We propose a quantum model for finding a resetting input sequence (RS) which can take a finite state transition system (FA) independent of its current state.<n>We represent the FA states, inputs, and transition function in quantum space.<n>As a proof of concept we provide results of several simulated FAs on a quantum simulator.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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. As a proof of concept we provide results of several simulated FAs on a quantum simulator.

Related papers

• Efficient classical representation and quantum state preparation of complete active space wavefunctions [0.0]
  Quantum computers promise to solve the electronic structure problem for a large class of molecules.<n>For classically challenging molecules with strong electron correlation, starting from multi-reference states, such as complete active space (CAS) wavefunctions is necessary.<n>Here, we show that there exists an efficient classical representation of CAS states and to design a new state preparation routine outperforming previous ones.
  arXiv  Detail & Related papers  (2026-06-17T18:00:28Z)
• On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach [59.589793281734636]
  We show that Statistical Query hardness can be established when both the alphabet size and input length are in the number of states.<n>Our result is derived solely from the internal state-transition structure of semiautomata.
  arXiv  Detail & Related papers  (2025-10-05T09:35:35Z)
• Efficient Preparation of Solvable Anyons with Adaptive Quantum Circuits [0.0]
  We show how to prepare anyon theories that admit a gapped boundary via Adaptive Finite-Depth Local Unitary (AFDLU)<n>Specifically, we introduce a sequential gauging procedure, with an AFDLU implementation, to produce a string-net ground state in any topological phase.<n>In addition, we introduce a sequential ungauging and regauging procedure, with an AFDLU implementation, to apply string operators of arbitrary length for anyons.
  arXiv  Detail & Related papers  (2024-11-07T18:55:09Z)
• Prompting a Pretrained Transformer Can Be a Universal Approximator [105.59562522323274]
  We show that much smaller pretrained models than previously thought can be universal approximators when prefixed. We also offer Jackson-type bounds on the length of the prefix needed to approximate a function to a desired precision.
  arXiv  Detail & Related papers  (2024-02-22T18:12:48Z)
• Sufficient condition for universal quantum computation using bosonic circuits [44.99833362998488]
  We focus on promoting circuits that are otherwise simulatable to computational universality. We first introduce a general framework for mapping a continuous-variable state into a qubit state. We then cast existing maps into this framework, including the modular and stabilizer subsystem decompositions.
  arXiv  Detail & Related papers  (2023-09-14T16:15:14Z)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit. We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
  arXiv  Detail & Related papers  (2023-03-02T18:08:08Z)
• Orthogonal-ansatz VQE: Locating excited states without modifying a cost-function [0.0]
  We develop an excited-state VQE solver which trades increasing measurement complexity for increasing circuit complexity. We demonstrate our approach with three distinct ansatze, beginning with a simple single-body example, before generalizing to accommodate the full Hilbert space spanned by all qubits.
  arXiv  Detail & Related papers  (2022-04-09T02:22:09Z)
• Quantum simulation of $\phi^4$ theories in qudit systems [53.122045119395594]
  We discuss the implementation of quantum algorithms for lattice $Phi4$ theory on circuit quantum electrodynamics (cQED) system. The main advantage of qudit systems is that its multi-level characteristic allows the field interaction to be implemented only with diagonal single-qudit gates.
  arXiv  Detail & Related papers  (2021-08-30T16:30:33Z)
• On quantum states with a finite-dimensional approximation property [0.0]
  We consider a class of quantum states containing finite rank states containing infinite rank states with the sufficient rate decreasing of eigenvalues. We show that this property implies finiteness of the entropy von Neumann entropy but unsolved the question concerning the converse implication. We establish the uniform continuity of the above characteristics as functions of a channel w.r.t.
  arXiv  Detail & Related papers  (2021-03-17T13:15:04Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• On the Complexity of Symbolic Finite-State Automata [7.386725677365395]
  We revisit the complexity of procedures on SFAs (such as intersection, emptiness, etc.) and analyze them according to the measures we find suitable for symbolic automata. We pay attention to the special forms of SFAs: normalized SFAs and neat SFAs, as well as to SFAs over a monotonic effective Boolean algebra.
  arXiv  Detail & Related papers  (2020-11-10T20:55:55Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.