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:0809.2093

An approximation algorithm for approximation rank

Troy Lee, Adi Shraibman

Published Sep 11, 2008• 1 citation
arXivHTMLPDF

Abstract

One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.

DOI
10.48550/arxiv.0809.2093

Related papers

An Approximation Algorithm for Approximation Rank

Troy Lee, Adi Shraibman

One of the strongest techniques available for showing lower bounds on bounded-error communication complexity is the logarithm of the approximation rank of the communication matrix-the minimum rank of a matrix which is close to the communication matrix in lscrinfinnorm. Krause showed that the logarithm of approximation rank is a lower bound in the randomized case, and later Buhrman and de Wolf showed it could also be used for quantum communication complexity. As a lower bound technique, approximation rank has two main drawbacks: it is difficult to compute, and it is not known to lower bound the model of quantum communication complexity with entanglement. Linial and Shraibman recently introduced a quantity, called gamma2alpha, to quantum communication complexity, showing that it can be used to lower bound communication in the model with shared entanglement. Here alpha is a measure of approximation which is related to the allowable error probability of the protocol. This quantity can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rkalpha. We show that in fact log gamma2alpha(A) and log rkalpha(A) agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximation rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.

IEEE Conference on Computational Complexity (CCC)•Jul 1, 2009•31 citations

Approximation norms and duality for communication complexity lower bounds

Troy Lee, Adi Shraibman

Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound quantity phrased as a maximization problem, which can be more convenient to work with in showing lower bounds. We discuss two applications of this approach. 1. The approximation rank of a matrix A is the minimum rank of a matrix close to A in ell_infty norm. The logarithm of approximation rank lower bounds quantum communication complexity and is one of the most powerful techniques available, albeit difficult to compute in practice. We show that an approximation norm known as gamma_2 is polynomially related to approximation rank. This results in a polynomial time algorithm to approximate approximation rank, and also shows that the logarithm of approximation rank lower bounds quantum communication complexity even with entanglement which was previously not known. 2. By means of an approximation norm which lower bounds multiparty number-on-the-forehead complexity, we show non-trivial lower bounds on the complexity of the disjointness function for up to c log log n players, c <1.

Dagstuhl Seminar Proceedings•Jan 1, 2008•0 citations

Communication complexity lower bounds by polynomials

Harry Buhrman, Ronald de Wolf

The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the "log rank" lower bound extends to the strongest variant of quantum communication complexity (qubit communication+unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.

arXiv:cs/9910010•IEEE Conference on Computational Complexity (CCC)•Nov 13, 2002•127 citations

Quantum Log-Approximate-Rank Conjecture is Also False

Anurag Anshu, Naresh Goud Boddu, Dave Touchette

In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function f, hence refuting the log approximate rank conjecture of Lee and Shraibman [2009]. We provide an alternate proof of their randomized communication complexity lower bound using the information complexity approach. Using the intuition developed there, we derive a polynomially-related quantum communication complexity lower bound using the quantum information complexity approach, thus providing an exponential separation between the log approximate rank and quantum communication complexity of f. Previously, the best known separation between these two measures was (almost) quadratic, due to Anshu, Ben-David, Garg, Jain, Kothari and Lee [CCC, 2017]. This settles one of the main question left open by Chattopadhyay, Mande and Sherif, and refutes the quantum log approximate rank conjecture of Lee and Shraibman [2009]. Along the way, we develop a Shearer-type protocol embedding for product input distributions that might be of independent interest.

arXiv:1811.10525•Annual Symposium on Foundations of Computer Science•Nov 1, 2019•12 citations

Separation of the Factorization Norm and Randomized Communication Complexity

Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini +1 more

In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate γ₂-factorization norm is a lower bound for these parameters and asked whether a stronger lower bound that replaces approximate γ₂ norm with the γ₂ norm holds. We answer the question of Linial and Shraibman in the negative by exhibiting a 2ⁿ×2ⁿ Boolean matrix with γ₂ norm 2^Ω(n) and randomized communication complexity O(log n). As a corollary, we recover the recent result of Chattopadhyay, Lovett, and Vinyals (CCC '19) that deterministic protocols with access to an Equality oracle are exponentially weaker than (one-sided error) randomized protocols. In fact, as a stronger consequence, our result implies an exponential separation between the power of unambiguous nondeterministic protocols with access to Equality oracle and (one-sided error) randomized protocols, which answers a question of Pitassi, Shirley, and Shraibman (ITSC '23). Our result also implies a conjecture of Sherif (Ph.D. thesis) that the γ₂ norm of the Integer Inner Product function (IIP) in dimension 3 or higher is exponential in its input size.

Leibniz international proceedings in informatics•Jan 1, 2023•2 citations

Classical lower bounds from quantum upper bounds

Shalev Ben-David, Adam Bouland, Ankit Garg +1 more

We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt{n}) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma_2 norm) of F: X x Y -> {0,1} grows by a factor of Omega~(sqrt{n}) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrt{n}) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.

