HHLアルゴリズムにおける規格化係数の問題
前回のHHLアルゴリズムの実装
QiskitでHHLアルゴリズム(線形方程式を解く)
では、解く問題$Ax=b$の解$x$の規格化されたもの$x/|x|$が量子状態$|b \rangle$として実現されました。
しかし欲しいのは$x$であって、$x/|x|$ではないです。$|x|$は決定可能でしょうか？
この答えは YES です。
2021/1/12追記
いくつか説明を補足しました。
HHLアルゴリズム復習
QiskitでHHLアルゴリズム(線形方程式を解く)
では以下の手順で進めました。
-
$A$に対してスケーリング$2\pi$を掛ける ; $ A \to 2\pi A$
これは必須ではないのですが、以下の理由によるものです。
この後$V=e^{iH}$に対してQPEをかけます。QPEでは固有値の位相、それはつまり$H$の固有値ですが、これが$2\pi$で規格化されたものが
読みだされます。なので、最初から$H$に$2\pi$をかけておくことで、VへのQPEの結果がそのまま元の$H$の固有値となります。 -
$A$にスケーリング係数 $3/8$ を掛ける ; $ A \to (3/8)A $
これは以下の理由によるものです。QPEで位相を取り出すので、位相が$2\pi$を超えてしまっているとただしく推定されません。
つまり$V=e^{iH}$とするとき、$H$の固有値は1を超えてはいけません。なので、適当に小さい係数をかける必要があります。
また、(これは必須ではないですが)同時に固有値が2進小数2桁で掛けるようにしています。
結局、$A \to A' = 2\pi(3/8)A $ とすることで、上記要請が全て満たされます。
$(3/8)A$の固有値は$1/2$と$1/4$であり、$U = e^{i2\pi(3/8)A}$ へQPEすることで取り出せます。
HHLでは、$(3/8)A$の固有値をQPEで取り出した後、この固有値の逆数をかけることで $((3/8)A)^{-1}$ を表現します。
HHLアルゴリズムにおける規格化係数
この方法はHHLの元論文に載っています。
この問題の場合、単に補助量子ビットが $|1 \rangle$であるものの係数を拾ってきたものは
$$
| \psi \rangle = \frac{1}{\sqrt{2}}(q|u_{1}\rangle + s|u_{2}\rangle)
$$
とかけます。
$1/ \sqrt{2}$は、 $b_{1} = \langle b | u_{1}\rangle = 1/ \sqrt{2}$, $b_{2} = \langle b | u_{2}\rangle =1 / \sqrt{2}$であったために出てきている数値です。(つまり、$b$に依存しますのでこの式は一般性はありません。)
ここで $$ |u_{1}\rangle = \frac{1}{\sqrt{2}}[1, 1]^{T} , |u_{2}\rangle = \frac{1}{\sqrt{2}}[1, -1]^{T}$$
$$q = \frac{C}{\lambda_{1}}, s = \frac{C}{\lambda_{2}}$$ です。
$\lambda_{1,2}$は$(3/8)A$の固有値である$1/4$と$1/2$です。
補助量子ビットを$|1>$に射影測定できたとして、射影測定後の状態は、上記状態を規格化したもので与えられるので
$$
| \psi_{1} \rangle = \frac{1}{\sqrt{P_{1}}}\frac{1}{\sqrt{2}}(q|u_{1}\rangle + s|u_{2}\rangle
$$
となります。ここで$P_{1}$は、補助量子ビットが"1"となった確率です。いまは$P_{1}=0.15625$となります。
qiskitのチュートリアルでは、スケーリングを間違ったり、忘れたりしたまま計算をしており、$P_{1}$が1を超える値になっています。
この間違いはissueにあげてます。(2021/02/10)
https://github.com/qiskit-community/qiskit-textbook/issues/881
規格化前の解$x$（ただし$((3/8)A)$に対する)は
$$
x = \frac{1}{\sqrt{2}}\frac{1}{C}(q|u_{1}\rangle + s|u_{2}\rangle
$$
とかけますので、
$$
x = \sqrt{P_{1}} \frac{1}{C} | \psi_{1} \rangle
$$
となります。
これを実装してやると、
となります。$((3/8)A)$に対する厳密解$x=[3, 1]^{T}$に一致します。
あとはこれに$(3/8)$をかけてやれば、$A$に対する解$x$が求まることになります。
よって、規格化係数も含めて$x$が完全に復元されました。
もちろん、状態ベクトルに規格化係数の逆数をかけることは実際にはできません（ノルムが1でなくなる）が、
例えばオブザーバブル期待値を計算した後にスケーリングを戻すことにすれば有用です。
HHLアルゴリズムの成功率
HHLアルゴリズムは、補助量子ビットを$|1>$に射影測定できないと答えが得られません。
確率$P_{1}$は、例えば固有値逆回転のときに導入したパラメータ$C$の二乗に比例します。
$C=1/8$のときは$P_{1}=0.15625$で、$C=1/16$のときは$P_{1}=0.0390625$となります。
$C$を大きく取りたいところですが、
$C$は$A$の最小固有値(の$2\pi$規格化)よりも小さくなければならないので、上限があります。
つまり、固有値の大きさと成功率に関係性があるということになります。
大変面白いですね。
実際、HHLの計算量は、$A$の条件数$\kappa$（最大固有値と最小固有値の比)に依存することが広く知られています。
元の論文では、以下の部分です。
確率の小ささは、振幅増幅アルゴリズムでカバーすることが前提となっています。
結論
規格化されていない真の解$x$を求めることができた。