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, because the step with $\mathcal{O}(C^{1.37} N)$ is the step that dominates the complexity of the whole problem, and 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.

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.

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, because the step with $\mathcal{O}(C^{1.37} N)$ is the step that dominates the complexity of the whole problem, and this 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.

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, because the step with $\mathcal{O}(C^{1.37} N)$ is the step that dominates the complexity of the whole problem, and 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.