aiqbench analysis
This paper establishes a robust logarithmic lower bound on the shared-resource cost required for one-round $f$-routing protocols in quantum communication scenarios. By leveraging sign-rank arguments applied to matrices derived from routing correctness conditions, it demonstrates that the resource dimension must scale at least as $\log n - \log\log n$. This result advances fundamental limits on how much prior entanglement or shared randomness is necessary when parties exchange messages under specific error tolerances in quantum networks.
Robust logarithmic lower bound on shared-resource cost for $f$-routing
arXiv:2608.05775v1 Announce Type: new Abstract: In one-round $f$-routing, Alice receives an $n$-bit string and an unknown qubit, while Bob receives another $n$-bit string. They exchange one simultaneous message each, and the value of $f$ determines which party must recover the qubit. Message lengths, local systems, and local operations are unrestricted. We charge only $E_{\dim}(\rho_{LR})=\log_2\min\{\operatorname{rank}\rho_L,\operatorname{rank}\rho_R\}$, the logarithm of the smaller marginal support dimension of the shared state prepared before the inputs arrive. The state may be arbitrary and mixed. For the inner product modulo $2$, we prove that every protocol with worst-case error at most $0.09$ in both routing cases, measured in the full, unhalved diamond norm, satisfies $d\log_2(2d)=\Omega(n)$ for $d=\min\{\operatorname{rank}\rho_L,\operatorname{rank}\rho_R\}$. Thus $d=\Omega(n/\log n)$ and $E_{\dim}(\rho_{LR})\ge\log_2 n-\log_2\log_2 n-O(1)$. The closest earlier growing Schmidt-rank lower bound for an explicit routing function assumes zero error in one routing case. Our proof converts correctness into a matrix whose entries have a constant gap between the two routing cases. It approximates this matrix by one whose rank depends on $d$, but not on the dimensions of messages or local systems. A sign-rank lower bound for the matrix of the inner product modulo $2$ completes the argument. A lower bound polynomial in $n$ on $E_{\dim}$ remains open.
Abstract:In one-round $f$-routing, Alice receives an $n$-bit string and an unknown qubit, while Bob receives another $n$-bit string. They exchange one simultaneous message each, and the value of $f$ determines which party must recover the qubit. Message lengths, local systems, and local operations are unrestricted. We charge only $E_{\dim}(\rho_{LR})=\log_2\min\{\operatorname{rank}\rho_L,\operatorname{rank}\rho_R\}$, the logarithm of the smaller marginal support dimension of the shared state prepared before the inputs arrive. The state may be arbitrary and mixed. For the inner product modulo $2$, we prove that every protocol with worst-case error at most $0.09$ in both routing cases, measured in the full, unhalved diamond norm, satisfies $d\log_2(2d)=\Omega(n)$ for $d=\min\{\operatorname{rank}\rho_L,\operatorname{rank}\rho_R\}$. Thus $d=\Omega(n/\log n)$ and $E_{\dim}(\rho_{LR})\ge\log_2 n-\log_2\log_2 n-O(1)$. The closest earlier growing Schmidt-rank lower bound for an explicit routing function assumes zero error in one routing case. Our proof converts correctness into a matrix whose entries have a constant gap between the two routing cases. It approximates this matrix by one whose rank depends on $d$, but not on the dimensions of messages or local systems. A sign-rank lower bound for the matrix of the inner product modulo $2$ completes the argument. A lower bound polynomial in $n$ on $E_{\dim}$ remains open.
arXiv:2608.05775 [quant-ph]
(or arXiv:2608.05775v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2608.05775 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 287 words
