Information Potential: A Variational Approach to Quantum Information Complexity

AI summary

Overview

Research area: Quantum information theory, specifically quantum communication complexity and quantum information complexity (QIC).
Technical level: Advanced.
Scope: The paper introduces a variational tool called the information potential for analyzing QIC and uses it to prove tight bounded-round lower bounds for the AND function and Set Disjointness, along with direct-sum and asymmetric communication tradeoffs. The paper is theoretical and reports no experimental data.

What This Paper Is About

QIC measures the information revealed by an interactive quantum protocol and is known to equal amortized quantum communication complexity, making it a powerful lower-bound method. QIC is difficult to analyze because it is a sum of quantum conditional mutual information terms, especially when the conditioning register contains quantum side information. The paper develops a new variational approach, the information potential, to obtain a direct and tight analysis of the bounded-round QIC of AND and to lift that result to quantum communication lower bounds for Set Disjointness.

Key Contributions

1. Information potential framework. The authors define an information potential from Petz’s resolvent representation of quantum relative entropy, give a concave quadratic variational representation for each integrand, prove monotonicity under partial trace, and relate potential increments to quantum conditional mutual information and QIC.

2. Tight QIC for AND. They prove that every quantum protocol computing AND with at most (r) messages and worst-case error at most (1/3) has QIC at least (\Omega(1/r)) under the uniform distribution (\mu_0) on ({(0,0),(0,1),(1,0)}). Combined with an upper bound of (O(1/r)), this gives the tight bound (\Theta(1/r)) for the (r)-message QIC of AND.

3. Set Disjointness lower bounds and direct sum. They prove that every (r)-message quantum protocol for (\mathrm{DISJ}_n) with worst-case error at most (1/3) communicates at least (\Omega(\max{n/r,r})) qubits, which implies the tight (\Omega(\sqrt{n})) bound for unrestricted interaction. They also prove a direct-sum theorem: computing (k) instances of (\mathrm{DISJ}_n) with at most (r) messages in total requires (\Omega(kn/r)) qubits, provided each individual answer is correct with probability at least (2/3) on every joint input.

4. Asymmetric communication tradeoff. For protocols computing (\mathrm{DISJ}_n) with worst-case error at most (1/3), they prove ((q_A+1)(q_B+1)\geq \Omega(n)), where (q_A) and (q_B) are the total numbers of qubits sent by Alice and Bob. This holds without a bound on the number of messages and is optimal up to a logarithmic factor.

Main Findings

• Tight (r)-message QIC for AND: For every integer (r\geq 1), every quantum protocol computing AND with at most (r) messages and worst-case error at most (1/3) satisfies (\operatorname{QIC}(\Pi,\mu_0)\geq \Omega(1/r)). The bound holds with arbitrary prior entanglement and finite-dimensional private workspaces. The matching upper bound is (O(1/r)), so the (r)-message QIC of AND under (\mu_0) is (\Theta(1/r)).

• Optimal round tradeoff for Set Disjointness: Every quantum protocol computing (\mathrm{DISJ}_n) with at most (r) messages and worst-case error at most (1/3) communicates at least (\Omega(\max{n/r,r})) qubits. This immediately implies the tight (\Omega(\sqrt{n})) lower bound for unrestricted interaction.

• First direct information-theoretic proof: To the authors’ knowledge, this gives the first direct information-theoretic proof of the tight quantum communication lower bound for Set Disjointness, without invoking an existing communication lower bound for Set Disjointness.

• Improvement over prior bounds: The earlier (r)-round QIC lower bound for AND in Braverman, Garg, Ko, Mao, and Touchette was (\Omega(1/(r\log^8 r))). The earlier (r)-round quantum communication lower bound for Set Disjointness was (\Omega(n/(r\log^8 r))). The earlier Jain–Radhakrishnan–Sen bound was (\Omega(n/r^2)) for (r)-round protocols, yielding (\Omega(n^{1/3})) without a round restriction.

• Direct sum for bounded-round Set Disjointness: For all integers (n,k,r\geq 1), every quantum protocol computing (k) instances of (\mathrm{DISJ}_n) with at most (r) messages in total communicates at least (\Omega(kn/r)) qubits, provided each individual answer is correct with probability at least (2/3) on every joint input.

• Asymmetric tradeoff: Every quantum protocol computing (\mathrm{DISJ}_n) with worst-case error at most (1/3) satisfies ((q_A+1)(q_B+1)\geq \Omega(n)), with no bound on the number of messages. The tradeoff is optimal up to a logarithmic factor.

• Potential controls information: For a fixed positive definite reference state (\alpha_A), the potential satisfies [ 0\leq V(\rho_{ABC},A,BC)-V(\rho_{AB},A,B)\leq \frac{9}{2}I(A:C\mid B)_\rho. ] This preserves a direct connection to conditional mutual information without requiring the authors to estimate conditional mutual information directly.

Methodology in Plain English

The authors start from an integral representation of quantum relative entropy called the resolvent representation. They define the information potential by integrating the corresponding resolvent divergence over the fixed interval ([1,2]), rather than over ([0,\

Authors’ 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.