HHL算法(量子求解线性方程组)
HHL算法的目标
求解\(A\vec{x}=\vec{b}\),其中\(A\)是\(n\times n\)的方阵,\(\vec{x}\)和\(\vec{b}\)都是\(n\times1\)的向量。假设矩阵\(A\)是厄密的(即\(A^{\dagger}=A\)),则矩阵\(e^{iAt}\)是酉的(即\(AA^{\dagger}=A^{\dagger}A=I\)),同时\(A\)和\(e^{iAt}\)有相同的特征向量,若\(A|u\rangle=\lambda|u\rangle\),则\(e^{iAt}|u\rangle=e^{i\lambda t}|u\rangle\)。本问题中,还需假设\(\|\vec{x}\|=1,\|\vec{b}\|=1\)。因为\(e^{iAt}\)是酉矩阵,所以它有\(n\)个相互正交的特征向量。本问题中,将问题变形为\(A|x\rangle=|b\rangle\),并不完全等同于原问题。
很多地方笔者并没有完全搞懂,故省略了很多推导过程和证明,后面可能会补充。
HHL算法的量子线路图
其对应的latex代码为:
\documentclass{article}
\usepackage[]{qcircuit}
\usepackage{ifpdf}
\xyoption{all}
\newcommand{\ket}[1]{\ensuremath{\left\vert #1 \right\rangle}}
\newcommand{\bra}[1]{\ensuremath{\left\langle{#1}\right\vert}}
\begin{document}
\Qcircuit@C=0.7em@R=0.7em {
& & & & & & &\mbox{Controlled Rotation} \\
\lstick{Ancilla \ket{0}} &\qw &\qw&\qw &\qw &\qw &\qw&\gate{R} &\qw&\qw &\qw &\qw &\meter&\rstick{\ket{1}} \\
\lstick{EigenValue \ket{0}}&\qw{/^{n}}&\qw&\gate{H^{\otimes n}}&\ctrl{1}&\gate{FT^{\dagger}}&\qw&\ctrl{-1}&\qw&\gate{FT}&\ctrl{1}&\gate{H^{\otimes n}}&\rstick{\ket{0^{\otimes n}}}\qw \\
\lstick{Input \ket{\psi}} &\qw{/^{m}}&\qw&\qw &\gate{U}&\qw &\qw&\qw &\qw&\qw &\gate{U}&\qw&\rstick{\ket{\hat{x}}}\qw
\gategroup{3}{4}{4}{6}{.7em}{--} \gategroup{2}{8}{3}{8}{.7em}{--} \gategroup{3}{10}{4}{12}{.7em}{--}\\
&&&&\mbox{Phase Estimation}&&&&&&\mbox{Inverse Phase Estimation}
}
\end{document}