技術要約：誘導状態を用いた基底状態エネルギー推定のための最適量子アルゴリズム

問題設定

本論文は、量子シミュレーションにおける基本的タスクである、ハミルトニアン $H$ の最小固有値（基底状態エネルギー $E_0$）を精度 $\delta$ で推定する誘導基底状態エネルギー推定問題（guided ground-state energy estimation problem）を扱う。この問題は、ユニタリ演算子 $A$ によって準備された「誘導状態」 $|\psi\rangle$ へのアクセスを前提としており、この状態は $H$ の基底空間に対して約束されたオーバーラップ $\gamma$ を持つ（すなわち $\|\Pi_0|\psi\rangle\| \ge \gamma$）。

標準的な還元手法（時間発展ユニタリ $U = e^{-iH}$ または量子ウォーク演算子の使用）を通じて、この問題は誘導最大固有位相推定問題（guided maximum eigenphase estimation problem）へとマップされる。これは、対応する固有空間に対する入力状態 $|\psi\rangle$ のオーバーラップ $\gamma$ が与えられた条件下で、ユニタリ $U$ の最大固有位相 $x_0$ を推定する問題である。

本研究以前の最良の量子アルゴリズムでは、この問題に対して $O(\frac{1}{\gamma\delta} \log \frac{1}{\gamma})$ 回の $U$ へのクエリが必要であった。この対数因子は、量子位相推定（QPE）における離散化誤差を抑制するため、あるいは信号 $\gamma$ をノイズから区別するために、量子シンギュラ・バリュー変換（QSVT）におけるステップ関数を十分な精度で近似する必要があったことに起因していた。しかし、Mandeとde Wolf [MdW26] によって $\Omega(\frac{1}{\gamma\delta})$ という一致する下界が確立されており、既存のアルゴリズムには対数的なギャップが存在していた。

手法

著者らは、[BJY24] で開発されたトランスデューサ（transducers）に基づく量子アルゴリズムを導入することで、このギャップを解消する。トランスデューサのフレームワークは、典型的な対数的オーバーヘッドなしに量子サブルートを合成することを可能にする。

1. トランスデューサ・フレームワーク

トランスデューサは、量子計算を、「パブリック」な空間を自身に写像しつつ、「プライベート」な空間（触媒）を利用するプロセスとしてモデル化する。主要な特徴は、サブルートを $n$ 回呼び出す際に通常必要となる $O(\log n)$ のオーバーヘッドを負うことなく、トランスデューサを合成できることである。エラーを低減するために有界誤差のサブルートを繰り返す代わりに、正確な（エラーのない）トランスデューサを合成し、最後に結果を有界誤差アルゴリズムへと戻すことができる。

2. 決定バージョンと合成

アルゴリズムの核となるのは、最大固有位相問題の決定バージョン（閾値問題）である。これは、閾値 $s$ が与えられたとき、最大固有位相 $x_0 \ge s$ か、あるいは $x_0 \le s - \delta'$ であるかを判定するものである。

著者らは、以下の2つの単純なトランスデューサを合成することで、この閾値問題のための標準的なトランスデューサを構築する：

• 決定振幅増幅（Decision Amplitude Amplification）: ある状態とマークされた部分空間とのオーバーラップが非ゼロであるか（具体的には、オーバーラップ $\ge \gamma$ と $0$ の区別）を決定する。これは、境界エッジを持つグラフ上の量子ウォークとしてモデル化される。
• 決定位相推定（Decision Phase Estimation）: 固有位相 $x$ が閾値より大きいか小さいかを決定する無限次元のトランスデューサ。これは、ウォーク演算子の挙動が閾値に対する固有位相に依存する、無限直線上の量子ウォークとしてモデル化される。

これらを合成することで、著者らは閾値最大固有位相問題を決定するトランスデューサを作成する。極めて重要な点として、彼らはこのトランスデューサをオラクル $O_\gamma(A)$ に対して**標準的（canonical）**となるよう設計しており、これにより、ユニタリ $U$ よりも少ない回数の状態準備ユニタリ $A$ の呼び出しを可能にしている。

