⚛️ quantum physics

Equivalence of non-local computation tasks beyond Clifford operations

This paper establishes new reduction relationships among non-local quantum computation tasks relevant to quantum position-verification, demonstrating that protocols for simple classical-controlled redirection imply the ability to perform complex controlled operations (including arbitrary diagonal unitaries), thereby proving that many feasible position-verification schemes share the same asymptotic entanglement cost and security levels.

Original authors: Andreas Bluhm, Simon Höfer, Alex May, Florian Speelman, Philip Verduyn Lunel

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andreas Bluhm, Simon Höfer, Alex May, Florian Speelman, 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 two friends, Alice and Bob, who are miles apart. They want to perform a complex magic trick together on a quantum object (like a tiny particle of light) that they are holding. The catch? They are only allowed to send each other one single message at the same time. They cannot chat back and forth; it's a one-shot deal.

This scenario is called Non-Local Quantum Computation (NLQC). It's the foundation for a security system called Quantum Position Verification (QPV). In QPV, a "prover" tries to prove they are standing in a specific spot. If they are honest, they can do the trick locally. If they are cheating (and are actually far away), they have to try to fake the trick using only that one single message and some pre-shared "magic" (entanglement). The harder the trick is to fake, the more secure the location system is.

The Big Question: How Hard is the Trick?

The authors of this paper asked: Are all these different magic tricks equally hard to fake?

In computer science, we often ask if Problem A is just as hard as Problem B. If you can solve B, can you easily solve A? The authors found that for many of these quantum tricks, the answer is a resounding yes. They discovered a web of connections where solving one type of trick automatically gives you the ability to solve many others, often with very little extra effort.

The "Universal Translator" of Quantum Tricks

