Quantum-inspired classical algorithms provide us with a new way to understand the computational power of quantum computers for practically-relevant problems, especially in machine learning. In the past several years, numerous efficient algorithms for various tasks have been found, while an analysis of lower bounds is still missing.
Using communication complexity, in this work we propose the first method to study lower bounds for these tasks. We mainly focus on lower bounds for solving linear regressions, supervised clustering, principal component analysis, recommendation systems, and Hamiltonian simulations. More precisely, we show that for linear regressions, in the row-sparse case, the lower bound is quadratic in the Frobenius norm of the underlying matrix, which is tight. In the dense case, with an extra assumption on the accuracy we obtain that the lower bound is quartic in the Frobenius norm, which matches the upper bound.
For supervised clustering, we obtain a tight lower bound that is quartic in the Frobenius norm. For the other three tasks, we obtain a lower bound that is quadratic in the Frobenius norm, and the known upper bound is quartic in the Frobenius norm. Through this research, we find that large quantum speedup can exist for sparse, high-rank, well-conditioned matrix-related problems.

Finally, we extend our method to study lower bounds analysis of quantum query algorithms for matrix-related problems. Some applications are given.

§ INTRODUCTION

Initiated by Tang in the seminal work [25], quantum-inspired classical algorithms now provide a new way for us to understand the power and limitations of quantum computers for some practically relevant problems, especially in machine learning [6].
These algorithms are very different from standard classical algorithms that usually output vector solutions. Instead, they are more comparable to quantum algorithms and can be used as a tool to study quantum advantage.

Roughly, in a quantum-inspired classical algorithm for a matrix-relevant problem, such as a linear regression problem $\arg\min_{\x} \|A\x-\b\|$, we are given access to a matrix $A$ and vector $\b$ via some data structures (similar to QRAM access), and the goal is to output a data structure to the solution $$. The requirements of this data structure are that we must be able to query entries of the solution and sample from the distribution defined by the solution under the $ℓ_2$-norm. This data structure can be thus be viewed as a classical analog of the quantum state of the solution.

The importance of quantum-inspired classical algorithms lies in the finding that quantum computers only achieve polynomial speedups rather than exponential speedups as we originally expected for some matrix problems when the input matrices have low rank.
A typical example is the linear regression problem. Assuming the quantum random access memory (QRAM) data structure, the best quantum algorithm known so far has complexity linear in $A_$, which is believed to be optimal [5]. Here $A_$ is the Frobenius norm of $A$, which is defined as the square root of the sum of the absolute squares of all entries. Using a similar data structure to QRAM, some efficient quantum-inspired classical algorithms were also proposed [2, 24, 7, 6, 29].
The best algorithms known so far have complexity quartic in $A_$ [2, 24, 29]. This implies that the quantum speedup is at most quartic in terms of the Frobenius norm. We remark that the efficiency of quantum/quantum-inspired algorithms is also influenced by other parameters, however, the Frobenius norm is usually the dominating one.
%Recently, in [2], Bakshi and Tang showed that the singular value transformation for general bounded functions of matrices can also be done in time quartic in the Frobenius norm.

To better understand quantum-classical separations and also to see how far these quantum-inspired classical algorithms are far from optimal, we provide the first approach for proving lower bounds of quantum-inspired classical algorithms. We show that this quartic dependence on the Frobenius norm can not be improved further for some tasks like linear regression and supervised clustering. For some other tasks like principal component analysis, recommendation systems, and Hamiltonian simulation, we obtain a lower bound that is quadratic in the Frobenius norm. Through the study of these lower bounds, we have two positive findings:
\begin{itemize}
\item Large quantum speedup can exist for row and column sparse, high-rank, and well-conditioned matrix-relevant problems. Here by ``large", we mean the quantum speedup can be exponential. This provides a direction for looking for problems that can demonstrate large quantum speedups, see, e.g.~[17].
\item Quantum-inspired classical algorithms can play an important role in classical distributed computation. As a result, efficient classical protocols for many problems with low communication complexity can be found by quantum-inspired classical algorithms. We feel it is interesting to use this idea to find some useful applications, such as for machine learning problems discussed in [6].
\end{itemize}
And we also have a conjecture:
\begin{itemize}
\item If the matrix is row-sparse,\footnote{In this work, by a row-sparse matrix we always mean the number of nonzero entries of each row is polylogarithmic in the dimension. We can similarly define column sparse. A sparse matrix is a matrix that is both row and column sparse. If the matrix is not row or column sparse, then we call it dense.} then the quantum-classical separation is {\bf quadratic} for the above tasks (and/or for some other tasks that are not covered in this work) in terms of the Frobenius norm.\footnote{If the underlying matrix is sparse and Hermitian, then the separation can be much larger than quadratic. For example, the complexity could be $O(\|A\|)$ for quantum algorithms [5] and $O(\|A\|_{\F}^2)$ for quantum-inspired classical algorithms. Here $\|A\|$ is the operator norm of $A$, i.e., the maximal singular value of $A$. In the high rank case, we can have $\|A\|\ll \|A\|_\F$.}
If the matrix is dense, then the quantum-classical separation is {\bf quartic}.
\end{itemize}
To address this, more efficient quantum-inspired classical algorithms utilising the property of sparsity are waiting to be discovered in the sparse case, and some new ideas are required to prove better lower bounds in the dense case.

\subsection{Main results}

Our main focus of this work is on the lower bounds analysis of quantum-inspired classical algorithms for linear regressions, but we also study the lower bounds for some other problems (including supervised clustering, PCA, recommendation systems, and Hamiltonian simulation).
Our main technique is reductions from communication complexity. We will establish a connection between quantum-inspired classical algorithms and communication complexity, then use some well-known results in communication complexity (such as lower bounds for the Set-Disjointness and Gap-Hamming problems) to obtain some lower bounds.
As a by-product, we will also extend our method to study lower bounds analysis of quantum query algorithms for functions of matrices (see Section \ref{section: quantum connection}).

We now give more details. In quantum-inspired classical algorithms, we assume that we are given access to inputs via certain data structures called ``SQ". S and Q stand for Sampling and Query, respectively, and the rigorous definition of ``SQ" is given in Section \ref{section:Preliminaries}. For example, for a vector $=̌(v_1,…,v_n)$, $S()̌$ allows us to sample from the distribution defined by $$̌ under the $\ell_2$ norm (i.e., the probability of seeing $i$ is $|v_i|^2/\|\v\|^2$), and $Q(\v)$ allows us to query an entry and/or the norm of $\v$.

Recall that $A, A_$ refer to the operator norm and the Frobenius norm of $A$, respectively.
%Below, if $A=\sum_i \sigma_i \ket{u_i} \bra{v_i} $ is the SVD of $A$, then $A_{\geq \delta} = \sum_{\sigma_i\geq \delta} \sigma_i \ket{u_i} \bra{v_i}$.
The linear regression problem can be stated as follows.
%\nikhil{I'm a little confused by the definition of $A_{\geq \delta}$, how do you `truncate' $A$?}
%We don't compute $A_{\geq \delta}$ in advance. We only focus on singular values larger than some $\delta$ and then approximate this solution. I think here we suppose we know a lower bound of the singular values. Or do you mean the definition? If $A=\sum_i \sigma_i \ket{u_i} \bra{v_i} $ is the SVD of $A$, then $A_{\geq \delta} = \sum_{\sigma_i\geq \delta} \sigma_i \ket{u_i} \bra{v_i}$.
%\nikhil{I didn't know the definition. Added a line.}

%\cs{I will double check this notation because in the proofs below, we don't use $A^+_{\geq \delta}$. Maybe it is fine just using $A^+$.}

\begin{prob}[Linear regression]
\label{problem}
Let $A\in \mathbb{C}^{m\times n}, \b \in \mathbb{R}^m$.
For a linear regression $\argmin\|A\x-\b\|$, an algorithm is given access to $SQ(A), SQ(\b)$, and must output $SQ(\x_*)$, where $\x_*$ is an approximate solution satisfying $\|\x_*-A^+\b\| \leq \varepsilon \|A^+\b\|$, where $A^+$ means the pseudoinverse of $A$.
\end{prob}

Let $σ_min$ be the minimal nonzero singular value of $A$, denote
\be
\label{some notation}
\kappa_{\F}:=\|A\|_\F/\sigma_{\min}, \quad
\kappa := \|A\|/\sigma_{\min}, \quad
\gamma := \|A\x_*\|/\|\b\|.
\ee
These are the scaled condition number, condition number and the overlap of $$̱ is the column space of $A$, respectively.
In the lower bounds analysis, we will mainly focus on the analysis with respect to $\kappa_\F$, which relates the rank of $A$ and is usually the dominating term in the complexity. Indeed, if the rank of $A$ is $r$, then it is obvious that $\kappa_\F \geq \sqrt{r}$ because $\kappa_\F^2$ also equals the square sum of all singular values. So $\kappa_\F$ can be very large even if the matrix is well-conditioned.
Our main results for Problem <ref> are summarised in Table <ref>.

Algorithms     Upper bounds      Lower bounds
5*Row sparse case
$\widetilde{O}(\kappa_\F /\gamma)$ [5]
$\widetilde{\Omega}(\kappa_\F/\gamma)$ [8, 23]
Q     $\widetilde{O}(\kappa/\gamma)$ [5]

2*$\widetilde{\Omega}(\kappa/\gamma)$ [10]

column is sparse too
2*QIC     $\widetilde{O}(\kappa_\F^2)$ [24]     $\widetilde{\Omega}(\kappa_\F^2+1/\gamma^2)$

assumes $\gamma=1$     (Section <ref>)
4*Dense case       Q     $\widetilde{O}(\kappa_\F /\gamma)$ [5]     $\widetilde{\Omega}(\kappa_\F /\gamma)$  [8, 23]
/\varepsilon^2\gamma^2)$ [2]
QIC     $\widetilde{O}(\kappa_{\F}^4\kappa^2/\varepsilon^2)$ [24]     $\widetilde{\Omega}(\kappa_{\F}^4+1/\gamma^2)$$^*$

assumes $\gamma=1$     (Section <ref>)

Comparison of quantum (Q) and quantum-inspired classical  (QIC) algorithms for solving linear regression $\arg\min_{\x}\|A\x-\b\|$ (see Problem <ref>).
In the table, we highlight the quantum upper bound and classical lower bound to show the quantum-classical separation more clearly.
In the bottom-right entry, our lower bound only holds for Problem <ref> with additive error rather relative error as in the problem statement.

Below, we make some comments on this table.

* In the row-sparse case, the quantum-classical separation is quadratic. To prove the lower bound $\Omega(\kappa_\F^2+1/\gamma^2)$, we study the three standard requirements of the SQ data structure output separately. These are sampling from the distribution defined by the solution under the $\ell_2$ norm, approximation of the norm of the solution and, querying an entry of the solution up to certain accuracy. For the sampling task, we only obtain a lower bound of $\Omega((\kappa^2+\kappa_\F)/\gamma)$. The lower bound $\Omega(\kappa_\F^2+1/\gamma^2)$ holds for the other two tasks.

* In the dense case, the lower bound $\Omega(\kappa_{\F}^4)$ is for a weaker problem using additive error rather than the relative error stated in Problem <ref>. Also, this lower bound only holds for the task of norm approximation and querying an entry. For the sampling task, we only have a lower bound of $\Omega(\kappa_\F^2)$.

We also prove lower bounds for some other well-studied problems. We summarise these results in Table <ref>. From the table, we can claim that for these tasks the quantum speedup is at least quadratic. Although we feel the separation should be quartic, in this work we are not able to prove better lower bounds to close the gap. We remark that based on the results of [2], it is possible to further reduce the upper bound for principal component analysis in Table <ref>.

2*Problems     Upper bounds     Upper bounds      Lower bounds

(Q)     (QIC)     (QIC, Section <ref>)
Supervised clustering     $O(\|A\|_\F^2\|\b\|^2/\varepsilon )$ [15]     $O(\|A\|_\F^4\|\b\|^4/\varepsilon^2 )$ [6]     $\Omega(\|A\|_\F^4\|\b\|^4/\varepsilon)$

Principal component analysis     $O(\|A\|_\F)$ [5]     $O(\|A\|_\F^6)$ [6]     $\Omega(\|A\|_\F^2)$

Recommendation systems     $O(\|A\|_\F)$  [12]     $O(\|A\|_\F^4)$ [2]     $\Omega(\|A\|_\F^2)$

Hamiltonian simulation     $O(\|A\|_\F)$ [8]     $O(\|A\|_\F^4)$ [2]     $\Omega(\|A\|_\F^2)$

Upper and lower bounds for quantum (Q) and quantum-inspired classical (QIC) algorithms for some other problems. For the upper bounds of the latter three problems, we only show the dependence on $\|A\|_\F$ here. The explicit upper bounds of QIC are complicated and involve many other parameters; these are given explicitly in the cited papers. The definitions of these problems are given in Section <ref>.

§.§ Summary of main ideas

The form of access to input data in quantum-inspired classical algorithms is very similar to that in the setting of query complexity. However, a quantum-inspired classical algorithm has more power than a conventional query algorithm, since, for example, it can sample from the input data in a way that query algorithms can not. Thus, showing lower bounds query algorithms does not directly imply lower bounds for quantum-inspired classical algorithms. A standard model of computation that is studied, and richer than the query model, is that of communication complexity. As it turns out, quantum-inspired classical algorithms can indeed be efficiently simulated by communication protocols. Thus, showing communication complexity lower bounds for a task implies lower bounds for quantum-inspired classical algorithms solving the same task.

This approach is inspired by [18].

Below we sketch the main ideas behind our lower bounds for the linear regression problem.
Consider two players Alice and Bob, who are individually computationally unbounded. Alice has as input a matrix $A^{(1)}$ and a vector $\b^{(1)}$. Bob has another matrix $A^{(2)}$ and another vector $\b^{(2)}$. They can see their own inputs, but neither of the players can see the other player's input.

Their goal is to solve the linear regression $\x_*:=\arg\min_{\x}\|A\x-\b\|$, where $A = \begin{pmatrix}
A^{(1)} \\ A^{(2)}
\end{pmatrix}$ and $\b=\begin{pmatrix}
\b^{(1)} \\ \b^{(2)}
\end{pmatrix}$. To solve this problem, they are allowed to communicate with each other via a pre-determined communication protocol. The communication complexity is the total number of bits used in the communication on a worst-case input.
Without loss of generality, we assume the existence of a coordinator such that the communication is 2-way between each player and the coordinator. With a coordinator, it is easy to see how to generalise this idea to the multi-player model. Also, for convenience, we assume that each of the entries of $A,\b$ are specified by $O(1)$ bits.

In the model of quantum-inspired classical algorithms, we are given $SQ(A)$ and $SQ()̱$, and the goal is to output $SQ(_*)$ up to certain relative error. A quantum-inspired classical algorithm of complexity $T$ is a classical algorithm that uses $T$ applications of $SQ(A), SQ()̱$ and an arbitrary number of other arithmetic operations independent of ``SQ". We show below that a quantum-inspired classical algorithm of complexity $T$ for the above linear regression implies a communication protocol of complexity $O(Tlog(mn))$ for the same problem, where $m$ and $n$ are the total number of rows and columns of $A$, respectively.  To see this, it suffices to demonstrate a protocol for the coordinator to implement $SQ(A)$ and $SQ()̱$.

Let us first consider how the coordinator implements $SQ()̱$. Recall that $SQ()̱$ means sampling from the distribution defined by $(i) = |b_i|^2/^2$. The protocol is as follows:
\begin{itemize}
\item Firstly, Alice sends norm $\|\b^{(1)}\|$ and Bob sends norm $\|\b^{(2)}\|$ to the coordinator. At this point the coordinator knows $\|\b\|^2=\|\b^{(1)}\|^2+\|\b^{(2)}\|^2$.
\item Secondly, the coordinator samples an index from the distribution defined by $\Pr(i) = \frac{\|\b^{(i)}\|^2}{\|\b\|^2}$.
\item If the output is 1, then the coordinator asks Alice to sample an index from the distribution defined by $\b^{(1)}$ under the $\ell_2$ norm.
Otherwise, the coordinator asks Bob to sample an index from the distribution defined by $\b^{(1)}$ under the $\ell_2$ norm.
\end{itemize}
Now, it is not hard to check that the result is a desired sample. Next, let us consider how the coordinator implements $Q()̱$, i.e., query the $i$th entry of $$̱, say. This task is simpler.
Firstly, Alice sends the dimension, say $m_1$, of $\b^{(1)}$ to the coordinator. Secondly, if the index $i\leq m_1$, then the coordinator asks Alice to send back the $i$-th entry of $\b^{(1)}$. Otherwise, the coordinator asks Bob to send back the $(i-m_1)$-th entry of $\b^{(2)}$. The protocol for the coordinator to use $SQ(A)$ is similar.

As a result, if we know the lower bounds of communication complexity of solving linear regressions, we then can obtain lower bounds of quantum-inspired classical algorithms for the same task. With this idea, we then only need to focus on the lower bounds analysis of the communication complexity of linear regressions.
For this, we reduce some well-studied problems like the Set-Disjointness problem and the Gap-Hamming problem to some matrix inversion problems derived from the original linear regression problem. As can be observed from Table <ref>, the main difficulty of this reduction is that there are many parameters we need to take into account, such as $\kappa_\F, \kappa, \gamma$. So to obtain a nontrivial lower bound with respect to $\kappa_\F$ we need to make sure that $\kappa, \gamma = O(1)$ in the reduction. All of these factors make the reduction nontrivial.

§.§ Outline of the paper

The rest of the paper is organised as follows: Section <ref> contains some preliminary results on quantum-inspired classical algorithms and communication complexity. Section <ref> builds the formal connection between quantum-inspired classical algorithms and communication complexity. In Section <ref> we show lower bounds for quantum-inspired classical algorithms for linear regressions. Section <ref> discusses lower bounds of quantum-inspired classical algorithms for some other machine learning problems. Finally, as a generalisation of the above idea, Section <ref> studies the connection between quantum query complexity and quantum communication complexity of functions of matrices. Some applications are introduced. Appendix <ref> describes another connection between quantum-inspired classical algorithms and communication complexity, which might be useful in future applications.

§ PRELIMINARIES

§.§ The model for quantum-inspired classical algorithms

In this section, we recall definitions of the model used in quantum-inspired classical algorithms. For more details, we refer the reader to [6].

For a vector $\v=(v_1,\ldots,v_n) \in \mathbb{C}^n$, we have $Q(\v)$, query access to $\v$}, if for all $i ∈[n]$, we can query for $v_i$. Likewise, for a matrix $A=(A_ij) ∈ℂ^m×n$, we have $Q(A)$ if for all $(i,j) ∈[m] ×[n]$, we can query for $A_ij$.
\end{defn}

\begin{defn}[Sampling and query access to a vector] For a vector $\v=(v_1,\ldots,v_n) \in \mathbb{C}^n$, we have $SQ(\v)$, \emph{sampling and query access to $\v$}, if we can

\begin{itemize}
\item query for entries of $\v$ as in $Q(\v)$;
\item obtain independent samples of indices $i \in [n]$, each distributed as $\Pr(i)=|v_i|^2/\|\v\|^2$;
\item query for $\|\v\|$.
\end{itemize}
\end{defn}

\begin{defn}[Sampling and query access to a matrix]
\label{defn:Sampling and query access to a matrix}
For a matrix $A \in \mathbb{C}^{m\times n}$, we have
$SQ(A)$ if we have $SQ(A_{i*})$ for all $i \in [m]$ and $SQ(\a)$ for $\a=(\|A_{1*}\|,\ldots,\|A_{m*}\|)$. Here $A_{i*}$ refers to the $i$-th row of $A$.
\end{defn}

