Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.39328

Information Potential: A Variational Approach to Quantum Information Complexity

Penghui Yao, Yifan Zhou

quant-phcs.CCSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations• Revised Oct 3, 2026 (v2)
v1 · Sep 30, 2026v2 · Oct 3, 2026
arXivHTMLPDF

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.

Related papers

Quantum Information Complexity and Amortized Communication

Dave Touchette

We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate the properties of such quantities. These are the fully quantum generalizations of the analogous quantities for bipartite classical functions that have found many applications recently, in particular for proving communication complexity lower bounds. Our definition is strongly tied to the quantum state redistribution task. Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite channel on a given state. This generalizes a result of Braverman and Rao to quantum protocols, and even strengthens the classical result in a bounded round scenario. Also, this provides an analogue of the Schumacher source compression theorem for interactive quantum protocols, and answers a question raised by Braverman. We also discuss some potential applications to quantum communication complexity lower bounds by specializing our definition for classical functions and inputs. Building on work of Jain, Radhakrishnan and Sen, we provide new evidence suggesting that the bounded round quantum communication complexity of the disjointness function is Ω(n/M + M), for M-message protocols. This would match the best known upper bound.

arXiv:1404.3733•Apr 14, 2014•16 citations

Direct Sum Theorem for Bounded Round Quantum Communication Complexity

Dave Touchette

We prove a direct sum theorem for bounded round entanglement-assisted quantum communication complexity. To do so, we use the fully quantum definition for information cost and complexity that we recently introduced, and use both the fact that information is a lower bound on the communication, and the fact that a direct sum property holds for quantum information complexity. We then give a protocol for compressing a single copy of a protocol down to its quantum information cost, up to terms depending on the number of rounds and the allowed increase in error. Two important tools to derive this protocol are a smooth conditional min-entropy bound for a one-shot quantum state redistribution protocol, and the quantum substate theorem of Jain, Radhakrishnan and Sen (FOCS'02) to transform this bound into a von Neumann conditional entropy bound. This result further establishes the newly introduced notions of quantum information cost and complexity as the correct quantum generalisations of the classical ones in the standard communication complexity setting. Finding such a quantum generalization of information complexity was one of the open problem recently raised by Braverman (STOC'12).

arXiv:1409.4391•Sep 15, 2014•4 citations

Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness

Mark Braverman, Ankit Garg, Young Kun Ko +2 more

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with r rounds, we prove a lower bound of Omega(n/r) on the communication required for computing disjointness of input size n, which is optimal up to logarithmic factors. The previous best lower bound was Omega(n/r̂2) due to Jain, Radhakrishnan and Sen. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function f is at most 2 ̂O(QIC(f)), where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).

arXiv:1505.03110•Annual Symposium on Foundations of Computer Science•Oct 1, 2015•25 citations

Quantum Information Complexity

Dave Touchette

