5
$\begingroup$

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.)

  1. 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!

$\endgroup$
  • $\begingroup$ Possible duplicate of cstheory.stackexchange.com/a/2952/35155 ? $\endgroup$ – user1271772 Aug 31 '18 at 21:05
  • 2
    $\begingroup$ There have been, but the thing about quantum algorithms for matrix multiplication is that they're very specific (based on sparsity, condition numbers, etc.). Why not ask a separate question asking specifically what you want (quantum algorithm for matrix multiplication with certain properties), rather than talking about multi-variable regression? $\endgroup$ – user1271772 Aug 31 '18 at 21:14
  • $\begingroup$ See there's already an answer now which speculatively picks out one of the first search results from when you search "quantum algorithm for matrix multiplication" on Google. Is that really what you want? I'm sure you already did that search and found a dozen papers on quantum algorithms for matrix multiplication right? So what is it exactly that you're looking for? $\endgroup$ – user1271772 Aug 31 '18 at 23:47
  • $\begingroup$ Thanks for the edit. You are asking for a general purpose matrix multiplication algorithm and at the same time you want to know how it affects the complexity of regression. But in regression, the matrix multiplication is extremely rectangular. That is why you are saying that the cost of multiplication is $\mathcal{O}(C^2N)$ rather than $\mathcal{O}(N^{2.37})$. So the $N^2$ algorithm given in the other person's answer is actually slower than the $\mathcal{O}(N)$ classical algorithm you suggest in your question, which is linear scaling in $N$. $\endgroup$ – user1271772 Sep 1 '18 at 18:58
1
+50
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Could you please summarize the algorithm and state what restrictions it demands on the matrices? $\endgroup$ – Sanchayan Dutta Sep 1 '18 at 7:31
  • $\begingroup$ The classical algorithm in linear regression has scaling linear in $N$, but the quantum algorithm you're suggesting is quadratic in $N$ and is thus slower. $\endgroup$ – user1271772 Sep 1 '18 at 19:00
  • $\begingroup$ By the way this algorithm is a hyper-parallel algorithm, which involves entanglement on two different types of qubits at the same time, so comparing the complexity of this to the complexity of something else needs to be taken with a grain of salt I think. If this hyper-parallel quantum algorithm can be compiled into a gate set like $\{CNOT, H, T\}$ on ordinary qubits without exceeding $\mathcal O(C^{1.37}N)$ complexity it might be interesting, but as written it involves things like a hyper-CNOT which is outside of the gate set of (ordinary) quantum computation. $\endgroup$ – user1271772 Sep 2 '18 at 10:18
4
$\begingroup$

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:

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})$.

$\endgroup$
  • $\begingroup$ If you are wondering whether or not there's a quantum algorithm to do matrix multiplication, that is another question all together, but here you seem to be asking about it in the context of speeding up regressions, so I've given the best quantum algorithms for doing regressions. $\endgroup$ – user1271772 Aug 29 '18 at 20:50
  • $\begingroup$ Thanks for the answer. However, as mentioned in the question I'm looking for methods to improve upon the "matrix multiplications" (as mentioned in the title and the question body) in steps 1 and 2 rather than using a completely different technique for performing the multi-linear regression. It would be nice to know how far we can improve the complexities of the three steps I mentioned in the question. $\endgroup$ – Sanchayan Dutta Aug 29 '18 at 20:55
  • $\begingroup$ I see. Step 2 is asking for a quantum algorithm for a matrix times a vector, and step 1 is asking for a quantum algorithm for a matrix times its transpose. In the regression case, is there anything special about these matrices and vectors which would make the answer here different from the answer to the question "is there a quantum algorithm for matrix-vector multiplication and/or multiplication of a matrix with its transpose?" $\endgroup$ – user1271772 Aug 29 '18 at 21:02
  • 1
    $\begingroup$ Do you have a source for that saying the constant hidden by big O is that absurd? I don't think I've ever seen it evaluated/estimated. $\endgroup$ – AHusain Aug 29 '18 at 22:20
  • 1
    $\begingroup$ @AHusain: I was also curious and looked it up 2 hours ago when I was answering this question, so I left a comment saying I wanted to add a bounty but didn't have enough reputation on MathOverflow: mathoverflow.net/questions/1743/… $\endgroup$ – user1271772 Aug 29 '18 at 23:21
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.