Many Hamiltonians Are Sparsifiable

本論文は、パウリストリングや高ランク演算子から構成されるものを含む広範な$r$-局所ハミルトニアンが、そのスペクトル特性を保持しつつ、はるかに少ない項数に頑健に疎化可能であることを示しており、これにより従来の見解に挑戦し、量子 Max-Cut などの問題に対する改良された半ストリーミングアルゴリズムの実現を可能にしている。

要約

巨大で極めて複雑な量子ケーキのレシピを想像してください。このレシピは単なる材料のリストではなく、ケーキの異なる部分がどのように相互作用するかを指示する、数千に及ぶ具体的な手順（「項」と呼ばれる）の集まりです。このケーキを焼くには、すべての手順に従わなければなりません。しかし、もし手順の 99% を捨て去っても、全く同じ味になるケーキが完成するとしたらどうでしょうか？

これが、本論文で扱われるハミルトニアンの疎化の核心となるアイデアです。

量子物理学の世界において、「ハミルトニアン」とは、量子系（例えば量子ビットの集団）の振る舞いやそのエネルギー量を記述する、本質的に数学的な規則集です。通常、これらの規則集は膨大で、数百万の項を含んでいます。本論文の著者たちは問いかけます：これらの規則集を、系の物理学を変えずに、小さく管理可能なサイズに縮小することは可能でしょうか？

大きな驚き：多くの系において、可能です！

長らく、科学者たちは答えは「いいえ」だと信じていました。以前の研究では、多くの量子系において、項を捨て去れば物理法則が崩壊してしまうため、単純に項を削除することはできないと示唆されていました。これは「不可能定理」と考えられていたのです。

しかし、この論文は状況を一転させます。著者たちは、多くの一般的な種類の量子系において、答えは断固とした**「はい」**であることを示しました。項のほとんどを剥ぎ取り、わずか数個だけ残しても、系はほぼ同じように振る舞います。

秘密の材料：「非冗長性」

彼らはそれをどのように実現したのでしょうか？彼らは**「非冗長性」**と呼ばれる、問題を捉える新しい方法を考案しました。

ハミルトニアンを、建物を監視する警備員のチームだと考えてみてください。

• 冗長： 警備員 A と警備員 B が同じドアを監視しており、警備員 B を解雇しても、警備員 A が警備員 B が見ていたすべてを見ている場合、警備員 B は「冗長」です。警備員 B を解雇してもセキュリティは失われません。
• 非冗長： 警備員 C が特定の隠れた窓を唯一監視しており、警備員 C を解雇するとその窓が監視されなくなる場合、警備員 C は「非冗長」です。彼らを解雇することはできません。

著者たちは、疎化（縮小）された規則集のサイズは、完全に非冗長な項の数に依存することに気づきました。系に膨大な数の項があっても、それらの大半が制御する内容において互いの「複製」に過ぎない場合、その複製を削除することができます。

彼らは、系が持つ「固有の」項が正確にいくつあるかを測定する数学的なツールを開発しました。固有の項の数が少なければ、系は縮小しやすいのです。

彼らが縮小した 3 種類の系

この論文は、この手法が量子の「レシピ」の 3 つの特定のタイプで機能することを証明しています。

1. パウリ・ストリング（「標準的な」ブロック）： これらはほとんどの量子コンピュータの構成要素です。著者たちは、これらで構築された巨大な系であっても、サイズを量子ビットの数に対して線形的に増加する規模（小さな誤差因子を加えて）に縮小できることを示しました。10,000 の手順のうち、実際に固有なのは 500 だけだと気づいたようなものです。
2. ランダム演算子（「カオス的な」系）： 規則がランダムに生成される系を想像してください。驚くべきことに、著者たちはこれらのカオス的な系は、古典的な対応物よりも縮小しやすいことを発見しました。古典的な世界（標準的な論理パズルなど）では、ランダムな規則の単純化は困難です。しかし、量子世界では、ランダムな規則には多くの「重複」が含まれており、その大半を削除できるのです。
3. 量子 SAT（「厳しい」制約）： これは規則が非常に厳格（ランクが高い）な系に関わります。著者たちは、これらの厳格な系さえも、大幅に単純化できることを示しました。

