Metraipolis › archive › dc_69acee4015a2

A quantum let within the lambda calculus — arXiv:2608.29380

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.29380
License (as archived)
CC0-1.0
Archived
2026-10-17T10:07:18.152Z
SHA-256 of the archived text
601d458d7733a550d7543860cc7830c1c4887a7bc4c77ae95f5a3dac7fcd17d8
Stable URL of this page
https://metraipolis.com/documento/dc_69acee4015a2

How to cite

A quantum let within the lambda calculus — arXiv:2608.29380 — arXiv (en), https://arxiv.org/abs/2608.29380 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_69acee4015a2 (Metraipolis archive dc_69acee4015a2, sha256 601d458d7733a550d7543860cc7830c1c4887a7bc4c77ae95f5a3dac7fcd17d8)
BibTeX
@misc{dc69acee4015a2,
  title = {A quantum let within the lambda calculus — arXiv:2608.29380},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.29380},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_69acee4015a2; sha256 601d458d7733a550d7543860cc7830c1c4887a7bc4c77ae95f5a3dac7fcd17d8},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.29380. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Since the seminal work of Selinger and Valiron, the standard design for quantum lambda calculi has kept the quantum state outside the program: terms manipulate pointers to an external register. This is largely due to the difficulty of eliminating tensor products. For example, the calculus $\lambda_\rho^\circ$ embeds density matrices directly within terms, where terms carry the entire computation state, a feature particularly appealing for program verification. However, lacking a tensor elimination construct, it can neither access the individual qubits of a compound state nor discard them. Borgna showed that this inability to discard qubits makes the calculus strictly less expressive than the quantum lambda calculus of Selinger and Valiron. In this paper we show that tensor elimination is possible in this setting. The key observation is that the Pauli decomposition, combined with the spectral decomposition of the Pauli matrices, allows any $n$-qubit density matrix to be expressed as a real linear combination of tensor products of single-qubit density matrices. Exploiting this fact, we extend $\lambda_\rho^\circ$ with a construct $\mathrm{let}\ x^{\otimes n} = \rho\ \mathrm{in}\ t$, which binds each $x_i$ to a single-qubit density matrix arising from the decomposition of $\rho$. We equip the extended calculus with a rewrite system, a type system, and a denotational semantics, and prove Subject Reduction, Progress, Strong Normalisation, Soundness, and Adequacy. The new construct also recovers the missing ability to discard qubits, thereby restoring expressiveness. Moreover, we show that this is achieved in a physically principled way: a variable unused in $t$ is interpreted exactly as being partial-traced out, as dictated by the no-deleting theorem. We illustrate the resulting compositionality through quantum teleportation and the three-qubit bit-flip code.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in cs.LO).
Categorie arXiv: Logic in Computer Science (cs.LO) ; Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2608.29380 — 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-17T10:02:03.596Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).