Quantum information potential method sharpens communication lower bounds
Information Potential: A Variational Approach to Quantum Information Complexity
Computational Complexity
Summary
Understanding how much communication quantum computers need to work together is tricky because the math is complicated. The authors introduce a new way to analyze this using something called information potential, which simplifies the problem to something like a quadratic form. This makes it easier to find limits on how efficient quantum communication protocols can be. They use this method to solve a long-standing question about quantum communication needed to check shared data overlaps. They also discover new trade-offs in how much each party must communicate.
What this means in practice
- •For quantum communication engineers: Design tighter protocols by knowing the minimal quantum communication needed for interactive tasks like Set-Disjointness verification over multiple rounds.
- •For quantum cryptography developers: Use precise lower bounds on quantum communication to improve security guarantees in interactive quantum protocols by understanding communication costs.
A theory result. No direct application yet.
Authors
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.