Formalize Open Quantum Problem #48: The entanglement cost of f-routing

### What is the conjecture

This is problem [#48](https://oqp.iqoqi.oeaw.ac.at/large-lower-bounds-for-the-entanglement-cost-of-f-routing), listed in the [Open Quantum Problems master list](https://oqp.iqoqi.oeaw.ac.at/open-quantum-problems).

> **Problem (Open Quantum Problem #48: “The entanglement cost of `f`-routing”).**
> Fix `ε > 0`. Find an explicit family of Boolean functions
> `f_n : {0,1}^n × {0,1}^n → {0,1}`
> for which every `ε`-sound `f_n`-routing protocol requires entanglement cost `poly(n)`.

A standard formalization is in terms of **one-round entanglement-assisted routing protocols**:

* Fix a Boolean function `f : {0,1}^n × {0,1}^n → {0,1}` and a fixed finite-dimensional quantum register `Q` (typically `O(1)`-dimensional, often just a qubit).
* Alice receives the quantum system `Q` and the classical input `x ∈ {0,1}^n`.
* Bob receives the classical input `y ∈ {0,1}^n`.
* Before inputs arrive, Alice and Bob share an entangled resource state `|ψ⟩` on local ancilla spaces `A_0 ⊗ B_0`, where both local spaces have dimension `d`. The **entanglement cost** of the protocol is `log_2 d`.
* After seeing `x`, Alice applies a quantum channel `V_x^A` to `Q A_0`, keeping one output register and sending one output register to Bob.
* After seeing `y`, Bob applies a quantum channel `V_y^B` to `B_0`, keeping one output register and sending one output register to Alice.
* After the simultaneous exchange, Alice applies a second channel `W_x^A` to her remaining register together with Bob’s message; Bob analogously applies `W_y^B` to his remaining register together with Alice’s message.
* Let `Ω^A_{xy}` and `Ω^B_{xy}` denote the induced quantum channels from the input system `Q` to Alice’s and Bob’s final output systems.

The routing protocol is then judged by whether it successfully transports the unknown input state in `Q` to the correct side:

* The protocol is **correct** if
* `Ω^A_{xy} = I_Q` whenever `f(x,y)=0`, and
* `Ω^B_{xy} = I_Q` whenever `f(x,y)=1`,
where `I_Q` is the identity channel on `Q`.
* The protocol is **`ε`-sound** if
* `||Ω^A_{xy} - I_Q||_⋄ ≤ ε` whenever `f(x,y)=0`, and
* `||Ω^B_{xy} - I_Q||_⋄ ≤ ε` whenever `f(x,y)=1`,
where `||·||_⋄` denotes the diamond norm.

Define the cost function
`E_ε(f) := min { log_2 d : there exists an ε-sound f-routing protocol for f using local resource dimension d }`.

Then the OQP can be formalized as:

* **Main lower-bound problem:** for a fixed constant `ε > 0`, exhibit an explicit family `(f_n)_n` such that
`E_ε(f_n) ≥ n^c`
for some constant `c > 0`.
A stronger target would be a **linear** lower bound `E_ε(f_n) = Ω(n)`.

This task comes from **quantum position verification** / **non-local quantum computation**, where an honest prover effectively computes `f(x,y)` and routes the incoming quantum system accordingly, while dishonest spatially separated players are limited to one simultaneous communication round plus pre-shared entanglement.

A few useful equivalent viewpoints / related directions are:

* The problem asks for an **explicit hard family** of classically controlled routing tasks, not just random functions.
* Known upper bounds show that every Boolean `f` admits an `f`-routing protocol with subexponential cost, and some low-complexity families admit polynomial-cost protocols, so the open challenge is to prove **polynomial lower bounds** for an explicit family in the full bounded-error model.
* Via the connection to **conditional disclosure of secrets (CDS)**, strong lower bounds on `f`-routing would also imply strong lower bounds on CDS randomness complexity and thus on related secret-sharing / span-program quantities.
* Natural intermediate targets are restricted settings already studied in the literature, such as one-sided perfect correctness or purified/unitary attack models, where partial linear lower bounds are known.

### Where to find the details / references

Primary sources:

* [Open Quantum Problems site (Problem #48)](https://oqp.iqoqi.oeaw.ac.at/large-lower-bounds-for-the-entanglement-cost-of-f-routing)
* [Open Quantum Problems master list (for numbering/metadata)](https://oqp.iqoqi.oeaw.ac.at/open-quantum-problems)
* R. Allerstorfer, H. Buhrman, A. May, F. Speelman and P. V. Lunel, “Relating non-local quantum computation to information theoretic cryptography” (Quantum 8, 1387 (2024); [arXiv:2306.16462](https://arxiv.org/abs/2306.16462))
(core reference for the `f`-routing / CDS connection, and for general upper bounds)

Key related references (as listed on the OQP page):

* A. Kent, W. J. Munro, and T. P. Spiller, “Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints” (Phys. Rev. A 84, 012326 (2011))
(position-verification origin of the task)
* H. Buhrman, S. Fehr, C. Schaffner, and F. Speelman, “The garden-hose model” (ITCS 2013)
(foundational routing / position-verification model)
* B. Applebaum and P. N. Vasudevan, “Placing conditional disclosure of secrets in the communication complexity universe” (Journal of Cryptology 34 (2021))
(explains why large CDS lower bounds are important)
* Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes” (J. Comput. Syst. Sci. 60, 592–629 (2000))
(classical CDS / secret-sharing connection)
* A. Bluhm, S. Höfer, A. May, M. Stasiuk, P. V. Lunel, and H. Yuen, “A complexity theory for non-local quantum computation” ([arXiv:2505.23893](https://arxiv.org/abs/2505.23893))
(includes partial lower bounds for random functions in restricted models, and reductions/equivalences among NLQC tasks)
* V. R. Asadi, E. Culf, and A. May, “Rank lower bounds on non-local quantum computation” (Phys. Rev. A 109, L061304 (2024); [arXiv:2402.18647](https://arxiv.org/abs/2402.18647))
(linear lower bounds for several explicit functions in one-sided perfect models)
* R. Gay, I. Kerenidis, and H. Wee, “Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption” (CRYPTO 2015; [IACR ePrint 2015/665](https://eprint.iacr.org/2015/665))
(logarithmic lower bounds for classical CDS)
* V. R. Asadi, K. Kuroiwa, D. Leung, A. May, S. Pasterski, and C. Waddell, “Conditional disclosure of secrets with quantum resources” (Quantum 9, 1885 (2025); [arXiv:2404.14491](https://arxiv.org/abs/2404.14491))
(quantum CDS / CDQS, closely related to `f`-routing)

### Prerequisites needed

* Finite-dimensional quantum information: quantum states, channels, entanglement, tensor products
* Entanglement-assisted one-round communication / non-local quantum computation models
* Linear algebra / operator theory for quantum systems; Schmidt rank / local dimension; basic channel norms
* Diamond norm and basic correctness / approximation notions for quantum channels
* Communication complexity viewpoint for Boolean functions `f(x,y)`
* (Optional) quantum position verification, CDS, secret sharing, and span programs

### [AMS categories](https://github.com/google-deepmind/formal-conjectures/labels?q=ams-)

* ams-81 (Quantum theory)
* ams-94 (Information and communication theory)
* ams-68 (Computer science)
* ams-47 (Operator theory)

### Choose either option

* [ ] I plan on adding this conjecture to the repository
* [x] This issue is up for grabs: I would like to see this conjecture added by somebody else

---

Start by reading the Open Quantum Problems page for Problem #48 and the cited routing and conditional-disclosure references. Then inspect the repository's existing formalized conjectures to determine the expected Lean entry point and statement style. Done means the conjecture is added in the repository's established format, with any required validation passing.

Written by the indexing model from the issue text.