arXiv:2609.39328
Information Potential: A Variational Approach to Quantum Information Complexity
Penghui Yao, Yifan Zhou
Abstract
Quantum information complexity (QIC), introduced by Touchette [Touchette, STOC 2015], has been shown to be one of the most powerful methods for proving quantum communication complexity and has also been shown to be equal to amortized quantum communication complexity. Unfortunately, QIC is generally hard to analyze because it is a sum of quantum conditional mutual information terms, which are difficult to estimate. In this work, we introduce a new variational approach, the information potential, for analyzing QIC and proving quantum communication lower bounds inspired by the resolvent representation for quantum relative entropy. This approach connects the QIC of individual messages to a quadratic form, making it more amenable and thus enables us to bound the cumulative positive increments of the potential throughout an interactive quantum protocol by its QIC. Lower bounds on the growth of the potential therefore translate into lower bounds on both QIC and quantum communication complexity. As an application, we give an optimal $Ω(1/r)$ lower bound on the QIC of the two-bit $\mathsf{AND}$ function as well as an optimal $Ω(n/r)$ lower bound on the quantum communication complexity of $r$-round Set-Disjointness, answering an open problem in~[Braverman, Garg, Ko, Mao, Touchette FOCS 2015]. Moreover, we further prove a direct-sum theorem for bounded-round quantum communication complexity of Set Disjointness. With the tight bound on the QIC of $\mathsf{AND}$ function, we further establish a nearly tight tradeoff for the asymmetric quantum communication complexity of $\mathsf{Set} \mathsf{Disjointness}$: $(q_A+1)(q_B+1)=Ω(n)$, where $q_A$ and $q_B$ denote the total numbers of qubits sent by Alice and Bob, respectively.
AI Summary
Quantum information complexity (QIC) characterizes amortized quantum communication, but its conditional-mutual-information terms are difficult to estimate directly. This paper introduces an information potential for analyzing information flow in interactive protocols and applies it to AND and Set Disjointness. The potential integrates resolvent divergences over a fixed parameter interval. A quadratic variational representation expresses each partial-trace data-processing gap as a weighted squared distance between optimizers. Potential increments are bounded by $\frac{9}{2}$ times the corresponding conditional mutual information, so QIC controls cumulative increases. A stability estimate bounds changes in the square root of these gaps by purification-path length. For two-bit AND, under the uniform distribution on $00,01,10$ and with worst-case error at most $1/3$, the paper proves the tight $r$-message bound $\mathrm{QIC}=\Theta(1/r)$, removing the previous $\log^8 r$ loss. The proof adds probability $p$ to input $11$: stability costs $O(rp)$, while correctness forces potential growth of order $\sqrt p$; choosing $p=\Theta(r^{-2})$ yields the bound. Consequences include $\Omega(n/r)$ communication for $r$-message Set Disjointness, an information-theoretic route to its unrestricted $\Omega(\sqrt n)$ bound, and $\Omega(kn/r)$ communication for $k$ instances with per-instance correctness. The asymmetric tradeoff is $(q_A+1)(q_B+1)=\Omega(n)$, accompanied by upper bounds matching up to logarithmic factors. The results allow arbitrary prior entanglement and finite-dimensional workspaces. Applications of the potential beyond AND and these reductions remain prospective; the direct-sum result does not assert a strong direct-product theorem.
Discussion with the model helped inspire the concept of information potential and assisted us in proving the results in this paper.
Error found: The introductory Set Disjointness theorem incorrectly includes an Ω(r) communication lower bound for protocols using at most r messages, although a fixed one-message protocol remains admissible as r grows. The local-alignment lemma uses a Holevo–fidelity inequality incompatible with the paper's natural-logarithm convention, invalidating its stated numerical constants but admitting a constant-factor repair.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.