quantum-computing

Regular language quantum states

Quantum Science and Technology (arXiv overlay)

29 min read

0 likes

Summarize this article with:

AbstractWe 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.Popular summaryQuantum many-body systems lie at the heart of modern physics, yet their inherent complexity makes them difficult to study or simulate. A key strategy to overcome this challenge is to identify families of quantum states that admit simpler or more convenient representations. This has led to powerful frameworks like Gaussian-, stabilizer-, or tensor network-states. In our work, we introduce a physically relevant family of states -regular language states (RLS)- drawing inspiration from formal language theory in computer science. Then, we demonstrate how this connection enables us to tackle challenges that are out of reach for state-of-the-art techniques in many-body physics. We define RLS as the uniform superpositions of all strings of a fixed length that belong to a regular language. These languages, characterized by simple patterns and finite automata, benefit from a rich set of analytical tools originally developed for applications ranging from text processing to compiler design. By harnessing these tools, we effectively extend the fundamentally relevant framework of tensor networks, to encompass a broader class of quantum states. This extension proves crucial for tackling critical issues such as classifying phases of matter and understanding entanglement. Moreover, our approach is bidirectional: while formal language tools shed new light on open questions in many-body physics, we show that tensor network-inspired methods also offer novel algorithms for problems concerning regular languages. Therefore, this link not only bridges two foundational disciplines but also opens up exciting research questions at the interface of the two fields.► BibTeX data@article{FloridoLlinas2026regularlanguage, doi = {10.22331/q-2026-04-29-2089}, url = {https://doi.org/10.22331/q-2026-04-29-2089}, title = {Regular language quantum states}, author = {Florido-Llin{\`{a}}s, Marta and Alhambra, {\'{A}}lvaro M. and P{\'{e}}rez-Garc{\'{i}}a, David and Cirac, J. Ignacio}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2089}, month = apr, year = {2026} }► References [1] Alfred V. Aho. Chapter 5 - algorithms for finding patterns in strings.

In Jan Van Leeuwen, editor, Algorithms and Complexity, Handbook of Theoretical Computer Science, pages 255–300. Elsevier, Amsterdam, 1990. ISBN 978-0-444-88071-0. 10.1016/B978-0-444-88071-0.50010-2. https://doi.org/10.1016/B978-0-444-88071-0.50010-2 [2] Alfred V. Aho and Jeffrey D. Ullman. The theory of parsing, translation, and compiling. Prentice-Hall, Inc., USA, 1972. ISBN 0139145567. [3] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: principles, techniques, and tools. Always learning. Pearson, 2014. ISBN 978-1-292-02434-9. [4] Andris Ambainis and Abuzer Yakaryılmaz. Automata and quantum computing, 2018. URL https://arxiv.org/abs/1507.01988. arXiv:1507.01988 [5] Anselmo, Marcella, Giammarresi, Dora, Madonia, Maria, and Restivo, Antonio. Unambiguous recognizable two-dimensional languages. RAIRO-Theor. Inf. Appl., 40 (2): 277–293, 2006. 10.1051/ita:2006008. https://doi.org/10.1051/ita:2006008 [6] Stéphane Ayache, Rémi Eyraud, and Noé Goudian. Explaining black boxes on sequential data using weighted automata.

In Olgierd Unold, Witold Dyrka, and Wojciech Wieczorek, editors, Proceedings of The 14th International Conference on Grammatical Inference 2018, volume 93 of Proceedings of Machine Learning Research, pages 81–103. PMLR, feb 2019. URL https://proceedings.mlr.press/v93/ayache19a.html. https://proceedings.mlr.press/v93/ayache19a.html [7] Ivan Baburin and Ryan Cotterell. An analysis of on-the-fly determinization of finite-state automata, 2023. URL https://arxiv.org/abs/2308.14077. arXiv:2308.14077 [8] Armando Bellante, Reinis Irmejs, Marta Florido-Llinàs, María Cea Fernández, Marianna Crupi, Matthew Kiser, and J. Ignacio Cirac. Compiling quantum regular language states, 2026. URL https://arxiv.org/abs/2602.02698. arXiv:2602.02698 [9] L. Berman and J. Hartmanis. On isomorphisms and density of np and other complete sets. SIAM Journal on Computing, 6 (2): 305–322, 1977. 10.1137/0206023. https://doi.org/10.1137/0206023 [10] Jean Berstel and Christophe Reutenauer.

Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications.

Cambridge University Press, 2010. [11] Amandeep Singh Bhatia and Ajay Kumar. Quantum finite automata: survey, status and research directions, 2019. URL https://arxiv.org/abs/1901.07992. arXiv:1901.07992 [12] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest. Measurement-based quantum computation. Nature Physics, 5 (1): 19–26, 2009. ISSN 1745-2481. 10.1038/nphys1157. https://doi.org/10.1038/nphys1157 [13] Janusz A. Brzozowski. Towards a theory of complexity of regular languages, 2017. URL https://arxiv.org/abs/1702.05024. arXiv:1702.05024 [14] Xie Chen, Zheng-Cheng Gu, and Xiao-Gang Wen. Classification of gapped symmetric phases in one-dimensional spin systems. Phys. Rev. B, 83: 035107, Jan 2011. 10.1103/PhysRevB.83.035107. https://doi.org/10.1103/PhysRevB.83.035107 [15] Noam Chomsky and George A. Miller. Finite state languages. Information and Control, 1 (2): 91–112, 1958. 10.1016/S0019-9958(58)90082-2. https://doi.org/10.1016/S0019-9958(58)90082-2 [16] J. Ignacio Cirac, David Pérez-García, Norbert Schuch, and Frank Verstraete. Matrix product states and projected entangled pair states: Concepts, symmetries, theorems. Rev. Mod. Phys., 93: 045003, Dec 2021. 10.1103/RevModPhys.93.045003. https://doi.org/10.1103/RevModPhys.93.045003 [17] Corinna Cortes, Mehryar Mohri, and Ashish Rastogi. On the computation of some standard distances between probabilistic automata. In Oscar H. Ibarra and Hsu-Chun Yen, editors, Implementation and Application of Automata, pages 137–149.

Springer Berlin Heidelberg, 2006. ISBN 978-3-540-37214-1. 10.1007/11812128_14. https://doi.org/10.1007/11812128_14 [18] Gregory M. Crosswhite and Dave Bacon. Finite automata for caching in matrix product algorithms. Phys. Rev. A, 78: 012356, Jul 2008. 10.1103/PhysRevA.78.012356. https://doi.org/10.1103/PhysRevA.78.012356 [19] R. H. Dicke. Coherence in spontaneous radiation processes. Phys. Rev., 93: 99–110, Jan 1954. 10.1103/PhysRev.93.99. https://doi.org/10.1103/PhysRev.93.99 [20] W. Dür, G. Vidal, and J. I. Cirac. Three qubits can be entangled in two inequivalent ways. Phys. Rev. A, 62: 062314, Nov 2000. 10.1103/PhysRevA.62.062314. https://doi.org/10.1103/PhysRevA.62.062314 [21] Flavio D’Alessandro, Benedetto Intrigila, and Stefano Varricchio. On the structure of the counting function of sparse context-free languages.

Theoretical Computer Science, 356 (1): 104–117, 2006. ISSN 0304-3975. 10.1016/j.tcs.2006.01.037. https://doi.org/10.1016/j.tcs.2006.01.037 [22] Manuel Erhard, Mario Krenn, and Anton Zeilinger. Advances in high-dimensional quantum entanglement. 2 (7): 365–381. ISSN 2522-5820. 10.1038/s42254-020-0193-5. https://doi.org/10.1038/s42254-020-0193-5 [23] G. Evenbly and G. Vidal. Tensor network states and geometry. Journal of Statistical Physics, 145 (4): 891–918, 2011. 10.1007/s10955-011-0237-4. https://doi.org/10.1007/s10955-011-0237-4 [24] M. Fannes, B. Nachtergaele, and R. F. Werner. Finitely correlated states on quantum spin chains. Communications in Mathematical Physics, 144 (3): 443–490, 1992. ISSN 1432-0916. 10.1007/BF02099178. https://doi.org/10.1007/BF02099178 [25] Douglas R. Farenick. Algebras of linear transformations. Universitext. Springer, 2001. ISBN 978-0-387-95062-4. [26] Henning Fernau, Stefan Hoffmann, and Michael Wehar. Finite automata intersection non-emptiness: Parameterized complexity revisited, 2021. URL https://arxiv.org/abs/2108.05244. arXiv:2108.05244 [27] Marta Florido-Llinàs, Álvaro M. Alhambra, David Pérez-García, and J. Ignacio Cirac. Uniform matrix product states with a boundary, 2025. URL https://arxiv.org/abs/2512.11968. arXiv:2512.11968 [28] Jeffrey EF Friedl. Mastering regular expressions. O'Reilly Media, Inc., 2006. ISBN 978-0596528126. [29] Ángel J. Gallego and Román Orús. Language design as information renormalization. SN Computer Science, 3 (2): 140. ISSN 2661-8907. 10.1007/s42979-021-01002-y. https://doi.org/10.1007/s42979-021-01002-y [30] José Garre-Rubio, Alex Turzillo, and András Molnár. Mps stability and the intersection property, 2025. URL https://arxiv.org/abs/2501.17109. arXiv:2501.17109 [31] PaweŁ Gawrychowski, Dalia Krieger, Narad Rampersad, and Jeffrey Shallit. Finding the growth rate of a regular or context-free language in polynomial time. International Journal of Foundations of Computer Science, 21 (04): 597–618, 2010. 10.1142/S0129054110007441. https://doi.org/10.1142/S0129054110007441 [32] Dora Giammarresi and Antonio Restivo. Two-Dimensional Languages, pages 215–267.

Springer Berlin Heidelberg, 1997. ISBN 978-3-642-59126-6. 10.1007/978-3-642-59126-6_4. https://doi.org/10.1007/978-3-642-59126-6_4 [33] Lei Gioia, Sanjay Moudgalya, and Olexei I. Motrunich. Distinct types of parent hamiltonians for quantum states: Insights from the $w$ state as a quantum many-body scar, 2025. URL https://arxiv.org/abs/2510.24713. arXiv:2510.24713 [34] Ivan Glasser, Ryan Sweke, Nicola Pancotti, Jens Eisert, and J. Ignacio Cirac. Expressive power of tensor-network factorizations for probabilistic modeling.

Curran Associates Inc., Red Hook, NY, USA, 2019. 10.5555/3454287.3454421. https://doi.org/10.5555/3454287.3454421 [35] Sarang Gopalakrishnan. Push-down automata as sequential generators of highly entangled states. Journal of Physics A: Mathematical and Theoretical, 58 (5): 055301, jan 2025. 10.1088/1751-8121/adab9f. https://doi.org/10.1088/1751-8121/adab9f [36] Daniel Gottesman. Stabilizer codes and quantum error correction, 1997. URL https://arxiv.org/abs/quant-ph/9705052. arXiv:quant-ph/9705052 [37] Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger.

Going Beyond Bell's Theorem, pages 69–72. Springer Netherlands, Dordrecht, 1989. ISBN 978-94-017-0849-4. 10.1007/978-94-017-0849-4_10. https://doi.org/10.1007/978-94-017-0849-4_10 [38] Jutho Haegeman, Bogdan Pirvu, David J. Weir, J. Ignacio Cirac, Tobias J. Osborne, Henri Verschelde, and Frank Verstraete. Variational matrix product ansatz for dispersion relations. Phys. Rev. B, 85: 100408(R), Mar 2012. 10.1103/PhysRevB.85.100408. https://doi.org/10.1103/PhysRevB.85.100408 [39] J. Hartmanis and S. R. Mahaney. An essay about research on sparse np complete sets. In P. Dembiński, editor, Mathematical Foundations of Computer Science 1980, pages 40–57.

Springer Berlin Heidelberg, 1980. ISBN 978-3-540-38194-5. 10.1007/BFb0022494. https://doi.org/10.1007/BFb0022494 [40] M. Hein, J. Eisert, and H. J. Briegel. Multiparty entanglement in graph states. Phys. Rev. A, 69: 062311, Jun 2004. 10.1103/PhysRevA.69.062311. https://doi.org/10.1103/PhysRevA.69.062311 [41] Stefan Hoffmann. Computational complexity of synchronization under sparse regular constraints.

In Evripidis Bampis and Aris Pagourtzis, editors, Fundamentals of Computation Theory, pages 272–286, Cham, 2021.

Springer International Publishing. ISBN 978-3-030-86593-1. 10.1007/978-3-030-86593-1_19. https://doi.org/10.1007/978-3-030-86593-1_19 [42] John Hopcroft. An n log n algorithm for minimizing states in a finite automaton.

In Zvi Kohavi and Azaria Paz, editors, Theory of Machines and Computations, pages 189–196. Academic Press, 1971. ISBN 978-0-12-417750-5. 10.1016/B978-0-12-417750-5.50022-1. https://doi.org/10.1016/B978-0-12-417750-5.50022-1 [43] John E. Hopcroft and R. M. Karp. A linear algorithm for testing equivalence of finite automata. Technical report, University of California, 1971. URL https://hdl.handle.net/1813/5958. https://hdl.handle.net/1813/5958 [44] John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. Introduction to automata theory, languages, and computation.

Acm Sigact News, 32 (1): 60–65, 2001. [45] Katsushi Inoue and Akira Nakamura. Some properties of two-dimensional on-line tessellation acceptors. Information Sciences, 13 (2): 95–121, 1977. ISSN 0020-0255. 10.1016/0020-0255(77)90023-8. https://doi.org/10.1016/0020-0255(77)90023-8 [46] Galina Jirásková and Alexander Okhotin. State complexity of cyclic shift. RAIRO - Theoretical Informatics and Applications, 42 (2): 335–360, 2008. 10.1051/ita:2007038. https://doi.org/10.1051/ita:2007038 [47] Sampath Kannan, Z. Sweedyk, and Steve Mahaney. Counting and random generation of strings in regular languages. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '95, page 551–557, USA, 1995. Society for Industrial and Applied Mathematics. ISBN 0898713498. 10.5555/313651.313803. https://doi.org/10.5555/313651.313803 [48] Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, Björn Wachter, and James Worrell. Language equivalence for probabilistic automata.

In Ganesh Gopalakrishnan and Shaz Qadeer, editors, Computer Aided Verification, pages 526–540.

Springer Berlin Heidelberg, 2011. ISBN 978-3-642-22110-1. 10.1007/978-3-642-22110-1_42. https://doi.org/10.1007/978-3-642-22110-1_42 [49] S. C. Kleene. Representation of Events in Nerve Nets and Finite Automata, pages 3–42.

Princeton University Press, Princeton, 1956. ISBN 9781400882618. 10.1515/9781400882618-002. https://doi.org/10.1515/9781400882618-002 [50] B. Kraus. Local unitary equivalence of multipartite pure states. Phys. Rev. Lett., 104: 020504, Jan 2010. 10.1103/PhysRevLett.104.020504. https://doi.org/10.1103/PhysRevLett.104.020504 [51] Kenneth Krohn and John Rhodes. Algebraic theory of machines. i. prime decomposition theorem for finite semigroups and machines. 116 (0): 450–464. ISSN 0002-9947, 1088-6850. 10.1090/S0002-9947-1965-0188316-1. https://doi.org/10.1090/S0002-9947-1965-0188316-1 [52] Hing Leung. Descriptional complexity of nfa of different ambiguity. International Journal of Foundations of Computer Science, 16 (05): 975–984, 2005. 10.1142/S0129054105003418. https://doi.org/10.1142/S0129054105003418 [53] Dafa Li. Stochastic local operations and classical communication (SLOCC) and local unitary operations (LU) classifications of n qubits via ranks and singular values of the spin-flipping matrices.

Quantum Information Processing, 17 (6): 132. ISSN 1573-1332. 10.1007/s11128-018-1900-3. https://doi.org/10.1007/s11128-018-1900-3 [54] Tianyu Li, Doina Precup, and Guillaume Rabusseau. Connecting weighted automata, tensor networks and recurrent neural networks through spectral learning. Machine Learning, 113 (5): 2619–2653, 2024. ISSN 1573-0565. 10.1007/s10994-022-06164-1. https://doi.org/10.1007/s10994-022-06164-1 [55] Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata.

In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=De4FYqjFueZ. https://openreview.net/forum?id=De4FYqjFueZ [56] Mateusz Michałek and Yaroslav Shitov. Quantum version of wielandt’s inequality revisited. IEEE Transactions on Information Theory, 65 (8): 5239–5242, 2019. 10.1109/TIT.2019.2897772. https://doi.org/10.1109/TIT.2019.2897772 [57] Ashwin Nayak and Dave Touchette. Augmented index and quantum streaming algorithms for dyck(2), 2022. URL https://arxiv.org/abs/1610.04937. arXiv:1610.04937 [58] Takamasa Okudono, Masaki Waga, Taro Sekiyama, and Ichiro Hasuo. Weighted automata extraction from recurrent neural networks via regression on state spaces. 34 (4): 5306–5314. ISSN 2374-3468, 2159-5399. 10.1609/aaai.v34i04.5977. https://doi.org/10.1609/aaai.v34i04.5977 [59] Román Orús. Tensor networks for complex quantum systems.

Nature Reviews Physics, 1 (9): 538–550, 2019. ISSN 2522-5820. 10.1038/s42254-019-0086-7. https://doi.org/10.1038/s42254-019-0086-7 [60] Alexandros Palioudakis, Kai Salomaa, and Selim G. Akl. State complexity and limited nondeterminism.

In Martin Kutrib, Nelma Moreira, and Rogério Reis, editors, Descriptional Complexity of Formal Systems, pages 252–265, Berlin, Heidelberg, 2012.

Springer Berlin Heidelberg. ISBN 978-3-642-31623-4. 10.1007/978-3-642-31623-4_20. https://doi.org/10.1007/978-3-642-31623-4_20 [61] Jian-Wei Pan, Zeng-Bing Chen, Chao-Yang Lu, Harald Weinfurter, Anton Zeilinger, and Marek Żukowski. Multiphoton entanglement and interferometry. Rev. Mod. Phys., 84: 777–838, May 2012. 10.1103/RevModPhys.84.777. https://doi.org/10.1103/RevModPhys.84.777 [62] Christopher J Pappacena. An upper bound for the length of a finite-dimensional algebra. Journal of Algebra, 197 (2): 535–545, 1997. ISSN 0021-8693. 10.1006/jabr.1997.7140. https://doi.org/10.1006/jabr.1997.7140 [63] D. Perez-Garcia, F. Verstraete, M.M. Wolf, and J.I. Cirac. Matrix product state representations. Quantum Information and Computation, 7 (5): 401, 2007. 10.26421/QIC7.5-6-1. https://doi.org/10.26421/QIC7.5-6-1 [64] Luca Pezzè, Augusto Smerzi, Markus K. Oberthaler, Roman Schmied, and Philipp Treutlein. Quantum metrology with nonclassical states of atomic ensembles. Rev. Mod. Phys., 90: 035005, Sep 2018. 10.1103/RevModPhys.90.035005. https://doi.org/10.1103/RevModPhys.90.035005 [65] M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3 (2): 114–125, 1959. 10.1147/rd.32.0114. https://doi.org/10.1147/rd.32.0114 [66] Robert Raussendorf and Hans J. Briegel. A one-way quantum computer. Phys. Rev. Lett., 86: 5188–5191, May 2001. 10.1103/PhysRevLett.86.5188. https://doi.org/10.1103/PhysRevLett.86.5188 [67] Bala Ravikumar and Oscar H. Ibarra. Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM Journal on Computing, 18 (6): 1263–1282, 1989. 10.1137/0218083. https://doi.org/10.1137/0218083 [68] Paul M. Riechers and Thomas J. Elliott. Identifiability and minimality bounds of quantum and post-quantum models of classical stochastic processes, 2025. URL https://arxiv.org/abs/2509.03004. arXiv:2509.03004 [69] Shinsei Ryu and Tadashi Takayanagi. Holographic derivation of entanglement entropy from the anti–de sitter space/conformal field theory correspondence. Phys. Rev. Lett., 96: 181602, May 2006. 10.1103/PhysRevLett.96.181602. https://doi.org/10.1103/PhysRevLett.96.181602 [70] Subir Sachdev.

Quantum Phase Transitions.

Cambridge University Press, 2 edition, 2011. 10.1017/CBO9780511973765. https://doi.org/10.1017/CBO9780511973765 [71] Jacques Sakarovitch. Elements of automata theory.

Cambridge University Press, 2009. 10.1017/CBO9781139195218. https://doi.org/10.1017/CBO9781139195218 [72] David Sauerwein, Andras Molnar, J. Ignacio Cirac, and Barbara Kraus. Matrix product states: Entanglement, symmetries, and state transformations. Phys. Rev. Lett., 123: 170504, Oct 2019. 10.1103/PhysRevLett.123.170504. https://doi.org/10.1103/PhysRevLett.123.170504 [73] Ulrich Schollwöck. The density-matrix renormalization group in the age of matrix product states. Annals of Physics, 326 (1): 96–192, 2011. ISSN 0003-4916. 10.1016/j.aop.2010.09.012. https://doi.org/10.1016/j.aop.2010.09.012 [74] Norbert Schuch, David Pérez-García, and Ignacio Cirac. Classifying quantum phases using matrix product states and projected entangled pair states. Phys. Rev. B, 84: 165139, Oct 2011. 10.1103/PhysRevB.84.165139. https://doi.org/10.1103/PhysRevB.84.165139 [75] M.P. Schützenberger. On the definition of a family of automata. Information and Control, 4 (2): 245–270, 1961. ISSN 0019-9958. 10.1016/S0019-9958(61)80020-X. https://doi.org/10.1016/S0019-9958(61)80020-X [76] Peter W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52: R2493–R2496, Oct 1995. 10.1103/PhysRevA.52.R2493. https://doi.org/10.1103/PhysRevA.52.R2493 [77] Michael Sipser. Introduction to the theory of computation. Boston : PWS Pub. Co., 1997. ISBN 978-0-534-94728-6. 10.2307/2586778. https://doi.org/10.2307/2586778 [78] R. E. Stearns and H. B. Hunt III. On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. SIAM Journal on Computing, 14 (3): 598–611, 1985. 10.1137/0214044. https://doi.org/10.1137/0214044 [79] Andrew Szilard, Sheng Yu, Kaizhong Zhang, and Jeffrey Shallit. Characterizing regular languages with polynomial densities. In Ivan M. Havel and Václav Koubek, editors, Mathematical Foundations of Computer Science 1992, pages 494–503.

Springer Berlin Heidelberg, 1992. ISBN 978-3-540-47291-9. 10.1007/3-540-55808-X_48. https://doi.org/10.1007/3-540-55808-X_48 [80] Barbara M. Terhal. Quantum error correction for quantum memories. Rev. Mod. Phys., 87: 307–346, Apr 2015. 10.1103/RevModPhys.87.307. https://doi.org/10.1103/RevModPhys.87.307 [81] Christian Weedbrook, Stefano Pirandola, Raúl García-Patrón, Nicolas J. Cerf, Timothy C. Ralph, Jeffrey H. Shapiro, and Seth Lloyd. Gaussian quantum information. Rev. Mod. Phys., 84: 621–669, May 2012. 10.1103/RevModPhys.84.621. https://doi.org/10.1103/RevModPhys.84.621 [82] Gail Weiss, Yoav Goldberg, and Eran Yahav. Learning deterministic weighted automata with queries and counterexamples. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc. 10.5555/3454287.3455055. https://doi.org/10.5555/3454287.3455055 [83] Sheng Yu. Regular Languages, pages 41–110.

Springer Berlin Heidelberg, 1997. ISBN 978-3-642-59136-5. 10.1007/978-3-642-59136-5_2. https://doi.org/10.1007/978-3-642-59136-5_2 [84] Sheng Yu, Qingyu Zhuang, and Kai Salomaa. The state complexities of some basic operations on regular languages.

Theoretical Computer Science, 125 (2): 315–328, 1994. ISSN 0304-3975. 10.1016/0304-3975(92)00011-F. https://doi.org/10.1016/0304-3975(92)00011-F [85] Bei Zeng, Xie Chen, Duan-Lu Zhou, and Xiao-Gang Wen.

Quantum Information Meets Quantum Matter: From Quantum Entanglement to Topological Phases of Many-Body Systems. Quantum Science and Technology. Springer, 2019. ISBN 978-1-4939-9082-5 978-1-4939-9084-9. 10.1007/978-1-4939-9084-9. https://doi.org/10.1007/978-1-4939-9084-9 [86] Wucheng Zhang. Sequential generation of two-dimensional super-area-law states with local parent hamiltonian. PRX Quantum, Oct 2025. 10.1103/t7py-glgv. https://doi.org/10.1103/t7py-glgv [87] Yifan Zhang and Edgar Solomonik. On stability of tensor networks and canonical forms, 2020. URL https://arxiv.org/abs/2001.01191. arXiv:2001.01191Cited by[1] Lei Gioia, Sanjay Moudgalya, and Olexei I. Motrunich, "Distinct Types of Parent Hamiltonians for Quantum States: Insights from the $W$ State as a Quantum Many-Body Scar", arXiv:2510.24713, (2025). [2] Borja Aizpurua, Saeed S. Jahromi, Sukhbinder Singh, and Roman Orus, "Quantum Large Language Models via Tensor Network Disentanglers", arXiv:2410.17397, (2024). [3] Wucheng Zhang, "Sequential Generation of Two-Dimensional Super-Area-Law States with Local Parent Hamiltonian", PRX Quantum 7 1, 010311 (2026). [4] Armando Bellante, Reinis Irmejs, Marta Florido-Llinàs, María Cea Fernández, Marianna Crupi, Matthew Kiser, and J. Ignacio Cirac, "Compiling Quantum Regular Language States", arXiv:2602.02698, (2026). The above citations are from SAO/NASA ADS (last updated successfully 2026-04-29 12:31:50). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-04-29 12:31:43: Could not fetch cited-by data for 10.22331/q-2026-04-29-2089 from Crossref. This is normal if the DOI was registered recently.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractWe 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.Popular summaryQuantum many-body systems lie at the heart of modern physics, yet their inherent complexity makes them difficult to study or simulate. A key strategy to overcome this challenge is to identify families of quantum states that admit simpler or more convenient representations. This has led to powerful frameworks like Gaussian-, stabilizer-, or tensor network-states. In our work, we introduce a physically relevant family of states -regular language states (RLS)- drawing inspiration from formal language theory in computer science. Then, we demonstrate how this connection enables us to tackle challenges that are out of reach for state-of-the-art techniques in many-body physics. We define RLS as the uniform superpositions of all strings of a fixed length that belong to a regular language. These languages, characterized by simple patterns and finite automata, benefit from a rich set of analytical tools originally developed for applications ranging from text processing to compiler design. By harnessing these tools, we effectively extend the fundamentally relevant framework of tensor networks, to encompass a broader class of quantum states. This extension proves crucial for tackling critical issues such as classifying phases of matter and understanding entanglement. Moreover, our approach is bidirectional: while formal language tools shed new light on open questions in many-body physics, we show that tensor network-inspired methods also offer novel algorithms for problems concerning regular languages. Therefore, this link not only bridges two foundational disciplines but also opens up exciting research questions at the interface of the two fields.► BibTeX data@article{FloridoLlinas2026regularlanguage, doi = {10.22331/q-2026-04-29-2089}, url = {https://doi.org/10.22331/q-2026-04-29-2089}, title = {Regular language quantum states}, author = {Florido-Llin{\`{a}}s, Marta and Alhambra, {\'{A}}lvaro M. and P{\'{e}}rez-Garc{\'{i}}a, David and Cirac, J. Ignacio}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2089}, month = apr, year = {2026} }► References [1] Alfred V. Aho. Chapter 5 - algorithms for finding patterns in strings.

Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications.

In Evripidis Bampis and Aris Pagourtzis, editors, Fundamentals of Computation Theory, pages 272–286, Cham, 2021.

In Ganesh Gopalakrishnan and Shaz Qadeer, editors, Computer Aided Verification, pages 526–540.

In Martin Kutrib, Nelma Moreira, and Rogério Reis, editors, Descriptional Complexity of Formal Systems, pages 252–265, Berlin, Heidelberg, 2012.

Quantum Phase Transitions.

Cambridge University Press, 2 edition, 2011. 10.1017/CBO9780511973765. https://doi.org/10.1017/CBO9780511973765 [71] Jacques Sakarovitch. Elements of automata theory.

Read Original

Source Information

Source: Quantum Science and Technology (arXiv overlay)

Website: https://quantum-journal.org/feed