<p>If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical solution $x$ to a system $Ax=b$" then the answer is no. As you mention, the final quantum state  in Harrow, Hassidim, Lloyd's algorithm does not immediately give you the classical solution $x$ of the system but a quantum states that encodes $x$ in its amplitudes; it is hard to extract the "explicit information" $x$ from that state.</p>

<p>However there are indeed interesting applications of the HHL linear systems algorithm as a subroutine to solve other problems, using the output of the quantum algorithm in "more quantum" ways. </p>

<ul>
<li><p>The HHL algorithm can be readily applied to compute expectation values
$\langle x| M | x \rangle$ of a poly-size Hermitian operator $M$.</p></li>
<li><p><a href="http://arxiv.org/abs/1010.2745">Dominic Berry</a> gave a generalized version of hte HHL algorithm to solve linear systems of the differential equations. The HHL algorithm is used as a subroutine there. (Berry's algorithm uses HHL's as a subroutine.) The final solution of Berry's algorithm is also encoded in the amplitudes of a quantum state.</p></li>
<li><p><a href="http://arxiv.org/abs/1204.5242">Wiebe, Braun, Lloyd</a>  gave an algorithm based on HHL's that can be used to find the optimal least-square fit to some discrete data. Although the output of that algorithm is again encoded in some quantum amplitudes, the authors also gave a quantum algorithm to asses the quality of an optimal least-square fit in a quantum computer, and there the output is classical. For certain types of fit functions, their quantum algorithm outperforms classical ones.</p></li>
<li><p>Recently, HHL's algorithm has been employed in <a href="http://arxiv.org/abs/1307.0411">Lloyd-Mohseni-Rebentrost's</a> quantum algorithm for machine learning.</p></li>
</ul>

<p>Note that, in all of these algorithms,   <em>quantum</em> manipulations of the output state of the HHL's algorithm are performed, instead of <em>classical</em> ones. This is similar to the case of the quantum Fourier transform (QFT), which can be computed exponentially faster in a quantum computer as a quantum gate than the classical discrete Fourier transform. We cannot use this fact in quantum algorithms to Fourier-transform classical functions faster. However, the QFT has remarkable applications in <a href="http://arxiv.org/abs/quantph/9508027">Shor's factoring algorithm</a> and <a href="http://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm">quantum phase estimation</a>.</p>

CC BY-SA 3.0
2014-07-22T08:23:00.103Z
2014-07-22T09:00:39.370Z
2014-07-22T09:00:39.370Z
Juan Bermejo Vega
<p>In <a href="https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations" rel="nofollow">HHL's algorithm for solving a system of linear equations</a> (HHL = Harrow, Hassidim and Lloyd) the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a problems which would classically use the solutions of the linear equations?</p>

CC BY-SA 3.0
2014-07-26T03:56:50.763Z
The algorithm is due to Harrow, Hassidim, and Lloyd.
Robin Kothari
CC BY-SA 3.0
2015-03-14T22:54:31.993Z
Scott Aaronson answers your question in his essay linked in this blog post http://www.scottaaronson.com/blog/?p=2196
Logan Mayfield
CC BY-SA 3.0
2015-04-05T12:53:23.230Z
This paper beautifully explains the same http://www.scottaaronson.com/papers/qml.pdf
kashyap kashyap
<ds.algorithms><quantum-computing><quantum-information><linear-equations>
Applications of HHL's algorithm for solving linear equations
Sam Burville
# Applications of HHL's algorithm for solving linear equations

(Asked by: username_0 on 2014-07-21)

In [HHL's algorithm for solving a system of linear equations](https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations) (HHL = Harrow, Hassidim and Lloyd) the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a problems which would classically use the solutions of the linear equations?

**Tags:** ds.algorithms, quantum-computing, quantum-information, linear-equations

> **Comments:**
> **username_1**: The algorithm is due to Harrow, Hassidim, and Lloyd.  
> **username_2**: Scott Aaronson answers your question in his essay linked in this blog post http://www.scottaaronson.com/blog/?p=2196  
> **username_3**: This paper beautifully explains the same http://www.scottaaronson.com/papers/qml.pdf  

---

## 1 answers

### Answer by username_4 on 2014-07-22. Score: 10 | Accepted answer

If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical solution $x$ to a system $Ax=b$" then the answer is no. As you mention, the final quantum state in Harrow, Hassidim, Lloyd's algorithm does not immediately give you the classical solution $x$ of the system but a quantum states that encodes $x$ in its amplitudes; it is hard to extract the "explicit information" $x$ from that state.

However there are indeed interesting applications of the HHL linear systems algorithm as a subroutine to solve other problems, using the output of the quantum algorithm in "more quantum" ways.

* The HHL algorithm can be readily applied to compute expectation values
  $\langle x| M | x \rangle$ of a poly-size Hermitian operator $M$.
* [Dominic Berry](http://arxiv.org/abs/1010.2745) gave a generalized version of hte HHL algorithm to solve linear systems of the differential equations. The HHL algorithm is used as a subroutine there. (Berry's algorithm uses HHL's as a subroutine.) The final solution of Berry's algorithm is also encoded in the amplitudes of a quantum state.
* [Wiebe, Braun, Lloyd](http://arxiv.org/abs/1204.5242) gave an algorithm based on HHL's that can be used to find the optimal least-square fit to some discrete data. Although the output of that algorithm is again encoded in some quantum amplitudes, the authors also gave a quantum algorithm to asses the quality of an optimal least-square fit in a quantum computer, and there the output is classical. For certain types of fit functions, their quantum algorithm outperforms classical ones.
* Recently, HHL's algorithm has been employed in [Lloyd-Mohseni-Rebentrost's](http://arxiv.org/abs/1307.0411) quantum algorithm for machine learning.

Note that, in all of these algorithms, *quantum* manipulations of the output state of the HHL's algorithm are performed, instead of *classical* ones. This is similar to the case of the quantum Fourier transform (QFT), which can be computed exponentially faster in a quantum computer as a quantum gate than the classical discrete Fourier transform. We cannot use this fact in quantum algorithms to Fourier-transform classical functions faster. However, the QFT has remarkable applications in [Shor's factoring algorithm](http://arxiv.org/abs/quantph/9508027) and [quantum phase estimation](http://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm).


---