We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum tasks. These are the fully quantum generalizations of the analogous quantities for bipartite classical tasks that have found many applications recently, in particular for proving communication complexity lower bounds and direct sum theorems. Finding such a quantum generalization of information complexity was one of the open problems recently raised by Braverman (STOC'12).

ACM Symposium on Theory of Computing (STOC)•Jun 3, 2015•41 citations

The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting

Mathieu Laurière, Dave Touchette

In the context of two-party interactive quantum communication protocols, we study a recently defined notion of quantum information cost (QIC), which possesses most of the important properties of its classical analogue. Although this definition has the advantage to be valid for fully quantum inputs and tasks, its interpretation for classical tasks remained rather obscure. Also, the link between this new notion and other notions of information cost for quantum protocols that had previously appeared in the literature was not clear, if existent at all. We settle both these issues: for quantum communication with classical inputs, we provide an alternate characterization of QIC in terms of information about the input registers, avoiding any reference to the notion of a purification of the classical input state. We provide an exact operational interpretation of this alternative characterization as the sum of the cost of transmitting information about the classical inputs and the cost of forgetting information about these inputs. To obtain this characterization, we prove a general lemma, the Information Flow Lemma, assessing exactly the transfer of information in general interactive quantum processes. Furthermore, we clarify the link between QIC and IC of classical protocols by simulating quantumly classical protocols. Finally, we apply these concepts to argue that any quantum protocol that does not forget information solves Disjointness on n-bits in Omega (n) communication, completely losing the quadratic quantum speedup. This provides a specific sense in which forgetting information is a necessary feature of interactive quantum protocols. We also apply these concepts to prove that QIC at zero-error is exactly n for the Inner Product function, and n (1 - o(1)) for a random Boolean function on n+n bits.

arXiv:1701.02062•Leibniz international proceedings in informatics•Jan 1, 2017•5 citations

Separating Quantum Communication and Approximate Rank

Anurag Anshu, Shalev Ben-David, Ankit Garg +3 more

One of the best lower bound methods for the quantum communication complexity of a function H (with or without shared entanglement) is the logarithm of the approximate rank of the communication matrix of H. This measure is essentially equivalent to the approximate gamma-2 norm and generalized discrepancy, and subsumes several other lower bounds. All known lower bounds on quantum communication complexity in the general unbounded-round model can be shown via the logarithm of approximate rank, and it was an open problem to give any separation at all between quantum communication complexity and the logarithm of the approximate rank. In this work we provide the first such separation: We exhibit a total function H with quantum communication complexity almost quadratically larger than the logarithm of its approximate rank. We construct H using the communication lookup function framework of Anshu et al. (FOCS 2016) based on the cheat sheet framework of Aaronson et al. (STOC 2016). From a starting function F, this framework defines a new function H=F_G. Our main technical result is a lower bound on the quantum communication complexity of F_G in terms of the discrepancy of F, which we do via quantum information theoretic arguments. We show the upper bound on the approximate rank of F_G by relating it to the Boolean circuit size of the starting function F.

arXiv:1611.05754•Leibniz international proceedings in informatics•Nov 17, 2016•2 citations
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)Ω(1/r)Ω(1/r) lower bound on the QIC of the two-bit AND\mathsf{AND}AND function as well as an optimal Ω(n/r)Ω(n/r)Ω(n/r) lower bound on the quantum communication complexity of rrr-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\mathsf{AND}AND function, we further establish a nearly tight tradeoff for the asymmetric quantum communication complexity of SetDisjointness\mathsf{Set} \mathsf{Disjointness}SetDisjointness: (qA+1)(qB+1)=Ω(n)(q_A+1)(q_B+1)=Ω(n)(qA​+1)(qB​+1)=Ω(n), where qAq_AqA​ and qBq_BqB​ denote the total numbers of qubits sent by Alice and Bob, respectively.
We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate the properties of such quantities. These are the fully quantum generalizations of the analogous quantities for bipartite classical functions that have found many applications recently, in particular for proving communication complexity lower bounds. Our definition is strongly tied to the quantum state redistribution task. Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite channel on a given state. This generalizes a result of Braverman and Rao to quantum protocols, and even strengthens the classical result in a bounded round scenario. Also, this provides an analogue of the Schumacher source compression theorem for interactive quantum protocols, and answers a question raised by Braverman. We also discuss some potential applications to quantum communication complexity lower bounds by specializing our definition for classical functions and inputs. Building on work of Jain, Radhakrishnan and Sen, we provide new evidence suggesting that the bounded round quantum communication complexity of the disjointness function is Ω(n/M + M), for M-message protocols. This would match the best known upper bound.
We prove a direct sum theorem for bounded round entanglement-assisted quantum communication complexity. To do so, we use the fully quantum definition for information cost and complexity that we recently introduced, and use both the fact that information is a lower bound on the communication, and the fact that a direct sum property holds for quantum information complexity. We then give a protocol for compressing a single copy of a protocol down to its quantum information cost, up to terms depending on the number of rounds and the allowed increase in error. Two important tools to derive this protocol are a smooth conditional min-entropy bound for a one-shot quantum state redistribution protocol, and the quantum substate theorem of Jain, Radhakrishnan and Sen (FOCS'02) to transform this bound into a von Neumann conditional entropy bound. This result further establishes the newly introduced notions of quantum information cost and complexity as the correct quantum generalisations of the classical ones in the standard communication complexity setting. Finding such a quantum generalization of information complexity was one of the open problem recently raised by Braverman (STOC'12).
We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with r rounds, we prove a lower bound of Omega(n/r) on the communication required for computing disjointness of input size n, which is optimal up to logarithmic factors. The previous best lower bound was Omega(n/r̂2) due to Jain, Radhakrishnan and Sen. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function f is at most 2 ̂O(QIC(f)), where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).
We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum tasks. These are the fully quantum generalizations of the analogous quantities for bipartite classical tasks that have found many applications recently, in particular for proving communication complexity lower bounds and direct sum theorems. Finding such a quantum generalization of information complexity was one of the open problems recently raised by Braverman (STOC'12).
In the context of two-party interactive quantum communication protocols, we study a recently defined notion of quantum information cost (QIC), which possesses most of the important properties of its classical analogue. Although this definition has the advantage to be valid for fully quantum inputs and tasks, its interpretation for classical tasks remained rather obscure. Also, the link between this new notion and other notions of information cost for quantum protocols that had previously appeared in the literature was not clear, if existent at all. We settle both these issues: for quantum communication with classical inputs, we provide an alternate characterization of QIC in terms of information about the input registers, avoiding any reference to the notion of a purification of the classical input state. We provide an exact operational interpretation of this alternative characterization as the sum of the cost of transmitting information about the classical inputs and the cost of forgetting information about these inputs. To obtain this characterization, we prove a general lemma, the Information Flow Lemma, assessing exactly the transfer of information in general interactive quantum processes. Furthermore, we clarify the link between QIC and IC of classical protocols by simulating quantumly classical protocols. Finally, we apply these concepts to argue that any quantum protocol that does not forget information solves Disjointness on n-bits in Omega (n) communication, completely losing the quadratic quantum speedup. This provides a specific sense in which forgetting information is a necessary feature of interactive quantum protocols. We also apply these concepts to prove that QIC at zero-error is exactly n for the Inner Product function, and n (1 - o(1)) for a random Boolean function on n+n bits.
One of the best lower bound methods for the quantum communication complexity of a function H (with or without shared entanglement) is the logarithm of the approximate rank of the communication matrix of H. This measure is essentially equivalent to the approximate gamma-2 norm and generalized discrepancy, and subsumes several other lower bounds. All known lower bounds on quantum communication complexity in the general unbounded-round model can be shown via the logarithm of approximate rank, and it was an open problem to give any separation at all between quantum communication complexity and the logarithm of the approximate rank. In this work we provide the first such separation: We exhibit a total function H with quantum communication complexity almost quadratically larger than the logarithm of its approximate rank. We construct H using the communication lookup function framework of Anshu et al. (FOCS 2016) based on the cheat sheet framework of Aaronson et al. (STOC 2016). From a starting function F, this framework defines a new function H=F_G. Our main technical result is a lower bound on the quantum communication complexity of F_G in terms of the discrepancy of F, which we do via quantum information theoretic arguments. We show the upper bound on the approximate rank of F_G by relating it to the Boolean circuit size of the starting function F.