arXiv:1807.06256•Jul 17, 2018•2 citations
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)andlogrkalpha(A) and log rk_{alpha}(A)andlogrkalpha​(A) agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
One of the strongest techniques available for showing lower bounds on bounded-error communication complexity is the logarithm of the approximation rank of the communication matrix-the minimum rank of a matrix which is close to the communication matrix in lscrinfinnorm. Krause showed that the logarithm of approximation rank is a lower bound in the randomized case, and later Buhrman and de Wolf showed it could also be used for quantum communication complexity. As a lower bound technique, approximation rank has two main drawbacks: it is difficult to compute, and it is not known to lower bound the model of quantum communication complexity with entanglement. Linial and Shraibman recently introduced a quantity, called gamma2alpha, to quantum communication complexity, showing that it can be used to lower bound communication in the model with shared entanglement. Here alpha is a measure of approximation which is related to the allowable error probability of the protocol. This quantity can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rkalpha. We show that in fact log gamma2alpha(A) and log rkalpha(A) agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximation rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound quantity phrased as a maximization problem, which can be more convenient to work with in showing lower bounds. We discuss two applications of this approach. 1. The approximation rank of a matrix A is the minimum rank of a matrix close to A in ell_infty norm. The logarithm of approximation rank lower bounds quantum communication complexity and is one of the most powerful techniques available, albeit difficult to compute in practice. We show that an approximation norm known as gamma_2 is polynomially related to approximation rank. This results in a polynomial time algorithm to approximate approximation rank, and also shows that the logarithm of approximation rank lower bounds quantum communication complexity even with entanglement which was previously not known. 2. By means of an approximation norm which lower bounds multiparty number-on-the-forehead complexity, we show non-trivial lower bounds on the complexity of the disjointness function for up to c log log n players, c <1.
The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the "log rank" lower bound extends to the strongest variant of quantum communication complexity (qubit communication+unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.
In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function f, hence refuting the log approximate rank conjecture of Lee and Shraibman [2009]. We provide an alternate proof of their randomized communication complexity lower bound using the information complexity approach. Using the intuition developed there, we derive a polynomially-related quantum communication complexity lower bound using the quantum information complexity approach, thus providing an exponential separation between the log approximate rank and quantum communication complexity of f. Previously, the best known separation between these two measures was (almost) quadratic, due to Anshu, Ben-David, Garg, Jain, Kothari and Lee [CCC, 2017]. This settles one of the main question left open by Chattopadhyay, Mande and Sherif, and refutes the quantum log approximate rank conjecture of Lee and Shraibman [2009]. Along the way, we develop a Shearer-type protocol embedding for product input distributions that might be of independent interest.
In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate γ₂-factorization norm is a lower bound for these parameters and asked whether a stronger lower bound that replaces approximate γ₂ norm with the γ₂ norm holds. We answer the question of Linial and Shraibman in the negative by exhibiting a 2ⁿ×2ⁿ Boolean matrix with γ₂ norm 2^Ω(n) and randomized communication complexity O(log n). As a corollary, we recover the recent result of Chattopadhyay, Lovett, and Vinyals (CCC '19) that deterministic protocols with access to an Equality oracle are exponentially weaker than (one-sided error) randomized protocols. In fact, as a stronger consequence, our result implies an exponential separation between the power of unambiguous nondeterministic protocols with access to Equality oracle and (one-sided error) randomized protocols, which answers a question of Pitassi, Shirley, and Shraibman (ITSC '23). Our result also implies a conjecture of Sherif (Ph.D. thesis) that the γ₂ norm of the Integer Inner Product function (IIP) in dimension 3 or higher is exponential in its input size.
We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt{n}) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma_2 norm) of F: X x Y -> {0,1} grows by a factor of Omega~(sqrt{n}) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrt{n}) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.