Metraipolis › archive › dc_6b8a2c32ee6a
Towards Datalog on Quantum Annealers: Compiling Recursive Logic Programs with Bottom-up Semantics to 2-local Ising Models — arXiv:2608.04645
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.04645
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T12:00:04.725Z
- SHA-256 of the archived text
a71c8ac8d552518b27dbfde5349de7549cdb86c25244d5b1a9941051ce051ab1- Stable URL of this page
https://metraipolis.com/documento/dc_6b8a2c32ee6a
How to cite
Towards Datalog on Quantum Annealers: Compiling Recursive Logic Programs with Bottom-up Semantics to 2-local Ising Models — arXiv:2608.04645 — arXiv (en), https://arxiv.org/abs/2608.04645 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6b8a2c32ee6a (Metraipolis archive dc_6b8a2c32ee6a, sha256 a71c8ac8d552518b27dbfde5349de7549cdb86c25244d5b1a9941051ce051ab1)
BibTeX
@misc{dc6b8a2c32ee6a,
title = {Towards Datalog on Quantum Annealers: Compiling Recursive Logic Programs with Bottom-up Semantics to 2-local Ising Models — arXiv:2608.04645},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.04645},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6b8a2c32ee6a; sha256 a71c8ac8d552518b27dbfde5349de7549cdb86c25244d5b1a9941051ce051ab1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.04645. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Quantum annealers solve problems by finding the lowest-energy (ground) state of a programmable physical system, a 2-local Ising model, whose energy function is the Hamiltonian. We compile recursive Datalog programs into such models so that the ground state projects onto the program's minimal Herbrand model. The compiler has four stages: binarization, grounding, reduction to a Min-Ones SAT formula, and Ising encoding. Each rule becomes an energy penalty on the one assignment that violates it, and a small uniform cost on every true atom selects the minimal model. We contribute both in theory and in practice with per-stage correctness lemmas and a correspondence theorem, verified in Lean 4, establishing that the ground state of the compiled model projects onto the program's minimal Herbrand model. We map the compiled models onto the topologies of commercial annealers and characterize, under classical and simulated-quantum annealing, whether and when that certified ground state is attained. Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-08-06 in cs.PL). Categorie arXiv: Programming Languages (cs.PL). Pagina del lavoro: https://arxiv.org/abs/2608.04645 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-31T11:48:38.603Z dalla pagina https://arxiv.org/catchup/cs.PL/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).