By a quantum-inspired classical algorithm of (query) complexity $T$ for solving a matrix-related problem, e.g., solving a linear regression $\min\|A\x-\b\|$, we mean we ``solve'' the problem by obtaining the ``SQ" data structure of the solution, with $T$ applications of $SQ(A), SQ(\b)$ and an arbitrary number of other arithmetic operations that are independent of ``SQ".

\subsection{Communication complexity}

Communication complexity was first introduced by Yao more than 4 decades ago in the study of distributed computation [28]. It has wide applications in many areas, especially in showing lower bounds, which has extensively been studied both in the classical and quantum fields [27, 21]. There are many models to study communication complexity in. In this work, we will focus on the coordinator model [20].

In the coordinator model, there are $k\geq 2$ players $\P_1,\ldots,\P_k$ and a coordinator $\C$. Each player holds some private information, and their goal is to solve some problem using as little communication as possible. The communication occurs between a player and the coordinator via a 2-way private channel. The computation is in terms of rounds: at the beginning of each round, the coordinator sends a message to one of the $k$ players, and then that player sends a message back to the coordinator. In the end, the coordinator returns an answer. Unless mentioned otherwise, the protocol must output a correct answer with probability at least $2/3$. The communication complexity is defined to be the total number of bits sent through the channels, on a worst-case input and worst-case outcomes of the internal randomness of the protocol.

A fundamental example is the Set-Disjointness problem. When $k=2$, player $\P_1$ receives an $n$-bit string $\x=(x_1,\ldots,x_n)\in\{0,1\}^n$ and player $\P_2$ receives another $n$-bit string $\y=(y_1,\ldots,y_n)\in\{0,1\}^n$, their goal is to determine if there is an $i$ such that $x_i=y_i=1$. It is well-known that the naive protocol ($\P_1$ has to send all $\x$ to the coordinator $\C$ who then sends $\x$ to $\P_2$, and finally $\P_2$ sends the right answer to $\C$) is asymptotically optimal [11, 22]. Namely, the communication complexity of the Set-Disjointness problem is $\Theta(n)$.

Another fundamental problem is the Gap-Hamming problem. In this problem, Alice has a $n$-bit string $\x$, Bob has a $n$-bit string $\y$, and they wish to compute
\be
\label{defn:gap-hamming}
1 & \text{if } \Delta(\x,\y)\geq n/2+\varepsilon n, \\
0 & \text{if } \Delta(\x,\y)\leq n/2-\varepsilon n, \\
* & \text{otherwise}.
\end{cases}
\ee
In the above, $\Delta(\x,\y)$ computes the hamming distance of $\x,\y$.
As shown in [4] the communication complexity for this problem is $\Theta(\min(d, 1/\varepsilon^2))$.

For those problems, there are also some multiplayer versions. We state them as follows.

