Metraipolis › archive › dc_c768647abc50
Exponential lower bounds for low-degree strategies in position-based quantum cryptography — arXiv:2609.35592
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35592
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:45:38.517Z
- SHA-256 of the archived text
6ab9d08f845210bbd7f294d05d5aac08fe456ae5d08894fe11106881122cd0b3- Stable URL of this page
https://metraipolis.com/documento/dc_c768647abc50
How to cite
Exponential lower bounds for low-degree strategies in position-based quantum cryptography — arXiv:2609.35592 — arXiv (en), https://arxiv.org/abs/2609.35592 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c768647abc50 (Metraipolis archive dc_c768647abc50, sha256 6ab9d08f845210bbd7f294d05d5aac08fe456ae5d08894fe11106881122cd0b3)
BibTeX
@misc{dcc768647abc50,
title = {Exponential lower bounds for low-degree strategies in position-based quantum cryptography — arXiv:2609.35592},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35592},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c768647abc50; sha256 6ab9d08f845210bbd7f294d05d5aac08fe456ae5d08894fe11106881122cd0b3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35592. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary $U_{AB}$ by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary $U_{AB}$ whose implementation in NLQC requires extra quantum systems with dimensions ${\rm exp}(n^{\Omega(1)})$, where $n$ is the dimension of systems $A$ and $B$. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in $n$. In this paper we consider the family of diagonal ${\pm 1}$ valued unitaries $U_{\varepsilon}$, indexed by an element of the Boolean hypercube $\varepsilon \in \{\pm 1\}^{n^2}$, i.e. $U_{\varepsilon}|i\rangle_A|j\rangle_B =\varepsilon_{ij} |i\rangle_A|j\rangle_B$. We show that if $U_{\varepsilon}$ can be implemented in NLQC with constant accuracy for all $\varepsilon$, and the dependency on $\varepsilon$ in the first round of the associated strategy is a polynomial of degree $O(n^{\frac{1}{4}-\delta})$, then the implementation of at least one $U_{\varepsilon}$ in NLQC requires resources scaling as $\exp\left(\Omega\left(\frac{n^{2\delta}}{(\log n)^2}\right)\right)$. The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.
Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-29 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.35592 — 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-08T00:19:23.526Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).