⚛️ quantum physics

Linear gate bounds against natural functions for position-verification

This paper establishes a linear lower bound on the quantum gate and measurement complexity required to implement specific classical functions in position-verification schemes like $f$ -routing and $f$ -BB84, proving that these protocols are secure against adversaries with sub-linear quantum resources while remaining feasible for honest provers with linear classical and constant quantum resources.

Original authors: Vahid Asadi, Richard Cleve, Eric Culf, Alex May

Published 2026-07-28

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Vahid Asadi, Richard Cleve, Eric Culf, Alex May

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 you are trying to prove to a group of friends that you are standing exactly in the middle of a giant, empty room. You can't just say "I'm here," because they can't see you. Instead, they shout questions at you from opposite walls and demand an answer the instant the sound waves hit your ears. If you are actually in the middle, the timing works out perfectly. If you are hiding in a corner, the sound takes too long to reach you, and your reply arrives late, giving you away. This is the basic idea behind position verification: using the speed of light as a ruler to prove where someone is.

But here's the tricky part: what if the person trying to cheat has a superpower? In the world of quantum physics, there's a rule called the "no-cloning theorem" which says you can't make a perfect copy of a secret quantum message. This was supposed to make position verification unbreakable. However, clever cheaters realized they could use a different superpower: entanglement. Imagine two magical coins that always land on the same side, no matter how far apart they are. If a team of cheaters shares these coins, they can pretend to be in the middle of the room even if they are standing at the edges, by using their magical connection to simulate the answer instantly.

For a long time, scientists wondered: How much of this magical entanglement does a cheater need to pull off the trick? If the answer is "a lot," then honest people can stay safe because building that much magic is too hard. But if the answer is "just a little," then the whole system is broken. This paper dives into that question, specifically looking at schemes where the honest person only needs to do a simple math problem (like adding up numbers) and a tiny bit of quantum magic to stay honest.

The Paper's Big Discovery: It's Not Just About the Magic Coins, It's About the Work

In this study, the authors, Vahid R. Asadi, Richard Cleve, Eric Culf, and Alex May, decided to look at the problem from a new angle. Previous research had focused on how many "magic coins" (qubits) a cheater needed to hold. But the authors realized that holding the coins isn't the whole story; the cheater also has to do something with them. They have to run a program, flipping switches and performing calculations, to figure out the right answer.

The paper proves a surprising and powerful fact: To cheat successfully, a dishonest player has to do a massive amount of quantum work.

Specifically, the authors show that the number of quantum "gates" (the basic steps a quantum computer takes to calculate) and measurements a cheater needs is directly tied to how hard the math problem is. If the honest person has to solve a problem that requires a lot of communication to solve (like the "Inner Product" function, which is a specific way of multiplying and adding two lists of numbers), then the cheater must perform a number of quantum operations that grows linearly with the size of the input.

Think of it like a heist movie. In the old stories, the thieves just needed a really big vault (a lot of entanglement) to hide their loot. This paper says, "Wait a minute! Even if you have the vault, you still have to run a marathon to get the keys." The authors proved that for certain types of position-verification schemes (called f-routing and f-BB84), the cheater cannot just sit back and wait. They have to actively compute the answer using a number of quantum steps that is roughly proportional to the size of the puzzle.

The "Inner Product" Test Case

To make this concrete, the authors tested their theory on a specific math problem called the Inner Product. Imagine you and a friend each have a list of 1,000 numbers (0s and 1s). You want to know if the total number of times you both have a "1" in the same spot is odd or even. This is the Inner Product.

The paper shows that if the honest person is just doing this math on a normal computer (which is easy and fast for them), a cheater trying to fake their location would need to perform a number of quantum steps that grows linearly with the length of those lists. If the list has $n$ numbers, the cheater needs roughly $n$ quantum steps.

This is a big deal because it creates a huge gap between the honest person and the cheater:

The Honest Person: Needs to do simple math (linear effort) and only a tiny, fixed amount of quantum work (like holding one or two qubits).
The Cheater: Needs to do a massive amount of quantum work (linear effort) to pull off the deception.

