Skip to content

Quantum finite automaton

A finite-control input-reading quantum automaton whose specified transitions and measurements assign acceptance probabilities to words.

Version
v1 · 2026-10-17 · History
Domain-specific #
14268
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Quantum Computation, Formal Language Theory → Computer Science & Software Engineering
Aliases
QFA

Core Idea

A quantum finite automaton (QFA) is a formal machine with finite control that reads an input word through specified quantum transitions and measurements. Its fixed rules assign each word an acceptance probability. The definition must say how the input is read, when observation occurs, and which results accept, reject, or continue. This is a mathematical model, not a claim that a physical device was built.[ref-9b16a20cac2d][ref-a116ad98cb89]

QFA names several exact models. Ambainis and Freivalds study one-way machines with different measurement conventions. Kondacs and Watrous define a two-way machine whose head can revisit the word and whose quantum configuration includes head position. A theorem for one version retains its reading, measurement, and error premises.[ref-9b16a20cac2d][ref-a116ad98cb89]

Use Within the Domain

Researchers compare how finite control, quantum evolution, head motion, and observation affect word recognition. Before making that comparison, state the input and head rule, valid transition, observation schedule, and acceptance or error criterion. An acceptance probability alone does not imply bounded-error recognition.[ref-9b16a20cac2d][ref-a116ad98cb89]

Each fixed QFA contains a Function Mapping from admitted words to acceptance probabilities. The alphabet supplies the word domain, [0,1] the codomain, and the fixed machine rules give one value per word, even though an individual observed outcome is random. This mapping is an internal constituent; the whole QFA also requires quantum control and input-reading semantics.[ref-9b16a20cac2d][ref-a116ad98cb89]

Clarity

Keep four roles separate: finite control and word input, admissible quantum transitions, measurement and halting rules, and resulting acceptance probability. A language theorem adds a declared cutpoint or error gap. Acceptance above the one-half cutpoint differs from a uniform gap bounded away from one half.[ref-9b16a20cac2d][ref-a116ad98cb89]

“Finite” applies to internal control. In the two-way model, the head position participates in quantum configurations and can range over an input of growing length. A fixed-size whole-configuration register therefore does not describe every QFA.[^ref-a116ad98cb89]

Manages Complexity

Finite control plus transition and readout rules specify behavior for many words without listing each run. Valid updates and measurements determine each word's acceptance probability. This helps compare state costs and recognition power when the model conventions are explicit.[ref-9b16a20cac2d][ref-a116ad98cb89]

The compression has limits. A final-only measurement formula cannot replace intermediate measurements, and a one-way state count does not account for the two-way model's input-dependent head-position configurations.[ref-9b16a20cac2d][ref-a116ad98cb89]

Abstract Reasoning

To test a proposed QFA, identify its finite control, input-reading rule, valid quantum transition, and accepting, rejecting, and continuing outcomes. Determine the acceptance probability for a word. Only then apply a declared cutpoint or error condition to a language claim.[ref-9b16a20cac2d][ref-a116ad98cb89]

The original one-way unary-divisibility and two-way nonregular-language constructions illustrate why these checks matter: their head and observation rules differ, so one theorem cannot simply be transferred to the other.[ref-9b16a20cac2d][ref-a116ad98cb89]

Knowledge Transfer

The four-role test applies across formal one-way, two-way, measure-once, and measure-many QFA variants. Exact language classes and resource bounds do not transfer merely from the shared name. A quantum circuit, quantum cellular automaton, or laboratory detector is not automatically another finite-control word reader.[ref-9b16a20cac2d][ref-a116ad98cb89]

Example

One-way unary divisibility. For prime p, Ambainis and Freivalds give a one-way QFA for words a^i whose length is divisible by p, using O(log p) states for each fixed target error parameter. Symbol-conditioned unitary rotations and the chosen observation convention support this construction. The bound is specific to it.[^ref-9b16a20cac2d]

Two-way nonregular recognition. Kondacs and Watrous give a two-way QFA for {a^m b^m : m ≥ 1} with one-sided bounded error and, for a fixed construction parameter, certain linear-time halting. Its head can revisit the word, and observation separates accept, reject, and nonhalting components. This is not the one-way unary model.[^ref-a116ad98cb89]

Relationships to Other Abstractions

Local relationship map for Quantum finite automatonParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Quantum finiteautomatonDOMAINPrime abstraction: Function (Mapping) — is part ofFunction(Mapping)PRIME

Current abstraction Quantum finite automaton Domain-specific

Parents (1) — more general patterns this builds on

  • Quantum finite automaton is part of Function (Mapping) Prime

    A fixed QFA contains a single-valued rule assigning every admitted input word its acceptance probability.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

Quantum finite automaton sits in a sparse region of the domain-specific corpus (89th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2721 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-17

Not to Be Confused With

A deterministic finite automaton has a classical unique-state run, without QFA amplitude and measurement semantics. A quantum cellular automaton is organized around a spatial cell lattice; a quantum circuit is a gate network rather than, by itself, a finite-control word-reading machine. Physical quantum measurement includes a laboratory system and apparatus that these formal definitions do not assert. A random observed outcome is also different from the fixed machine's acceptance probability for a word.[ref-9b16a20cac2d][ref-a116ad98cb89]

References

[^ref-9b16a20cac2d]: Andris Ambainis and Rūsiņš Freivalds, “1-way quantum finite automata, strengths, weaknesses and generalizations,” arXiv:quant-ph/9802062v3 (30 September 1998). The published title prints a colon after “automata.” Introduction, §2.1, and §4.1 Theorem 8. https://arxiv.org/html/quant-ph/9802062 [^ref-a116ad98cb89]: Attila Kondacs and John Watrous, “On the Power of Quantum Finite State Automata,” Proceedings of the 38th Annual Symposium on Foundations of Computer Science (1997): 66–75. Author-hosted original PDF, abstract and §§2, 4 (Proposition 2), 6 (Propositions 6–7). https://cs.uwaterloo.ca/~watrous/Papers/QuantumFiniteAutomata.pdf