1
$\begingroup$

How can we show that HHL algorithm achieves exponential speedup?

$\endgroup$
4
  • 2
    $\begingroup$ Hi @Omkar! Could you add a little bit more precisions? Do you want to know where you can find the proof of the exponential speed-up, or where to learn the mathematical tools used to prove this speed-up (and used in the HHL algorithm)? $\endgroup$ – Adrien Suau Feb 5 '20 at 13:28
  • $\begingroup$ Hi @Nelimee. Yes I want to learn the prove of this exponential speed-up $\endgroup$ – Omkar Feb 5 '20 at 14:19
  • $\begingroup$ This is for instance covered in the lecture notes of Ronald de Wolf (arxiv.org/abs/1907.09415) $\endgroup$ – smapers Feb 5 '20 at 15:47
  • $\begingroup$ You cannot prove an exponential speedup. You can prove that the HHL algorithm solves a BQP-complete problem, so as strongly as we believe that quantum computers provide an exponential speedup over classical is how strongly we believe that HHL is exponentially faster that what can be achieved classically. $\endgroup$ – DaftWullie Feb 5 '20 at 15:54
1
$\begingroup$

You can find details about the algorithm optimality and complexity in the original paper by Harrow, Hassidim and Lloyd: Quantum algorithm for solving linear systems of equations, mainly in parts III and appendix 5.

An article Quantum Circuit Design for Solving Linear Systems of Equations may be interesting for you as well. It contains a "practical" example HHL algorithm application.

$\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.