Information Potential: A Variational Approach to Quantum Information Complexity
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 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 AND function, we further establish a nearly tight tradeoff for the asymmetric quantum communication complexity of Set Disjointness: (qA+1)(qB+1)=Ω(n), where qA and qB denote the total numbers of qubits sent by Alice and Bob, respectively.
Related
- Logic, Information, Holography: A Recursive Unification of Complexity Across Computational, Physical, and Geometric Substrates
- Bellman-sufficient Information Complexity
- Information Entropy and Dissipation Potential in Stochastic Nambu Nonequilibrium Thermodynamics
- The coupled spread of information and potential-driven motion in evacuating agent populations
- Information geometry of non-equilibrium quantum states: Mixed metric structures on an extended information manifold
BibTeX
@misc{yao2026information,
title = {{Information Potential: A Variational Approach to Quantum Information Complexity}},
author = {Penghui Yao and Yifan Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.39328},
eprint = {2609.39328},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39328},
}
RIS
TY - UNPB
TI - Information Potential: A Variational Approach to Quantum Information Complexity
AU - Penghui Yao
AU - Yifan Zhou
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2609.39328
UR - https://arxiv.org/abs/2609.39328
AB - 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 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 AND function, we further establish a nearly tight tradeoff for the asymmetric quantum communication complexity of Set 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.
ER -