A complexity theory for non-local quantum computation

This paper establishes a complexity theory for non-local quantum computation by introducing resource-efficient reductions to prove that the $f$-measure and $f$-route tasks are equivalent under constant overhead, thereby simplifying existing proofs and deriving new sub-exponential upper bounds and efficient protocols for various functions.

The Gist

Imagine you have two friends, Alice and Bob, who are far apart. They want to perform a magic trick together: they need to swap a secret object between them or measure it, but they aren't allowed to meet in person. Instead, they can only send one quick text message back and forth and share a special "magic connection" (entanglement) beforehand. This setup is called Non-Local Quantum Computation (NLQC).

The big mystery in this field is: How much of that "magic connection" (entanglement) do they actually need to pull off different tricks?

The authors of this paper say, "We can't easily calculate the exact cost for every single trick because the math gets too hard (it would solve some of the biggest unsolved problems in computer science). So, instead of measuring the cost directly, let's compare the tricks to each other."

Here is the paper's story, explained with everyday analogies:

1. The "Reduction" Strategy: Comparing Difficulty

Think of NLQC tasks like different video game levels. Some levels are easy; some are hard.

• The Old Way: Try to count exactly how many "coins" (entanglement) you need to beat Level A, then count for Level B, then compare the numbers.
• The Paper's Way: Ask, "If I have a cheat code that lets me beat Level A, can I use that same cheat code (with maybe just a tiny bit of extra effort) to beat Level B?"
  • If the answer is yes, then Level B is not harder than Level A.
  • If you can do this both ways, then Level A and Level B are essentially the same difficulty.

The authors used this "cheat code" method to map out which quantum tricks are equivalent.

2. The Big Discovery: Three Different Names, Same Game

The paper focuses on three specific types of tricks that have been studied for years:

1. f-route: Alice and Bob have a quantum object. Depending on a math problem they solve together (a function $f$), they must decide whether to send the object to Alice or Bob.
2. f-measure: Alice and Bob have a quantum object. Depending on the math problem, they must both guess a secret bit (0 or 1) correctly.
3. CDQS: A "Conditional Disclosure of Secrets" game where they only reveal a secret if the math problem says "Yes."

The Paper's Claim: These three tasks are equivalent.

• Analogy: Imagine you have a key that opens a Front Door, a Back Door, and a Side Door. For a long time, people thought these were three different locks requiring three different keys. This paper proves that one key opens all three doors (with only a tiny, constant amount of extra effort).
• Why it matters: If a scientist proves a rule for the "Front Door" (f-route), they automatically know it applies to the "Back Door" (f-measure) and the "Side Door" (CDQS). This saves a massive amount of work and simplifies the whole field.

3. The "Coherent" vs. "Classical" Control

The paper also looks at more advanced tricks where the "decision" to swap or measure isn't just based on a simple "Yes/No" answer, but on a quantum superposition (a state where it's both Yes and No at the same time).

• The Finding: They found that even these fancy "Coherent" tricks are powerful enough to perform the simpler "Classical" tricks (like the three doors mentioned above).
• Analogy: If you have a master chef who can cook a complex, multi-layered soufflé (Coherent task), they can definitely cook a simple grilled cheese sandwich (Classical task) just as well. The paper shows that the "master chef" tools are strong enough to handle the simpler jobs.

4. The "Interchange" vs. "Distinguish" Trick

Finally, the paper looks at two very abstract tasks that don't even involve a math function $f$:

• Interchange: Swapping two specific quantum states.
• Distinguish: Telling two specific quantum states apart.
• The Finding: If you can efficiently swap two states, you can also efficiently tell them apart.
• Analogy: If you have a machine that can perfectly swap a red ball and a blue ball, you can also build a machine that tells you which is which. The paper proves this link exists in the quantum world, though they couldn't prove the reverse (that telling them apart implies you can swap them).

Summary of Results

• Simplification: They proved that the three most famous quantum tasks (f-route, f-measure, CDQS) are actually the same difficulty. This means researchers don't need to study them separately anymore.
• New Bounds: Because of this equivalence, they could take known "upper limits" (maximum cost) for one task and apply them to the others. For example, they found a new, tighter limit on how much entanglement is needed for the "f-measure" task.
• Harder Tasks: They showed that "Coherent" tasks (where inputs are in superposition) are generally harder or at least as hard as the "Classical" ones.

What the paper does NOT claim:

• It does not claim to have built a working quantum computer.
• It does not claim to have solved the P vs NP problem (though it notes that solving the entanglement cost directly would have done so).
• It does not propose new medical or commercial applications. It is purely a theoretical map of how these quantum "games" relate to one another.

In short, the authors built a Rosetta Stone for Non-Local Quantum Computation. They showed that different languages (tasks) are actually just dialects of the same language, allowing the scientific community to translate results from one area to another instantly.

Technical Summary

Technical Summary: A Complexity Theory for Non-Local Quantum Computation

Problem Statement
Non-local quantum computation (NLQC) replaces local interactions between two systems with a single round of communication and shared entanglement. A central quantity of interest in NLQC is the entanglement cost required to implement specific computations. However, a complete characterization of this cost faces fundamental obstructions: lower bounds on entanglement for certain NLQC tasks would imply lower bounds on established complexity measures (e.g., memory or communication complexity), which are notoriously difficult to prove. For instance, proving super-polynomial lower bounds for the f-route task for functions in P would separate complexity classes L and P.

