arXiv:2609.35592
Exponential lower bounds for low-degree strategies in position-based quantum cryptography
Isabel M. Moreno-Cuadrado, David Perez-Garcia, Carlos Palazuelos
Abstract
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^{Ω(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}-δ})$, then the implementation of at least one $U_{\varepsilon}$ in NLQC requires resources scaling as $\exp\left(Ω\left(\frac{n^{2δ}}{(\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.
AI Summary
Non-local quantum computation (NLQC) models coordinated attacks on position-based quantum verification. The paper asks whether implementing an $n\times n$ bipartite unitary requires auxiliary dimension exponential in a positive power of $n$, counting both classical and quantum registers. It studies public, fixed diagonal sign unitaries $U_\varepsilon|ij\rangle=\varepsilon_{ij}|ij\rangle$, with $\varepsilon\in\{\pm1\}^{n^2}$. The main result restricts the dependence of the full first-round strategy operator on $\varepsilon$ to Fourier–Walsh degree at most $d$, while allowing unrestricted second rounds. Any such strategy family achieving constant average success requires $\log k\ge c\sqrt n/((d+1)^2[\log(2n)]^2)-\log(2n)$, where $k$ is the padded auxiliary-register dimension. Consequently, degree $d\le n^{1/4-\delta}$ implies $k\ge\exp(\Omega(n^{2\delta}/(\log n)^2))$ for fixed $0<\delta<1/4$. Success is measured by entanglement fidelity. The proof represents optimized success using Banach-space tensor norms, applies known type-2 estimates, and combines random restrictions of Boolean functions with a Banach-valued Bernstein inequality. Applications include an exponential dimension bound for attacks whose first-round dependence occurs through parallel copies $U_\varepsilon^{\otimes N}$, and a query lower bound for polynomial-dimension black-box NLQC protocols. The unrestricted resource lower-bound problem remains open: the proved bound concerns low-degree families, not one fixed unitary against every strategy. A separate conjecture on a type-2 constant would imply unrestricted exponential lower bounds for some fixed sign unitary. Here $n$ denotes local Hilbert-space dimension, not qubit count.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 28 pages, 1 figure. No artificial intelligence tools were used in the preparation of this manuscript