Regular language quantum states

\'Alvaro M. Alhambra; David P\'erez-Garc\'ia; J. Ignacio Cirac; Marta Florido-Llin\`as

arxiv: 2407.17641 · v2 · submitted 2024-07-24 · 🪐 quant-ph · cs.FL

Regular language quantum states

Marta Florido-Llin\`as , \'Alvaro M. Alhambra , David P\'erez-Garc\'ia , J. Ignacio Cirac This is my paper

Pith reviewed 2026-05-23 22:23 UTC · model grok-4.3

classification 🪐 quant-ph cs.FL

keywords regular languagesmatrix product statesquantum many-body statesfinite automatalocal unitary equivalenceshift invariance

0 comments

The pith

Regular language states are superpositions over strings accepted by finite automata that admit exact matrix-product representations together with a canonical form deciding local-unitary equivalence.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines regular language states as the equal superposition of every word belonging to a regular language. These states are shown to coincide exactly with a subclass of matrix product states whose tensors are taken from the transition matrices of the accepting automaton, yielding efficient recognition criteria. A canonical reduction of the automaton produces a fundamental theorem that classifies when two such states are identical, including after arbitrary local unitary transformations. The same tensor-network construction supplies an efficient test for whether the underlying language is invariant under a global shift of all positions.

Core claim

Regular language states arise as the uniform superposition over all words of a regular language. They are exactly the matrix product states whose local tensors come from the transition matrices of a deterministic finite automaton. A canonical reduction of these automata yields a theorem stating that two such states are equal if and only if their canonical automata coincide, and the same reduction classifies equivalence under local unitary transformations. The construction additionally supplies an efficient test for shift-invariance of the language.

What carries the argument

Matrix product states whose tensors are built directly from the transition function of the finite automaton accepting the regular language.

If this is right

States such as the GHZ, W and Dicke states belong to the regular language family.
Membership of an arbitrary quantum state in this family can be decided by an efficient matrix-product criterion.
Equivalence of two regular language states, even after local unitaries, reduces to checking equality of their canonical automata.
Shift-invariance of any regular language can be decided by a simple tensor-network test.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The automata-to-tensor mapping may let properties such as entanglement scaling be read directly from the structure of the accepting automaton.
The same construction could be used to generate new families of states whose symmetry is controlled by the choice of automaton.

Load-bearing premise

The superposition of all words in a regular language yields a physically meaningful quantum many-body state whose properties are fully captured by the classical automata theory without additional quantum constraints or convergence issues in the infinite-chain limit.

What would settle it

An explicit regular language for which the corresponding superposition state has vanishing or divergent norm on an infinite chain, or two regular language states that are locally unitarily equivalent yet possess distinct canonical automata.

read the original abstract

We introduce regular language states, a family of quantum many-body states. They are built from a special class of formal languages, called regular, which has been thoroughly studied in the field of computer science. They can be understood as the superposition of all the words in a regular language and encompass physically relevant states such as the GHZ-, W- or Dicke-states. By leveraging the theory of regular languages, we develop a theoretical framework to describe them. First, we express them in terms of matrix product states, providing efficient criteria to recognize them. We then develop a canonical form which allows us to formulate a fundamental theorem for the equivalence of regular language states, including under local unitary operations. We also exploit the theory of tensor networks to find an efficient criterion to determine when regular languages are shift-invariant.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines regular language states as superpositions over regular languages and claims MPS recognition criteria plus an equivalence theorem, but only the abstract is available.

read the letter

The core contribution is a definition of regular language states as the uniform superposition of all words accepted by a regular language, which includes standard examples like GHZ, W, and Dicke states. The authors then map these to matrix product states, state efficient recognition criteria, introduce a canonical form, prove an equivalence theorem that covers local unitary equivalence, and give a tensor-network test for shift invariance. That package of constructions is new on the face of the abstract. The approach is straightforward: it imports an established body of automata theory and applies it inside the MPS formalism without inventing new quantum objects from scratch. The abstract gives no sign of circular definitions or unsupported steps that can be spotted at this level. The main limitation is that the full text is not supplied, so none of the claimed criteria or the fundamental theorem can be checked for gaps, edge cases in the infinite-chain limit, or normalization subtleties. If the proofs are as clean as the abstract suggests, the work supplies a clean classification layer that could be useful for people already working with tensor networks. If the details turn out to have hidden assumptions, the framework would still be a reasonable starting point but would need tightening. This is the sort of paper that belongs in a quantum-information or condensed-matter journal that handles tensor-network methods; the ideas are concrete enough that a referee can evaluate them once the proofs are on the table. I would send it to review rather than desk-reject.

Referee Report

1 major / 0 minor

Summary. The manuscript introduces regular language states as a family of quantum many-body states formed by superposing all words belonging to a regular language. These states include physically relevant examples such as the GHZ, W, and Dicke states. The authors claim to express them via matrix product states, supply efficient criteria for their recognition, introduce a canonical form that yields a fundamental theorem on equivalence (including under local unitaries), and derive an efficient tensor-network criterion for determining when the underlying regular languages are shift-invariant.

Significance. If the claimed results hold, the work would establish a direct link between automata theory and tensor-network representations of quantum states, potentially supplying computationally efficient methods for state identification and equivalence testing that exploit existing results from computer science.

major comments (1)

[Abstract] Abstract: the manuscript consists solely of the abstract; no derivations, proofs, explicit MPS constructions, canonical-form definitions, or tensor-network arguments are supplied. It is therefore impossible to verify whether the stated efficient recognition criteria, the fundamental equivalence theorem, or the shift-invariance criterion are correct or free of gaps.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their comments. We address the sole major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the manuscript consists solely of the abstract; no derivations, proofs, explicit MPS constructions, canonical-form definitions, or tensor-network arguments are supplied. It is therefore impossible to verify whether the stated efficient recognition criteria, the fundamental equivalence theorem, or the shift-invariance criterion are correct or free of gaps.

Authors: We acknowledge that only the abstract is provided in the current version. The full manuscript will include all derivations, explicit MPS constructions, the definition of the canonical form, the proof of the equivalence theorem (including under local unitaries), and the tensor-network criterion for shift-invariance. These follow from combining the Myhill-Nerode theorem and minimal DFA representations with standard MPS gauge fixing and contraction techniques; the abstract summarizes results that are fully derived in the complete text. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The abstract describes a framework that maps regular languages (an established concept from computer science) onto quantum states via matrix product states and tensor networks, then derives recognition criteria, a canonical form, an equivalence theorem, and a shift-invariance condition. All steps are presented as applications of pre-existing external theories rather than quantities defined in terms of the paper's own outputs. No equations, self-citations, fitted parameters, or ansatzes are supplied in the available text, so no load-bearing step reduces to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on the standard mathematical theory of regular languages and finite automata (already established in computer science) plus the assumption that these can be directly lifted to quantum superpositions representable by matrix product states.

axioms (2)

standard math Theory of regular languages and finite automata from computer science
Leveraged throughout to define the states and derive criteria
domain assumption Matrix product states and tensor networks form a complete representational language for the states in question
Invoked to obtain efficient recognition and shift-invariance tests

invented entities (1)

regular language states no independent evidence
purpose: New family of quantum many-body states defined as superpositions over regular languages
Introduced in the paper; no independent evidence supplied in abstract

pith-pipeline@v0.9.0 · 5644 in / 1477 out tokens · 26034 ms · 2026-05-23T22:23:20.194375+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat recovery; no automata/MPS link unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Any family of RLS Lq admits an MPS description... given any UFA F=⟨Q,Σ,δ,I,F⟩... Ai_j^x = 1 if j∈δ(i,x)
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel (J unique) unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Canonical decomposition... L=∪m∪j S(m)(Lm_j,Xm_j) ... minimal DFA tensors

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.