⚛️ quantum physics

Quantum gate lower bounds for loss-tolerant position verification

This paper establishes nearly-linear quantum gate lower bounds for attacks on the $f$ -BB84 position verification scheme under realistic conditions, including up to 50% transmission loss, imperfect state preparation, and slow quantum messages, by deriving a tight analytic tradeoff for a lossy BB84 monogamy-of-entanglement game.

Original authors: Alex May, Philip Verduyn Lunel

Published 2026-08-18

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Alex May, Philip Verduyn Lunel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine trying to prove you are standing in a specific spot on Earth without ever leaving that spot. In the world of cryptography, this is the goal of quantum position verification. It is a method where a verifier, located far away, sends out signals to a prover and measures the time it takes for the response to return. Because nothing travels faster than light, the timing constraints can mathematically prove that the prover must be located within a specific region of space. If the response comes back too quickly or too slowly, the prover is either misrepresenting their location or is not where they claim to be. This concept relies on the strange rules of quantum mechanics, where information can be encoded in particles like photons, and the act of measuring them changes their state. While the idea sounds like a perfect way to secure physical locations, recent experiments have shown that real-world conditions, such as signals getting lost in fiber optic cables or imperfect equipment, can create loopholes that attackers might exploit.

A team of researchers has now closed a significant gap in our understanding of these security loopholes. They focused on a specific, widely studied method of position verification known as the f-BB84 scheme. In this setup, two distant referees send classical instructions and a single quantum particle to a prover. The prover must perform a specific calculation based on the instructions and then measure the particle to generate a response. The challenge for an attacker is that the quantum particle and the instructions needed to measure it are split between two locations. To subvert the system, the attackers would need to share a massive amount of entangled quantum resources to coordinate their actions instantly across space. Previous studies had suggested that as the complexity of the instructions grew, the resources needed to subvert the system would grow exponentially, making the scheme secure. However, proving this rigorously in the presence of real-world noise, specifically signal loss, had remained an open and difficult problem.

The researchers in this study tackled the problem of signal loss directly. In a real-world scenario, a significant portion of quantum signals can be lost before they reach the prover. An attacker could potentially exploit this by simply guessing the correct measurement basis and, if they guess wrong, claiming the signal was lost rather than admitting they failed. The team proved that even if an attacker is allowed to declare that half of the signals were lost, they still cannot subvert the system without using a prohibitive amount of computational power. Specifically, they demonstrated that to successfully attack the scheme under these conditions, an attacker would need to perform a number of quantum operations that grows linearly with the size of the input. In contrast, an honest prover only needs to perform a constant, small number of operations. This creates a massive gap in difficulty: the honest player does a tiny amount of work, while the subverter must do a massive amount of work that scales up with the complexity of the task.

To reach this conclusion, the authors developed a new mathematical tool to analyze a game of quantum entanglement. They modeled the interaction between the attackers and the verifier as a game where the attackers try to guess the outcome of a measurement on a shared quantum particle. They proved a strict limit on how well the attackers can do, even if they are allowed to say "I don't know" or "the signal is lost" for a large fraction of the attempts. This limit is tight, meaning it represents the absolute best performance an attacker could possibly achieve. By applying this limit to the position verification scheme, they showed that any strategy that tries to bypass the timing constraints requires a number of quantum gates that increases directly with the length of the input data. This result holds true even when the quantum states sent by the verifier are not perfect and when the attackers are allowed to be very slow in their processing.

The significance of this work lies in its applicability to current and future experiments. Recent laboratory tests have successfully implemented these position verification schemes, but their security in the face of high signal loss was not fully understood. This paper provides a rigorous proof that these schemes remain secure, provided the attackers do not have access to an unlimited number of quantum gates. The researchers established a clear boundary for security: as long as the error rate and the rate of declared signal loss stay within a specific range, the honest prover can be trusted. If an attacker tries to subvert the system outside this range, they would need to perform a linear number of quantum operations, which is currently impossible for any realistic quantum computer to sustain for large inputs. This finding reassures researchers that the f-BB84 scheme is a viable tool for securing physical locations, even in imperfect, noisy environments.

The study also addressed the practical reality that quantum states are never prepared perfectly. The authors showed that their security bounds hold even when the initial quantum particles are slightly flawed, as long as the flaws are within a certain measurable distance from the ideal state. They did not rely on numerical simulations or approximations but provided a complete analytical proof. This means the result is a firm mathematical guarantee rather than a suggestion based on computer models. The work effectively rules out the possibility that an attacker could use a simple, low-resource strategy to break the system, even when allowed to claim that half the signals were lost. By establishing that the cost of subverting the system scales linearly with the input size, the paper confirms that the honest prover has a distinct and insurmountable advantage in terms of resource efficiency.

In the broader context of quantum cryptography, this research helps bridge the gap between theoretical security proofs and experimental reality. It moves the field past the question of whether these schemes can work in a perfect vacuum and addresses how they function when signals fade and equipment is imperfect. The authors did not claim to have solved every possible attack vector, but they have firmly closed the door on a major class of attacks that rely on low-resource subversion in lossy environments. Their work suggests that with the right choice of functions and within the established security region, quantum position verification can be a robust method for confirming location. This provides a solid foundation for the next generation of experiments, allowing scientists to build more complex and secure systems with the confidence that the underlying mathematics holds up under the stress of real-world conditions.

Technical Summary: Quantum Gate Lower Bounds for Loss-Tolerant Position Verification

