Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
To address the long-standing open question of whether non-local quantum computation (NLQC) requires exponential quantum memory, the authors investigate the ancilla dimensions required to implement diagonal bipartite unitaries indexed over the Boolean hypercube. Establishing these exponential lower bounds is vital for certifying the theoretical security of position-based quantum cryptography and bounding the overhead of universal quantum simulators. They prove that whenever the adversary's first-round communication strategy depends polynomially on the input with degree $O(n^{1/4-\delta})$, implementing the unitary requires ancilla dimensions scaling exponentially as $\exp\left(\Omega\left(\frac{n^{2\delta}}{(\log n)^2}\right)\right)$, breaking past prior sublinear barriers.
Breaking the long-standing sublinear barrier in non-local quantum computation, low-degree adversaries are now proven to require exponential quantum memory to break protocols, bringing position-based quantum cryptography closer to provable security guarantees.
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.