The authors proved this mathematically, showing that you cannot cheat these schemes with "sub-linear" resources. In other words, you can't get away with doing a tiny fraction of the work if the puzzle is big.

Why This Matters: The "Loss-Tolerant" Bonus

One of the coolest things about this paper is that it applies to a version of the scheme that is loss-tolerant. In the real world, sending quantum signals (like photons of light) over long distances is messy; many of them get lost or absorbed. Previous theories suggested that if you lost too many signals, the security guarantees might vanish.

However, the authors show that their new bound holds up even in these messy, lossy conditions. This means that even if the honest person loses some of their quantum signals, the cheater still has to do that massive amount of quantum work to fake their location. It's like saying that even if the heist movie has a few scenes cut out, the thief still has to run the full marathon to get the keys.

What This Rules Out

The paper explicitly rules out the idea that a cheater can get away with doing very little quantum work. It argues against the hope that you could design a system where the cheater only needs a small, fixed amount of quantum resources regardless of how big the input is. The authors show that for these specific schemes, the work required scales up with the problem size.

They also clarify that they are not just counting the size of the "magic vault" (the number of qubits held), but the actual work (the number of gates and measurements performed). This is a stricter and more realistic measure of difficulty.

How Sure Are They?

The authors are very confident in their results. They didn't just simulate this on a computer or suggest it might be true; they provided a rigorous mathematical proof. They showed that if a cheater tries to break the system with fewer quantum steps than their bound predicts, they simply cannot succeed with a high enough accuracy. The proof holds for a wide range of scenarios, including when the cheater is allowed to share entanglement and when the system is lossy.

In short, this paper draws a bright line in the sand: if you want to verify someone's location using these specific quantum methods, you can be mathematically sure that a cheater will need to do a lot of hard quantum work to fool you. It turns the difficulty of the cheat from "how much magic do you have?" into "how hard are you willing to work?"—and for big problems, that work is simply too heavy to carry.

Technical Summary: Linear Gate Bounds against Natural Functions for Position-Verification

Problem Statement
Quantum position-verification (PV) schemes aim to verify the spatial location of a prover by challenging them with quantum and classical inputs that must be responded to within specific spacetime constraints. While unconditional security is impossible for classical inputs due to copy-and-forward attacks, and impossible for quantum inputs in the unconditional setting due to entanglement-based attacks, research has shifted to bounded-resource models. Specifically, protocols like $f$ -routing and $f$ -BB84 require an honest prover to compute a classical Boolean function $f$ on inputs of length $n$ while manipulating only $O(1)$ quantum systems.

Previous work [15] established that for random functions $f$ , a dishonest prover requires a resource system of size linear in $n$ (in terms of qubits) to break these schemes. However, this bound applied to the dimensionality of the resource system in a purified (unitary) view, which conflates classical processing with quantum resources. Furthermore, for random functions, the honest prover requires exponential classical resources, rendering the scheme impractical. The central problem addressed here is to establish lower bounds on the quantum computational resources (gates and measurements) required by a dishonest prover to attack these schemes when $f$ is a "natural," low-complexity function (specifically the inner product), while allowing the honest prover to operate with linear classical resources and constant quantum resources.

Methodology
The authors develop a reduction from the position-verification tasks ( $f$ -routing and $f$ -BB84) to the Simultaneous Message Passing (SMP) communication complexity model with shared entanglement ( $SMP^*$ ).