Problem Statement
Quantum Position Verification (QPV) is a cryptographic task where a verifier attempts to establish the spatial location of a prover. The specific scheme analyzed is the f-BB84 scenario, a well-studied protocol where a prover receives classical inputs $x$ and $y$ at two distinct spacetime locations and a quantum system $Q$ . The prover must compute a Boolean function $f(x, y)$ to determine the measurement basis (computational or Hadamard) for $Q$ , measure it, and return the outcome to specific locations. The security relies on the relativistic constraint that an honest prover must perform the operation within a specific spacetime region, while attackers located outside this region must reproduce the operation non-locally using shared entanglement.

While previous work established that attacking f-BB84 requires resources growing with the input size $n$ , these bounds often relied on idealized conditions: zero transmission loss, perfect state preparation, and specific assumptions about the function $f$ . Real-world implementations face significant challenges, particularly photon loss (which can exceed 50% over long distances) and imperfect state preparation. Furthermore, proving super-logarithmic lower bounds on entanglement cost for explicit functions is hindered by connections to the Conditional Disclosure of Secrets (CDS) problem, a long-standing open problem in classical cryptography. Consequently, the security of f-BB84 under realistic loss and noise conditions remained incompletely understood.

Methodology
The authors employ a reductionist approach, linking the f-BB84 verification task to communication complexity and monogamy-of-entanglement (MoE) games.

Lossy Monogamy-of-Entanglement (MoE) Games: The core technical tool is a new analysis of a "lossy" BB84 MoE game. In this game, two players (Alice and Bob) share a state and receive a basis choice from a referee. They must output the correct measurement result or declare a "loss" ( $\perp$ ). Unlike prior numerical approaches, the authors derive a tight analytic tradeoff between the probability of joint correctness ( $C$ ) and joint loss ( $L$ ). Crucially, this bound holds without requiring the players' outputs to always agree, and it accounts for imperfections in the referee's input states.
Reduction to Simultaneous Message Passing (SMP): The authors construct a reduction from any f-BB84 protocol to the SMP communication scenario. In this reduction, the number of quantum gates and measurements performed by the attackers in the first round of the f-BB84 protocol upper-bounds the communication cost in an SMP protocol.
- The attackers in the f-BB84 scheme are modeled as Alice and Bob in the SMP scenario.
- They send descriptions of their local operations (gates and measurements) to a referee.
- The referee uses these descriptions to simulate the density matrix resulting from the attackers' strategy and attempts to compute $f(x, y)$ .
Continuity Arguments: To handle imperfect input states (where the prepared states are $\eta$ -close in trace distance to ideal BB84 states), the authors utilize a continuity lemma. This links the performance of the protocol on ideal inputs to its performance on noisy inputs, allowing the analytic MoE bounds to be applied to realistic experimental conditions.

Key Contributions and Results

Analytic Lossy MoE Bound: The paper proves a tight inequality for the lossy BB84 MoE game:
$C + \frac{L}{\sqrt{2}} \leq \cos^2(\pi/8)$
where $C$ is the probability of both players being correct and $L$ is the probability of both declaring a loss. This result is derived analytically, replacing previous numerical semidefinite programming (SDP) optimizations, and is valid even when players do not coordinate their outputs.
Gate Lower Bounds under Loss and Noise: By combining the MoE bound with the SMP reduction, the authors establish a lower bound on the quantum resources required to attack f-BB84. For the inner product function (which has linear SMP complexity), the number of quantum gates ($CG$) and single-qubit measurements ($CM$) required by attackers satisfies:
$(\log(q) + 1)(2CG + CM) \geq n - O(1)$
This holds provided the protocol parameters fall within a specific security region defined by:
$\frac{\epsilon(1 - L)}{s} + 2L + \frac{\eta}{s} < 1$
where $s = \sin^2(\pi/8)$ , $L$ is the declared loss probability, $\epsilon$ is the error probability (conditioned on non-loss), and $\eta$ bounds the trace distance of input states from ideal.
Optimality of the Security Region: The authors demonstrate that this security region is optimal at least when considering ideal BB84 state inputs ( $\eta=0$ ). Outside this region, there exists a trivial attack using only $O(1)$ quantum gates and no shared entanglement (a strategy involving guessing the basis and declaring loss with probability 50%). The paper notes that the tightness of the bound with respect to the imperfection parameter $\eta$ remains unproven.
Robustness to Imperfections: The results apply to scenarios with up to 50% declared loss (at zero error) and tolerate imperfect state preparation. The bounds also hold even if the quantum messages are "arbitrarily slow," accommodating the physical reality of quantum information traveling slower than light in fiber optics.

Significance and Claims
The paper claims to provide the first nearly-linear quantum gate lower bounds for the f-BB84 scheme that are robust against realistic experimental imperfections, specifically transmission loss and state preparation errors.

Evading the CDS Barrier: By focusing on gate complexity rather than entanglement cost, the authors bypass the theoretical obstruction posed by the CDS problem, which makes proving super-logarithmic entanglement lower bounds for explicit functions difficult.
Experimental Relevance: The results are directly applicable to recent and upcoming experimental implementations of f-BB84. The paper establishes that these schemes remain secure under a "bounded quantum gate" assumption on the attacker, even when allowing for significant loss (up to 50%) and non-ideal states.
Tightness: The authors assert that their derived security region is as large as possible for ideal inputs, as any point outside this region admits an $O(1)$ gate attack.

The work does not propose new experimental setups or applications but rather provides a rigorous theoretical foundation validating the security of existing and near-term f-BB84 protocols against attackers with limited quantum computational resources, even in noisy environments.

Technical Summary: Quantum Gate Lower Bounds for Loss-Tolerant Position Verification

More like this