The Childs, Kthari, and Rolando (2017) (CKS) algorithm can solve the quantum linear systems problem (QLSP) in $\operatorname{poly}(\log N, \log(1/\epsilon))$ time while the HHL algorithm solves it in $\operatorname{poly}(\log N, 1/\epsilon)$ time. So, if the CKS algorithm is superior, then why is the HHL more popular?

Additionally, are there any examples of the CKS algorithm being used to solve a system of equations on a real or simulated quantum computer?

  • 1
    $\begingroup$ I suppose only because HHL came earlier and is easier to understand? $\endgroup$
    – wdc
    Mar 26 '21 at 17:05
  • $\begingroup$ Yea, that makes sense. I was just wondering if there is a technical reason for it. $\endgroup$ Mar 26 '21 at 18:24
  • $\begingroup$ I've added the hamiltonian-simulation tag since the CKS algorithm uses it, and people in that field may be interested in providing more insight here in the future. $\endgroup$ Nov 27 '21 at 8:57

HHL is more popular because it is much older (and it was the first in its category). The CKS algorithm (which you've been calling the Childs algorithm, even though the paper had three equally contributing authors in alphabetical order) is simply an improvement to the HHL algorithm in terms of its computational complexity.

The reason you haven't seen it being used to solve a real system of equations on a quantum computer, is because of the resources you'd need in order use the algorithm on even a matrix is that would be considered simple by classical computation standards.


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.