Strategy Model: The authors model the dishonest prover as two agents (Alice and Bob) located outside the verification region who intercept inputs and attempt to simulate the required quantum operation non-locally. They analyze the state of the system after the first round of operations.
State Separation:
- For $f$ -BB84, they prove that for sufficiently high fidelity ( $\epsilon < 0.11$ ), the set of states allowing successful measurement in the computational basis ( $S^0_\epsilon$ ) and the set allowing success in the Hadamard basis ( $S^1_\epsilon$ ) are disjoint. This implies the state after the first round effectively determines the value of $f(x,y)$ .
- For $f$ -routing, they utilize the monogamy of entanglement and properties of squashed entanglement to show that the sets of states allowing the qubit to be recovered on the left ( $\tilde{S}^0_\epsilon$ ) or right ( $\tilde{S}^1_\epsilon$ ) are disjoint for $\epsilon < 0.027$ .
Reduction to $SMP^*$ : The authors construct an $SMP^*$ $S M P^{*}$ protocol where Alice and Bob send descriptions of their local quantum operations (gates and measurement outcomes) to a referee. The referee reconstructs the state $\rho_{RMM'}$ $ρ_{R M M^{'}}$ and determines which set ($0$ or $1$) it belongs to, thereby computing $f(x,y)$ $f (x, y)$ .
- Crucially, the authors work in an unpurified model. They allow the agents to use mid-circuit measurements and classical processing to condition subsequent gates. The message size in the $SMP^*$ protocol corresponds to the number of bits required to describe the sequence of quantum gates and measurements performed by the dishonest prover.
Lower Bound Derivation: By relating the message size in the $SMP^*$ protocol to the number of gates ( $C_G$ ) and measurements ( $C_M$ ) used by the prover, they derive the inequality:
$(\log(q) + 1)(2C_G(f) + C_M(f)) \geq SMP^*_{\epsilon', \delta}(f)$
where $q$ is the number of qubits held by the agents.

Key Contributions and Results

Linear Lower Bound for Inner Product: By applying known linear lower bounds for the inner product function ($IP$) in the $SMP^*$ model with shared entanglement [24, 30], the authors prove that any successful attack on $f$ -routing or $f$ -BB84 using the inner product function requires a number of quantum gates and measurements that is linear in the input size $n$ .
$(\log q + 1)(2C_G(IP) + C_M(IP)) \geq \Omega(n)$
Robustness: The bound holds even if the protocol succeeds on only a constant fraction of inputs (specifically, a fraction $1/2 + g(n)$ where $g(n)$ decays slower than $2^{-n/4}$ ).
Applicability to Loss-Tolerant Schemes: The result applies to the loss-tolerant variant of $f$ -BB84 [22], addressing a practical limitation of previous proofs.
Upper Bound Tightness: The authors demonstrate that for the inner product function, a "garden-hose" attack strategy [17] can achieve the task using $O(n)$ EPR pairs and $O(n)$ measurements. This shows the lower bound on the number of operations is tight up to logarithmic factors.

Significance and Claims
The paper claims a significant advancement in understanding the security of position-verification schemes against dishonest provers with bounded quantum resources:

Shift from System Size to Computational Complexity: Unlike previous bounds that focused on the dimension of the shared entangled state (which can be inflated by purifying classical operations), this work bounds the actual number of quantum gates and measurements. This provides a more direct measure of the computational difficulty for an attacker.
Feasibility for Honest Provers: The results apply to the inner product function, which is computationally feasible (linear complexity) for an honest prover with classical resources, unlike the random functions used in prior work.
Separation of Difficulty: Assuming that implementing quantum gates is harder than classical gates, the authors establish a separation where an honest prover needs only linear classical resources and $O(1)$ quantum resources, while a dishonest prover requires linear quantum resources (gates/measurements) to break the scheme.
Refined Bounds on System Size: By restricting the dishonest prover's circuit depth to be comparable to the honest prover's (e.g., $d = O(\log n)$ ), the authors derive an improved lower bound on the number of qubits required by the attacker ( $q \gtrsim n/\log n$ ), which is stronger than the $q \gtrsim \log n$ bound from [15] and avoids the pitfalls of the purified view.

The authors conclude that these schemes are secure against attackers with sub-linear quantum resources, provided the honest prover can compute the function efficiently.

The Paper's Big Discovery: It's Not Just About the Magic Coins, It's About the Work

The "Inner Product" Test Case

Why This Matters: The "Loss-Tolerant" Bonus

What This Rules Out

How Sure Are They?

More like this