Finding the singularity of a matrix is a basic problem in linear algebra. Chu and Schnitger [SC95] first considered this problem in the communication complexity model, in which Alice holds the first half of the matrix and Bob holds the other half. They proved that the deterministic communication complexity is Omega(n^2 log p) for an n by n matrix over the finite field F_p. Then, Clarkson and Woodruff [CW09] introduced the singularity problem to the streaming model. They proposed a randomized one pass streaming algorithm that uses O(k^2 log n) space to decide if the rank of a matrix is k, and proved an Omega(k^2) lower bound for randomized one-way protocols in the communication complexity model. We prove that the randomized/quantum communication complexity of the singularity problem over F_p is Omega(n^2 log p), which implies the same space lower bound for randomized streaming algorithms, even for a constant number of passes. The proof uses the framework by Lee and Shraibman [LS09], but we choose Fourier coefficients as the witness for the dual approximate norm of the communication matrix. Moreover, we use Fourier analysis to show the same randomized/quantum lower bound when deciding if the determinant of a non-singular matrix is a or b for non-zero a and b.Finding the singularity of a matrix is a basic problem in linear algebra. Chu and Schnitger [SC95] first considered this problem in the communication complexity model, in which Alice holds the first half of the matrix and Bob holds the other half. They proved that the deterministic communication complexity is Omega(n^2 log p) for an n by n matrix over the finite field F_p. Then, Clarkson and Woodruff [CW09] introduced the singularity problem to the streaming model. They proposed a randomized one pass streaming algorithm that uses O(k^2 log n) space to decide if the rank of a matrix is k, and proved an Omega(k^2) lower bound for randomized one-way protocols in the communication complexity model. We prove that the randomized/quantum communication complexity of the singularity problem over F_p is Omega(n^2 log p), which implies the same space lower bound for randomized streaming algorithms, even for a constant number of passes. The proof uses the framework by Lee and Shraibman [LS09], but we choose Fourier coefficients as the witness for the dual approximate norm of the communication matrix. Moreover, we use Fourier analysis to show the same randomized/quantum lower bound when deciding if the determinant of a non-singular matrix is a or b for non-zero a and b.

Leibniz international proceedings in informaticsJan 1, 201212 citations

Quantum Computation and Quantum Communication

Mladen Pavičić

Springer eBooksJan 1, 2006206 citations

Nonlinear Matrix Dynamic Quantum State Generation

Jincheng Zhang

This paper investigates the generation of complex quantum states using a dynamic matrix approach. Traditional matrix operations are often static, limiting the potential for efficient computation and communication in the quantum realm. This work proposes a novel algorithm that leverages the inherent adaptability of matrices to generate novel quantum states, specifically tailored for applications in quantum computing and quantum communication. The core mechanism centers around the design of a 'dynamic matrix' generation algorithm, aiming to surpass the limitations of static matrix operations by employing self-adaptive matrix transformations. The paper presents a detailed explanation of the algorithm's design, its operational principles, and preliminary results demonstrating its effectiveness in generating complex quantum states. The research explores how this dynamic matrix approach can enhance the capabilities of quantum algorithms and protocols.This paper investigates the generation of complex quantum states using a dynamic matrix approach. Traditional matrix operations are often static, limiting the potential for efficient computation and communication in the quantum realm. This work proposes a novel algorithm that leverages the inherent adaptability of matrices to generate novel quantum states, specifically tailored for applications in quantum computing and quantum communication. The core mechanism centers around the design of a 'dynamic matrix' generation algorithm, aiming to surpass the limitations of static matrix operations by employing self-adaptive matrix transformations. The paper presents a detailed explanation of the algorithm's design, its operational principles, and preliminary results demonstrating its effectiveness in generating complex quantum states. The research explores how this dynamic matrix approach can enhance the capabilities of quantum algorithms and protocols.

Sep 2, 20260 citations

The Communication Complexity of Approximating Matrix Rank

Alexander A. Sherstov, Andrey A. Storozhenko

We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where $0\leqslant r < R\leqslant n$ are given integers and Alice and Bob need to determine whether their respective matrices $A, B\in \mathbb{F}^{n\times n}$ satisfy rk $(A+B)=r$ versus rk $(A+B)=R$ . We show that this problem has commu-nication cost $\Omega(r^{2}\log\vert \mathbb{F}\vert)$ , which is optimal. Our lower bound holds even for quantum protocols and even for error probability $\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})$ , which too is optimal because this problem has a two-bit classical protocol with error $\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})$ . Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integers $r$ and $R$ , with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspace $S$ , Bob has a subspace $T$ ) and they need to approximate the dimension of the subspace $S+T$ generated by $S$ and $T$ (equivalently, approximate the dimension of $S\cap T$ ). As an application, we obtain an $\Omega(n^{2}\log\vert \mathbb{F}\vert)/k$ memory lower bound for any streaming algorithm with $k$ passes that approximates the rank of an input matrix $M\in \mathbb{F}^{n\times n}$ within a factor of $\sqrt{2}-\delta$ , for any $\delta > 0$ . Our result is an exponential improvement in $k$ over previous work.We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where$0\leqslant r < R\leqslant n$are given integers and Alice and Bob need to determine whether their respective matrices$A, B\in \mathbb{F}^{n\times n}$satisfy rk$(A+B)=r$versus rk$(A+B)=R$. We show that this problem has commu-nication cost$\Omega(r^{2}\log\vert \mathbb{F}\vert)$, which is optimal. Our lower bound holds even for quantum protocols and even for error probability$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})$, which too is optimal because this problem has a two-bit classical protocol with error$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})$. Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integers$r$and$R$, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspace$S$, Bob has a subspace$T$) and they need to approximate the dimension of the subspace$S+T$generated by$S$and$T$(equivalently, approximate the dimension of$S\cap T$). As an application, we obtain an$\Omega(n^{2}\log\vert \mathbb{F}\vert)/k$memory lower bound for any streaming algorithm with$k$passes that approximates the rank of an input matrix$M\in \mathbb{F}^{n\times n}$within a factor of$\sqrt{2}-\delta$, for any$\delta > 0$. Our result is an exponential improvement in$k$over previous work.

arXiv:2410.20094Annual Symposium on Foundations of Computer ScienceOct 27, 20241 citation

Quantum communication and information processing

Travis Roland Beals

Jan 1, 20084 citations

We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where

0\leqslant r < R\leqslant n

are given integers and Alice and Bob need to determine whether their respective matrices

A, B\in \mathbb{F}^{n\times n}

satisfy rk

(A+B)=r

versus rk

(A+B)=R

. We show that this problem has commu-nication cost

\Omega(r^{2}\log\vert \mathbb{F}\vert)

, which is optimal. Our lower bound holds even for quantum protocols and even for error probability

\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})

, which too is optimal because this problem has a two-bit classical protocol with error

\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})

. Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integers

r

and

R

, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspace

S

, Bob has a subspace

T

) and they need to approximate the dimension of the subspace

S+T

generated by

S

and

T

(equivalently, approximate the dimension of

S\cap T

). As an application, we obtain an

\Omega(n^{2}\log\vert \mathbb{F}\vert)/k

memory lower bound for any streaming algorithm with

k

passes that approximates the rank of an input matrix

M\in \mathbb{F}^{n\times n}

within a factor of

\sqrt{2}-\delta

, for any

\delta > 0

. Our result is an exponential improvement in

k

over previous work.