The paper focuses on a specific, simple trick called f-measure. Imagine Alice and Bob have a secret code (a function $f$ ) based on their inputs. Depending on the code, they must measure a quantum particle in one of two ways (like checking if it's "up" or "down," or "left" or "right").

The authors proved that f-measure is the "Universal Translator" for a huge class of quantum tasks. Here is what they found:

The Simple Swap is the Key: There is a very basic trick called f-routing, which is just like a remote-controlled switch. If the code says "1," the particle goes to Bob; if "0," it stays with Alice. The authors showed that if you can do this simple switch, you can also do the more complex f-measure trick.
One Trick Fits All: They proved that any variation of the f-measure trick (measuring in any two different directions) is essentially the same difficulty as the simplest version. If you can break the simple version, you can break them all.
Clifford Magic: They showed that even if the trick involves applying complex "Clifford" operations (a specific family of quantum gates that are the "bread and butter" of quantum computers), it's still no harder than the simple switch.
The Surprising Non-Clifford Result: This is the biggest surprise. Usually, quantum tricks that go beyond "Clifford" operations are considered much harder and more secure. However, the authors found that even tricks involving a specific type of complex rotation (called a "diagonal unitary") can be reduced to the simple switch.

The "Security" Takeaway

Think of the "entanglement" (the pre-shared magic) as the ammunition a cheater needs to break the system.

If a task requires a lot of ammunition, it's secure.
If a task requires very little, it's insecure.

The authors' discovery is like finding out that all these different locks are actually made of the same weak material. Even though some locks look more complicated (involving complex rotations or multi-qubit operations), they don't actually require more ammunition to break than the simplest lock.

The "How-To" (The Magic Gadget)

How did they prove this? They used clever "gadgets" inspired by teleportation and measurement-based computing.

Imagine you have a box that can measure a particle in a specific way.
The authors showed that by using this box as a "black box" (an oracle) and adding a few extra wires and pre-shared entangled pairs, you can build any other box you need.
It's like showing that if you have a Swiss Army Knife with a screwdriver, you can build a hammer, a saw, and a wrench just by arranging the screwdriver in different ways.

The Bottom Line

The paper concludes that for the types of quantum position-verification schemes that are currently feasible (using large classical inputs and small quantum inputs), there is no "super-secure" variation hiding in the complex ones.

If a simple "switch" protocol can be broken with a certain amount of entanglement, then all these more complex protocols (involving controlled measurements and unitary operations) can be broken with roughly the same amount of entanglement. They are all in the same "difficulty league."

In short: The authors mapped out the landscape of these quantum tasks and found that the "hardest" looking ones are actually just as easy to break as the simplest ones. This means that for building secure location systems, we don't need to invent increasingly complex quantum tricks; the simple ones are already as secure (or insecure) as the complex ones can possibly be.

Technical Summary: Equivalence of Non-local Computation Tasks Beyond Clifford Operations

Problem Statement
Non-local quantum computation (NLQC) investigates how two spatially separated parties, Alice and Bob, can implement a joint quantum channel on distributed systems using only a single simultaneous round of quantum communication and shared entanglement. While it is known that any quantum channel can be implemented via NLQC, the resource cost—specifically the amount of pre-shared entanglement required—varies significantly across different tasks.

A primary motivation for studying NLQC is its application to Quantum Position Verification (QPV). In QPV, a prover attempts to convince verifiers of their physical location. A cheating prover, located elsewhere, must simulate the honest prover's local operations using NLQC. The security of a QPV scheme relies on the hardness of the NLQC task: if a cheating prover requires an exponentially large amount of entanglement to simulate the task, the scheme is considered secure.

The central problem addressed in this work is the lack of a unified understanding of the relative hardness of different NLQC tasks. Specifically, while the "f-routing" task (classically controlled routing of a quantum system) has been extensively studied, it is unclear whether other plausible QPV protocols—particularly those involving controlled quantum measurements or unitaries beyond simple routing—offer improved security. The authors aim to determine if these seemingly distinct tasks are reducible to one another, thereby establishing whether they share the same asymptotic entanglement costs.

Methodology
The authors employ a framework of reductions between families of NLQC tasks, analogous to reductions in computational complexity theory. They define two types of reductions:

Resource State Reduction: Task $G$ reduces to task $F$ if $G$ can be implemented using a small number of copies of the resource state required for $F$ .
Oracle Reduction: Task $G$ reduces to task $F$ if $G$ can be implemented using a small number of black-box calls to an oracle that implements $F$ , plus local operations and a small amount of additional shared resources.

The paper focuses on f-controlled 2→2 tasks, where the operation performed depends on the value of a Boolean function $f(x, y)$ given to Alice ( $x$ ) and Bob ( $y$ ). The input systems are typically of constant size (O(1) qubits), while the classical inputs can be large ( $n$ bits).

The technical approach involves:

Gate Teleportation and Measurement-Based Quantum Computation (MBQC): The authors utilize gadgets inspired by gate teleportation and non-adaptive MBQC to construct protocols that transform one NLQC task into another.
Angle Characterization and Manipulation: For single-qubit measurements, the authors characterize tasks by rotation angles on the Bloch sphere. They develop techniques to add, split, and approximate these angles using combinations of simpler protocols (e.g., combining $f$ -measure protocols with angles $\theta_1$ and $\theta_2$ to simulate $\theta_1 + \theta_2$ ).
Port-Based Teleportation: Used in the appendices to demonstrate that the spatial distribution of quantum inputs (whether on Alice's side, Bob's side, or split) does not significantly alter the hardness of the task, provided the input size is constant.

Key Contributions and Results

Equivalence of Single-Qubit f-Measure Protocols:
The authors prove that all non-trivial single-qubit $f$ -measure protocols (where the measurement basis is chosen between two arbitrary bases $U$ and $V$ based on $f(x,y)$ ) are equivalent under O(1) oracle reductions.
- Specifically, any $f$ -measure( $U, V$ ) can be reduced to the canonical case $f$ -measure( $I, H$ ) (measurement in computational or Hadamard basis).
- This implies that no single-qubit projective measurement protocol offers a security advantage over the simplest case, as they all inherit the same sub-exponential entanglement upper bounds known for $f$ -routing.
Reduction of Controlled Clifford Operations:
The paper demonstrates that $f$ -controlled Clifford unitaries and measurements in Clifford-related bases can be reduced to $f$ -measure( $I, H$ ).
- By establishing an equivalence between $f$ -measure( $I, H$ ) and $f$ -Bell measurement (measurement in the Bell basis), the authors show that controlled Clifford operations can be implemented via gate teleportation strategies using $f$ -Bell oracles.
- This extends the class of tasks reducible to $f$ -routing, confirming that even multi-qubit Clifford-controlled operations do not inherently require more entanglement than the basic routing task.
Extension to Controlled Diagonal Unitaries:
A significant result is the reduction of $f$ -controlled unitaries of the form $U = C_1 D C_0$ , where $C_0, C_1$ are Clifford circuits and $D$ is an arbitrary diagonal unitary.
- The authors show that $f$ -unitary( $I, U$ ) can be oracle-reduced to $f$ -measure( $I, H$ ) with O( $n_Q$ ) overhead (where $n_Q$ is the number of qubits).
- This is surprising because $D$ can have high T-depth, making $U$ highly non-Clifford. Yet, the implementation cost remains tied to the simpler Clifford-based $f$ -measure task.
- The construction relies on "Z-rotation injection gadgets" that relate controlled single-qubit X-rotations (implementable via $f$ -measure) to controlled multi-qubit Z-rotations via CZ gates.

Significance and Claims
The paper claims that the landscape of feasible QPV protocols is more constrained than previously thought. By establishing a rich structure of reductions, the authors demonstrate that:

Security Limitations: Many proposed QPV schemes involving controlled single-qubit measurements, Clifford operations, and even certain non-Clifford diagonal unitaries do not offer improved security over the basic $f$ -routing task. They all share the same asymptotic scaling for entanglement cost (sub-exponential in the classical input size).
Unified Hardness: The relative hardness of these tasks is unified; if a sub-exponential attack exists for $f$ -routing, it extends to these broader classes of tasks via the established reductions.
Technique Advancement: The work introduces new strategies for NLQC, such as specific gate-teleportation gadgets and angle-splitting techniques, which may be of independent interest for constructing upper bounds on entanglement costs for other NLQC tasks.

The authors remain modest regarding the scope of these results, noting that while they cover a broad class of "feasible" protocols (large classical input, small quantum input), it remains an open question whether two layers of diagonal gates or other more complex unitary structures could provide higher security levels that evade these reductions. The results do not claim to prove super-linear lower bounds but rather clarify that many intuitive extensions of $f$ -routing do not escape the known upper bounds.