Polynomial shared-resource lower bounds for routing
- Fields
- Topics
Problem
Does an explicit total Boolean family require polynomial shared-state cost for bounded-error one-round \(f\)-routing? More precisely, do there exist constants \(c>0\) and \(\varepsilon>0\) and a sequence
such that one uniform deterministic algorithm computes \(f_n(x,y)\) from \((n,x,y)\) in time polynomial in \(n\), and every routing protocol for the map in Eq. (1) with worst-case diamond-norm error at most \(\varepsilon\) has cost at least \(n^c\)?
In an \(f\)-routing protocol, Alice receives \(x\) and an unknown qubit \(Q\), Bob receives \(y\), and they may share an arbitrary state \(\rho_{LR}\) before the inputs arrive. After one simultaneous message in each direction, Alice must recover \(Q\) when \(f(x,y)=0\), and Bob must recover it when \(f(x,y)=1\). Message sizes and local operations are unrestricted. Measure only the shared state by
The target is a family in Eq. (1) for which every valid protocol satisfies \(E_{\mathrm{dim}}(\rho_{LR})\geq n^c\), with the cost defined in Eq. (2).
Source
Bogner explicitly asks for polynomial, or even superlogarithmic for an explicit total family, shared-resource lower bounds for \(f\)-routing [Bog26].
Progress
Reports do not certify correctness or automatically change the problem's status. Progress policy.
Every Boolean function admits an \(f\)-routing protocol with worst-case shared-resource cost at most
\begin{equation} 2^{O(\sqrt{n\log n})}. \tag{3} \end{equation}The construction underlying Eq. (3) also relates routing quantitatively to conditional disclosure of secrets [ABM+24].
Rank methods give nontrivial lower bounds for explicit functions when one routing case is required to be perfectly correct, but do not establish a polynomial lower bound on Eq. (2) in the two-sided bounded-error model [ACM24].
For the explicit inner-product function, the best robust result is
\begin{equation} f_n(x,y)=\bigoplus_{i=1}^n x_i y_i, \qquad d\log_2(2d)=\Omega(n), \qquad E_{\mathrm{dim}}\geq \log_2n-\log_2\log_2n-O(1), \tag{4} \end{equation}where \(d=\min\{\operatorname{rank}\rho_L, \operatorname{rank}\rho_R\}\) and the worst-case error is at most \(0.09\) [Bog26]. Equation (4) is logarithmic rather than polynomial in the cost measure of Eq. (2).
- Reported progress: PR #87.
Comment
Bogner explicitly leaves a polynomial lower bound on Eq. (2) open and notes that even a superlogarithmic bound for an explicit total family is unknown. The quantity \(E_{\mathrm{dim}}\) is a rank-based shared-resource cost for arbitrary mixed states, not an entanglement monotone.