⚛️ quantum physics

Compiling Quantum Regular Language States

This paper presents a quantum state-preparation compiler that accepts structure-aware specifications of regular language states and their complements, translating them into minimized deterministic finite automata and matrix product states to generate efficient, hardware-aware circuits with predictable resource guarantees.

Original authors: Armando Bellante, Reinis Irmejs, Marta Florido-Llinàs, María Cea Fernández, Marianna Crupi, Matthew Kiser, J. Ignacio Cirac

Published 2026-02-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Armando Bellante, Reinis Irmejs, Marta Florido-Llinàs, María Cea Fernández, Marianna Crupi, Matthew Kiser, J. Ignacio Cirac

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to program a quantum computer. Usually, telling the machine what to do is like trying to describe a massive, complex city by listing every single street address, house number, and resident. If the city has a million houses, you have to write down a million addresses. This is slow, tedious, and impossible for large systems.

Alternatively, you might know a specific type of city layout (like a grid or a circle) and use a pre-made "blueprint" just for that. But what if your city is a unique mix of patterns that doesn't fit a standard blueprint?

This paper introduces a new "translator" (a compiler) that sits between these two extremes. It allows users to describe a quantum state using simple, structured rules—like a recipe or a traffic map—rather than a massive list of data. The authors call these Regular Language States (RLS).

Here is how their system works, explained through everyday analogies:

1. The Input: Giving Instructions in Plain English

Instead of forcing the user to list every single valid combination of bits (like 001, 110, 101...), the user can describe the pattern in three easy ways:

A List: "Here are the 10 specific strings I want."
A Regex (Pattern): "I want all strings that look like 001 followed by any number of 1s." (Like a search filter).
A Flowchart (DFA): A simple diagram showing how to move from a "Start" to an "Accept" state based on 0s and 1s.

The Magic Trick: The user can also say, "I want everything except this pattern." Usually, describing "everything except X" is a nightmare because the "except" list is huge. This compiler handles that effortlessly.

2. The Middleman: The "Traffic Cop" (DFA)

Once the user gives the instructions, the compiler doesn't jump straight to the quantum machine. First, it converts the input into a Deterministic Finite Automaton (DFA).

Think of the DFA as a traffic cop or a turnstile. It's a simple machine that checks if a string of bits is "allowed" or "forbidden."

The compiler takes the user's messy input and cleans it up into the smallest, most efficient version of this traffic cop.
Why this matters: Instead of doing heavy, expensive math on a giant list of numbers, the compiler does simple logic puzzles on this traffic cop. It's much faster and reveals the hidden structure of the data.

3. The Blueprint: The "MPS" (Matrix Product State)

Once the traffic cop is optimized, the compiler translates it into a Matrix Product State (MPS).

Analogy: Imagine the quantum state as a long chain of beads. An MPS breaks this chain into small, manageable links. Each link only needs to know about its immediate neighbors, not the whole chain.
This step compresses the information. If the pattern is simple (like a repeating rhythm), the chain of links stays short. If the pattern is chaotic, the links get bigger. The compiler automatically figures out the smallest size needed.

4. The Construction: Building the Circuit

Now the compiler has the compressed blueprint (the MPS). It needs to build the actual quantum circuit (the instructions for the computer). The paper offers two ways to build this, depending on the hardware:

SeqRLSP (The Assembly Line):
- Best for: Computers where qubits are lined up in a row and can only talk to their immediate neighbors.
- How it works: It builds the state one bead at a time, moving down the line. It's efficient and doesn't need extra "helper" qubits (ancillae).
TreeRLSP (The Tree House):
- Best for: Computers where any qubit can talk to any other qubit (all-to-all).
- How it works: It builds the state in a tree structure, combining pairs of qubits, then pairs of pairs, and so on. This is much faster (logarithmic depth) because it does many things at once.

5. The "Complement" Superpower

One of the paper's biggest claims is handling complements (the "NOT" version of a state).

The Problem: If you want a state that includes every possible string except 000, listing the "allowed" strings is impossible (there are billions).
The Solution: The compiler realizes that if the "forbidden" list is small (just 000), the "allowed" list is huge, but the structure is still simple. It proves that building the "allowed" state takes the same amount of effort as building the "forbidden" one. It's like saying, "It's just as easy to build a wall around a small garden as it is to build a wall around the rest of the world, if you already have the garden's map."

Summary of Results

The authors built this entire system and tested it. They showed that:

It works: They successfully compiled complex states (like Dicke and W states) and their complements.
It's efficient: The time it takes to compile and the size of the resulting circuit are predictable and scale well with the complexity of the pattern, not the size of the universe of possibilities.
It's flexible: It works on different types of quantum hardware (linear chains vs. fully connected networks).

In short, this paper provides a tool that lets programmers describe quantum states using simple rules (like a recipe) rather than massive data dumps, automatically figuring out the most efficient way to build them on a quantum computer, even for the "everything except this" scenarios.

