HHL算法

HHL算法简介

HHL算法被用来求解线性方程组,由Aram Harrow等人于2009年提出。 该算法在一些假设的前提下,能够在求解线性方程组方面较经典算法有指数加速效果,是目前量子人工智能算法中的关键步骤。

HHL算法的基本思路

HHL算法主要是为了求解线性方程组 \({\rm{A}}\overrightarrow {\rm{x}} {\rm{ = \vec b}}\),其中矩阵 \(A\) 和向量 \(\vec b\) 已知。

算法的大概步骤如下:

  1. 初始化:将矢量 \(\vec b\) 初始化为量子态 \(\left| b \right\rangle\)
  2. 估计矩阵A的特征值:利用相位估计算法估计 \({e^{2\pi i\lambda }}\)\(\lambda\) 的值,也就是矩阵A的本征值。
  3. 受控旋转:根据估计特征值对辅助比特做受控旋转,用 \({\rm{sin}}\left( {\frac{\theta }{{{2^r}}}} \right)\) 来近似 \(\frac{\theta }{{{2^r}}}\) ,s 即本征值的倒数。
  4. 反相位估计算法将 \(\left| {{q_0}{q_1}} \right\rangle\) 重新变为 \(\left| {00} \right\rangle\)
  5. 测量 \(\left| {q_3} \right\rangle\),如果得到的结果为1,则对应的量子态 \(\left| {q_2} \right\rangle = \left| {x} \right\rangle\),从而得到方程的近似解。

HHL算法的量子电路图如下:

../images/HHL.png

参考文献: