Quantum algorithms for equational reasoning
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914573170245632 |
|---|---|
| author | Rattacaso, Davide Jaschke, Daniel Ballarin, Marco Siloi, Ilaria Montangero, Simone |
| author_facet | Rattacaso, Davide Jaschke, Daniel Ballarin, Marco Siloi, Ilaria Montangero, Simone |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_21122 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum algorithms for equational reasoning Rattacaso, Davide Jaschke, Daniel Ballarin, Marco Siloi, Ilaria Montangero, Simone Quantum Physics 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. |
| title | Quantum algorithms for equational reasoning |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2508.21122 |