The paper Quantum linear systems algorithms: a primer by Dervovic et al has this table on page 3:

enter image description here

I'm not sure why there's no $N$ in the time complexity of the algorithm by Childs et al. i.e. $\mathcal{O}(s\kappa \ \text{polylog}(s\kappa/\epsilon))$. It's a bit hard to believe that the time complexity doesn't depend on the dimensions of the matrix involved. I also checked the original paper by Childs et al but I couldn't find the time complexity written in this form there. Any ideas?

  • 2
    $\begingroup$ In page 3 they define a matrix as sparse when $s=\text{poly}(\log(N))$. $\endgroup$ – user96233 Oct 25 '18 at 7:04
  • $\begingroup$ what are $s$, $\kappa$ and $\epsilon$ here? It might be worth adding it to the post. Anyway, I haven't read the paper but I wouldn't find this too surprising. After all, the sparsity sorts of gives you an "effective dimension" of the matrix. If you increase $N$ with fixed $s$, you are just adding more zeros to the matrix, so it makes sense that you are not really making the problem more difficult to solve. This said, it is still highly nontrivial how exactly this happens of course, but I haven't read the paper yet so I cannot say anything about that $\endgroup$ – glS Oct 25 '18 at 12:02
  • $\begingroup$ @user96233, glS: Yes, upon going through Dervovic's paper that seems like the only plausible explanation so far. Thanks! $\endgroup$ – Sanchayan Dutta Oct 25 '18 at 13:08
  • 2
    $\begingroup$ @glS: $\kappa$ is the condition number and $\epsilon$ is the precision term. Smaller $\epsilon$ would imply lesser error. And yeah, I agree on the non-triviality part :P The math in that paper seems almost impenetrable! Would take several days of dedicated reading I guess. $\endgroup$ – Sanchayan Dutta Oct 25 '18 at 13:10

Your Answer

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

Browse other questions tagged or ask your own question.