% \nikhil{This definition is unclear to me. Shouldn't their goal be to determine if there is a $\ell \in [n]$ such that $T_{j\ell} = 1$ for all $j \in [k]$?}
% \cs{It is for one $j$, basically they want to determine if player $P_1$ and one player $P_j$ has an intersection or $P_1$ is disjoint from all other players. i.e., they want to solve DISJ between $P_1$ and $\vee_{j=2}^k P_j$.}\nikhil{We should check again if the proposition below holds for this definition. The standard definition would be to solve DISJ between $P_1$ and $\wedge_{j=2}^k P_j$.}
% \cs{I am pretty sure it is between $P_1$ and $\vee_{j=2}^k P_j$. I know this problem from https://arxiv.org/pdf/1906.05832.pdf. Check the end of page 17. Also if there is only one intersection between $P_1$ and $\wedge_{j=2}^k P_j$, then this problem might be easy because $P_1$ only to check with $P_2$ to find the common index. Do you know the complexity of $P_1$ and $\wedge_{j=2}^k P_j$? If it is hard, then maybe we can use this in the paper.}
% \nikhil{Ok, this version seems fine. But the second version you say also seems hard: I think Theorem 1.1 of https://arxiv.org/pdf/1305.4696.pdf shows this.}
% \cs{This is cool, I don't know this before. I will think about this problem to see if we can obtain better results.}

\begin{defn}[$k$-player Set-Disjointness problem]
\label{defn:k-DISJ}
For $i\in[k]$, player $\P_i$ receives a bit string $T_i=(T_{i1}, \ldots, T_{in})\in\{0,1\}^n$. Their goal is to determine if there is a $j\in\{2,\ldots,k\}$ such that $T_{1\ell}=T_{j\ell}=1$ for some $\ell\in[n]$.
\end{defn}

\begin{prop}[Theorem 3.3 of [20]]
\label{prop:k-DISJ}
When $n \geq 3200k$, for any classical protocol that succeeds with probability $1-1/k^3$ for solving $k$-player Set-Disjointness problem, the randomised communication complexity is $\Theta(k n)$.
\end{prop}

\begin{defn}[$k$-Gap-Hamming problem]
\label{defn:k-gap}
For $i\in \{1,2,\ldots,k+1\}$, player $\P_i$ receives a bit string $T_i\in\{\pm 1\}^n$ with the promise that $T := \sum_{i=1}^k T_i\in \{\pm 1\}^n$ and $\sum_{j=1}^k T_{j}\cdot T_{k+1, j} \in [-c_2\sqrt{n}, c_2\sqrt{n}]$.
% Their goal is to determine if $\sum_{i=1}^k T_i\cdot T_{k+1} \geq c_1\sqrt{n}$ or $\leq -c_1\sqrt{n}$. If $\sum_{i=1}^k T_i\cdot T_{k+1}$ is in between then any output is allowed.
% For $i\in \{1,2,\ldots,k+1\}$, player $\P_i$ receives a bit string $T_i\in\{\pm 1\}^n$ with the promise that $\sum_{i=1}^k T_i\in \{\pm 1\}^n$ and $\sum_{i=1}^k T_i\cdot T_{k+1} \in [-c_2\sqrt{n}, c_2\sqrt{n}]$.
% Their goal is to determine if $\sum_{i=1}^k T_i\cdot T_{k+1} \geq c_1\sqrt{n}$ or $\leq -c_1\sqrt{n}$. If $\sum_{i=1}^k T_i\cdot T_{k+1}$ is in between then any output is allowed.
\end{defn}

\begin{prop}[Theorem 3.3 of [14]]
\label{prop:k-gap}
Any protocol that solves the $k$-Gap-Hamming problem with large constant probability requires $\Omega(kn)$ bits of communication.
\end{prop}

Let $P=(p_1,\ldots,p_n)$ be a distribution. When we say that we \emph{approximately sample} from $P$, we mean that we output a sample from any distribution $\widetilde{P}=(\tilde{p}_1,\ldots,\tilde{p}_n)$ such that $\|\widetilde{P}-P\|_1:=\sum_i |p_i - \tilde{p}_i| \leq \varepsilon$ for some constant inaccuracy $\varepsilon$.

\begin{defn}[Distributed sampling problem]
\label{defn:DSP}
Assume that Alice has as input a function $f:\{0,1\}^n \rightarrow \{\pm 1\}$ and
Bob has as input a function $g:\{0,1\}^n \rightarrow \{\pm 1\}$.
Their goal is to approximately sample from the distribution defined by
\[
\Pr(y) := \left(\frac{1}{2^n}  \sum_{x\in\{0,1\}^n} f(x) g(x) (-1)^{x\cdot y} \right)^2.
\]
\end{defn}

\begin{prop}[Theorem 1 of [16]]
\label{prop:DSP}
There exists a universal constant $\varepsilon$ such that, for sufficiently large $n$, any 2-way classical communication protocol for Distributed Fourier Sampling with shared randomness and inaccuracy $\varepsilon$ must communicate at least $\Omega(2^n)$ bits.
\end{prop}

\subsection{Some background on quantum computing}
\label{subsection:Some background on quantum computing}

In this paper, we often use the Dirac notation to represent unit vectors.
For a unit column vector $\v$, we sometimes write it as $\ket{\v}$. In the quantum case, it will be called a quantum state.
Its complex conjugate is denoted as $\bra{\v}$.
The standard basis of $\mathbb{C}^n$ will be denoted as $\ket{1}, \ket{2}, \cdots, \ket{n}$.
Let $\ket{\a}=\sum_i a_i \ket{i}$ be a quantum state. The coefficients $a_i$ must satisfy $\sum_{i = 1}^n |a_i|^2=1$. When we measure it in the standard basis, then we will observe $i$ with probability $|a_i|^2$. So measurement naturally corresponds to the operation of sampling.
In this paper, the quantum notation $\ket{0}^n$ will also be used.
This is the same as $\ket{1}$ in $\mathbb{C}^{2^n}$.
For more about quantum computation, we refer the reader to the book [19].

\section{The connection}
\label{section:the connection}

We below discuss the connection between quantum-inspired classical algorithms and communication complexity. Our main result is the following theorem, which shows that there is an efficient simulation of a quantum-inspired classical algorithm using a classical communication protocol.

\begin{thm}
\label{thm:connection1}

In the multi-player coordinator model, for each $i\in\{1,\ldots,k\}$, assume that player $\P_i$ holds a matrix $A^{(i)}\in \mathbb{R}^{\ell_i\times n}$ and a vector $\b^{(i)}\in \mathbb{R}^{m_i}$ with $m:=\sum_i \ell_i = \sum_i m_i$.
Assume that all entries are specified by $O(\log q)$ bits.
\be
\label{thm:eq}
A^{(1)} \\
\vdots \\
A^{(k)} \\
\end{pmatrix}_{m\times n},
\quad
\b=\begin{pmatrix}
\b^{(1)} \\
\vdots \\
\b^{(k)}
\end{pmatrix}_{m\times 1}.
\ee
Then we have the following:
\begin{itemize}
\item The coordinator $\C$ can use $SQ(\b)$ $O(T)$ times, using $O((T+k) \log(qm))$ bits of communication.
\item The coordinator $\C$ can use $SQ(A)$ $O(T)$ times, using $O((T+k) \log (qmn))$ bits of communication.
\end{itemize}

\end{thm}

\begin{proof}

For the coordinator $\C$ to use $SQ(\b)$, i.e., sample from and query for $\b$, the player $\P_i$ first sends $\|\b^{(i)}\|$ to $\C$. This requires $O(k\log (qm))$ bits of communication. Here $O(\log(qm))$ is the number of bits used to specify $\|\b^{(i)}\|$.
Notice that this only needs to be done once for the whole protocol, rather than once for each access.
At this point, the coordinator knows $\|\b\|$, and also can sample from the distribution
\[
\D_{\b} (i) = \frac{\|\b^{(i)}\|^2}{\|\b\|^2},
\quad i\in\{1,2,\ldots,k\}.
\]
To sample from $\b$, the coordinator first uses the distribution $\D_{\b}$ to obtain a random index $i$, then communicates with $\P_i$ and asks $\P_i$ to sample from the distribution defined by $\b^{(i)}$ under the $\ell_2$-norm. For an arbitrary index $j \in [m]$, suppose the $j$'th entry of $\b$ is held by player $i$, and say $b^{(i)}_k = \b_j$. Then it is easy to see that
\bes
\Pr(j) = \frac{\|\b^{(i)}\|^2}{\|\b\|^2} \frac{|b^{(i)}_k|^2}{\|\b^{(i)}\|^2}
\ees
which is the same as the distribution defined in $SQ(\b)$.

To query the $j$-th entry of $\b$, the coordinator can communicate with the player who holds index $j$. To this end, player $\P_i$ only needs to send $m_i$ to $\C$, which costs $O(\log m)$ bits of communication.
%\nikhil{Shouldn't the analysis here be: coordinator needs to specify an index to the relevant player, sending this index takes at most $\log(m_i) = O(\log m)$ bits, and the player responds with $O(\log q)$ bits. The total should then be $O(\log(qm))$ bits then right? (Instead of the $k \log m$ below). We can assume that the coordinator knows each player's input length in advance.}
% \cs{Yes, right. The analysis here did not assume the coordinator knows each player's input length. I think this is fine. In our reduction below, usually $k$ is small compared to $T$. So I think it is not very important.}
So in total $O(k\log m)$ bits of communication. In conclusion, for the coordinator $\C$ to use $SQ(\b)$ $O(T)$ times, they use $O(T\log (qm)+k\log (qm) )$ bits of communication. Here $O(T \log(qm))$ counts the total number of bits of receiving indices or entries from all players, and $O(k \log(qm))$ counts the total number of bits of receiving the norm $\|\b^{(i)}\|$ and $m_i$ from player $\P_i$ for all $i$.

Similarly, for the coordinator to use $SQ(A)$, the player $\P_i$ first sends $\|A^{(i)}\|_{\F}$ to the coordinator $\C$. This costs $O(k\log (qmn))$ bits of communication, where $O(\log(qmn) )$ is the number of bits used to specify $\|A^{(i)}\|_\F$. The coordinator now has access to the distribution
\bes
\D_A(i) = \frac{\|A^{(i)}\|_{\F}^2}{\|A\|_{\F}^2}, \quad i\in\{1,2,\ldots,k\}.
\ees
As in Definition \ref{defn:Sampling and query access to a matrix}, let $\a=(\|A_{1*}\|,\cdots,\|A_{m*}\|)$, where $A_{i*}$ is the $i$'th row of $A$. The coordinator can use $SQ(\a)$ in a similar way to $SQ(\b)$. Now each entry is specified by $O(\log (qn))$ bits. To use $SQ(A_{i*})$, the coordinator only needs to communicate with the player who has the row index $i$. In summary, for the coordinator to use $SQ(A)$ $O(T)$ times, they use $O((T+k) \log(qmn))$ bits of communication.
\end{proof}

Recall that a quantum-inspired classical algorithm of complexity $O(T)$ means an algorithm that uses $O(T)$ applications of the data structure ``SQ" and an arbitrary number of other arithmetic operations. As a result of Theorem \ref{thm:connection1}, if there is a quantum-inspired classical algorithm of complexity $O(T)$, then there is a protocol for the same problem with communication complexity $O((T+k) \log(qmn))$. So we can use this to prove lower bounds of $T$.
To obtain a non-trivial lower bound from this result, it is useful to consider the regime where $k$ and $q$ are small. This is usually easy to enforce in the multi-player model.

Note that there are already many efficient quantum-inspired classical algorithms for a wide range of problems, e.g., see [2, 6], so we can use these algorithms to construct efficient communication protocols for the same problems based on Theorem \ref{thm:connection1}. One big advantage of this is that when studying communication complexity, the assumptions on quantum-inspired classical algorithms can be greatly relaxed. More precisely, one costly step of quantum-inspired classical algorithms is the preprocessing step of building the data structure ``SQ" for the input matrices or vectors. However, in communication complexity, local costs are not considered since the individual players are considered to be all-powerful. So each player can build the data structure ``SQ" to their own inputs independently, and this cost will not be counted when analyzing the communication complexity (note that the only power that we needed the players to have in the proof of Theorem~\ref{thm:connection1} was SQ access to their own inputs).
Namely, the preprocessing step can be resolved easily in the model of communication complexity.
This also means that quantum-inspired classical algorithms can play important roles in distributed computation.
To support this point, we introduce another connection in Appendix \ref{section:another connection}, which we expect to be more useful for applications. However, we will not consider specific applications of this in the current paper.

\section{Lower bounds for linear regressions}

\label{section:Lower bounds for linear regressions}

In this section, we use Theorem \ref{thm:connection1} to prove lower bounds for quantum-inspired classical algorithms for linear regressions. We study the row-sparse case and dense case separately. In each case, we focus on the three tasks required for SQ access separately: sampling from the distribution of the solution, approximating the norm of the solution, and querying an entry of the solution.

Recall that in the problem of linear regression, we are given $SQ(A)$ and $SQ(\b)$, the goal is to output $SQ(\tilde{\x}_*)$ such that $\|\tilde{\x}_*-\x_*\|\leq \varepsilon \|\x_*\|$, where $\x_*=A^+\b$.
With Theorem \ref{thm:connection1}, it suffices to give lower bounds on the communication complexity of linear regressions where $A,\b$ are defined in the form of (\ref{thm:eq}) in the coordinator model.

From [2], in the dense case the complexity of the best quantum-inspired classical algorithm known so far for linear regression is $\widetilde{O}(\kappa_\F^4 \kappa^{11}/\varepsilon^2 \gamma^2)$, where $\kappa_\F, \kappa, \gamma$ are defined in Equation (\ref{some notation}). In the row-sparse case, the complexity is $O(s\kappa_\F^2\log(1/\varepsilon))$ when $\gamma=\Theta(1)$ [24], where $s$ is the row sparsity. Thus there are five parameters we have to consider in the lower bounds analysis, i.e., $\kappa_\F, \kappa, \varepsilon, \gamma, s$. Our main focus will be on the dependence on $\kappa_\F$, so in our reductions we try to ensure that all the other parameters $\kappa, \varepsilon, \gamma, s$ are $O(1)$, to obtain non-trivial lower bounds in terms of $\kappa_\F$.

% In Theorem \ref{thm:connection1}, there is a logarithmic factor in the communication complexity. Below, for convenience, we will not include this factor in the complexity.
We use the notation $\widetilde{\Omega}(\cdot)$ to hide all factors that are polylogarithmic in the input size. Specifically, we ignore the logarithmic factors in Theorem~\ref{thm:connection1} for the sake of readability.

\subsection{Row-sparse case}

\begin{prop}[Sampling]
Assume that $A$ is row sparse and $\varepsilon\in(0,1)$ is a constant. Then $\varepsilon$-approximately sampling from $A^+\b$ requires making $\widetilde{\Omega}((\kappa^2+\kappa_\F)/\gamma)$ calls to $SQ(A), SQ(\b)$.
\end{prop}

\begin{proof} We give a reduction from the $k$-player Set-Disjointness problem, defined in Definition~\ref{defn:k-DISJ}. Suppose the $k$ players $\P_1, \dots, \P_k$ are given inputs to the Set-Disjointness problem (using the notation given in Definition \ref{defn:k-DISJ}).
Player $\P_j$ constructs the following vector:
\bes
\t_j = \sum_{\ell=1}^n T_{j \ell} \ket{\ell}, \quad
\ket{\t_j} = \t_j/\alpha_j,
\ees
where $\alpha_j=\|\t_j\|= \Theta(\sqrt{n})$ for all $j$.
Here we used the ket notation $\{\ket{1},\ldots,\ket{n}\}$ to represent the standard basis of $\mathbb{C}^n$, see Subsection \ref{subsection:Some background on quantum computing}. So $\ket{\t_j}$ is a unit vector.

Let $\beta_A,\beta_b$ be parameters that will be fixed later.
\beas
A = \beta_A \ket{1}_k \otimes \ket{1}_n \bra{1}_k + \sum_{j=2}^k \ket{j}_k  \otimes \ket{\t_j} \bra{j}_k , \quad
\b =   \beta_b \ket{1}_k \otimes \ket{1}_n + n\sum_{j=2}^k \ket{j}_k \otimes \ket{\t_1},
\eeas
where the subindex $k$ or $n$ refers to the dimension of base vectors.
In matrix form,
\[
A = \begin{pmatrix}
\beta_A \ket{1}_n & \\
& \ket{\t_2} & \\
& & \ddots \\
& & & \ket{\t_k} \\
\end{pmatrix}_{kn \times k},
\quad
\b =
\begin{pmatrix}
\beta_b \ket{1}_n  \\
n \ket{\t_1}  \\
\vdots \\
n \ket{\t_1} \\
\end{pmatrix}_{kn \times 1}.
\]
For the above matrix, the row sparsity is 1,
and it is easy to check that
\[
A^\T A = \beta_A^2\ket{1}_k \bra{1}_k + \sum_{j=2}^k \ket{j}_k \bra{j}_k,
\quad
A^\T\b = \beta_A\beta_b \ket{1}_k + n \sum_{j=2}^k \langle \t_1|\t_j\rangle \ket{j}_k.
\]
The optimal solution of the linear regression $\arg\min\|A\x-\b\|$ is
\[
\x_* = (A^\T A)^{-1} A^\T\b = \frac{\beta_b}{\beta_A}\ket{1}_k + n\sum_{j=2}^k \langle \t_1|\t_j\rangle \ket{j}_k.
\]
If there is no intersection, then $\x_* = \frac{\beta_b}{\beta_A}\ket{1}_k$. Measuring this state only returns index 1 with probability 1. If there is an intersection with one common index, then there is a $j\in\{2,\ldots,k\}$ such that
\[
\x_* = \frac{\beta_b}{\beta_A}\ket{1}_k + \frac{n}{\alpha_1 \alpha_j} \ket{j}_k.
\]
Note that $\alpha_1 \alpha_j = \Theta(n)$, so if choose $\beta_A=\Theta(\beta_b)$, then with a constant probability we will see index $j$ by sampling from the distribution defined by $\x_*$. So if we can sample from $\x_*$, we then can solve the Set-Disjointness problem using a constant number of such samples. In the remaining part of the proof we analyse the parameters of this problem and conclude the lower bound using Theorem~\ref{thm:connection1} and Proposition~\ref{prop:k-DISJ}.

The overlap of $\b$ in the column space of $A$ is
\[
\gamma^2 = \frac{\|A\x_*\|^2}{\|\b\|^2} =
\frac{\beta_b^2 + n^2 \sum_{j=2}^k \langle \t_1|\t_j\rangle^2 }{\beta_b^2 + (k-1)n^2} =
\frac{\beta_b^2 + c }{\beta_b^2 + (k-1)n^2}
\]
for some constant $c=\Theta(1)$.
We also have
\[
\|A\|_\F^2 = \beta_A^2 + k-1, \quad
\sigma_{\min} = \min\{ \beta_A, 1 \}.
\]
\[
\kappa^2 = \frac{\max(\beta_A^2,1)}{\min(\beta_A^2,1)}, \quad
\kappa_\F^2 = \frac{\|A\|_\F^2}{\sigma_{\min}^2} = \frac{\beta_A^2 + k-1}{\min(\beta_A^2,1)}, \quad \gamma^2 = \frac{\beta_b^2+c}{\beta_b^2 + (k-1)n^2}.
\]

If we choose $\beta_A^2 = \beta_b^2 = k$, then
$\kappa^2, \kappa^2_\F = \Theta(k), \gamma^2 = \Theta(1/n^2)$. Now we cannot determine the dependence on $\kappa_\F$. But note that $\kappa_\F \geq \kappa$, so by Theorem \ref{thm:connection1} a lower bound we can claim is $\Omega(\kappa^2/\gamma)$ because the communication complexity of the $k$-player Set-Disjointness problem is $\Theta(kn)$ by Proposition \ref{prop:k-DISJ}.
If we choose $\beta_A^2=\beta_b^2 = 1$, then $\kappa = 1, \kappa_\F^2 = \Theta(k), \gamma^2 = \Theta(1/kn^2)$, now we obtain a lower bound of $\Omega(\kappa_\F/\gamma)$.

One thing we did not analyse is the error. In the above constructions, we have $\x_* = \ket{1}_k$ or $\x_* = \ket{1}_k + d \ket{j}_k$ with $d=\Theta(1)$. The error will not change the sampling result when the inaccuracy $\varepsilon=O(1)$ is a constant.
\end{proof}

\begin{prop}[Norm approximation]
\label{prop:Norm approximation}
Assume that $A$  is row sparse and $\varepsilon\in(0,1)$. Then approximating $\|A^+\b\|$ up to relative error  $\varepsilon$ requires making $\widetilde{\Omega}(\kappa_\F^2+1/\gamma^2)$ calls to $SQ(A), SQ(\b)$.
\end{prop}

\begin{proof}
We give a reduction from the Gap-Hamming problem, see Equation (\ref{defn:gap-hamming}). Assume that Alice has an $n$-bit string $\a=(a_1,\ldots,a_n)\in\{\pm 1\}^n$ and Bob has another $n$-bit string $\b=(b_1,\ldots,b_n)\in\{\pm1\}^n$. Their goal is to determine if $\a\cdot \b\geq \sqrt{n}$ or $\leq -\sqrt{n}$. We consider the following local constructions by Alice and Bob, respectively:
\[
1 &   &        & a_1/\sqrt{n} \\
& \ddots &        & \vdots \\
&   & 1 & a_n/\sqrt{n} \\
&   &        & 1
\end{pmatrix},
\quad
\tilde{\b} = \begin{pmatrix}
b_1/\sqrt{n} \\
\vdots \\
b_n/\sqrt{n} \\
\end{pmatrix}.
\]
The solution of $A\x=\tilde{\b}$ is
\[
\x=\ket{n+1} + \frac{1}{\sqrt{n}} \sum_{i=1}^n (b_i-a_i) \ket{i}.
\]
\[
\|\x\|^2 = 1 +  \frac{1}{n} \sum_{i=1}^n (b_i-a_i)^2 = 1 +  \frac{1}{n} \left(\sum_{i=1}^n a_i^2 + \sum_{i = 1}^n b_i^2 - 2\sum_{i = 1}^n a_ib_i\right) = 3 - \frac{2}{n} \sum_{i=1}^n a_i b_i = 3-\frac{2}{n} \a\cdot \b .
\]
Let $\tilde{\x}$ be an approximate solution such that $\|\tilde{\x} - \x\| \leq \varepsilon \|\x\|$, then $|\|\tilde{\x}\| - \|\x\|| \leq \varepsilon \|\x\|$. If $\a\cdot \b \geq \sqrt{n}$, then $\|\tilde{\x}\| \leq (1+\varepsilon) (3-2/\sqrt{n})$.
If $\a \cdot \b \leq -\sqrt{n}$, then $\|\tilde{\x}\| \geq (1-\varepsilon) (3+2/\sqrt{n})$.
The gap of these two cases is at least $\frac{4}{\sqrt{n}}-6\varepsilon$, which equals $1/\sqrt{n}$ if we choose $\varepsilon=1/2\sqrt{n}$. Thus, if Alice and Bob can distinguish between these two cases, they can solve the Gap-Hamming problem on their original instances $\a, \b$. In this construction, $\|A\|_\F^2=n+2, \sigma_{\min} =\frac{\sqrt{5}-1}{2}, \sigma_{\max} =\frac{\sqrt{5}+1}{2}, \gamma =1$.
Since $A$ is invertible now, the upper bound of the complexity is
polynomial logarithmic in $1/\varepsilon$ by [24], also see Table \ref{table1}.
Although $\varepsilon=1/2\sqrt{n}$ is very small in this construction, it will not affect the analysis of the lower bound with respect to $\kappa_\F$.
Note that $k=2$ in this construction, so by Theorem~\ref{thm:connection1}, we obtain a lower bound of $\widetilde{\Omega}(n)=\widetilde{\Omega}(\kappa_\F^2)$.

We next consider another reduction from the Gap-Hamming problem. Let $A$ be the column vector $\a/\sqrt{n}$ and consider the linear regression problem $\min \|A\x - \sqrt{n}\b\|$. The solution is $x=\a \cdot \b$. In this example, $\kappa = \kappa_\F=1, \gamma^2=\Theta(n)$. If we can approximate $x$, we can solve the Gap-Hamming problem. So we obtain a lower bound of $\Omega(1/\gamma^2)$ by Proposition~\ref{prop:k-gap}.
\end{proof}

In the above two proofs, the linear regressions we constructed have dense columns. In this case, the best quantum algorithm known so far has complexity linear in $\|A\|_\F$, see \cite[Theorem 30 and Corollary 32]{chakraborty_et_al:LIPIcs:2019:10609}. Thus the quantum speedup we can claim is at least quadratic. However, as we show below, the quadratic dependence on $\kappa^2$ or $\kappa_\F^2$ in the above results also holds even if the matrices are totally sparse. Before proving this, we remark that the complexity of the quantum algorithm is linear in $\kappa$ when the matrix is both row and column sparse. So the quantum speedup can be very large when $\kappa_F \gg \kappa$, i.e., for sparse and high-rank linear regressions with small condition numbers.

We show below that the quadratic dependence on $\kappa^2$ or $\kappa_\F^2$ in the above results also holds even if the matrices are totally sparse.
First, we consider a reduction from the Set-Disjointness problem, where Alice has $(a_1,\ldots,a_n)\in\{0,1\}^n$ and Bob has $(b_1,\ldots,b_n)\in\{0,1\}^n$. Now Alice constructs a diagonal matrix $A$ with $i$-th diagonal entry equaling $\eta$ (whose value will be set later) if $a_i=1$ and $1$ if $a_i=0$. Bob constructs the vector $\b$ that is exactly the same as his input. Then we can see that the solution of $A\x=\b$ is
\[
\x = \frac{1}{\eta}  \sum_{a_i=1,b_i=1} \ket{i} + \sum_{a_i=0,b_i=1}   \ket{i}.
\]
By setting $\eta=1/\sqrt{n}$, measuring state $\x$ will return an index $i$ such that $a_i=1,b_i=1$ with probability at least 1/2. Thus, if Alice and Bob can solve this regression problem efficiently, they can solve their original Set-Disjointness instance. In this construction, we have $\kappa_F = n, \kappa=\sqrt{n}, \gamma=1$. So by Theorem~\ref{thm:connection1}, for the task of sampling, we obtain a lower bound of $\kappa^2$.
Next, consider the following construction:
\[
A = \sum_{i\in [n]} \frac{1}{1+a_i} \ket{i} \bra{i}, \quad  \b =  \sum_{i\in [n]} (1+b_i) \ket{i}.
\]
The solution is
\[
\x = \sum_{i\in [n]} (1+a_i) (1+b_i) \ket{i}.
\]
Recall that $a_i,b_i\in\{0,1\}$. Hence, we have $(1+a_i)^2=1+2a_i+a_i^2=1+3a_i$, and
so the norm of the solution is  $\|\x\|^2 = \sum_{i\in [n]} (1+3a_i) (1+3b_i) = n + 3 |\a|+3|\b| + 9 \a\cdot \b$. If we set $\eta=1/n$, then we can determine $\a\cdot \b = 1$ or not, which solves the Set-Disjointness problem. In this example, $\kappa=\gamma=1, \kappa_\F^2=n$.
From Table \ref{table1}, when $A$ is invertible, there is a quantum-inspired classical algorithm whose complexity is only
polynomial logarithmic in $1/\varepsilon$. So in the lower bound analysis here, we can ignore the influence of $\varepsilon$ even if it is small. So by Theorem~\ref{thm:connection1} we obtain a lower bound of $\Omega(\kappa_\F^2)$ for norm approximation.

\begin{lem}[Weyl's inequality [26]]
\label{prop:Weyl inequality}
For any two matrices $A, B$ of the same size, we have $|\sigma_i(A) - \sigma_i(B)|\leq \|A-B\|$ for any $i$-th singular value $\sigma_i$.
\end{lem}

\begin{prop}[Query an entry]
Assume that $A$ is sparse and $\varepsilon\in(0,1)$. Then there is an index $i$ such that computing $x_i$ with $|x_i - (A^+\b)_i|\leq \varepsilon$ requires making $\widetilde{\Omega}(\kappa_\F^2+1/\gamma^2)$ calls to $SQ(A), SQ(\b)$.
\end{prop}

\begin{proof}
We give a reduction from the Gap-Hamming problem, where Alice has $(a_1,\ldots,a_n) \in \{\pm 1\}^n$ and Bob has $(b_1,\ldots,b_n) \in \{\pm 1\}^n$. Recall that their goal is to determine if $\sum_i a_ib_i \geq \sqrt{n}$ or $\leq -\sqrt{n}$.
Consider the following construction by Alice and Bob:
\[
1/a_1 & -t  &        &  \\
& a_1/a_2 & \ddots       &  \\
&   & \ddots & -t & \\
&   &        & a_{n-1}/a_n
\end{pmatrix}, \quad
\b = \begin{pmatrix}
b_1 \\
b_2/t \\
\vdots \\
b_n/t^{n-1} \\
\end{pmatrix}.
\]
The first entry of the solution of $A\x=\b$ is $\sum_i a_i b_i$. Let $B$ as the diagonal part of $A$, then it is obvious that
$\|A-B\| = t$. By Weyl's inequality, the singular values of $A$ satisfy $|\sigma_i(A) - 1|\leq t$. So if we choose $t=1/2$, then $\kappa =\Theta(1), \kappa_\F^2=\Theta(n)$ and $\gamma=1$. Thus, if we can approximate the first entry of the solution we then can solve the Gap-Hamming problem. This leads to a lower bound of $\widetilde{\Omega}(\kappa_\F^2)$.
The lower bound $\widetilde{\Omega}(1/\gamma^2)$ follows from the second part of the proof of Proposition \ref{prop:Norm approximation}.
\end{proof}

\subsection{Dense case}

\begin{prop}[Sampling]
Assume that $\varepsilon\in(0,1)$ is a constant. Then $\varepsilon$-approximately sampling from $A^+\b$ requires making $\widetilde{\Omega}(\kappa_\F^2)$ calls to $SQ(A), SQ(\b)$.
\end{prop}

\begin{proof}
Here we give a reduction from the distributed sampling problem. We below use the notations stated in Definition \ref{defn:DSP}. Let $D_f =\sum_x f(x)  \ket{x}\bra{x} $ be the diagonal matrix such that the $x$-th diagonal entry is $f(x)$ and let $ \ket{g} = \frac{1}{\sqrt{2^n}} \sum_x g(x) \ket{x}$ be a unit column vector whose entries are $g(x)$, then the distribution in the distributed sampling problem is defined by the state $(D_f H^{\otimes n})^{-1} \ket{g}$, where
$H=\frac{1}{\sqrt{2}} \begin{pmatrix}
1 & 1 \\ 1 & -1
\end{pmatrix}$ is the Hadamard gate.
Now it is easy to check that
for matrix $D_f H^{\otimes n}$ we have $\kappa_\F^2 = 2^n$, $\kappa=\gamma=1$. So we obtain a lower bound of $\widetilde{\Omega}(\kappa_\F^2)$ by Proposition \ref{prop:DSP} and Theorem \ref{thm:connection1}.
% \cs{OK, we can remove this part as it is not clear. Here I mainly want to highlight low-rank, but this does not change this proposition.}
% In particular, if we restrict ourselves to the case that $f(x)\in\{\pm 1\}$ if $x\in S\subseteq \{0,1\}^n$ and $f(x)=0$ if $x\not\in S$, then the communication complexity for this restricted distributed sampling problem is $\Omega(|S|)$. \nikhil{Is there a reference for this?}\cs{I don't have a reference here. I think this follows directly from Prop 9 once we know $S$.}\nikhil{Hmm, I don't see how this follows directly from Prop 9.}If we use this problem, the matrix $D_f H^{\otimes n}$ has rank $|S|$ that can be much smaller than $2^n$. Namely, it defines a low-rank linear regression.
\end{proof}

For the sampling problem, the following is a plausible way of proving a lower bound of $\widetilde{\Omega}(\kappa_\F^4)$. However, we are not able to prove this claim in this work.
Assume that player $\P_i$ holds a unit vector $\a_i=(a_{i1},\ldots,a_{in}) \in \mathbb{C}^n$ and a number $b_i\in \mathbb{C}$, where $i\in[k]$.
Let $A=\sum_{i\in[k]} \ket{i} \bra{\a_i} $ and $\b = \sum_{i\in[k]} b_i \ket{i}$. Further, assume that $A$ has orthogonal rows and $\b$ is a unit vector.
The complex conjugate of $A$ is denoted as $A^\dag$.
The goal is for the coordinator to approximately sample from the distribution defined by $A^\dag \b=\sum_{i\in[k]} b_i \ket{\a_i}$, i.e., for any $j\in [n]$
\[
\Pr(j) = \Big(\sum_{i\in[k]} b_i a_{ij}\Big)^2.
\]
We conjecture that the classical communication complexity for this problem is $\Theta(k^2)$.

The upper bound uses rejection sampling [25]. The basic idea of the protocol is as follows: Let $Q$ be our target distribution defined by $\sum_{i=1}^k b_i  \ket{\a_i}$, let $P$ be a distribution which is defined later. We first draw a sample $s$ from $P$, and then compute $r_s = Q(s)/M P(s)$ for some constant $M$. We accept $s$ with probability $r_s$, otherwise restart.
In our case, $P$ is the distribution by first sampling an index $j$ with probability proportional to $b_j^2$,
then sampling from $\ket{\a_j}$. So $P(s) = \sum_{j=1}^k b_j^2 a_{js}^2/(\sum_{j=1}^k b_j^2)$. We also have $Q(s) = (\sum_{j=1}^k b_ja_{js})^2/(\sum_{j=1}^k b_j^2)$. By the Cauchy-Schwarz inequality
\[
r_s = \frac{(\sum_{j=1}^k b_ja_{js})^2}{M \sum_{j=1}^k b_j^2 a_{js}^2} \leq \frac{k}{M}.
\]
So we can set $M=k$. Computing $r_s$ costs $O(k)$ queries. So in total $O(k^2)$.

For the above sampling problem, we have that the matrix is low-rank with rank $k$. We also have $\|A\|_\F^2 = k, \kappa = \gamma =1$. If the above claim is correct, then we will obtain a lower bound of $\widetilde{\Omega}(\kappa_\F^4)$ for the sampling task. More generally, let $f(x)$ be an odd polynomial, then using the above construction we can prove that $\widetilde{\Omega}(\kappa_\F^4)$ calls to $SQ(A),SQ(\b)$ are required in order to approximately sample from $f^{(\rm SV)}(A^\dag)\b$, which is proportional to $\sum_{i=1}^k b_i \ket{\a_i}$. Here if $f(x) = x g(x^2)$, then $f^{{\rm (SV)}}(A^\dag) := A^\dag \cdot g(AA^\dag)$ is the singular value transformation of $A$ with respect to $f(x)$.

\begin{prop}[Norm approximation]
Assume that $\varepsilon\in(0,1)$. Then approximating $\|A^+\b\|^2$ up to additive error $\varepsilon$ requires making $\widetilde{\Omega}(\kappa_\F^4)$ calls to $SQ(A), SQ(\b)$.
\end{prop}

\begin{proof}
We show a reduction from the $k$-Gap-Hamming problem, see Proposition \ref{prop:k-gap}. The notations below come from Definition \ref{defn:k-gap}.
Let $\a_i=(a_{i1},\ldots,a_{in})\in \{\pm 1\}^n$ for $i\in[k+1]$. Let $\e=\frac{1}{m}(1,\ldots,1) \in \mathbb{R}^n$, where $m$ is an integer such that $\e\cdot \a_{k+1}=O(1)$.
%If this $\e$ does not satisfy the condition, player $\P_{k+1}$ can slightly modify it and let other players know. The cost of this step is negligible.
Let $M\in \mathbb{R}^{k\times n}$ be the matrix such that the $i$-th row is $\a_i+\e$.
Consider the following construction
\[
A = \begin{pmatrix}
I_n & \0 \\
M/2n & I_k
\end{pmatrix},
\quad
\b = \begin{pmatrix}
-2n\a_{k+1}  \\
\0
\end{pmatrix}.
\]
The solution is
\[
\x = \begin{pmatrix}
-2n\a_{k+1} \\
(\a_1+\e) \cdot\a_{k+1}\\
\vdots \\
(\a_1+\e) \cdot\a_{k+1}  \\
\end{pmatrix}.
\]
The square of the norm of the solution is
\[
\|\x\|^2 = 4n^3 + \sum_{i=1}^k  \Big(
(\a_i\cdot\a_{k+1})^2 + (\a_{k+1}\cdot\e)^2 + 2 (\a_i\cdot\a_{k+1}) (\a_{k+1}\cdot\e)
\Big).
\]

Similarly, if we set $M$ to be the matrix such that the $i$-th row is $\a_i-\e$, then the  square of the norm of the solution is
\[
\|\x'\|^2 = 4n^3 + \sum_{i=1}^k  \Big(
(\a_i\cdot\a_{k+1})^2 + (\a_{k+1}\cdot\e)^2 - 2 (\a_i\cdot\a_{k+1}) (\a_{k+1}\cdot\e)
\Big).
\]
\[
\|\x\|^2 - \|\x'\|^2
=4(\a_{k+1}\cdot\e) \sum_{i=1}^k  (\a_i\cdot\a_{k+1}) .
\]
The player $\P_{k+1}$ can send the information of $\a_{k+1}\cdot\e$ to the coordinator, and send $m$ to all other players and the coordinator in advance. This in total costs $O(k)$ bits of communication, which is negligible compared with the total cost of the $k$-Gap-Hamming problem. In conclusion, if one can
approximate the square norm of the solution up to a constant additive error, then one can solve the $k$-Gap-Hamming problem.

For the matrix $A=\begin{pmatrix}
I_n & \0 \\
M/2n & I_k
\end{pmatrix} = I_{n+k} + \begin{pmatrix}
\0 & \0 \\
M/2n & \0
\end{pmatrix}$, by Weyl's inequality (see Proposition \ref{prop:Weyl inequality}), we have $|\sigma_i(A) - 1|\leq \|M/2n\| \leq 1/2$ for any singular value of $A$. This means that $A$ is well-conditioned.
Hence $\kappa_\F^2 = k+n$, $\kappa=\Theta(1)$ and $\gamma=1$. By Proposition \ref{prop:k-gap}, the lower of $k$-Gap-Hamming problem is $\Omega(kn)=\Omega(n^2)$ when $k=\Theta(n)$. The above argument gives a lower bound of $\Omega(\kappa_\F^4)$ by Theorem \ref{thm:connection1}.
\end{proof}

We remark here that the above proof only gives a bound of $\Omega(\kappa_\F^4)$ for the task of computing $\|A^+\b\| \pm \varepsilon$ for some constant $\varepsilon$ rather than computing $\|A^+\b\| (1\pm \varepsilon)$. So we do not obtain a lower bound of $\Omega(\kappa_\F^4)$ for the task of approximating the norm up to some relative error mentioned in Problem \ref{problem}.
This is also the case in the following result.

\begin{prop}[Query an entry]
Assume that $\varepsilon\in(0,1)$. Then there is an index $i$ such that computing $x_i$ with $|x_i - (A^+\b)_i|\leq \varepsilon$ requires making $\widetilde{\Omega}(\kappa_\F^4)$ calls to $SQ(A), SQ(\b)$.
\end{prop}

\begin{proof}
We again reduce from the $k$-Gap-Hamming problem. The construction is similar to that of the previous proof.
Let $\a_i=(a_{i1},\ldots,a_{in})\in \{\pm 1\}^n$ for $i\in[k+1]$. For convenience, we assume that $k=2^\ell$ is a power of 2. Let $M\in \{\pm 1\}^{k\times n}$ be the matrix such that the $i$-th row is $\a_i$.
Consider the following construction
\[
A = \begin{pmatrix}
I_n & \0 \\
M/2n & I_k
\end{pmatrix} \begin{pmatrix}
I_n & \0 \\
\0 & H^{\otimes l}
\end{pmatrix},
\quad
\b = \begin{pmatrix}
-2n\a_{k+1} \\
\0
\end{pmatrix},
\]
where $H=\frac{1}{\sqrt{2}} \begin{pmatrix}
1 & 1 \\ 1 & -1
\end{pmatrix}$ is the Hadamard gate.
The solution of $A\x=\b$ is
\[
\x = \begin{pmatrix}
-2n\a_{k+1} \\
\frac{1}{\sqrt{k}} \sum_{i=1}^k \a_i\cdot\a_{k+1} \\
\vdots
\end{pmatrix}.
\]
If we can query the $(n+1)$-th entry of $\x$, then we can recover the value $\sum_i \a_i\cdot \b/\sqrt{k}$. In particular, assume that $k=c_1 n$, then $\frac{1}{\sqrt{k}} \sum_{i=1}^k \a_i\cdot\a_{k+1} \geq c_1 \sqrt{n}$ or $\leq -c_1 \sqrt{n}$. We can still recover this information from $\tilde{\x}$ if $\|\tilde{\x} - \x\|_\infty \leq \varepsilon$.

Note that multiplying a unitary matrix does not change the singular values, so by a similar argument to the above proof, we also have $\kappa_\F^2 = k+n$, $\kappa=\Theta(1)$ and $\gamma=1$. Hence we obtain a lower bound of $\widetilde{\Omega}(\kappa_\F^4)$.
\end{proof}

\section{Lower bounds for other machine learning problems}
\label{section:Lower bounds for other machine learning problems}

In this section, we use Theorem \ref{thm:connection1} to prove lower bounds for four other problems: supervised clustering, principal component analysis, recommendation systems, and Hamiltonian simulation. These problems are well-studied both in the quantum case [15, 5, 12, 8] and in the quantum-inspired classical case [6, 2]. Below, the statements of these problems come from [6].

\begin{prob*}[Supervised clustering]
Let $\p, \q_1, \ldots,\q_n \in \mathbb{R}^d$ and $\varepsilon\in(0,1)$, denote
\[
A = \begin{pmatrix}
-\p/\|\p\| \\
\q_1/\|\q_1\|\sqrt{n} \\
\vdots \\
\q_n/\|\q_n\|\sqrt{n}
\end{pmatrix}, \quad
\b = \begin{pmatrix}
\|\p\| \\
\|\q_1\|/\sqrt{n} \\
\vdots \\
\|\q_n\|/\sqrt{n}
\end{pmatrix}.
\]
Given $SQ(A), SQ(\b)$, compute $\|\b^\T A\|^2 \pm \varepsilon$.
\end{prob*}

If we denote $\q = \frac{1}{n} \sum_{i=1}^n \q_i$, then $\|\b^\T A\|^2=\|\p - \q\|^2$, which is the distance between $\p$ and the center of $\{\q_1,\ldots,\q_n\}$. This task is widely used in supervised cluster assignments. In this problem, we are given a vector $\p$ and some sets of vectors $Q_1, \ldots, Q_k$. The goal is to assign $\p$ to one of the sets. In supervised clustering, the criterion relies on the distance between $\p$ and the centers. We will assign $\p$ to $Q_i$ if the distance between $\p$ and the center of $Q_i$ is the smallest one.

For supervised clustering, by \cite[Corollary 6.10]{chia2022sampling}, there is a quantum-inspired classical algorithm with complexity $O(\|A\|_\F^4\|\b\|^4\varepsilon^{-2})$. In the quantum case, by [15], there is a quantum algorithm of complexity $O(\|A\|_\F^2\|\b\|^2\varepsilon^{-1})$. Below we show a near-tight lower bound of quantum-inspired classical algorithms, which implies that the quantum-classical separation for supervised clustering is quadratic.

\begin{prop}
For supervised clustering, any quantum-inspired classical algorithms must use $\Omega(\|A\|_\F^4\|\b\|^4\varepsilon^{-1} + \varepsilon^{-2})$ applications of $SQ(A), SQ(\b)$.
\end{prop}

\begin{proof}
We obtain the first term via a reduction from the $n$-Gap-Hamming problem. Let $\x,\y_i\in \{\pm 1\}^d$ and $\alpha$ be a scaling parameter, which will be determined later. Let $\p=\alpha \x, \q_i = \alpha \y_i$. So $\|A\|_\F^2=2, \|\b\|^2=2\alpha^2 d$. Moreover, $\|\p-\q\|_2^2 = 2\alpha^2 d - \frac{2\alpha^2}{n} \sum_{i=1}^n \x \cdot \y_i$. In the $n$-Gap-Hamming problem, the promise is that $\sum_{i=1}^n \x \cdot \y_i \geq \sqrt{d}$ or $\leq -\sqrt{d}$. To distinguish them it suffices to choose $\varepsilon = \alpha^2 \sqrt{d}/n$. We now set $\alpha$ such that $\alpha^2 \sqrt{d} = 1$, then $\varepsilon=1/n$ and $\|\b\|^2=2\sqrt{d}$.
By Proposition~\ref{prop:k-gap}, the lower bound of the $n$-Gap-Hamming problem is $\Omega(nd) = \Omega(\|A\|_\F^4\|\b\|^4\varepsilon^{-1})$, so we obtain the first part of the claimed lower bound using Theorem~\ref{thm:connection1}.

In particular, when $n=1$, the reduction is from the (2-player) Gap-Hamming problem. We now set $\p=\x/\sqrt{d}, \q=\y/\sqrt{d}$ as unit vectors. Then
$\|\p-\q\|_2^2 = \frac{4}{d}\Delta(\x,\y)$. If we can approximate this quantity up to additive error $\varepsilon $, we then can solve the Gap-Hamming problem. So we obtain a lower bound of $\Omega(\varepsilon^{-2})$.
\end{proof}

\begin{prob*}[Principal component analysis]
\label{prob: Principal component analysis}
Let $A\in \mathbb{C}^{m\times n}$ be a matrix such that $A^\dag A$ has top $k$ eigenvalues $\{\lambda_i:i\in[k]\}$ and corresponding eigenvectors $\{\v_i:i\in[k]\}$. Given $SQ(A)$, with probability $\geq 1-\delta$, compute eigenvalues $\{\tilde{\lambda}_i:i\in[k]\}$
such that $\sum_{i\in[k]} |\tilde{\lambda}_i - \lambda_i|\leq \varepsilon \|A\|_\F^2$ and eigenvectors $\{SQ(\title{\v}_i):i\in[k]\}$ such that $\|\v_i - \tilde{\v}_i\| \leq \varepsilon$.
\end{prob*}

About this problem, by \cite[Corollary 6.12]{chia2022sampling} there is a quantum-inspired classical algorithm whose complexity is $\widetilde{O}( \frac{\|A\|_{\F}^6}{\lambda_k^2 \|A\|^2} \eta^{-6} \varepsilon^{-6} )$, where $\eta = \min_{i\in[k]} |\lambda_i-\lambda_{i+1}|/\|A\|^2$. In particular, when $k=1$, the complexity becomes $\widetilde{O}( \frac{\|A\|_{\F}^6\|A\|^6} {|\lambda_1-\lambda_2|^6}\varepsilon^{-6} )$. In comparison, the quantum complexity is $\widetilde{O}(\|A\|_\F/\varepsilon)$ when $k=1$ [5]. In this particular case, we can prove the following lower bound for quantum-inspired classical algorithms. It indicates the quantum-classical separation is at least quadratic.

\begin{prop}
\label{prop:PCA1}
Let $A$ be a matrix with maximal singular value $\sigma$ and corresponding right singular vector $\v$, then computing $\sigma\pm \varepsilon$ or $\varepsilon$-approximately sampling from $\v$ requires $\Omega(\|A\|_\F^2)$ applications of $SQ(A)$.
\end{prop}

\begin{proof}
We show a reduction from the Set-Disjointness problem.
In the Set-Disjointness problem, Alice has $(a_1,\ldots,a_n) $ $ \in \{0,1\}^n$ and Bob has $(b_1,\ldots,b_n) \in \{0,1\}^n$. The goal is to determine if there is an $i$ such that $a_i=b_i=1$. If $i$ exists, we can assume that there is only one such $i$. For this problem, the lower bound is $\Omega(n)$. To use this result, Alice constructs a diagonal matrix $D_a = {\rm diag}(a_1,\ldots,a_n)$, and Bob constructs another diagonal matrix $D_b = {\rm diag}(b_1,\ldots,b_n)$. Let $A=\begin{pmatrix}
D_a \\
\end{pmatrix}$. Then we have $A^\dag A = D_a^2 + D_b^2$. If there is an intersection, say $a_i=b_i=1$, then $\sigma=\sqrt{2}$ and $\v=\ket{i}$. Otherwise $\sigma=1$. The corresponding right singular vectors are $\v=\ket{j}$ for any $j$ with $a_j=0,b_j=1$ or $a_j=1,b_j=0$. So if we can approximate $\sigma$ or sampling from $\v$, we then can solve the Set-Disjointness problem. In this construction, we have $\|A\|_\F^2 = \Theta(n), \|A\|=\Theta(1), \varepsilon=\Theta(1)$. So we obtain the claimed lower bound by Theorem~\ref{thm:connection1}.
\end{proof}

Recall that if the singular value decomposition of $A$ is $\sum_i \sigma_i \ket{u_i} \bra{v_i}$, then $A_{\geq \delta} := \sum_{i : \sigma_i\geq \delta}\sigma_{i} \ket{u_i} \bra{v_i}$.

\begin{prob*}[Recommendation systems]
\label{prob: Recommendation systems}
Let $A\in \mathbb{C}^{m\times n}$ be a matrix and $i\in[m]$. Let $\varepsilon, \delta >0$. Given $SQ(A)$, the goal is to $\varepsilon$-approximately sample from the $i$-th row of $A_{\geq \delta}$.
\end{prob*}

For the problem of recommendation systems, by \cite[Corollary 1.2]{bakshi2023improved}, there is a quantum-inspired classical algorithm of complexity $O(\|A\|_{\F}^4/\sigma^8\varepsilon^2)$. In comparison, there is a quantum algorithm of complexity $O(\|A\|_\F/\sigma)$ [12]. As a corollary of Proposition \ref{prop:PCA1}, we have the following lower bound.

\begin{prop}
Approximately sample from the $i$-th row of $A_{\geq \delta}$ requires making $\Omega(\|A\|_\F^2)$ calls to $SQ(A)$.
\end{prop}

\begin{proof}
We use the same construction as in the proof of Proposition \ref{prop:PCA1}. Now we choose $\delta \in (1,\sqrt{2})$, then $A_{\geq \delta} = \sigma \ket{\u} \bra{\v}$ for some $\u$ if there is an intersection, and $A_{\geq \delta} = 0$ if no intersection. So if we can sample from the $i$-th row of $A_{\geq \delta}$ approximately, we then can solve the Set-Disjointness problem.
\end{proof}

\begin{prob*}[Hamiltonian simulation]
\label{prob: Hamiltonian simulation}
Let $A\in \mathbb{C}^{n\times n}$ be a Hermitian matrix with $\|A\|\leq 1$ and $\v\in\mathbb{C}^{n\times n}$ be a unit vector. Let $\varepsilon, \delta \in (0,1]$. Given $SQ(A), SQ(\v)$, output $SQ(\u)$ with probability at least $1-\delta$ such that $\|\u-e^{iA t} \v\|\leq \varepsilon$.
\end{prob*}

From \cite[Corollary 1.6]{bakshi2023improved}, we know that there is a quantum-inspired classical algorithm for Hamiltonian simulation with complexity $O(\|A\|_\F^4 t^{8}/\varepsilon^2)$. In comparison, the quantum algorithm has complexity $O(\|A\|_\F t)$. About this problem, we have the following lower bound.

\begin{prop}
Assume that $\varepsilon\in(0,1)$ is a constant. Then $\varepsilon$-approximately sampling from $e^{iA} \v$ requires making $\Omega(\|A\|_\F^2)$ calls to $SQ(A), SQ(\v)$.
\end{prop}

\begin{proof}
The result follows via a reduction from the distributed Fourier sampling problem. In this problem, Alice has a function $f:\{0,1\}^n \rightarrow \{\pm 1\}$ and Bob has a function $g:\{0,1\}^n \rightarrow \{\pm 1\}$. Let $D_f, D_g$ be the diagonal matrices defined by $f(x),g(x)$ respectively. Let $H_2$ be the Hadamard gate. Then their goal is to sample from $D_f H_2^{\otimes n} D_f D_g H_2^{\otimes n} \ket{0}^n$. By Proposition \ref{prop:DSP}, the communication complexity of this problem is $\Theta(2^n)$.

\[
A = D_f \left(\frac{1}{2n}  \sum_{j=1}^n I_2^{\otimes (j-1)} \otimes (I_2-H_2) \otimes I_2^{\otimes(n-j)} \right) D_f,
\]
then it is easy to check that $D_f H_2^{\otimes n}D_f = e^{i A t}$, where $t=n\pi$. This matrix is in Alice's hand. For this matrix, it is not hard to show that $\|A\|_\F^2 = \Theta(2^n), \|A\|=1$. In the Hamiltonian simulation, we set $\v=D_g H_2^{\otimes n} \ket{0}^n$. This vector is in Bob's hand. Finally, by Proposition \ref{prop:DSP} and Theorem~\ref{thm:connection1}, we obtain a lower bound of $\Omega(\|A\|_\F^2)$.
\end{proof}

\section{A connection between quantum query and communication complexities of matrix problems}
\label{section: quantum connection}

In this section, we generalise Theorem \ref{thm:connection1} to the quantum case. We focus on two types of quantum algorithms for matrix-based problems.

\begin{description}
\item[The query model:]
For a matrix $A = (A_{ij}) \in \mathbb{C}^{m\times n}$, we assume that there is a quantum oracle that can query its entries in the form of
\be
\label{oracleA}
\mathcal{O}_A:  \ket{i,j} \ket{b} \mapsto  \ket{i,j} \ket{b\oplus A_{ij}}.
\ee
For sparse matrices, two additional oracles that reveal the information of positions of nonzero entries are given, i.e.,
\bea
&& \mathcal{O}_R : \ket{i} \ket{j} \mapsto \ket{i} \ket{r_{ij}},
\label{oracleR} \\
&& \mathcal{O}_C : \ket{i} \ket{j} \mapsto \ket{c_{ij}} \ket{j},
\label{oracleC}
\eea
where $r_{ij}$ is the index for the $j$-th non-zero entry of the $i$-th row of $A$, and if there are less than $s$ non-zero entries, then it is $j+n$; $c_{ij}$ are defined similarly according to columns.

%\nikhil{To be a little more precise, I think we should define $\mathcal{O}_R : \ket{i} \ket{j} \ket{b} \mapsto \ket{i} \ket{j}\ket{b + r_{ij}~\mod{M}}$ where $M$ is an upper bound on all entries (assuming they're integers. If they're not, we'll need to do some more hacks here.). Similarly for the column oracle.}
%\cs{I agree with what you said. The above are standard notation from quantum computing and commonly used in this way, maybe we can just keep this form.}

In this setting, we focus on quantum query algorithms of the following form:
\be
\label{quantum alg1}
U_T \mathcal{O} U_{T-1} \mathcal{O} \cdots U_2 \mathcal{O} U_1 \, \ket{0..0},
\ee
where $\mathcal{O}\in \{I \otimes \mathcal{O}', \mathcal{O}' \otimes I: \mathcal{O}' \in\{ \mathcal{O}_A, \mathcal{O}_A^{-1}, \mathcal{O}_R, \mathcal{O}_R^{-1}, \mathcal{O}_C, \mathcal{O}_C^{-1}\}\}$, and $U_1,U_2, \ldots,U_T$ are unitaries independent of the oracles.

\item[The block-encoding model:]
For a matrix $A$, we assume that we are given a block-encoding of $A$, i.e., we are given the following unitary for some $\alpha\geq \|A\|$
\be \label{block-encoding}
W = \begin{pmatrix}
A/\alpha & \cdot \\
\cdot & \cdot
\end{pmatrix}.
\ee
In this setting, we focus on quantum algorithms of the following form:
\be
\label{quantum alg2}
U_T \widetilde{W} U_{T-1} \widetilde{W} \cdots U_2 \widetilde{W} U_1 \ket{0..0},
\ee
where $\widetilde{W} \in \{I\otimes W', W' \otimes I: W'\in \{W, W^\dag, c\text{-}W, c\text{-}W^\dag\}\}$ and $U_1,U_2,\ldots,U_T$ are unitaries independent of $W$. Here, $c\text{-}W$ means control-$W$.
\end{description}

Let $\ket{\psi_A}$ be the final state of (\ref{quantum alg1}) or (\ref{quantum alg2}). Regarding the output of quantum algorithms, if the goal is to produce a quantum state, then we assume that $\ket{\psi_A} = \sqrt{1-\varepsilon} \, \ket{0} \ket{\phi_0} + \sqrt{\varepsilon} \, \ket{1} \ket{\phi_1}$ for some $\varepsilon\in[0,1/3]$. There is flag qubit (i.e., $\ket{0}$) that tells us the desired state (i.e., $\ket{\phi_0}$). If the output state is a number, say a bit, then we assume that $\ket{\psi_A} = p \ket{0} \ket{\phi_0} + \sqrt{1-p^2} \ket{1} \ket{\phi_1}$. If the output is 0 then $|p|^2 \geq 2/3$, otherwise $|p|^2 \leq 1/3$. For the above two tasks, we only need to measure the first qubit. With high probability, we will obtain the desired result.

There are some connections between the above two models.
To see this, recall that the block-encoding of a sparse matrix is constructed as follows [8]: assume that $\max_{i,j} |A_{ij}|\leq 1$ for simplicity, define unitary
\be
\label{sparse BE 1}
U_L:\ket{0} \ket{i}  \rightarrow \ket{i}\ket{0}
\rightarrow \frac{1}{\sqrt{s}}\sum_{j=1}^s \ket{i} \ket{j}
\xrightarrow{\mathcal{O}_R}
\frac{1}{\sqrt{s}}\sum_{j=1}^s \ket{i} \ket{r_{ij}} .
\ee
And define unitary
\bea
U_R: && \ket{0} \ket{j} \ket{0}\ket{0}
\rightarrow \frac{1}{\sqrt{s}}\sum_{i=1}^s \ket{i} \ket{j} \ket{0}\ket{0}
\xrightarrow{\mathcal{O}_C \otimes I \otimes I}
\frac{1}{\sqrt{s}}\sum_{i=1}^s \ket{c_{ij}} \ket{j} \ket{0}\ket{0} \nonumber \\
&& \xrightarrow{\mathcal{O}_A\otimes I}
\frac{1}{\sqrt{s}}\sum_{i=1}^s \ket{c_{ij}} \ket{j} \ket{A_{c_{ij},j}} \ket{0} \nonumber  \\
&& \rightarrow  \frac{1}{\sqrt{s}}\sum_{i=1}^s \ket{c_{ij}} \ket{j} \ket{A_{c_{ij},j}} \left(A_{c_{ij},j} \ket{0} + \sqrt{1 - A_{c_{ij},j}^2} \ket{1} \right) \nonumber  \\
&& \xrightarrow{\mathcal{O}_A^{-1}\otimes I}  \frac{1}{\sqrt{s}}\sum_{i=1}^s \ket{c_{ij}} \ket{j} \ket{0} \left(A_{c_{ij},j} \ket{0} + \sqrt{1 - A_{c_{ij},j}^2} \ket{1} \right).
\label{sparse BE 2}
\eea
\beas
W &=&  (U_L\otimes I\otimes I)^\dag U_R
\\
&=& U_1 (\mathcal{O}_R^{-1} \otimes I\otimes I) (\mathcal{O}_A^{-1}\otimes I) U_2 (\mathcal{O}_A \otimes I) (\mathcal{O}_C\otimes I\otimes I) U_3 \\
&=& \begin{pmatrix}
A/s & \cdot \\
\cdot & \cdot
\end{pmatrix}
\eeas
is a block encoding of $A$, where $U_1, U_2, U_3$ are some unitaries independent of the oracles. As a result, if using this $W$, then the algorithm described in (\ref{quantum alg2}) is in the query model.

\subsection{Known results in these models}

It is possible that the oracles $\mathcal{O}_A,\mathcal{O}_R,\mathcal{O}_C$ or the block-encoding $W$ can be used in some ways that are very different from (\ref{quantum alg1}), (\ref{quantum alg2}) in a quantum algorithm, but most quantum algorithms for matrix problems known so far are in these two models. We below present some examples to support this.

\subsubsection{Quantum query algorithms for Boolean functions}

Let $f$ be a Boolean function. Given oracle access to $(x_1,\ldots,x_n) \in \{-1,1\}^n$, the goal is to compute $f(x_1,\ldots,x_n)$. A commonly used oracle is $\mathcal{O}: \ket{i} \ket{b} \mapsto \ket{i} \ket{b\oplus x_i}$, and a quantum query algorithm for evaluating $f(x_1,\ldots,x_n)$ works as the form $U_T \mathcal{O} U_{T-1} \mathcal{O} \cdots U_2 \mathcal{O} U_1 \, \ket{0}$. This fits into the model described in (\ref{quantum alg1}). Here we only need to view $(x_1,\ldots,x_n)$ as the diagonal matrix $\text{diag}(x_1,\ldots,x_n)$.

\subsubsection{Quantum eigenvalue transformation}

Let $A$ be a $p$-qubit operator, $\alpha, \varepsilon\in \mathbb{R}^+$ and $q\in \mathbb{N}$, then we say that the $(p+q)$-qubit unitary $W$ is an $(\alpha,q,\varepsilon)$-block-encoding of $A$, if $\|A - \alpha (\bra{0}^p\otimes I ) W (\ket{0}^p\otimes I )\| \leq \varepsilon.$
Namely, up to some error $\varepsilon$, $W$ has the form (\ref{block-encoding}).

Block-encoding is a building block of the quantum singular value transformation [8]. We below state it for Hermitian matrices. Let $P(x)$ be a polynomial of degree $d$. By \cite[Theorems 17 and 56]{gilyen2019quantum}, we can construct a $(1, q+2, 4d\sqrt{\varepsilon/\alpha})$ block encoding $\widetilde{W}$ of $P(A/\alpha)$ as follows.

\begin{itemize}
\item If $P(x)$ is an even polynomial, then there exist unitaries $U_1,\ldots,U_d$ at most depending on $P(x)$ such that
\be
\widetilde{W} = \prod_{k=1}^{d/2} \Big (U_{2k-1} W^\dag U_{2k} W\Big).
\ee
\item If $P(x)$ is an odd polynomial, then there exist unitaries  $W_1,\ldots,W_d$ at most  depending on $P(x)$ such that
\be
\widetilde{W} = U_1 W \prod_{k=1}^{(d-1)/2} \Big(U_{2k} W^\dag U_{2k+1} W\Big).
\ee
\item Generally, denote $\ell=\lfloor d/2 \rfloor$. Then
there exist unitaries $U_1, U_2, \ldots, U_{2\ell + 2} $ at most depending on $P(x)$ such that
\be
\widetilde{W}
= U_1
\begin{pmatrix}
I   & 0\\
0 & W
\end{pmatrix}
\left( \prod_{k=1}^{\ell}
(I \otimes W^\dag)
(I \otimes W) \right) U_{2\ell+2}.
\ee
\end{itemize}

As a block-encoding, we have
\[
\widetilde{W} \approx \begin{pmatrix}
P(A/\alpha) & \cdot \\
\cdot & \cdot
\end{pmatrix}.
\]
For any given state $\ket{\b} = V \ket{0\cdots 0}$, applying $\widetilde{W}$ to $\ket{0}\ket{\b}$ gives
\ket{\psi} = \ket{0}\otimes P(A/\alpha)\ket{\b} + \beta \ket{1} \otimes \ket{G},
where $\beta$ is the amplitude and $\ket{G}$ is some garbage state.
To obtain the state $\ket{P(A/\alpha) \b}$, we can apply amplitude amplification. A key operator that will be used many times to increase the success probability is the reflection $2 \ket{\psi} \bra{\psi} - I
= \widetilde{W} (2\ket{0}\ket{\b} \bra{0}\bra{\b} - I) \widetilde{W}^\dag$.
Now it is not hard to see that the above quantum algorithm that prepares the state $\ket{P(A/\alpha) \b}$ lies in the model described in (\ref{quantum alg2}). The uniatries $U_1,  U_2, \ldots, U_T$ are independent of $W$ but may depend on unitary $V$ that prepares the state $\ket{\b}$.

\subsubsection{Sparse Hamiltonian simulation and its applications}

The oracles (\ref{oracleA}), (\ref{oracleR}), (\ref{oracleC}) for sparse matrices were used by Berry and Childs [3] to do Hamiltonian simulation. Their quantum algorithm fits into the model (\ref{quantum alg1}).\footnote{Although not in the same model, the quantum algorithm for recommendation systems also has a similar structure~[13].} The key idea of their quantum algorithm is using quantum phase estimation to a discrete-time quantum walk described by a unitary $V = i S (2TT^\dag - I)$, where $S \ket{j,k}=\ket{k,j}$ and $T = \sum_j \ket{j} \ket{\phi_j} \bra{j}$. Here if the  Hamiltonian is $H=(H_{jk})$, then $\ket{\phi_j} = \sqrt{\frac{\varepsilon}{\Lambda_1}} \sum_k \sqrt{H_{jk}^*} \ket{k}\ket{0} + \sqrt{1-\frac{\varepsilon \sigma_j}{\Lambda_1}} \ket{\zeta_j} \ket{1}$, where $\Lambda_1$ is a known upper bound of $\|H\|_1$, $\sigma_j=\sum_k |H_{jk}|, \ket{\zeta_j}$ is some garbage state, and $\varepsilon\in(0,1]$ is a small parameter that ensures a lazy quantum walk. The state $\ket{\phi_j}$ can be prepared using $O(1)$ calls to the oracles $\mathcal{O}_A,\mathcal{O}_R,\mathcal{O}_C$, which is similar to the process (\ref{sparse BE 2}). This is indeed how the oracles are used in their whole quantum algorithm for Hamiltonian simulation. So it fits into the model (\ref{quantum alg1}).
Hamiltonian simulation is a useful subroutine of many quantum algorithms for linear algebra problems. A famous example is the HHL algorithm for linear systems of equations [10]. As a result, all these algorithms found so far based on [3] also fit into the model (\ref{quantum alg1}).

\subsection{Connections to quantum communication complexity}

Similar to the classical setting, we can also build connections between quantum protocols and quantum query algorithms for matrix problems. In the quantum case, we will mainly focus on the case that $k=2$, i.e., the Alice-Bob model. It turns out that this is enough for us.
One key reason is that in the quantum case, the cost will be roughly $kT$ when there are $k$ players. This is in sharp contrast to $k+T$ in the classical case (see Theorem \ref{thm:connection1}).
So we focus on the following simplified setting: Suppose Alice has a matrix $A^{(1)}\in \mathbb{R}^{m_1\times n}$ and a vector $ \b^{(1)} \in \mathbb{R}^{m_1}$, Bob has another matrix $A^{(2)}\in \mathbb{R}^{m_2\times n}$ and another vector $ \b^{(2)} \in \mathbb{R}^{m_2}$. Let $f(x)$ be a univariate function. Their goal is for Alice or Bob to output the state $\ket{f(A) \b}$, where
\be
A^{(1)} \\
A^{(2)} \\
\end{pmatrix}, \quad
\b=\begin{pmatrix}
\b^{(1)} \\
\b^{(2)}
\end{pmatrix}.
\label{matrix}
\ee

\begin{prop}
\label{thm:model 1}
Assume that $A\in \mathbb{C}^{m\times n}$ has the decomposition (\ref{matrix}).
For Alice or Bob to use the oracle $\mathcal{O}_A, \mathcal{O}_R$ or $\mathcal{O}_C$ once, they need to communicate $O(\log (mn))$ qubits.
\end{prop}

\begin{proof}
Let $\sum_{i,j} \alpha_{ij} \ket{i,j} \ket{0}$ be a quantum state in Alice's hand. To implement $\mathcal{O}_A$, she first applies $\mathcal{O}_{A^{(1)}}$ in her hand to the state to obtain $\sum_{i\leq m_1} \sum_j \alpha_{ij} \ket{i,j} \ket{A_{ij}} + \sum_{i> m_1} \sum_j \alpha_{ij} \ket{i,j} \ket{0}$. She then sends the state to Bob who applies $\mathcal{O}_{A^{(2)}}$ to it to obtain $\sum_{i,j} \alpha_{ij} \ket{i,j} \ket{A_{ij}}$. Bob then sends the state back to Alice. This costs $2\log(mn)$ qubits of communication. The protocol for using $\mathcal{O}_R$ is similar.

Next, we consider how to implement $\mathcal{O}_C$.
For $i\in\{1,2\}$, denote the number of nonzero entries of $j$-th column of $A^{(i)}$ as $s_j^{(i)}$. So Alice knows $\{s_1^{(1)}, \ldots, s_n^{(1)}\}$ and Bob knows  $\{s_1^{(2)}, \ldots, s_n^{(2)}\}$. For any state $\sum_{i,j} \alpha_{ij} \ket{i} \ket{j} $ in Alice's hand, she first
queries the indices in superposition $\sum_{i,j} \alpha_{ij} \ket{i} \ket{j} \ket{s_j^{(1)}} =
\sum_{i\leq s_j^{(1)}} \alpha_{ij} \ket{i} \ket{j} \ket{s_j^{(1)}}
+\sum_{i>s_j^{(1)}} \alpha_{ij} \ket{i} \ket{j} \ket{s_j^{(1)}} $.
Next, she applies
$\mathcal{O}_{C}$ for $A^{(1)}$ to this state  to obtain $\sum_{i\leq s_j^{(1)}} \alpha_{ij} \ket{c_{ij}} \ket{j} \ket{s_j^{(1)}}
+\sum_{i>s_j^{(1)}} \alpha_{ij} \ket{i+m_1} \ket{j} \ket{s_j^{(1)}} $.
Alice then sends the state to Bob and asks him to do similar operations for the second term. Here for the second term, Bob has to query the $(i-s_j^{(1)})$-th nonzero entry based on the oracle he has.
In the end, he sends the state back to Alice who undoes the query of $s_j^{(1)}$. This uses $2(2\log m+\log n)$ qubits of communication in total.
\end{proof}

From the above proof, if there are $k$-players and a coordinator, then for the coordinator to use the oracles once, they need $O(k\log(mn))$ qubits of communication.
The following result follows from step 1 of \cite[Proof of Proposition~14]{montanaro-shao2023}.

\begin{prop}
For each $i\in\{1,2\}$, let $W_i$ be an $(\alpha_i,1,0)$ block-encoding of $A^{(i)} \in \mathbb{R}^{m_i\times n}$. Then there is a quantum protocol for Alice or Bob to use an $(\sqrt{\alpha_1^2+\alpha_2^2},2,0)$ block-encoding of $A$ once with quantum communication complexity $O(\log(mn))$.
\end{prop}

With the above two propositions, it is not hard to obtain the following result.

\begin{thm}
\label{thm:model 2}
If there is a quantum algorithm of the form (\ref{quantum alg1}) or (\ref{quantum alg2}) of complexity $O(T)$, then there is a quantum protocol for the same task with quantum communication complexity $O(T \log (mn))$.
\end{thm}

\subsection{Applications: Lower bounds analysis of quantum query algorithms}

In this part, we present some applications of Theorem \ref{thm:model 2}. We will focus on a further simplified case than the setting (\ref{matrix}). Here suppose Alice has a matrix $A$ and Bob has a state $\ket{\b}$, their goal is to prepare the state $\ket{f(A)\b}$ by Alice or Bob, where $f$ is a public function. In the model (\ref{quantum alg1}) or (\ref{quantum alg2}), we now assume that the unitaries $U_1,U_2, \ldots, U_T$ can depend on the unitary that prepares the state $\ket{\b}$. We below use Theorem \ref{thm:model 2} to prove certain lower bounds in the quantum query model, either the number of queries or the number of block-encodings we must use. We can even obtain lower bounds with respect to the number of copies of $\ket{\b}$.
To be more exact, if it is Alice to output $\ket{f(A)\b}$, then there is no need to communicate the oracles or the block-encoding of $A$. What she needs is $U_1,U_2,\ldots,U_T$, which may depend on $\ket{\b}$. So we will obtain a lower bound on the number of copies of $\ket{\b}$.
If Bob is the one to output $\ket{f(A)\b}$, then we will obtain a lower bound on the number of calls of the block-encoding of $A$, or the number of calls of queries to $A$.

% As a corollary of Theorem \ref{thm:model 2}, we have

% \begin{cor}
% If there is a $T$-query quantum algorithm (\ref{quantum alg1}) or (\ref{quantum alg2}) that prepares $\ket{A^+\b}$ then there is a quantum protocol for Alice-Bob to prepare $\ket{A^+\b}$ that communicates $2T\log (mn)$ qubits.
% \end{cor}

\begin{prop}[Lower bounds for matrix inversion]
\label{prop:Lower bounds for matrix inversion}
Any quantum algorithm in the form (\ref{quantum alg1}) or (\ref{quantum alg2}) that prepares $\ket{A^+\b}$ requires making $\Omega(\kappa/\log (mn))$ calls to the oracles or block-encoding of $A$, and requires $\Omega(\kappa/\log (mn))$ copies of the state $\ket{\b}$.
\end{prop}

\begin{proof}
The proof is inspired by \cite[Theorem 10 (3)]{montanaro2022quantum}. Let Alice have $(a_1,\ldots,a_n)\in \{0,1\}^n$ and Bob have $(b_1,\ldots,b_n)\in \{0,1\}^n$. Alice constructs a diagonal matrix $A$ by setting $A_{ii}=1/\sqrt{n}$ if $a_i=1$ and $1$ if $a_i=0$. Bob constructs a quantum state $\ket{\b} \propto \sum_{b_i=1} \ket{i}$. Then the quantum state $\ket{A^{-1}\b} \propto \sqrt{n} \sum_{a_i=b_i=1} \ket{i} + \sum_{a_i=0,b_i=1} \ket{i} $. When there is only one intersection, then we will set index $i$ with $a_i=b_i=1$ with probability close to $1/2$. So if we have the state $\ket{A^{-1}\b}$, we then can solve the Set-Disjointness problem using constantly many invocations of the above, whose communication complexity is $\Omega(\sqrt{n})=\Omega(\kappa)$. By Theorem \ref{thm:model 2}, we obtain the claimed lower bound.
%\nikhil{Set-Disjointness is $\Theta(\sqrt{n})$ quantumly, the last line has something wrong.}
%\cs{Thanks, updated because $\kappa= \sqrt{n}$.}
\end{proof}

Note that in the query model, there is a similar proof based on Grover's algorithm [9]. Let $(x_1,\ldots,x_n)\in\{0,1\}^n$. Assume that there is an $i_0$ such that $x_{i_0}=1$ and $x_j=0$ for all $j\neq i_0$. It is known that the quantum query complexity of finding $i_0$ is $\Theta(\sqrt{n})$.
Let $A$ be a diagonal matrix with $A_{ii}=1/\sqrt{n}$ if $i=i_0$ and $A_{ii}=1$ if $i\neq i_0$. Let $\ket{\b}= \frac{1}{\sqrt{n}} \sum_i \ket{i}$. Then the quantum state $\ket{A^{-1}\b} = \frac{1}{\sqrt{2n-1}}(\sqrt{n} \ket{i_0} + \sum_{j\neq i_0} \ket{j})$. If we can prepare this state, then we can solve the search problem by measuring $\ket{A^{-1}\b}$. For this problem, the condition number $\kappa=\sqrt{n}$. So it gives a lower bound $\Omega(\kappa)$ of query complexity for the matrix inversion problem. Although the lower bound in Proposition \ref{prop:Lower bounds for matrix inversion} is weaker by a factor of $\log (mn)$, it gives a lower bound on the number of copies of the state $\ket{\b}$ at the same time. Moreover, the lower bounds also hold in the block-encoding model.

\begin{prop}[Lower bounds for matrix exponential]
Any quantum algorithm in the form (\ref{quantum alg1}) or (\ref{quantum alg2}) that prepares $\ket{e^{At}\b}$ requires making $\Omega(e^t/\log (mn))$ calls to the oracles or block-encoding of $A$, and requires $\Omega(e^t/\log (mn))$ copies of the state $\ket{\b}$.
\end{prop}

\begin{proof}
The proof is similar to the previous one. Imagine that Alice has $\a\in\{0,1\}^n$ and Bob has $\b\in\{0,1\}^n$. Alice constructs a diagonal matrix $A$ using $\a$. Then
\[
e^{At} \b = \sum_{i=1}^n e^{a_i t} b_i \ket{i}
= \sum_{a_i=b_i=1} e^{t} \ket{i} + \sum_{a_i=0,b_i=1} \ket{i}.
\]
Let $t= \frac{1}{2} \ln n$. If we can prepare $\ket{e^{At} \b}$, then sampling from it returns $i$ such that $a_i=b_i=1$ with probability close to $1/2$. So, just like in the previous proof, we can solve the Set-Disjointness problem using this routine constantly many times. As the lower bound of the Set-Disjointness problem is $\Omega(\sqrt{n})$ and $e^t=\sqrt{n}$, by Theorem \ref{thm:model 2}, we obtain a lower bound of $\Omega(e^{t}/\log(mn))$ for preparing the state $\ket{e^{At}\b}$.
%\nikhil{It's not clear how you concluded a lower bound of $\Omega(e^t)$.} \cs{Hope it is clear now, mainly because $e^t=\sqrt{n}$.}
\end{proof}

Recall that in \cite[Proposition 14]{an2022theory}, An et al.~showed that the number of copies of $\ket{\b}$ required to preparing state $\ket{e^{At}\b}$ is $\Omega(e^{t})$. In the above, we gave a simple proof of this and also proved the same lower bound on the query complexity with respect to $A$ at the same time.

\begin{prop}[Lower bounds for matrix powers]
Any quantum algorithm in the form (\ref{quantum alg1}) or (\ref{quantum alg2}) that prepares $\ket{A^d\b}$ requires making $\Omega((\kappa^d+1/\gamma)/\log(mn))$ calls to the oracles or block-encoding of $A$, and requires $\Omega((\kappa^d+1/\gamma)/\log(mn))$ copies of the state $\ket{\b}$.
\end{prop}

\begin{proof}
We will use similar constructions as the above proofs. Alice constructs a diagonal matrix $A$ with diagonal entry $A_{ii}=1$ if $a_i=1$ and $A_{ii}=\varepsilon$ if $a_i=0$. Bob uses this input to define the state $\ket{\b}$. Then the state $\ket{A^d \b}$ is proportional to $\sum_{a_i=b_i=1}\ket{i} + \varepsilon^d \sum_{a_i=0, b_i=1}\ket{i}$. We will choose $\varepsilon$ such that $\varepsilon^{2d} n = 1$. So we can solve the Set-Disjointness problem with high probability by measuring this state. The condition number of $A$ is $\kappa=1/\varepsilon$ and so $\kappa^d = \sqrt{n}$. It equals the complexity of the Set-Disjointness problem. So we obtain a lower bound of $\Omega(\kappa^d)$.
To prove $\Omega(1/\gamma)$, Alice sets $\varepsilon=0$. Now $\kappa=1$ and $\gamma = \|A^d\b\|/\|\b\| = 1/\sqrt{n}$.
\end{proof}

\section{Conclusions and open problems}

In this work, we built a connection between quantum-inspired classical algorithms and communication complexity. In particular, we showed that quantum-inspired classical algorithms can be efficiently simulated using communication protocols. Using this connection, we proved some lower bounds of quantum-inspired classical algorithms for some matrix-relevant problems. We also generalised the idea to the quantum case. The following are some open problems that we think merit further study.

\begin{enumerate}
\item The most exciting problem is to prove better lower bounds for the tasks mentioned in this work. We feel some new ideas are required. For example, the known results on communication complexity used in this paper are Set-Disjointness and Gap-Hamming problem in the coordinator model. If we have more candidate hard problems for communication in this model, we may use them to obtain better lower bounds.

\item In our proofs of the lower bounds, most constructions are based on sparse matrices with certain structures. This greatly simplified the analysis. We feel in the sparse case, more efficient quantum-inspired classical algorithms than those in~[2] can be found. So it is interesting to see how the sparsity is used in the design of such algorithms. For linear regressions, some results are known [24, 29].

\item In this paper, we only used the connection on one side, i.e., proving lower bounds. As discussed at the end of Section \ref{section:the connection}, via the connection, we can also propose efficient protocols for many matrix-relevant problems from quantum-inspired classical algorithms we know so far, e.g., [2, 24, 6]. So it is interesting to see some useful applications of this method in communication complexity. Theorem \ref{thm:connection2} might be helpful in this direction.
\end{enumerate}

\section*{Acknowledgements}

This research is supported by the National Key Research Project of China under Grant No. 2023YFA1009403.

\bibliographystyle{plain}
\begin{thebibliography}{10}

[1]
Dong An, Jin-Peng Liu, Daochen Wang, and Qi~Zhao.
\newblock A theory of quantum differential equation solvers: limitations and
\newblock {\em {\tt arXiv:2211.05246}}, 2022.

[2]
Ainesh Bakshi and Ewin Tang.
\newblock An improved classical singular value transformation for quantum
machine learning.
\newblock {\em {\tt arXiv:2303.01492}}, 2023.

[3]
Dominic~W Berry and Andrew~M Childs.
\newblock {Black-box Hamiltonian simulation and unitary implementation}.
\newblock {\em Quantum Information and Computation}, 12(1-2):29--62, 2012.

[4]
Amit Chakrabarti and Oded Regev.
\newblock An optimal lower bound on the communication complexity of
\newblock In {\em Proceedings of the forty-third annual ACM symposium on Theory
of computing}, pages 51--60, 2011.

[5]
Shantanav Chakraborty, Andr{\'a}s Gily{\'e}n, and Stacey Jeffery.
\newblock {The Power of Block-Encoded Matrix Powers: Improved Regression
Techniques via Faster Hamiltonian Simulation}.
\newblock In {\em 46th International Colloquium on Automata, Languages, and
Programming (ICALP 2019)}, volume 132, pages 33:1--33:14, 2019.
\newblock {\tt arXiv:1804.01973}.

[6]
Nai-Hui Chia, Andr{\'a}s~Pal Gily{\'e}n, Tongyang Li, Han-Hsuan Lin, Ewin Tang,
and Chunhao Wang.
\newblock Sampling-based sublinear low-rank matrix arithmetic framework for
dequantizing quantum machine learning.
\newblock {\em Journal of the ACM}, 69(5):1--72, 2022.
\newblock {\tt arXiv:1910.06151}.

[7]
Andr{\'a}s Gily{\'e}n, Zhao Song, and Ewin Tang.
\newblock An improved quantum-inspired algorithm for linear regression.
\newblock {\em Quantum}, 6:754, 2022.
\newblock {\tt arXiv:2009.07268}.

[8]
Andr{\'a}s Gily{\'e}n, Yuan Su, Guang~Hao Low, and Nathan Wiebe.
\newblock Quantum singular value transformation and beyond: exponential
improvements for quantum matrix arithmetics.
\newblock In {\em Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing}, pages 193--204, 2019.

[9]
Lov~K Grover.
\newblock A fast quantum mechanical algorithm for database search.
\newblock In {\em Proceedings of the twenty-eighth annual ACM Symposium on
Theory of computing}, pages 212--219, 1996.

[10]
Aram~W Harrow, Avinatan Hassidim, and Seth Lloyd.
\newblock Quantum algorithm for linear systems of equations.
\newblock {\em Physical Review Letters}, 103(15):150502, 2009.

[11]
Bala Kalyanasundaram and Georg Schintger.
\newblock The probabilistic communication complexity of set intersection.
\newblock {\em SIAM Journal on Discrete Mathematics}, 5(4):545--557, 1992.

[12]
Iordanis Kerenidis and Anupam Prakash.
\newblock Quantum recommendation systems.
\newblock In {\em 8th Innovations in Theoretical Computer Science Conference
(ITCS 2017)}, page 49:1–49:21, 2017.
\newblock {\tt arXiv:1603.08675}.

[13]
Iordanis Kerenidis and Anupam Prakash.
\newblock {Quantum Recommendation Systems}.
\newblock In Christos~H. Papadimitriou, editor, {\em 8th Innovations in
Theoretical Computer Science Conference (ITCS 2017)}, volume~67 of {\em
Leibniz International Proceedings in Informatics (LIPIcs)}, pages
49:1--49:21, Dagstuhl, Germany, 2017. Schloss Dagstuhl--Leibniz-Zentrum fuer

[14]
Yi~Li, Honghao Lin, and David Woodruff.
\newblock {$\ell_p$-Regression in the Arbitrary Partition Model of
\newblock In {\em The Thirty Sixth Annual Conference on Learning Theory}, pages
4902--4928. PMLR, 2023.

[15]
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.
\newblock Quantum algorithms for supervised and unsupervised machine learning.
\newblock {\em {\tt arXiv:1307.0411}}, 2013.

[16]
Ashley Montanaro.
\newblock Quantum states cannot be transmitted efficiently classically.
\newblock {\em Quantum}, 3:154, 2019.

[17]
Ashley Montanaro and Changpeng Shao.
\newblock Quantum and classical query complexities of functions of matrices.
\newblock {\em {\tt arXiv:2311.06999}}, 2023.

[18]
Ashley Montanaro and Changpeng Shao.
\newblock Quantum communication complexity of linear regression.
\newblock {\em ACM Transactions on Computation Theory (accepted)}, 2023.
\newblock {\tt arXiv:2210.01601}.

[19]
Michael~A Nielsen and Isaac~L Chuang.
\newblock {\em {Quantum Computation and Quantum Information}}.
\newblock Cambridge university press, 2010.

[20]
Jeff~M Phillips, Elad Verbin, and Qin Zhang.
\newblock Lower bounds for number-in-hand multiparty communication complexity,
made easy.
\newblock In {\em Proceedings of the twenty-third annual ACM-SIAM Symposium on
Discrete Algorithms (SODA)}, pages 486--501. SIAM, 2012.
\newblock {\tt arXiv:1107.2559}.

[21]
Anup Rao and Amir Yehudayoff.
\newblock {\em Communication Complexity: and Applications}.
\newblock Cambridge University Press, 2020.

[22]
Alexander~A Razborov.
\newblock On the distributional complexity of disjointness.
\newblock In {\em Automata, Languages and Programming: 17th International
Colloquium Warwick University, England, July 16--20, 1990 Proceedings 17},
pages 249--253. Springer, 1990.

[23]
Changpeng Shao.
\newblock An improved quantum algorithm for low-rank rigid linear regressions
with vector solution outputs.
\newblock {\em {\tt arXiv:2301.06107}}, 2023.

[24]
Changpeng Shao and Ashley Montanaro.
\newblock Faster quantum-inspired algorithms for solving linear systems.
\newblock {\em ACM Transactions on Quantum Computing}, 3(4):1--23, 2022.
\newblock {\tt arXiv:2103.10309}.

[25]
Ewin Tang.
\newblock A quantum-inspired classical algorithm for recommendation systems.
\newblock In {\em Proceedings of the 51st annual ACM SIGACT Symposium on Theory
of Computing}, pages 217--228, 2019.
\newblock {\tt arXiv:1807.04271}.

[26]
Hermann Weyl.
\newblock Das asymptotische verteilungsgesetz der eigenwerte linearer
partieller differentialgleichungen (mit einer anwendung auf die theorie der
\newblock {\em Mathematische Annalen}, 71(4):441--479, 1912.

[27]
Ronald~de Wolf.
\newblock Quantum communication and complexity.
\newblock {\em Theoretical Computer Science}, 287(1):337--353, 2002.

[28]
Andrew Chi-Chih Yao.
\newblock Some complexity questions related to distributive computing
(preliminary report).
\newblock In {\em Proceedings of the 11th annual ACM Symposium on Theory of
Computing}, pages 209--213, 1979.

[29]
Qian Zuo and Tongyang Li.
\newblock Fast and practical quantum-inspired classical algorithms for solving
linear systems.
\newblock {\em {\tt arXiv:2307.06627}}, 2023.

\end{thebibliography}

\appendix

\section{Another connection}
\label{section:another connection}

Apart from the connection discussed in Section \ref{section:the connection}, another way to see the connection, which should be more general in practice, is considering $A=\sum_{i=1}^k \lambda_i A^{(i)}$ and $\b=\sum_{i=1}^k \mu_i \b^{(i)}$.
First, we list some definitions.

\begin{defn}
Let $p=(p_1,\ldots,p_n),q=(q_1,\ldots,q_n) \in \mathbb{R}^n_{\geq 0}$ be two distributions, i.e., $\sum p_i=\sum q_i=1$ we say $p$ $\phi$-oversamples $q$ if for all $i\in [n]$, $p_i \geq q_i/\phi$.
\end{defn}

\begin{defn}[Oversampling and query access to a vector]
\label{defn:oversampling}
Let $\v=(v_1,\ldots,v_n) \in \mathbb{C}^n$ and $\phi\geq 1$, we have $SQ_{\phi}(\v)$, $\phi$-oversampling and query access to $\v$, if we have $Q(\v)$ and $SQ(\tilde{\v})$ for some vector $\tilde{\v} =(\tilde{v}_1,\ldots,\tilde{v}_n) \in \mathbb{C}^n$ satisfying $\|\tilde{\v}\|^2 = \phi \|\v\|$ and $|\tilde{v}_i|^2 \geq |v_i|^2$ for all $i\in [n]$.
\end{defn}

\begin{defn}[Oversampling and query access to a matrix]
Let $A=(A_{ij}) \in \mathbb{C}^{m\times n}$ and $\phi\geq 1$, we have $SQ_{\phi}(\v)$, $\phi$-oversampling and query access to $\v$, if we have $Q(A)$ and $SQ(\widetilde{A})$ for some matrix $\widetilde{A}=(\widetilde{A}_{ij}) \in \mathbb{C}^{m\times n}$ satisfying $\|\widetilde{A}\|_{\F}^2 = \phi \|A\|_{\F}^2$ and $|\widetilde{A}_{ij}|^2 \geq |A_{ij}|^2$ for all $(i,j)\in [m]\times [n]$.
\end{defn}

\begin{lem}[Lemma 3.5 of [6]]
\label{lem3.5}
Suppose we are given $SQ_{\phi}(\v)$ and $\delta\in(0,1]$, then we can sample from $D_{\v}$ with probability $\geq 1-\delta$ with $O(\phi \log(1/\delta))$ applications of $SQ_{\phi}(\v)$. We can also estimate $\|\v\|$ to $\varepsilon$ multiplicative error for $\varepsilon \in (0,1]$ with probability  $\geq 1-\delta$ with $O(\varepsilon^{-2})$ applications of $SQ_{\phi}(\v)$.
\end{lem}

\begin{thm}
\label{thm:connection2}
Assume that player $\P_i$ holds a matrix $A^{(i)}\in \mathbb{R}^{m\times n}$ and a vector $\b^{(i)}\in \mathbb{R}^{m}$ whose entries are specified by $O(\log q)$ bits, where $i\in [k]$. Let $A=\sum_i \lambda_i A^{(i)}$ and $\b=\sum_i \mu_i \b^{(i)}$. Then in the coordinator model, we have the following.

\begin{itemize}

\item For the coordinator to use $SQ(\b)$ $O(T)$ times, it costs $O(kT\phi_b\log (qm))$ bits of communication, where
\[
\phi_b = k \frac{\sum_i  \|\mu_i \b^{(i)}\|^2 }{\|\b \|^2}.
\]

\item For the coordinator to use $SQ(A)$ $O(T)$ times, it costs $O(kT\phi_A \log (qmn))$ bits of communication, where
\[
\phi_A = k \frac{\sum_i  \|\lambda_i A^{(i)}\|_\F^2}{\|A\|_\F^2}.
\]

\end{itemize}
\end{thm}

In comparison, Theorem \ref{thm:connection1} has a lower complexity than the one stated in Theorem \ref{thm:connection2}. This is the main reason why we choose to use Theorem \ref{thm:connection1} to prove lower bounds.
However, the case discussed in Theorem \ref{thm:connection2} seems more powerful since, for example, the linear regression $\argmin\|A\x-\b\|$ with $A,\b$ given in (\ref{thm:eq}) is equivalent to $\argmin_\x\|\sum_i (A^{(i)})^\T A^{(i)} \x - \sum_i (A^{(i)})^\T \b^{(i)}\|$, which is a special case of the one discussed above. We feel Theorem \ref{thm:connection2} can play more important roles in designing efficient classical protocols for problems, such as machine learning problems or Hamiltonian simulation.

\begin{proof}
First, we show how the coordinator uses $SQ(\b)$.
We will use $b^{(i)}_j$ and $b_j$ to denote the $j$-th entry of $\b^{(i)}$ and $\b$ respectively.
Given $SQ(\b^{(i)})$ for all $i\in [k]$, we can construct $SQ_{\phi_b}(\b)$ (see Definition \ref{defn:oversampling} for $SQ_{\phi_b}$) in the following way, which is based on the proof of \cite[Lemma 3.6]{chia2022sampling} and also provides a protocol for the coordinator to use $SQ(\b)$.

\begin{enumerate}
\item Obtain $Q(\b)$: For each $j\in[m]$, we can compute $b_j=\sum_{i=1}^k \mu_i b^{(i)}_j$ by querying all $b^{(i)}_j$.

\item Obtain $SQ(\tilde{\b})$: Define $\tilde{\b}$ via
\[
\tilde{b}_j = \sqrt{k \sum_{i=1}^k |\mu_i b^{(i)}_j|^2}, \quad j \in [m].
\]
It is easy to check that $\|\tilde{\b}\|^2 = \phi_b \|\b\|^2$ and $|\tilde{b}_j| \geq |b_j|$ for all $j\in [m]$.
\begin{enumerate}
\item Query for $\|\tilde{\b}\|^2$: We can compute $\|\tilde{\b}\|^2 = k \sum_i  \|\mu_i \b^{(i)}\|^2$ directly by querying  $\|\b^{(i)}\|^2$ for all $i\in[k]$.
\item Query for $\tilde{b}_j$: We can compute $\tilde{b}_j$ by querying $ b^{(i)}_j$ for all $i\in[k]$.
\item Sample from $\tilde{\b}$: We first sample an index $i\in[k]$ with probability $\|\mu_i \b^{(i)}\|^2/\sum_j\|\mu_j \b^{(j)}\|^2$, then take a sample $j\in[m]$ from the distribution defined by $\title{\b}^{(i)}$. We can check that the probability is
\[
\sum_{i=1}^k \frac{\|\mu_i \b^{(i)}\|^2}{\sum_j\|\mu_j \b^{(j)}\|^2} \frac{|b^{(i)}_j|^2}{\|\b^{(i)}\|^2}
= \frac{\sum_{i=1}^k |\mu_i b^{(i)}_j|^2}{\sum_j\|\mu_j \b^{(j)}\|^2}
= \frac{|\tilde{b}_j|^2}{\|\title{\b}\|^2}.
\]
\end{enumerate}
\end{enumerate}

The above procedure provides a protocol for the coordinator to use $SQ_{\phi_b}(\b)$, from which the coordinator can construct $SQ(\b)$. Firstly, querying for entries of $\b$ is straightforward, which costs $O(k \log q)$ bits of communication. Secondly, query for $\|\tilde{\b}\|^2$ and $\tilde{b}_j$ are also straightforward, which costs $O(k \log q)$ bits of communication. Thirdly, to sample from $\tilde{\b}$, player $\P_i$ first sends $\|\tilde{\b}^{(i)}\|$ to the coordinator. This costs $O(k \log (qm))$ bits of communication. Now the coordinator can do step (2.c) discussed in the above procedure with $O(\log q)$ bits of communication with player $\P_i$. In summary, for the coordinator to use $SQ_{\phi_b}(\b)$ $O(T)$ times, they use $O(T\log q+kT\log (qm))=O(kT\log (qm))$ bits of communication. Combining Lemma \ref{lem3.5}, it costs $O(kT\phi_b \log (qm))$ bits of communication for the coordinator to use $SQ(\b)$ $O(T)$ times.

Similar results also hold for linear combinations of matrices.
Given $SQ(A^{(i)})$ for all $i\in [k]$, we can construct $SQ_{\phi}(A)$ in the following way, which is based on the proof of \cite[Lemma 3.9]{chia2022sampling}. Below for any matrix $M$, we use $M_{i,j}$ to denote its $(i,j)$-th entry and use $M_{i*}$ to denote the $i$-th row.

\begin{enumerate}
\item Obtain $Q(A)$: For each $(i,j)\in[m]\times [n]$, we can compute $A_{i,j}=\sum_{t=1}^k \lambda_t A^{(t)}_{i,j}$ by querying all $A^{(t)}_{i,j}$.

\item Obtain $SQ(\tilde{A})$: Define $\tilde{A}$ via
\[
\tilde{A}_{i,j} = \sqrt{k \sum_{t=1}^k |\lambda_t A^{(t)}_{i,j}|^2},
\]
It is easy to check that $\|\tilde{A}\|_\F^2 = \phi_A \|A\|_\F^2, |\tilde{A}_{ij}| \geq |A_{ij}|$ for all $(i,j)\in[m]\times [n]$.
\begin{enumerate}
\item Query for $\|\tilde{A}\|_\F^2$: We can compute $\|\tilde{A}\|_\F^2 = \sum_{t=1}^k  \|\lambda_t A^{(t)}\|_\F^2$ directly by querying  $\| A^{(i)}\|_\F^2$ for all $i\in[k]$.
\item Query for $\tilde{A}_{i,j}$: We can compute $\tilde{A}_{i,j}$ by querying $A^{(t)}_{i,j}$ for all $t\in[k]$.
\item Sample from $i$-th row $\tilde{A}_{i*}$: We first sample an index $s\in[k]$ with probability
$\frac{\|\lambda_s A^{(s)}_{i*}\|^2}{\sum_{t=1}^k \|\lambda_t A^{(t)}_{i*}\|^2},$
then take a sample $j\in[m]$ from $A^{(s)}_{i*}$. The probability of seeing $j$ is
\[
\sum_{s=1}^k\frac{\|\lambda_s A^{(s)}_{i*}\|^2}{\sum_{t=1}^k \|\lambda_t A^{(t)}_{i*}\|^2} \frac{|A^{(s)}_{i,j}|^2}{\|A^{(s)}_{i*}\|^2}
= \frac{\sum_{s=1}^k|\lambda_s A^{(s)}_{i,j}|^2}{\sum_{t=1}^k \|\lambda_t A^{(t)}_{i*}\|^2}
= \frac{|\widetilde{A}_{ij}|^2}{\|\widetilde{A}_{i*}\|^2}.
\]
\item Obtain $SQ(\a)$ where $\tilde{\a}=(\|\tilde{A}_{1*}\|, \ldots, \|\tilde{A}_{m*}\|)$: It is obvious that $\|\tilde{A}_{i*}\|^2 = k \sum_t \|\lambda_t \tilde{A}^{(t)} _{i*}\|^2$. So we can compute it by querying $\|\tilde{A}^{(t)} _{i*}\|^2$ for all $t\in[k]$. To sample from $\tilde{\a}$, we first sample $s\in[k]$ with probability ${\|\lambda_s A^{(s)}\|_\F^2}/{\sum_t \|\lambda_t A^{(t)}\|_\F^2}$, then take a sample $i\in[m]$ from the distribution defined by $\a^{(s)} = (\|A^{(s)}_{1*}\|,\ldots,\|A^{(s)}_{m*}\|)$. The probability is
\[
\sum_s\frac{\|\lambda_s A^{(s)}\|_\F^2}{\sum_t \|\lambda_t A^{(t)}\|_\F^2}
\frac{\|A^{(s)}_{i*}\|^2}{\|A^{(s)}\|_\F^2}
=\frac{\sum_s\|\lambda_s A^{(s)}_{i*}\|^2}{\sum_t \|\lambda_t A^{(t)}\|_\F^2}
\]
\end{enumerate}
\end{enumerate}

The analysis for the coordinator to use $SQ_{\phi}(A)$ is similar. For the coordinator to query $A_{i,j}, \tilde{A}_{i,j}$, it costs $O(k \log q)$ bits of communication. To query $\|\tilde{A}\|_\F^2=k\sum_i \|\lambda_i A^{(i)}\|_\F^2$, it costs $O(k\log (qmn))$ bits of communication. Here $O(\log (qmn))$ is the number of bits used to specify $\|A^{(i)}\|_\F^2$. To query for $\|\tilde{A}_{i*}\|^2 = k \sum_t \|\lambda_t A^{(t)} _{i*}\|^2$, it costs $O(k \log (qn))$ bits of communication. To sample from $\widetilde{A}_{i*}$, each player $\P_i$ first sends $\|A^{(s)}_{i*}\|$ to the coordinator, this uses $O(k(\log q+\log n))$ bits of communication. To sample from $\tilde{\a}$, since the coordinator already has the information of $\|A^{(i)}\|_\F^2$ for all $i\in[k]$, this step now only costs $O(\log q)$ bits of communication (namely communicate with player $\P_i$ once for some $i$).
Finally, to sample from $\tilde{A}_{i*}$, each player needs to send $\|A^{(s)}_{i*}\|$ to the coordinator, then the coordinator has the distribution of seeing $s$ with probability ${\|\lambda_s A^{(s)}_{i*}\|^2}/{\sum_t \|\lambda_t A^{(t)}_{i*}\|^2},$ this uses $O(\log (qn))$ bits of communication. Thus for the coordinator to use $SQ_{\phi_A}(A)$ $O(T)$ times, it costs $O(T\log (qn)+kT\log (qmn))$ bits of communication. By Lemma \ref{lem3.5}, it costs $O(kT\phi_A \log (qmn))$ bits of communication for the coordinator to use $SQ(A)$ $O(T)$ times.
\end{proof}

\end{document}

Check \cite{stewart1977perturbation}.

Since $D$ is singular, $D^2 + \varepsilon^2 (\ket{\b_2}\bra{\b_2} + \cdots +  \ket{\b_k}\bra{\b_k})$ can be nonsingular, it has some very small singular values. When we compute its inverse, these small singular values will cause a problem if we compute their inverse. So we should ignore them.

\section{Proof of Theorem \ref{main theorem2}}

We below indeed reanalyze the complexity of the algorithm presented in \cite[Theorem 12]{shao2022faster}, and show how it can be modified. The key finding is a better choice of a parameter stated in (\ref{choice of d}). This will lead to the claimed result stated in Theorem \ref{main theorem2}.
We first briefly recall the notation and the main idea used in [24].

Consider the linear regression problem $\argmin\|A\x-\b\|$, where $A\in \mathbb{R}^{m\times n}, \b\in \mathbb{R}^{m}$.
We use $A_{i*}, A_{*j}$ to denote the $i$-th row and $j$-th column respectively. The matrix $\widetilde{A}$ is obtained by normalising the rows of $A$, and the vector $\tilde{\b}\in \mathbb{R}^{m}$ is defined via $\tilde{b}_i = b_i/\|A_{i*}\|$. We denote $\kappa_F = \|A\|_{\F}/\delta, \kappa = \|A\|/\delta$. Using this notation, the result in Theorem \ref{main theorem2} becomes $\widetilde{O}(\kappa_F^4\kappa^2/\varepsilon^2)$. Finally, we denote $\x_* = A^+\b$.

The algorithm of [24] is based on the Kaczmarz method, described below: Let $\x_0$ be an arbitrary initial approximation to the solution.
For $k = 0, 1, \ldots$, compute
\be \label{Randomized Kaczmarz algorithm}
\x_{k+1}  =  \x_k  + \frac{b_{r_k} - \langle A_{r_k*}| \x_k \rangle   }{\|A_{r_k*}\|^2} A_{r_k*},
\ee
where $r_k$ is chosen from $[m]$ randomly with probability $\|A_{r_k*}\|^2/\|A\|_{\F}^2$. To apply the Kaczmarz method, we consider its dual form:
\be \label{updating for sparse case}
\y_{k+1} = \y_{k} +  \frac{b_{r_k}  - \langle A_{r_k*} |  A^\T | \y_{k} \rangle }{\|A_{r_k*}\|^2}  \e_{r_k},
\ee
where $\{\e_1,\ldots,\e_m\}$ is the standard basis of $\mathbb{R}^m$. The connection is $\x_k =A^\T \y_k$.

The main idea of the algorithm presented in [24] is computing $\y_T$ first for some $T$, then computing $SQ(\x_T)$. For this,
we modify the updating rule of $\y$ to:
\be \label{updating for y'}
\y_{k+1} = \y_{k}  +  \frac{1 }{\|A_{r_k*}\|} \left( \tilde{b}_{r_k} - \frac{1}{d}\sum_{j\in S} \tilde{A}_{r_k,j} \langle A_{*j}|\y_k  \rangle \frac{\|A\|_F^2}{\|A_{*j}\|^2}
\right) \e_{r_k} .
\ee
where $S$ is a sequence of row indices such that $i$-th index is chosen with probability $\|A_{i*}\|^2/\|A\|_{\F}^2$. In matrix form, let
\be \label{sampling matrix}
D =
\sum_{j\in S}
\frac{\|A\|_F^2}{d \|A_{*j}\|^2} \ket{j} \bra{j},
\ee
\be
\y_{k+1} = \y_k  + \frac{\tilde{b}_{r_k} - \langle \tilde{A}_{r_k*} | A^\dag| \y_{k} \rangle }{\|A_{r_k*}\|}  \e_{r_k} + \frac{\langle \tilde{A}_{r_k*} |(I-D) A^\dag| \y_{k} \rangle }{\|A_{r_k*}\|}  \e_{r_k}.
\label{updating for y'-matrix form}
\ee
This implies that the updating rule for $\x_k$ becomes
\be
\x_{k+1}  = \x_k + (\tilde{b}_{r_k} - \langle \tilde{A}_{r_k*} |\x_{k} \rangle )  \tilde{A}_{r_k*}
+ \langle\tilde{A}_{r_k*} | I - D |\x_{k} \rangle \tilde{A}_{r_k*} .
\label{randomized procedure}
\ee

$\mu_k = \langle \tilde{A}_{r_k*} |(I-D) A^\dag| \y_{k} \rangle$.
In \cite[Lemma 9]{shao2022faster}, it was shown that
\be
\E_D[\mu_k]=0, \quad
{\rm Var}_D[\mu_k] \leq   \frac{\|A\|_{\F}^2 \|\x_k\|^2}{d\min_{j \in [n]} \|A_{*j}\|^2} .
\ee
Indeed, the bound for ${\rm Var}_D[\mu_k]$ is too large. More precisely, from the calculation of ${\rm Var}_D[\mu_k]$ in the proof of \cite[Lemma 9]{shao2022faster}, we indeed have
\be
\label{upper bound of the variance}
{\rm Var}_D[\mu_k] \leq \frac{1}{d}  \sum_{j=1}^n
\tilde{A}_{r_k,j}^2 x_{k,j}^2 \frac{\|A\|_F^2}{\|A_{*j}\|^2}.
\ee
If we use this bound, then we can show that it suffices to choose
\be
\label{choice of d}
d = \widetilde{O}(\kappa_F^2/\varepsilon^2)
\ee
rather than $d = \widetilde{O}(\kappa_F^4/\varepsilon^2)$ stated in [24].
Consequently, the algorithm presented in \cite[Theorem 12]{shao2022faster} has complexity $\widetilde{O}(\kappa_F^4 \kappa^2/\varepsilon^2)$.

To show (\ref{choice of d}), recall that in the proof of \cite[Proposition 10]{shao2022faster}, we have
\be
\E[\|\x_{k+1} - \x_*\|^2]
\left(1 - \E\left[
\langle \frac{\x_{k} - \x_*}{\|\x_{k} - \x_*\|}| \tilde{A}_{r_k*} \rangle^2 \right]\right) \E[\|\x_{k} - \x_*\|^2] + \E[\mu_k^2].
\ee
To be more exact, it should be
\be
\E \Big [\E_D[\|\x_{k+1} - \x_*\|^2] \Big]
\left(1 - \E_{r_k}\left[
\langle \frac{\x_{k} - \x_*}{\|\x_{k} - \x_*\|}| \tilde{A}_{r_k*} \rangle^2 \right]\right) \E[\|\x_{k} - \x_*\|^2] + \E_{r_k} \Big[\E_D[\mu_k^2]\Big],
\ee
where $\E$ is taking expectation values with respect to the updating rule (\ref{randomized procedure}).

By (\ref{upper bound of the variance}), we have
\bea
\E_{r_k} \Big[\E_D[\mu_k^2]\Big] &\leq& \E_{r_k} \Bigg[\frac{1}{d}  \sum_{j=1}^n
\tilde{A}_{r_k,j}^2 x_{k,j}^2 \frac{\|A\|_{\F}^2}{\|A_{*j}\|^2} \Bigg] \\
&=& \frac{1}{d} \sum_{r_k=1}^m \sum_{j=1}^n
\tilde{A}_{r_k,j}^2 x_{k,j}^2 \frac{\|A\|_{\F}^2}{\|A_{*j}\|^2} \frac{\|A_{r_k*}\|^2}{\|A\|_{\F}^2} \\
% &=& \frac{1}{d} \sum_{r_k=1}^n \sum_{j=1}^n
% A_{r_k,j}^2 x_{k,j}^2 \frac{1}{\|A_{*j}\|^2}  \\
&=& \frac{\|\x_k\|^2}{d}.
\eea
Following the proof of \cite[Proposition 10]{shao2022faster}, we now have
\bea
\E[\|\x_{k+1} - \x_*\|^2]
\left(1 - \kappa_F^{-2} \right) \E[\|\x_{k} - \x_*\|^2] + \frac{1}{d} \E[\|\x_k\|^2] \\
\left(1 - \kappa_F^{-2} \right) \E[\|\x_{k} - \x_*\|^2] + \frac{2}{d} (\|\x_*\|^2 + \E[\|\x_k-\x_*\|^2]) \\
(1 - \kappa_F^{-2} + \frac{2}{d} ) \E[\|\x_{k}  - \x_*\|^2] + \frac{2}{d} \|\x_*\|^2 .
\eea
To ensure $\rho:=1 - \kappa_F^{-2} + \frac{2}{d} <1$ and the final error is bounded by $\varepsilon^2$, we only need to choose $d = O(\kappa_F^2\log(1/\varepsilon^2)/\varepsilon^2)$. The convergence rate is $T=\kappa_F^2 \log(1/\varepsilon^2)$, so $T/d = \varepsilon^2$. It is also easy to show that $\rho^T = O(\varepsilon^2)$. The analysis in Appendix B of [24] can be done similarly.
Therefore, the algorithm stated in \cite[Theorem 12]{shao2022faster} indeed has complexity $\widetilde{O}(\kappa_F^4 \kappa^2/\varepsilon^2)$.

Regarding this last part, in Appendix A of [24], it was shown that
\be
\phi= O\left(T^2+ T^2 \frac{\kappa^2 \|\b\|Z}{\|A\|_{\F}^2\|\x_*\|^2}  \right) ,
\ee
where $\phi$ is a complexity measure and $Z = \min\|A\x-\b\|$. We decompose $\b = A \x_* + \c$, where $\c$ has norm $Z$ and lies outside of the column space of $A$. Let $Z=\eta \|\b\|$, then  $\|\x^*\|^2 \geq \|A\x_*\|^2/\|A\|^2 = (1-\eta^2)\|\b\|^2/\|A\|^2$. So
\be
T^2 \frac{\kappa^2 \|\b\|Z}{\|A\|_{\F}^2\|\x_*\|^2}
\leq
\frac{\eta}{1-\eta^2} \kappa_F^2 \kappa^4.
\ee
This means $\phi = O(\kappa_F^4 + \frac{\eta}{1-\eta^2} \kappa_F^2 \kappa^4)$, which is smaller than $\kappa_F^4\kappa^2$ stated in Appendix A of [24]. Similarly, in the analysis of Appendix C of [24], we indeed have
$\phi = O(\kappa_F^2 \kappa^2 + \frac{\eta}{1-\eta^2} \kappa^6)$, which is smaller than $\kappa_F^2\kappa^4$ claimed in Appendix C of [24]. Thus, combining the complexity analysis of \cite[Theorem 12]{shao2022faster}, the exact complexity is
\be
\widetilde{O} \left(\kappa_F^4 \kappa^2/\varepsilon^2 + \frac{\eta}{1-\eta^2} \kappa_F^2 \kappa^6\right).
\ee
So if $\eta$ is small, i.e., if $\b$ almost lies in the column space of $A$, then the complexity is basically dominated by the first term.

\subsection{Dense case}

\subsection{Sparse case}

In this case, we will use the hardness of the 2-player disjointness problem. Recall that in the disjointness problem, there are two players and a coordinator. Player $\P_1$ has $\x=(x_1,\ldots,x_n) \in \{0,1\}^n$, player $\P_2$ has $\y= (y_1,\ldots,y_n)\in \{0,1\}^n$, they want to determine if there is an $i$ such that $x_i=y_i=1$. The communication complexity is $\Theta(n)$. Without loss of generality, we assume that the hamming weights of $\x,\y$ are $\Theta(n)$.

To prove a lower bound, we

\cs{The problem is $\|A\x_* - \b\|$ is too large.}

\cs{Consider query, sample and norm independently}

Gap-Hamming problem [4].
Let $\a,\b\in\{1/\sqrt{n},-1/\sqrt{n}\}^n$, consider
\[
1 &   &        & a_1 \\
& 1 &        & \vdots \\
&   & \ddots & a_n \\
&   &        & 1
\end{pmatrix},
\b = \begin{pmatrix}
b_1 \\
\vdots \\
b_n \\
\end{pmatrix},
\]
then the solution is
\[
\x=\ket{n+1} + \sum_{i=1}^n (b_i-a_i) \ket{i}.
\]
\[
\|\x\|^2 = 1 +  \sum_{i=1}^n (b_i-a_i)^2 = 3 -2 \sum_{i=1}^n a_i b_i.
\]
If we can compute $\|\x\|^2 \pm \varepsilon$, then we can solve the Gap-Hamming problem.
\[
\|A\|_\F^2 = n, \sigma_{\min}^2 \approx \frac{\sqrt{5}-1}{2}.
\]
Approximating $\langle a|b\rangle \pm \varepsilon$ costs $\Omega(1/\varepsilon^2)$.  This gives a lower bound of $\Omega(1/\varepsilon^2)$.

\[
a_1 & -1       &  \\
& a_2/a_1 & \ddots \\
&     & \ddots & -1 \\
&     &        & a_n/a_{n-1}
\end{pmatrix},
\b = \begin{pmatrix}
b_1 \\
b_2 \\
\vdots \\
\end{pmatrix},
\]
then the solution is
\[
\x = \begin{pmatrix}
a_1b_1+\cdots+a_nb_n \\
\vdots \\
(a_ib_i+\cdots+a_nb_n)/a_{i-1}  \\
\vdots \\
\end{pmatrix}.
\]
So if we can query $x_1$, then we can compute the inner product, which is lower bounded by $\Omega(1/\varepsilon^2)$.

Given two distributions $P=(p_1,\ldots,p_n)$ and $Q=(q_1,\ldots,q_n)$, where $q_i\neq 0$ for all $i$, how to sample from $R=\frac{1}{\sqrt{N}}(p_1/q_1,\ldots,p_n/q_n)$, where $N=\sum_i p_i^2/q_i^2$?

Use rejection sampling:
The proposal distribution $F$ is $P$, and the target distribution is $R$. Let $M=q_{\max}^2/q_{\min}^2$, then
\[
U(i):=\frac{R(i)}{F(i) M} = \frac{1}{q_i^2 N M} \leq 1,
\]
By Hoeffding's inequality, computing $N':=N + \varepsilon$ costs
$\varepsilon^{-2} (q_{\min}^{-2}-q_{\max}^{-2})^2.$ We actually define
\[
U(i) =  \frac{1}{q_i^2 N' M}.
\]
So the overall cost is
\[
\varepsilon^{-2} (q_{\min}^{-2}-q_{\max}^{-2})^2 + q_{\max}^2/q_{\min}^2.
\]
In the quantum case, it is $q_{\max}/q_{\min}.$

By inner product of [Proposition 4.2 of Ewin Tang], it costs $O(\varepsilon^{-2} \sum_i q_i^{-2})$ to compute $N\pm \varepsilon$.

If we do not want to compute $N$, then we can choose $M=N/q_{\min}^2$. There is no need to compute $M$. So $U(i) = q_{\min}^2/q_i^2$. Now the cost is
\[
q_{\min}^{-2} \sum_{i=1}^n \frac{p_i^2}{q_i^2}
\leq
q_{\min}^{-2} \sum_{i=1}^n \frac{1}{q_i^2}
\]
if we want to focus on $Q$ only.

% In the disjointness problem, usually the hamming weight of $\x, \y$ is of order $n$, so the example constructed above has a high rank. However, we can focus on bit strings of $\{0,1\}^r$ with $r\ll n$. Namely, the coordinator knows $n-r$ bits of $\x,\y$ and there is no need to communicate that part. This gives a low-rank matrix with rank at most $r$.

% Apart from this low-rank constraint, another issue of this reduction is $A$ is diagonal and has $\Theta(n)$ nonzero entries, a direct method of solving this linear regression costs $O(n)$. So it is not clear what is the dependence on $\|A\|_F$. We below consider another construction.

% Assume that $k$ is a factor of $n$. We decompose $\x=(\x_1,\ldots,\x_k)$, where $\x_i\in\{0,1\}^{n/k}$. Similarly we decompose $\y=(\y_1,\ldots,\y_k)$. We below view $\x_i,\y_i$ as column vectors. Let
% \be
% A =
% \begin{pmatrix}
%     1 \\
%     & \x_1 & \\
%     &      & \x_2 \\
%     &      &      & \ddots  \\
%     &      &      &   & \x_k \\
% \end{pmatrix}_{(n+1)\times (k+1)}, \quad
% \b =
% \begin{pmatrix}
%     1 \\
%     \y_1 \\
%     \y_2 \\
%     \vdots \\
%     \y_k
% \end{pmatrix}
% \ee

\section{Proof of Theorem \ref{thm:HS}}

We shall use the hardness of the $k$-party disjointness problem. We now state it in the language of bit strings. Assume that player $\P_j$ receives a bit string $T_j=(T_{j1}, \ldots, T_{jn})\in\{0,1\}^n$. Their goal is to determine if there is a $j\in\{2,\ldots,k\}$ such that $T_{1k}=T_{jk}=1$ for some $k$. This is apparently equivalent to the original problem.

We consider the following construction, player $\P_i$ constructs the following unit vector
\be
\ket{\b_j} = \frac{1}{\sqrt{|T_j|}}\sum_{k=1}^n T_{jk} \ket{k}.
\ee
\bea
H &=& \varepsilon \ket{1}\bra{1} \otimes  \ket{1}\bra{1} + \sum_{j=2}^k \ket{j} \bra{j} \otimes \ket{\b_j} \bra{\b_j} , \\
\ket{\v} &=& \frac{1}{\sqrt{2}} \left(\ket{1}\otimes  \ket{1} + \frac{1}{\sqrt{k-1}} \sum_{j=2}^k \ket{j} \otimes \ket{\b_1}\right).
\eea
Then it is easy to see that
\be
\exp(i  \pi H) \ket{\v} = H\ket{\v}
\frac{\varepsilon }{\sqrt{2}}
\ket{1}\otimes  \ket{1} +
\frac{1}{\sqrt{2(k-1)}} \sum_{j=2}^k
\frac{c_j}{\sqrt{|T_1||T_j|}} \ket{j} \otimes \ket{\b_j},
\ee
where $c_j = \#\{k\in[n]: T_{1k}=T_{jk}=1\}$. If there is no intersection at all, i.e., $c_j=0$ for all $j$, then $\exp(i \pi H) \ket{\v}=\0$.

$\varepsilon = (k/n)^{1/4}$, then
$\|H\|_F^2/\varepsilon^2 = (k+\sqrt{k/n})/\sqrt{k/n} = \sqrt{nk} + 1$.

$\v = \ket{1}\otimes  \ket{1} + C \sum_{j=2}^k \ket{j} \otimes \ket{\b_1} $, choose $C=n/\varepsilon$, then
\beas
H^+\v = \varepsilon^{-1} \ket{1}\otimes  \ket{1} + C \sum_{j=2}^k  \frac{c_j}{\sqrt{|T_1||T_j|}} \ket{j}\otimes \ket{\b_j}
\eeas

\beas
A_{\geq \delta}^+\v = \ket{1}\otimes  \ket{1} + n \sum_{j=2}^k  \frac{c_j}{\sqrt{|T_1||T_j|}} \ket{j}\otimes \ket{\b_j},
\eeas
where $c_j = \#\{k\in[n]: T_{1k}=T_{jk}=1\}$. If there is no intersection at all, i.e., $c_j=0$ for all $j$, then $A_{\geq \delta}^+\v \propto \ket{1}\otimes  \ket{1}$. When sampling from this solution, we will see $1$ in the first register. If there is a $j$ such that $c_j\geq 1$, then we will see $j$ in the first register when sampling from this solution.

In this construction, we choose $\delta = (k/n)^{1/4}$, then
$\|H\|_F^2/\delta^2 = (k+\sqrt{k/n})/\sqrt{k/n} = \sqrt{nk} + 1$. Thus the lower bound is $\Omega(\|H\|_F^4/\delta^4)$.

\be
\exp(i  \pi H) \ket{\v} = H\ket{\v}
\frac{\varepsilon }{\sqrt{2}}
\ket{1}\otimes  \ket{1} +
\frac{1}{\sqrt{2(k-1)}} \sum_{j=2}^k
\frac{c_j}{\sqrt{|T_1||T_j|}} \ket{j} \otimes \ket{\b_j},
\ee
where $c_j = \#\{k\in[n]: T_{1k}=T_{jk}=1\}$. If there is no intersection at all, i.e., $c_j=0$ for all $j$, then $\exp(i \pi H) \ket{\v}=\0$.

$\v = \ket{1}\otimes  \ket{1} + C \sum_{j=2}^k \ket{j} \otimes \ket{\b_1} $, choose $C=n/\varepsilon$, then
\beas
H^+\v = \varepsilon^{-1} \ket{1}\otimes  \ket{1} + C \sum_{j=2}^k  \frac{c_j}{\sqrt{|T_1||T_j|}} \ket{j}\otimes \ket{\b_j}
\eeas

\section{Recommendation system}

\section{Conclusion}

In this note, we provided a lower-bound analysis of quantum-inspired classical algorithms for solving linear regressions. In the general case, the lower bound is $\Omega(\|A\|_{\F}^4/\delta^4)$. Note that the upper bound is $\widetilde{O}(\|A\|_{\F}^4/\delta^4\times \|A\|^2/\delta^2\times \varepsilon^{-2})$. So a natural question is how to close this gap.

\section{Examples}

\begin{eg}{\rm
Consider the following construction:
\be
A = {\rm diag}(1,\delta x_1,\ldots,\delta x_n), \quad
\b = (1,\delta y_1,\ldots,\delta y_n)^\T,
\ee
where $\delta$ can be any small parameter.
The optimal solution stated in Problem \ref{problem} is
\be
\x_* = A^+_{\geq \delta}\b = \ket{0}+\sum_{i=1}^n x_i y_i \ket{i}.
\ee
Suppose the coordinator has $SQ(\x_*)$, then the coordinator can sample from this solution.
If there is no intersection, then $\x_* = \ket{0}$. So the coordinator only receives $0$ by sampling from $\x_*$. Otherwise, the coordinator will see an index different from $0$. Thus, from the sampling result, they can solve the disjointness problem. In this construction, to use $SQ(A)$ (respectively $SQ(\b)$) once, the coordinator only needs to communicate with $\P_1$ (respectively $\P_2$) once. Thus if there is a quantum-inspired classical algorithm that uses $SQ(A), SQ(\b)$ $O(T)$ times, then there is a protocol for the coordinator to solve the disjointness problem with communication complexity $O(T)$.

In this construction,
\be
\|A\|_\F^2/\delta^2 = \Theta(n), \quad \gamma = \Theta(1/n).
\ee

\begin{eg}{\rm
Consider the following linear regression
\be
\argmin \|A\x-\b\|, \quad
D \\
\varepsilon \b_2^{\T} \\
\vdots \\
\varepsilon \b_k^{\T} \\
\end{pmatrix}, \,\,
\b=
\begin{pmatrix}
0 \\
\varepsilon^{-1}  \\
\vdots \\
\varepsilon^{-1}  \\
\end{pmatrix}.
\ee
The player $\P_1$ constructs a diagonal matrix $D$ of form
\be
D = \ket{0} \bra{0} + \sum_{j\in[n]} d_j \ket{j} \bra{j},
\ee
\be
d_j = \begin{cases}
\delta & j\in T_1, \\
0 & j \notin T_1 .
\end{cases}
\ee
For $i\geq 2$, the player $\P_i$ constructs a vector $\b_i$ of the form
\be
\b_i =
\frac{1}{k-1} \ket{0} + \sum_{j\in[n]} b_{ij} \ket{j} ,
\ee
\be
\b_{ij} =
\begin{cases}
\delta^{2} & j\in T_i, \\
0 & j \notin T_i.
\end{cases}
\ee

We choose $\varepsilon \ll \delta$, say $\varepsilon = 1/(\delta^2 n\sqrt{k})$, then the solution stated in Problem \ref{problem} is
\bea
\x_* &=& A^+_{\geq \delta} \b \\
&=& (A^\T A)^{+}_{\geq \delta^2} A^\T \b\\
&=& (D^2 + \varepsilon^2 (\b_2\b_2^{\T} + \cdots +  \b_k\b_k^{\T}))_{\geq \delta^2}^{+} (\b_2+\cdots +\b_k) \\
&\approx& (D_{\geq \delta}^{+})^2 (\b_2+\cdots +\b_k) \label{weyl-ineq} \\
&=& \ket{0} + \sum_{j\in T_1 \cap T_i \text{ for some } i} c_j \ket{j},
\eea
where $c_j = \#\{i\in \{2,\ldots,k\}:j\in T_1 \cap T_i\}$. In the above, Equation (\ref{weyl-ineq}) follows from the Weyl inequality [26]. Indeed, by Weyl's inequality, for any two matrices $M,\Delta$, we have $|\sigma_i(M+\Delta) - \sigma_i(M)| \leq \|\Delta\|$, where $\sigma_i$ refers to the $i$-th singular value. In our case, $M=D^2, \Delta = \varepsilon^2 (\b_2\b_2^{\T} + \cdots +  \b_k\b_k^{\T})$. If $\varepsilon$ is small, say $1/(\delta^2 n\sqrt{k})$, then $\|\Delta\| \leq 1/n$.
So for any vector $\b$, by \cite[Theorem 3.3]{stewart1977perturbation} we have
\bea
\|(M+\Delta)^+_{\geq \delta^2} \b - (M_{\geq \delta}^+)^2 \b\|
\|(M+\Delta)^+_{\geq \delta^2} - (M_{\geq \delta}^+)^2 \| \|\b\|  \\
&\leq& \frac{1+\sqrt{5}}{2}\max\{\|(M+\Delta)^+_{\geq \delta^2}\|, \|(M_{\geq \delta}^+)^2\|\} \|\Delta\| \|\b\| \\
&=& O({\|\b\| }/{n\delta^2}).
\eea

Therefore, when having $SQ(\x_*)$, the coordinator can solve the $k$-player disjointness problem. As analysed previously, for the coordinator to use $SQ(A)$, each player only needs to send the size of the set to the coordinator. This only requires an extra $O(k\log (1/\delta))$ bits of communication. About $SQ(\b)$, it is given to the coordinator without any communication.

In this construction, we have
\[
\|A\|_{\F}^2/\delta^2 = \Theta( \|D\|_{\F}^2/\delta^2) =\Theta( n ).
\]

\section{Another connection}

Apart from the connection discussed above, another way to see the connection, which should be more general, is considering $A=\sum_{i=1}^k \lambda_i A^{(i)}$ and $\b=\sum_{i=1}^k \mu_i \b^{(i)}$. We are not aware of any applications of this connection in this work, but it might be useful in some problems.

For $i\in [k]$, let $\b^{(i)} \in \mathbb{C}^m$, $\lambda_i\in \mathbb{C}$, and $\b = \sum_{i=1}^k \lambda_i \b^{(i)}$. Denote
\be
\label{eq for phi}
\phi = k \frac{\sum_i \varphi_i \|\lambda_i \b^{(i)}\|^2 }{\|\b \|^2}.
\ee
Given $SQ_{\varphi_i}(\b^{(i)})$ for all $i\in [k]$, we can construct $SQ_{\phi}(\b)$ in the following way, which is based on the proof of \cite[Lemma 3.6]{chia2022sampling}.

\begin{enumerate}
\item Obtain $Q(\b)$: For each $j\in[m]$, we can compute $b_j=\sum_{i=1}^k \lambda_i b^{(i)}_j$ by querying all $b^{(i)}_j$.

\item Obtain $SQ(\tilde{\b})$: Define $\tilde{\b}$ via
\[
\tilde{b}_j = \sqrt{k \sum_{i=1}^k |\lambda_i \tilde{b}^{(i)}_j|^2}, \quad j \in [n].
\]
Here $\tilde{\b}^{(i)}$ is the vector claimed in $SQ_{\varphi_i}(\b^{(i)})$.
It is easy to check that $\|\tilde{\b}\|^2 = \phi \|\b\|^2, |\tilde{b}_j| \geq |b_j|$ for all $j\in [m]$.
\begin{enumerate}
\item Query for $\|\tilde{\b}\|^2$: We can compute $\|\tilde{\b}\|^2 = k \sum_i \varphi_i \|\lambda_i \b^{(i)}\|^2$ directly by querying  $\|\b^{(i)}\|^2$ for all $i\in[m]$.
\item Query for $\tilde{b}_j$: We can compute $\tilde{b}_j$ by querying $ \tilde{b}^{(i)}(j)$ for all $i\in[k]$.
\item Sample from $\tilde{\b}$: We first sample an index $i\in[k]$ with probability $\|\lambda_i \tilde{\b}^{(i)}\|^2/\sum_j\|\lambda_j \tilde{\b}^{(j)}\|^2$, then take a sample $j\in[n]$ from the distribution defined by $\title{\b}^{(i)}$.
\end{enumerate}
\end{enumerate}

The above procedure indeed provides a protocol for the coordinator to use $SQ_\phi(\b)$. We assume that entries of $\b^{(i)}$ are specified by $O(\log q)$ bits.
Firstly, querying for entries of $\b$ is straightforward, which costs $O(k \log q)$ bits of communication. Secondly, query for $\|\tilde{\b}\|^2$ and $\tilde{b}_j$ are also straightforward, which costs $O(k \log q)$ bits of communication. Thirdly, to sample from $\tilde{\b}$, player $\P_i$ first sends $\|\tilde{\b}^{(j)}\|$ to the coordinator. This costs $O(k (\log q +\log m))$ bits of communication. Now the coordinator can do step (2.c) discussed in the above procedure with $O(\log q)$ bits of communication with player $\P_i$. In summary, for the coordinator to use $SQ_\phi(\b)$ $O(T)$ times, they use $O(kT\log q+k(\log q+\log n))$ bits of communication. Combining Lemma \ref{lem3.5}, it costs $O(\phi(kT\log q+k(\log q+\log m)))$ bits of communication for the coordinator to use $SQ(\b)$ $O(T)$ times.

Similar results also hold for linear combinations of matrices. For $i\in [k]$, let $A^{(i)} \in \mathbb{C}^{m\times n}$, $\lambda_i\in \mathbb{C}$, and $A = \sum_{i=1}^k \lambda_i A^{(i)}$. Denote
\[
\phi = k \frac{\sum_i \varphi_i \|\lambda_i A^{(i)}\|_\F^2}{\|A\|_\F^2}.
\]
Given $SQ_{\varphi_i}(A^{(i)})$ for all $i\in [k]$, we can construct $SQ_{\phi}(A)$ in the following way, which is based on the proof of \cite[Lemma 3.9]{chia2022sampling}.

\begin{enumerate}
\item Obtain $Q(A)$: For each $(i,j)\in[m]\times [n]$, we can compute $A_{ij}=\sum_{t=1}^k \lambda_t A^{(t)}_{ij}$ by querying all $A^{(t)}_{ij}$.