To circumvent these direct lower-bound barriers, the authors propose an indirect approach analogous to classical complexity theory: studying the relative hardness of different NLQC tasks by identifying resource-efficient reductions between them. The goal is to establish a "complexity theory" for NLQC by mapping the relationships among various tasks, thereby simplifying existing proofs and transferring properties between equivalent tasks.

Methodology
The paper introduces a formal framework for NLQC reductions.

• Resource State Reduction: A task $G$ reduces to $F$ if a resource state sufficient to implement $F$ (with constant overhead) can be used to implement $G$.
• Oracle Reduction: A stricter form where the protocol for $G$ uses the protocol for $F$ as an oracle (black box), implying that the local operations of $F$ can be directly applied to $G$.
• Classes of Tasks: The authors categorize NLQC tasks into:
  1. Classically Controlled: Protocols where a small quantum operation is controlled by a large classical computation (e.g., f-route, f-measure, CDQS).
  2. Coherently Controlled: Protocols implementing unitaries controlled by inputs in superposition (e.g., Cf-SWAP, Cf-PHASE, Cf-PAULI).
  3. State/Unitary Classes: Tasks defined by state transformations rather than Boolean functions (e.g., Interchange and Distinguish).

The methodology involves constructing explicit reductions (implications) between these classes, often leveraging properties of quantum information theory such as the diamond norm, fidelity, and entropy inequalities (e.g., the CIT inequality).

Key Contributions and Results

1. Equivalence of Classically Controlled Tasks:
   The primary result is the proof that three major classically controlled NLQC tasks are equivalent under $O(1)$ overhead reductions:
   $$\text{f-route} \iff \text{f-measure} \iff \text{CDQS}$$

   • f-route: Routing a quantum system $Q$ to Alice or Bob based on a Boolean function $f(x,y)$.
   • f-measure: Alice and Bob output a bit $b$ where the input state is a BB84 state determined by $f(x,y)$.
   • CDQS (Conditional Disclosure of Secrets): A cryptographic primitive where a secret is revealed to a referee iff $f(x,y)=1$.
   • Implication: This equivalence simplifies the literature significantly. Properties previously proven separately for f-route and f-measure now apply to both. Specifically, f-measure inherits:
     • An upper bound of $2^{O(\sqrt{n} \log n)}$ for all functions.
     • Efficient protocols for functions in the complexity class $\text{Mod}_k\text{L}$.
     • Security results in the random oracle model and parallel repetition properties.

2. Reductions Among Coherently Controlled Operations:
   The authors establish a hierarchy and equivalence among coherent tasks:

   • Cf-SWAP $\implies$ Cf-PHASE: Implementing a coherent swap implies a coherent phase shift.
   • Cf-PHASE $\iff$ Cf-PAULI: The authors prove that coherent phase tasks are equivalent to coherent Pauli tasks (specifically Cf-Z or Cf-PAULI) under constant overhead.
   • Coherent $\implies$ Classical: Crucially, the paper shows that the coherent primitive Cf-PHASE (and thus Cf-PAULI) is strong enough to implement the classically controlled tasks (f-route, f-measure, CDQS). This suggests that coherent protocols are at least as hard as, and potentially harder than, incoherent ones.
   • Composition: The paper details how to compose these coherent tasks (e.g., adding controls via AND operations) with only linear overhead in the number of controls.

3. State Transformation Reductions:
   The authors investigate tasks not defined by Boolean functions. They prove that an efficient NLQC for Interchange (swapping two orthogonal states $|\psi_0\rangle$ and $|\psi_1\rangle$) implies an efficient NLQC for Distinguish (distinguishing the Fourier states $|\phi_\pm\rangle = \frac{1}{\sqrt{2}}(|\psi_0\rangle \pm |\psi_1\rangle)$). This result is inspired by similar equivalences in standard quantum circuit complexity. The reverse direction remains an open question.

Significance and Claims
The paper claims that by establishing these reductions, it lays the groundwork for a more complete complexity theory for NLQC.

• Simplification: The equivalence of f-route, f-measure, and CDQS unifies the study of these tasks, allowing researchers to focus on a single representative primitive.
• New Properties: The transfer of upper bounds (e.g., from f-route to f-measure) provides new efficient protocols and complexity bounds for previously less-studied tasks.
• Complexity Theory Insights: The authors suggest that studying these reductions may eventually provide a route to new lower bounds on complexity measures. Since entanglement costs in NLQC are upper-bounded by complexity measures, proving lower bounds on NLQC tasks could yield lower bounds for complexity classes.
• Barriers: The paper acknowledges that proving linear lower bounds for these tasks faces the same "CDS barrier" as classical cryptography, where such bounds would imply breakthroughs in classical communication complexity.
• Open Questions: The authors explicitly state they have not proven that all coherent tasks are strictly harder than all incoherent tasks, nor have they proven the reverse direction for the Interchange/Distinguish reduction. They also note that while Cf-SWAP implies Cf-PHASE, the reverse implication is not yet established.

In summary, the paper shifts the focus from direct entanglement cost estimation to a structural analysis of NLQC tasks, demonstrating that many distinct protocols are computationally equivalent and that coherent control offers a powerful, potentially harder, framework for non-local computation.