How to speed up the matrix multiplication steps in multi-linear regression?

Question

Context and Motivation:

As discussed here, in multilinear regression, we can express the linear system as $AX = b$. This leads to $A^TA \hat{X} = A^T b$. From here, the estimated value of $X$ is calculated as $(A^TA)^{-1}A^Tb$. The whole process basically involves three steps:

1. Matrix multiplication of $A$ and $A^T$: $\mathcal{O}(C^2N)$

2. Matrix multiplication of $A^T$ and column matrix $b$: $\mathcal{O}(CN)$

3. LU/Cholesky factorization of matrix $A^T A$ used to compute the product $(A^TA)^{-1}A^Tb$: $\mathcal{O}(C^3)$.

Note: $N$ is the number of training samples. $C$ is the number of features/variables.

---

Questions:

I guess we could speed up step $3$ by using the HHL although I guess that would be worth it only if $C$ is sufficiently large i.e. $C\lesssim N$. But is there any quantum algorithm to speed up steps 1 and 2 (which involve matrix multiplication)? The fastest classical matrix multiplication algorithms as of today have time complexities around $\mathcal{O}(N^{2.37})$.

So:

1. Can we do better than that? What are state-of-the-art general purpose quantum algorithms as of today, as far as matrix multiplication is concerned?

(By "general purpose" I mean that the algorithm should have no specific restrictions on the elements of the matrices. An user mentioned in the comments that there are different quantum matrix multiplication algorithms depending on sparsity, condition number, etc. which sounds reasonable to me. So any answer which lists and summarizes the best quantum algorithms for different such conditions/restrictions is also welcome.)

2. Would the state-of-the-art quantum matrix multiplication algorithm(s) coupled with HHL help to produce an overall reduction in the time complexity (considering all the three steps as a whole) of multilinear regression? If yes, by how much?

(I'm looking for an asymptotic analysis as in here which states that the overall time complexity of classical multilinear regression at best is $\mathcal{O}(C^2N)$).

---

Note:

Please summarize any algorithm you mention (along with the constraints involved). It is practically impossible for people to read each and every paper referenced in order to check whether it suits their criteria!

Answer 1

Maybe this one can be useful. Their algorithm is called quantum hyperparallel algorithm for matrix multiplication and they state that the time complexity is $O(N^2)$ which is the lower bound for matrix multiplication apparently.

I won't describe the whole procedure but give just the idea behind. You know matrix multiplication is just a calculation of inner products. There is a quantum algorithm called the swap Test which enables you to compute the overlap (inner product) between quantum states.

They based their algorithm on it. It seems you have no restrictions on your matrices. You need however oracles like many quantum algorithms.

Answer 2

You were correct to seek a new quantum algorithm for this rather than just using HHL to do step 3.

There are separate quantum algorithms to do regressions:

• Quantum Algorithm for Data Fitting (same journal and same last author as HHL)
• Quantum Algorithm for Linear Regression
• Fast quantum algorithms for least squares regression and statistic leverage scores
• Prediction by linear regression on a quantum computer

There is an interesting note about the $\mathcal{O}(N^{2.37})$ algorithm you mention for matrix multiplication. The constant hidden under the big O is larger than the number of particles in the visible universe. That is why almost 100% of the implementations (for example in MATLAB, BLAS, LAPACK, etc.) use Strassen's algorithm which has scaling $\mathcal{O}(N^{2.81})$.

Answer 3

First of all the cost on a classical computer of the dominant step can be improved from the $\mathcal{O}(C^2 N)$ in your question.

I managed to bring the classical cost down to $\mathcal{O}(C^{1.37} N)$ in my new answer to the question on the Mathematics Stack Exchange that you linked.

Now, you have two questions:

• (1) can a quantum computer do step 1 in time faster than $\mathcal{O}(C^{1.37} N)$, and
• (2) would this lead to an overall reduction in complexity of the entire regression algorithm?

The answer to (2) is yes. If your quantum algorithm improves the classical $\mathcal{O}(C^{1.37} N)$, then it improves the whole algorithm because this is the step that dominates the complexity of the whole problem. This is because $N$ has to be bigger than $C$ for the matrix to be invertible, which was pointed out by Chris Taylor in this answer.

The answer to (1) is an open problem.