Exponential lower bounds for low-degree strategies in position-based quantum cryptography
Abstract
Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary UAB 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 UAB whose implementation in NLQC requires extra quantum systems with dimensions exp(nΩ(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 ± 1 valued unitaries Uε, indexed by an element of the Boolean hypercube ε ∈ {± 1}n2, i.e. Uε|i⟩A|j⟩B =εij |i⟩A|j⟩B. We show that if Uε can be implemented in NLQC with constant accuracy for all ε, and the dependency on ε in the first round of the associated strategy is a polynomial of degree O(n1/4−δ), then the implementation of at least one Uε in NLQC requires resources scaling as exp(Ω(n2δ/((log n)2))). 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.
Related
- Lower Bounds for Preprocessing Attacks on Quantum Cryptography
- Consecutive Measurement Tradeoffs in Quantum Cryptography
- From Quantum Cryptography to Intuitionism and beyond: relativity, many-worlds and non-locality
- Reliable Entropy Estimation from Observed Statistics for Device-Independent Quantum Cryptography
- Quantum Cryptography and Autoformalization in Lean
BibTeX
@misc{morenocuadrado2026exponential,
title = {{Exponential lower bounds for low-degree strategies in position-based quantum cryptography}},
author = {Isabel M. Moreno-Cuadrado and David Perez-Garcia and Carlos Palazuelos},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35592},
eprint = {2609.35592},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35592},
}
RIS
TY - UNPB
TI - Exponential lower bounds for low-degree strategies in position-based quantum cryptography
AU - Isabel M. Moreno-Cuadrado
AU - David Perez-Garcia
AU - Carlos Palazuelos
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35592
UR - https://arxiv.org/abs/2609.35592
AB - 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 exp(n^Ω(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 ± 1 valued unitaries U_ε, indexed by an element of the Boolean hypercube ε ∈ {± 1}^n^2, i.e. U_ε|i⟩_A|j⟩_B =ε_ij |i⟩_A|j⟩_B. We show that if U_ε can be implemented in NLQC with constant accuracy for all ε, and the dependency on ε in the first round of the associated strategy is a polynomial of degree O(n^1/4−δ), then the implementation of at least one U_ε in NLQC requires resources scaling as exp(Ω(n^2δ/((log n)^2))). 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.
ER -