現実世界への応用：量子「最大カット」

この論文は理論にとどまらず、量子最大カットと呼ばれる有名な問題に応用されています。人々（量子ビット）のネットワークがあり、2 つのグループに分割して、グループ間の接続数を最大化したいと想像してください。

• 問題： これを解決するには、通常、ネットワーク内のすべての接続を確認する必要があります。ネットワークが巨大であれば、これには永遠に時間がかかります。
• 解決策： 疎化技術を用いることで、著者たちは接続の大半を捨て去り、わずかなサンプルだけを残しても、最良の分割を見つけることができることを示しました。
• 「ストリーミング」ボーナス： これは、ネットワーク接続のライブフィードのような、高速なストリームとしてデータが到着する場合に特に優れています。著者たちは、このデータを非常に少ないメモリ（疎化された微小なバージョンを保持するのに十分な量）で処理し、なおかつ正しい答えを得られることを示しました。これは、以前はコンピュータサイエンスにおいて未解決だった問いを解決します。

「古典対量子」の転回

最も魅力的な発見の一つは、古典系と量子系の比較です。

• 古典： 古典的な論理パズルの世界では、ランダムな規則の単純化はしばしば非常に困難です。
• 量子： 量子の世界では、ランダムな規則の単純化はしばしば容易です。

著者たちは、量子系は私たちが考えていたよりも「冗長性が高い」傾向があると示唆しています。量子状態は複雑な方法で互いに干渉し合うため、多くの項が同じ役割を果たすことになり、それらを削除することが可能になるのです。

まとめ

簡単に言えば、この論文は複雑な量子規則集を単純化する方法に関するガイドです。

• 古い見方： 「これらを単純化することはできない。すべての項が不可欠だ。」
• 新しい見方： 「実際には、ほとんどの項は互いのコピーに過ぎない。重複を見つける方法（彼らの「非冗長性」ツールを使用）を知っていれば、結果を変えずに規則集を大幅に縮小できる。」

この発見は、量子コンピュータのためのより効率的なアルゴリズムへの扉を開き、問題を「疎化された」バージョンで最初に処理することで、より速く、より少ないメモリで問題を解決することを可能にします。

技術概要

技術的サマリー：多くのハミルトニアンは疎化可能である

問題定義

本論文は、ハミルトニアンの疎化の問題を調査する。$n$ 量子ビットのハミルトニアン $H = \sum_{i=1}^m H_i$ が与えられたとき、ここで各 $H_i$ は $r$-局所な半正定値（PSD）項である。目標は、すべての量子状態 $|\psi\rangle \in \mathbb{C}^{2^n}$ に対して以下の式が成り立つような、項の疎な部分集合 $L \subseteq [m]$ と非負の重み $w: L \to \mathbb{R}_{\ge 0}$ を計算することである：
$$\sum_{i \in L} w(i) \langle \psi | H_i | \psi \rangle \in (1 \pm \varepsilon) \sum_{i=1}^m \langle \psi | H_i | \psi \rangle$$
目的は、基底状態や低エネルギー部分空間だけでなく、すべての状態のエネルギーを保存する、$|L| \ll m$ なる疎化子 $\tilde{H}$ を見出すことである。これは、基底状態とスペクトルギャップのみを保存することを要求する「ギャップシミュレーション」とは対照的である。

歴史的に、このタスクは一般的なハミルトニアンに対してはほぼ不可能であると考えられていた。Aharonov と Zhou [AZ19] は、特定のハミルトニアンが、より弱い目標であるギャップシミュレーションさえも疎化できないことを示し、ハミルトニアンの疎化には本質的な限界があるという支配的な信念を生み出した。本論文は、広範かつ頑健なクラスのハミルトニアンに対して疎化が可能であることを示すことで、その見解に挑戦する。