3. 無限次元の切り捨て

決定位相推定トランスデューサは、無限次元のヒルベルト空間（カウンタとして機能）上で動作する。著者らは、$K$ ステップの範囲内であれば、アルゴリズムが高いレベルにサポートを持たない状態から開始することを条件として、エラーを発生させることなく、この無限空間を有限次元 $D = O(K)$ に切り捨てられることを証明している。これにより、アルゴリズムが有限の量子ハードウェア上で実装可能であることが保証される。

主な貢献と結果

1. 最適なクエリ複雑性

主要な結果は、以下の複雑度で誘導最大固有位相推定問題を解くアルゴリズムである：

• $U$（および $U^\dagger$）への呼び出し回数: $O\left(\frac{1}{\gamma\delta}\right)$
• $A$（および $A^\dagger$）への呼び出し回数: $O\left(\frac{1}{\gamma} \log \frac{1}{\delta} \log \log \frac{1}{\delta}\right)$
• ゲート数: $O\left(\frac{1}{\gamma\delta} \log \frac{1}{\gamma\delta} + \frac{1}{\gamma} \log N \log \frac{1}{\delta} \log \log \frac{1}{\delta}\right)$

これは、[MdW26] で確立された $U$ への呼び出しに関する下界 $\Omega(\frac{1}{\gamma\delta})$ と一致しており、対数的なギャップを閉じたものである。状態準備ユニタリ $A$ の呼び出し回数は、多項式対数因子を除いて最適である。

2. アルゴリズムの構造

アルゴリズムは、固有位相の範囲 $[0, \pi/2]$ に対してバイナリサーチ（区間探索）を行う。各ラウンドにおいて、閾値トランスデューサを用いて区間を狭めていく。エラー予算は、総失敗確率を一定に保ちつつ、$U$ の呼び出しコスト（複雑度の支配要因）を各ラウンドで一定に保ち、$A$ の呼び出しコストを最小化するように各ラウンドに分配される。

3. 理論的意義

本論文は、誘導基底状態エネルギー推定の正確な漸近的クエリ複雑性に関する、Mandeとde Wolfによる未解決の問いに答えるものであると主張している。トランスデューサを活用することで、著者らは、位相推定におけるエラー低減のために必要と考えられていた対数的なオーバーヘッドを排除できることを示した。これは、同様の対数因子が発生する他の量子アルゴリズムの最適化において、トランスデューサが強力なツールとなり得ることを示唆している。

意義と限界

著者らは、本研究が誘導基底状態エネルギー問題に対して**クエリ最適（query-optimal）**なアルゴリズムを提供すると述べている。改善点は、従来の接近手法と比較して $1/\gamma$ の対数因子である。

論文における実用的な影響については、控えめな記述となっている：

• 定数因子: 著者らは、アルゴリズム設計において定数因子の最適化を行っていないことを指摘している。アルゴリズム自体は「特に複雑ではない」ものの、この漸近的な改善が、特定の物理的または化学的なパラメータに対して、さらなるエンジニアリングなしに実行速度の向上として現れるかどうかは不明である。
• 空間オーバーヘッド: 本アルゴリズムは、標準的な手法の $O(\log \frac{1}{\delta})$ に対し、$O(\log \frac{1}{\gamma\delta})$ の追加の量子ビットを必要とする。著者らは、空間複雑性をさらに削減できるかという問いを投げかけている。
• コヒーレンス: 論文では、アルゴリズムを完全にコヒーレントにする（丸め約束なしにする）ことには既知の限界があることを認めており、この側面に関する体系的な研究は今後の課題としている。

要約すると、本論文は、トランスデューサのフレームワークを利用して、誘導最大固有位相推定における既知の下界と一致する理論的な上界を確立し、クエリ複雑性における持続的な対数的オーバーヘッドを取り除いた。