Quantum algorithms for equational reasoning
Science Advances · 15.05.2026 · 12 (20)
DOI: 10.1126/sciadv.aec2736 ↗Kurz gefasst
Fachartikel in der Zeitschrift Science Advances, erschienen am 15.05.2026. Verfasst von Davide Rattacaso und 4 weiteren Autor:innen. Beteiligte Einrichtung: Dipartimento di Fisica e Astronomia "G. Galilei" and Padua Quantum Technologies Research Center, Università degli Studi di Padova, I-35131 Padova, It…. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 85 Literaturangaben. Der Volltext ist frei in PubMed Central verfügbar. Gefördert von: Horizon Europe, NextGenerationEU, Bundesministerium für Bildung und Forschung.
Abstract (Originalsprache)
As a cornerstone of automated reasoning, equational reasoning finds equivalences between symbolic expressions and fuels advances across scientific disciplines. Yet, its potential remains limited by the exponential growth of equivalent expressions with increasing problem size. We introduce quantum normal form reduction, a quantum computational framework designed to address this challenge. We construct an efficiently implementable quantum Hamiltonian whose ground state encodes all equivalent expressions in a quantum superposition. By preparing and manipulating these states, we tackle fundamental problems in equational reasoning, including verifying and counting equivalent expressions and identifying structural properties of equivalence classes. We demonstrate a quantum-inspired version of the algorithm using tensor networks to solve instances involving up to 10 28 equivalent expressions, far beyond the reach of classical graph exploration. This framework opens the path for quantum symbolic computation in areas from circuit design to data compression, computational group theory, linguistics, and macromolecular modeling, unlocking previously inaccessible problems.
Autor:innen und Institutionen
- Dipartimento di Fisica e Astronomia "G. Galilei" and Padua Quantum Technologies Research Center, Università degli Studi di Padova, I-35131 Padova, Italy.
- INFN, Sezione di Padova, via Marzolo 8, I-35131 Padova, Italy.
- Institute for Complex Quantum Systems, Ulm University, Albert-Einstein-Allee 11, 89069, Germany.
ORCID-Profile: Davide Rattacaso, Daniel Jaschke, Ilaria Siloi, Simone Montangero
Förderung
- Horizon Europe
- NextGenerationEU
- Bundesministerium für Bildung und Forschung
- Università degli Studi di Padova
- Istituto Nazionale di Fisica Nucleare
- Ministero dell'Università e della Ricerca
- Quantum Technologies Flagship
- Padova University
Zitieren
APA
Rattacaso, D., Jaschke, D., Ballarin, M., Siloi, I., & Montangero, S. (2026). Quantum algorithms for equational reasoning. Science Advances, 12(20). https://doi.org/10.1126/sciadv.aec2736
Vancouver
Rattacaso D, Jaschke D, Ballarin M, Siloi I, Montangero S. Quantum algorithms for equational reasoning. Science Advances. 2026;12(20). doi:10.1126/sciadv.aec2736
BibTeX
@article{Rattacaso2026,
author = {Rattacaso, Davide and Jaschke, Daniel and Ballarin, Marco and Siloi, Ilaria and Montangero, Simone},
title = {Quantum algorithms for equational reasoning},
journal = {Science Advances},
year = {2026},
volume = {12},
number = {20},
doi = {10.1126/sciadv.aec2736}
}
EUVIMED