手法と中核概念

1. 非冗長性

導入された中心的な技術的ツールは、古典的な制約充足問題（CSP）で用いられる概念の量子版である非冗長性である。

• 定義: ハミルトニアン $H$ が非冗長であるとは、各項 $H_i$ に対して、$\langle \psi | H_i | \psi \rangle \neq 0$ でありながら、すべての $j \neq i$ に対して $\langle \psi | H_j | \psi \rangle = 0$ となるような状態 $|\psi\rangle$ が存在する場合をいう。
• 含意: ハミルトニアンが非冗長である場合、それは疎化できない（任意の項を除去すると、その項を一意に満たす特定の状態に対する条件が破られるため）。
• 戦略: 著者らは、最大非冗長部分インスタンスのサイズ（述語行列 $M$ に対して $NRD(M, n)$と表記）を評価する。このサイズが小さい場合（例えば$n$ に対して線形の場合）、そのハミルトニアンは高度に疎化可能である。

2. 交差する項の分析

重要な洞察は、交差する局所項の核（基底状態）間の相互作用の分析である。

• 分離した核: 十分に高いランクを持つランダムなハミルトニアンについて、著者らは、2 つの項 $H_i$ と $H_j$ が少なくとも 1 つの量子ビットを共有する場合、それらの核は分離している（すなわち、$\ker(H_i) \cap \ker(H_j) = \{0\}$）ことを証明する。これは、状態が自明でない限り、いかなる状態も同時に 2 つの項をゼロエネルギーで満たすことはできないことを意味する。
• 自己同型群: より低いランク、または特定の構造を持つハミルトニアン（2 量子ビット系など）については、著者らは基底状態の自己同型群を分析する。交差する項が基底状態に対称性（量子ビットの置換）を誘起することを示す。相互作用グラフが特定のサイクルを含む場合、これらの対称性はハミルトニアンを冗長に強制し、それによって非冗長部分集合のサイズを制限する。

3. 疎化アルゴリズム

本論文は、項の「重要度スコア」に基づいた 2 つの主要なアルゴリズム戦略を採用している。

• 重要度サンプリング: 項 $H_i$ の重要度は $\max_{|\psi\rangle} \frac{\langle \psi | H_i | \psi \rangle}{\langle \psi | H | \psi \rangle}$ と定義される。交差する項の非交な対の和の最小固有値がゼロから離れて有界であれば、個々の項の重要度は小さくなる（$O(1/m)$）。
• 行列 Chernoff bound: 重要度スコアが有界になった後、著者らは行列 Chernoff 境界を用いて、適切に重み付けされた項のランダムサンプリングが高い確率で有効な疎化子を生み出すことを示す。
• 再帰的ピーリング: 零度 1 の述語については、アルゴリズムが「支配的カバ」を反復的に抽出し（スパンニング森と支配的辺）、残りを再帰的に疎化する。

主要な貢献と結果

1. パウリハミルトニアン

• 結果: $m$ 個の項を持つ任意の $r$-局所パウリハミルトニアン（項はシフトされたパウリストリング）は、サイズ $\tilde{O}_r(\varepsilon^{-2} n)$ に疎化可能である。
• 手法: 著者らは相互作用ハイパーグラフを $r$-部グラフに分割する。部グラフ設定ではパウリストリングが交換するため、基底変換を通じて古典的な XOR-CSP の疎化に問題を還元できる。その後、古典的 CSP の疎化結果を適用する。

2. 一般的なランダムハミルトニアン

• 結果: 各項がランク $R \ge 2^{r-1} + 1$ のランダムな PSD 行列であるハミルトニアンについて、高い確率でサイズ $\tilde{O}_r(\varepsilon^{-2} n)$ への疎化が可能である。
• 意義: この結果は、ランク不足行列であっても（ランクが十分に高ければ）成り立つ。これは、ランダムな量子ハミルトニアンが、しばしば超線形な疎化子サイズを必要とする古典的対応物（ランダム CSP）よりも著しく疎化しやすいことを示している。

