HHL（量子線形方程式ソルバ）

HHL が「解く」ものは何か

HHL アルゴリズム（Harrow–Hassidim–Lloyd, 2009）は、連立一次方程式 Ax = b を量子的に扱う手法です。ここで最初に押さえるべき最重要点は、HHL は解ベクトル x の成分を数値の配列として返さないという事実です。HHL が出力するのは、解に比例した振幅を持つ量子状態

|x> ∝ A^{-1} |b>

です。つまり右辺 b を量子状態 |b> = Σ_i b_i |i>（振幅に成分を符号化）として用意し、A^{-1} を作用させた状態 |x> を生成する、という装置だと捉えるのが正確です。この「配列ではなく状態を返す」性質こそ、後述する加速と但し書きの両方の根源になります。

中核のアイデア：固有値の逆数を振幅に掛ける

A がエルミートなら、スペクトル分解 A = Σ_j λ_j |u_j><u_j| を持ち、逆行列は固有値を逆数にした A^{-1} = Σ_j (1/λ_j) |u_j><u_j| です。右辺を固有基底で展開して |b> = Σ_j β_j |u_j> と書くと、求める解は次のようになります。

|x> ∝ A^{-1}|b> = Σ_j (β_j / λ_j) |u_j>

したがって HHL の本質は、|b> を固有成分に分け、各成分 β_j の振幅を 1/λ_j 倍するという一点に尽きます。問題は「固有値 λ_j を量子的にどう取り出し、どうやって 1/λ_j を振幅に反映するか」です。前者を量子位相推定（QPE）が、後者を補助量子ビットへの条件付き回転が担います。

アルゴリズムの3段構成

HHL は大きく3つの段階から成ります。レジスタは3種類——入力 |b> を載せる主レジスタ、固有値を書き込むクロックレジスタ、回転の成否を刻む1量子ビットの補助（アンシラ）——を使います。

**段階1（位相推定）**では、A を時間発展させるユニタリ e^{iAt}（ハミルトニアンシミュレーションで実装）をクロックレジスタ制御で作用させます。QPE の原理により、|u_j> に対応する固有値 λ_j がクロックレジスタに2進小数 |λ̃_j> として書き込まれます。QPE そのものの仕組みは 量子フーリエ変換 の記事で扱った逆QFTによる位相の復調が骨格です。

**段階2（条件付き回転）**が HHL の心臓部です。クロックに書かれた固有値 λ̃_j を制御に使い、補助量子ビットを次のように回転させます。

|λ̃_j>|0>  →  |λ̃_j>( √(1 - C²/λ_j²) |0> + (C/λ_j) |1> )

ここで C は正規化定数で、|C/λ_j| ≤ 1 を保つため C ≈ 1/κ（最小固有値のオーダー）に選びます。回転角は θ_j = arcsin(C/λ_j) で、これは「固有値 λ_j の逆数を振幅に埋め込む」操作そのものです。回転には固有値の逆数 1/λ_j を古典計算する副回路が要りますが、これも可逆に実装します。

**段階3（逆位相推定）**では段階1を逆順で実行し、クロックレジスタを |0> に戻して主レジスタと解きほぐします（アンコンピュテーション）。これでクロックが |b> の成分ともつれた状態が解消され、補助ビットと主レジスタだけの状態になります。

測定：ここで「1/λ 倍」を確定させる

段階3の後、補助ビットを測定して |1> が出た場合にのみ、主レジスタは目的の状態に射影されます。

補助ビットで |1> を観測  ⇒  主レジスタ ∝ Σ_j (β_j / λ_j) |u_j> = |x>

つまり |1> を得られたときだけ、各振幅が 1/λ_j 倍された解 |x> が手に入ります。逆に |0> が出たら失敗で、最初からやり直します。

計算量と「指数加速」の但し書き

HHL の計算量は、行列サイズ N（= 2^n）、スパース性 s、条件数 κ、目標精度 ε を使って概ね次のようにまとめられます。

HHL（振幅増幅込み）:  ~ O( s · κ · polylog(N) / ε )   （簡略表記）
古典の共役勾配法(CG):  ~ O( N · s · √κ · log(1/ε) )   （疎・良条件の場合）

注目すべきは、HHL が次元 N に polylog(N)（対数多項式） でしか依存しない点です。古典法が N に少なくとも線形に依存するのと比べ、これは N に関して指数的な加速に見えます。だからこそ HHL は「量子機械学習」ブームの火付け役になりました。しかし、この加速が本物であるためには4つの条件をすべて満たす必要があり、どれか一つでも崩れると加速は消えます。

条件数がなぜ本質的に効くのか

4つの但し書きの中でも、条件数 κ は HHL に固有の重みを持ちます。逆行列 A^{-1} の作用は最小固有値 λ_min の成分を 1/λ_min 倍に増幅しますが、λ_min が小さい（＝κ が大きい）ほどこの増幅が過激になり、条件付き回転の角度が微小になって成功確率が潰れます。

デクアンタイゼーション：加速はどこまで本物か

HHL 型の量子機械学習アルゴリズムには、近年強い留保が付きました。**デクアンタイゼーション（脱量子化）**と呼ばれる一連の古典アルゴリズムが、「量子と同じ入力仮定（サンプリングアクセス）を古典にも与えれば、多くの低ランク問題は古典でも polylog(N) 時間で解ける」ことを示したのです。

実機での位置づけ

HHL は QPE を含む深い回路を必要とし、e^{iAt} のハミルトニアンシミュレーションも多数のゲートを要します。これは誤り耐性量子計算機を前提とする重量級アルゴリズムであり、NISQとデコヒーレンス で述べた現行機の浅い回路制約とは相性が良くありません。実機の小規模デモは 2×2 程度の系に留まっています。NISQ 時代に線形方程式を扱うなら、変分回路で Ax=b の残差を最小化する VQLS（Variational Quantum Linear Solver） のような、浅い回路と古典最適化を組み合わせるハイブリッド手法が現実的で、これは 変分量子アルゴリズム（VQE・QAOA） と同じ設計思想の延長にあります。

まとめ

• HHL は Ax=b の解に比例する量子状態 |x> ∝ A^{-1}|b> を作るアルゴリズムで、解を配列として返すのではなく振幅に符号化する点が古典ソルバと本質的に異なる。
• 仕組みは、量子位相推定で A の固有値 λ_j をクロックへ転写し、補助ビットへの条件付き回転で振幅を 1/λ_j 倍して逆行列を実現し、逆位相推定で後片付けする3段構成。補助ビットが |1> を示したとき解 |x> が得られる。
• 次元 N に対する polylog(N) の指数加速は、スパース性 s・条件数 κ・安価な状態生成・期待値での読み出しの4条件が全て揃ったときのみ成立する。
• 特に読み出しの制約（全成分を得ると O(N) に戻る）と条件数の線形依存は原理的に消せず、さらにデクアンタイゼーションにより古典との分離が疑われる領域も広い。HHL は「特定構造の問題で、特定のスカラー量を問う」道具として理解するのが正確である。