Technical Summary: Compiling Quantum Regular Language States

Problem Statement
Current quantum state preparation compilers operate at two extremes: general-purpose routines that treat target states as opaque amplitude vectors (often missing exploitable structure and yielding inefficient circuits), and bespoke constructions for specific, well-known state families (e.g., GHZ, W, Dicke states). This gap leaves users without a method to provide simple, structure-aware specifications that do not require naming a specific state family, yet still guarantee predictable and efficient resource bounds. Furthermore, existing tools struggle with the "complement" problem: describing a state as the uniform superposition of all bitstrings except a small set of forbidden strings. While the forbidden set may be small, the resulting state has exponentially large support, making standard sparse-state compilation intractable.

Methodology
The authors propose a modular, end-to-end compiler pipeline that bridges formal language theory and tensor network synthesis. The pipeline accepts three types of user inputs: (i) a finite set of bitstrings, (ii) a regular expression, or (iii) a Deterministic Finite Automaton (DFA), with an optional flag to request the complement of the language.

The compilation proceeds through the following stages:

Input to Automaton: The user input is converted into a DFA. If a set of strings is provided, a Directed Acyclic Graph DFA (DAG-DFA) is constructed. If a regular expression is provided, it is compiled into a DFA (potentially via an NFA).
Minimization and Complement: The DFA is minimized using Hopcroft's algorithm to obtain a canonical minimal DFA. If a complement is requested, the automaton is modified by exchanging accepting and non-accepting states (and adding a sink state if necessary) before re-minimization. The authors prove that the minimal DFA size for a complement increases by at most 1 compared to the base language.
Automaton to Matrix Product State (MPS): The minimal DFA (or DAG-DFA) is mapped to an MPS. The DFA states correspond to bond indices, and input symbols correspond to physical indices. This yields an intermediate representation (IR) where the bond dimension $D$ equals the number of states in the minimal DFA (or the maximum layer size for DAG-DFAs).
MPS to Isometries: The MPS is decomposed into a network of isometries. The authors outline two backend strategies:
- SeqRLSP: A sequential SVD sweep (left-to-right and right-to-left) that produces a linear-depth, ancilla-free circuit suitable for Linear Nearest-Neighbor (LNN) architectures. This pass also optimizes the bond dimensions to match the exact Schmidt rank $\chi$ of the target state.
- TreeRLSP: A hierarchical, tree-based SVD scheme that produces a logarithmic-depth circuit suitable for all-to-all connectivity.
Circuit Synthesis: The isometries are padded to powers of two, embedded into unitaries, and transpiled into the target hardware's native gate set.

Key Contributions

Structure-Aware Specification: The paper introduces a specification method using regular languages (regex, DFA, or finite sets) that allows users to describe large, structured supports concisely without needing to identify specific state families.
Native Complement Handling: The compiler natively supports the synthesis of complement states. It demonstrates that the complement of a regular language state can be compiled with the same asymptotic quantum cost as the base description, as the maximal Schmidt rank increases by at most 1.
End-to-End Pipeline: The work bridges the gap between regular language theory and MPS-based circuit synthesis, providing a unified compiler with two hardware-aware backends (SeqRLSP and TreeRLSP).
Theoretical Bounds: The authors provide explicit bounds on circuit depth and gate count scaling with the system size $N$ and the maximal Schmidt rank $\chi$ . They also establish compile-time bounds, showing that the DFA minimization step offloads expensive linear algebra operations to simpler automata manipulations.
Empirical Evaluation: The full pipeline is implemented and benchmarked against general-purpose (Qiskit), sparse-state (Qualtran), and specialized baselines. Evaluations include Dicke states, W states, random uniform superpositions, and their complements.

Results

Resource Efficiency: The compiler achieves linear depth for LNN architectures and logarithmic depth for all-to-all architectures. The resource cost scales with the maximal Schmidt rank $\chi$ rather than the full Hilbert space dimension $2^N$ .
Complement Performance: The experiments confirm that preparing a complement state does not incur exponential overhead in circuit depth or gate count compared to the base state, provided the underlying language is regular.
Compile Time: The use of DFA minimization before MPS conversion significantly reduces compile time compared to methods that operate directly on large tensor representations or amplitude vectors.
Benchmarking: On Dicke and W states, the proposed method matches or outperforms specialized routines while offering a more general specification interface. For complement states, where sparse-state compilers fail due to dense support, the proposed method succeeds efficiently.

Significance
The paper claims to offer a "middle ground" solution that avoids the inefficiency of treating structured states as opaque vectors and the rigidity of requiring users to know specific state families. By leveraging the correspondence between regular languages and MPS, the compiler automatically uncovers hidden structure and compresses the state description. This enables the efficient preparation of states and their complements with predictable resource guarantees, a capability not supported by existing general-purpose or sparse-state compilers. The work suggests that formal language theory provides a powerful, scalable framework for quantum state synthesis, particularly for states defined by combinatorial constraints or symmetries.