3. 零度 1 のハミルトニアン（量子 SAT）

• 結果: 各項の零度が最大 1（ランク $\ge 2^r - 1$）であるハミルトニアンについて、サイズ $\tilde{O}_r(\varepsilon^{-2} n^2)$ の疎化子が存在する。
• 手法: 著者らは「支配的カバ」を構成し、再帰的サンプリング戦略を用いる。これは量子複雑性の基本的なクラスである量子 SAT 問題に適用される。

4. 非冗長性の特性付け

• テンソル積: 述語行列 $M$ がランク 1 行列のテンソル積である場合（例えば古典的な AND 述語）、非冗長性は $\Omega(n^r)$ であり、疎化は不可能であることを論文は証明する。これは古典的 AND 述語に対する既知の下限を一般化するものである。
• 2 量子ビット系: 著者らは 2 量子ビットハミルトニアンの非冗長性を完全に特性付ける。$NRD(M, n) = \Theta(n^2)$ となるのは、$M$ が 2 つのランク 1 行列のテンソル積である場合のみであり、それ以外の場合は $NRD(M, n) = \Theta(n)$ である。
• 一般的なランク: ランク $R = 2^{r-1} - 1$ のランダム行列について、非冗長性は $\tilde{O}(n)$ で有界であり、「一般的な」場合よりもわずかに低いランクであっても疎化を許容することを示している。

5. 量子 MAX-CUT への応用

• 結果: 本論文は、量子 MAX-CUT インスタンスを疎化する効率的なアルゴリズムを提供する。グラフ $G$ が与えられたとき、$O(\varepsilon^{-2} n)$ 個の辺を持つ疎な部分グラフ $\tilde{G}$ を見つけることができ、$\tilde{G}$ に対してほぼ最適である任意の状態は、$G$ に対してもほぼ最適となる。
• ストリーミング: この結果は Kallaugher と Parekh [KP22] による未解決問題を解決し、量子 MAX-CUT が $\tilde{O}(\varepsilon^{-2} n)$ の空間でストリーミングモデルにおいて解けることを示す。これにより、定数倍近似のみが可能となる $o(n)$ 空間から $\tilde{O}(n)$ 空間への近似可能性における位相転移が確立される。

意義と主張

本論文は、以前文献で引用されていた「ノー・ゴー」定理とは対照的に、ハミルトニアンの疎化は、自然なハミルトニアンクラスの広範な多様性に対して頑健な現象であると主張する。

1. 悲観論の否定: Aharonov と Zhou [AZ19] は特定のクラスに対する限界を示したが、この研究は、「大多数」のハミルトニアン（ランダムなものや量子符号化や SAT に由来するものを含む）が、準線形サイズまで疎化可能であることを実証する。
2. 量子対古典: この結果は、量子系と古典系の間の根本的な相違を浮き彫りにする。十分なランクを持つランダムな量子ハミルトニアンは、しばしば超線形な疎化子を必要とするランダムな古典 CSP よりも疎化しやすい。
3. アルゴリズム的有用性: 疎化子は量子アルゴリズムの前処理ステップとして機能する。項の数を削減することで、下流のアルゴリズムは記述複雑度が低いシステム上で動作できる。
4. 理論的枠組み: ハミルトニアンに対する非冗長性の体系的な理論の導入は、量子基底状態とその相互作用の構造を理解するための新たな視点を提供し、量子ハミルトニアン複雑性と古典的 CSP 理論の間のギャップを埋める。

著者らは結論として、疎化が普遍的ではないこと（例えば、テンソル積ランク 1 述語では失敗する）を認めつつも、それが成功する条件は広範であり、多くの物理的に関連性があり、アルゴリズム的に重要なシステムを含んでいると述べている。