テクニカル・サマリー：可換局所ハミルトニアン問題：BQP困難性に対する相対化された証拠

1. 問題設定と背景

可換局所ハミルトニアン (Commuting Local Hamiltonian: CLH) 問題は、すべての局所項が互いに可換である局所ハミルトニアンの基底状態エネルギーが、閾値 $\alpha$ 未満か、あるいは $\beta$ 以上であるかを判定する問題である。一般的な局所ハミルトニアン問題は QMA 完全であるが、可換な変種としての CLH の複雑さは、量子計算複雑性理論における中心的な未解決問題である。

先行研究では、特定の家族の可換ハミルトニアン（例：2-local、特定の3-local、または特定の格子上のもの）に対して、この問題が NP に属することが示されている。しかし、一般的な CLH 問題が QMA 完全 である可能性を排除する正式な証拠は存在していなかった。

QIMA (Quantum Interactive Merlin-Arthur with Commuting units) という複雑さのクラスは、Bostanci と Hwang によって、その局所的なテスト・ユニットが互いに可換な反射（reflection）である量子検証器の能力を捉えるものとして導入された。CLH 問題は QIMA 完全である。したがって、CLH が QMA 完全であるかという問いは、QIMA = QMA かどうかを問うことと同義である。

本論文は、相対化された設定において、QIMA と BQP (Bounded-error Quantum Polynomial time) の関係を調査する。具体的には、BQP$^O \not\subseteq$ QIMA$^O$ となるような古典的オラクル $O$ が存在するかどうかを決定することを目的とする。正の結果が得られれば、一般的な CLH 問題が BQP 困難である可能性（ひいては QMA 完全である可能性）に対する相対化された証拠となる。

2. 手法と定義

2.1 オラクルモデル QIMA$^O$

著者らは、QIMA$^O$ と表記される、QMA$^O$ の非自明な制限となるように設計された相対化された QIMA を以下のように定義する：

• 検証器の構造: 入力 $x$ に対し、検証器は古典的な前処理（$O$ への適応的なクエリ）を行い、量子ウィットネスに作用する一連の「ユニット」 $W_1^O, \dots, W_m^O$ を生成する。
• 可換性: 約束されたインスタンスにおいて、すべてのユニットは互いに可換である：$[W_i^O, W_j^O] = 0$。
• 反射の要件: 決定的に重要なのは、少なくとも一つの量子オラクルクエリを含むユニット $W_j^O$ は、厳密な反射（すなわち、$(W_j^O)^\dagger = W_j^O$ かつ $(W_j^O)^2 = I$）でなければならない点である。オラクルを含まないユニットは任意のユニタリ演算であってよい。
• 検証: 検証器はアダマール・テストを用いて、ウィットネスが各ユニットの $+1$ 固有空間にあるかどうかをチェックする。
• 信頼できる補助量子ビットの不在: 検証器は、アダマール・テストに使用される新鮮な制御量子ビットを除いて、信頼できるワークスペースを持たない。

著者らは、この反射の要件が不可欠であると主張している。これを、任意の可換なユニット（近似的な反射であっても）を許容するように緩和したり、信頼できる補助量子ビットを許可したりすると、クラスが QMA$^O$ に崩壊することを示している。

2.2 Forrelation 問題

分離の根拠となるのは、Aaronson によって定義された Forrelation 問題である。オラクルへのアクセス権を持つ 2 つのブール関数 $f, g: \{0,1\}^n \to \{-1, +1\}$ が与えられたとき、以下のいずれかを判別するタスクである：

• Yes: $f$ は $g$ のフーリエ変換と高い相関を持っている ($\Phi(f,g) \ge \alpha$)。
• No: 相関が小さい ($|\Phi(f,g)| \le \beta$)。

Forrelation は、定数個の量子クエリを持つ BQP アルゴリズムによって解くことができる。本論文の目的は、Forrelation に対する QIMA$^O$ 検証器の量子クエリ数に対して指数関数的な下限を証明することである。

3. 主な貢献と結果

3.1 オラクル分離: BQP$^O \not\subseteq$ QIMA$^O$

主要な結果は、BQP$^O \not\subseteq$ QIMA$^O$ となるような古典的オラクル $O$ の構成である。これは、Forrelation 問題に対する QIMA$^O$ 検証器に対する指数関数的なクエリ下限を証明することによって達成される。

定理 1.7 (非公式): すべての約束されたペア $(f, g)$ に対して Forrelation を決定する任意の QIMA$^O$ 検証器は、以下を満たさなければならない：
$$C(n) + T(n) \ge \beta 2^n - O(1)$$
ここで、$C(n)$ は古典的前処理クエリ数、$T(n)$ は総量子オラクルクエリ数である。

証明のスケッチ:

1. 多項式法 (Polynomial Method): 検証器の受理確率は、オラクルの真理値表の要素に関する多項式として表現される。
2. 可換性と反射: オラクルを含むユニットは厳密な反射であり、かつ可換であるため、それらの結合受理演算子は直交射影の積となる。これにより、著者らはすべての受理部分空間の共通部分を表す単一の射影体 $P_f$ を定義できる。
3. 次数の境界: 受理確率を表す多項式の次数は、総量子クエリ数 $T(n)$ によって抑えられる。
4. 完全な Forrelation ペア: 著者らは、$\Phi(g, h) = 1$ となる「完全な Forrelation ペア」（ベント関数）を利用する。$h$ を $k$ ビット摂動させたとき、Forrelation の値が線形に変化することを示す：$\Phi(g, f) = 1 - 2k/N$。
5. 対称化: 古典的なトランスクリプトを固定し、完全なペアからのハミング距離が一定であるような関数について平均化することで、一変数多項式 $q(k)$ を構築する。
6. 根の計数: 多項式 $q(k)$ は、すべての「No」インスタンス（大きな範囲の $k$）に対してゼロであり、「Yes」インスタンス（$k=0$）に対しては非ゼロでなければならない。非ゼロの多項式は、その次数よりも多くの根を持つことはできないため、次数（したがってクエリ数）は指数関数的にならざるを得ない。

3.2 分離の頑健性

本論文は、モデルのわずかな緩和に対しても分離が保持されることを示している：

• 無視可能な偏差: オラクルを含むユニットが、厳密な反射に（演算子ノルムにおいて）無視できる程度に近いことが許容される場合でも、クラスは QIMA$^O$ のままであり、下限は依然として成立する。
• 制限されたアドレス・サポート: オラクルを含まない回路が、クエリの周囲でアドレス量子ビットのわずかな数（$k$）にのみ非自明に作用する場合、反射ではないユニットであっても、クエリの下限は超多項式となる。

3.3 モデルのタイトさ (崩壊の結果)

QIMA$^O$ の定義における特定の制約を正当化するために、著者らはこれらの制約を緩和するとクラスが QMA$^O$ に崩壊することを証明している：

• 逆多項式偏差: ユニットが反射から逆多項式距離の範囲内であることが許容される場合（無視できる程度ではなく）、クラスは QMA$^O$ に崩壊する。これは、Marriott-Watrous の増幅ガジェットの変種を用いて、単一のユニットで QMA 検証器をシミュレートすることで示される。
• 反射なしの単一クエリ: 反射の要件が完全に除去され、かつユニットが単一のクエリに制限されている場合でも、クラスは依然として QMA$^O$ に崩壊する。これには、マルチクエリ・シミュレーションを単一クエリにエンコードするための、サイクリック・クロック構成（Feynman-Kitaev に類似）が用いられる。
• 信頼できる補助量子ビット: 検証器が（$|0\rangle$ に初期化された）単一の信頼できる補助量子ビットを持つことを許可すると、QIMA は QMA に、QIMA$^O$ は QMA$^O$ に崩壊する。これは、QMA 完全であることが知られている「Pinned Commuting Local Hamiltonian」問題に基づいている。

4. 意義と主張

本論文は、一般的な CLH 問題が BQP 困難である可能性に対する相対化された証拠を提供すると主張している。BQP は QMA に含まれるため、もし CLH が BQP 困難であれば、それは QMA に関する強力な構造的性質を意味することになる。分離 $BQP^O \not\subseteq QIMA^O$ は、QIMA における可換性の制約（およびひいては CLH における制約）が、たとえオラクルの存在下であっても、クラスが BQP の全能力を捉えることを妨げる重要な制限であることを示唆している。

さらに、本研究は QIMA 定義のタイトさを明確にしている。著者らは、可換性、オラクルクエリに対する反射の要件、および信頼できる補助量子ビットの不在という特定の組み合わせが、QMA よりも厳密に弱いクラスを定義するために必要であると主張している。これらの条件のいずれかを緩和すると、直ちに QMA の全能力が回復される。これは、QIMA の「量子性」が極めて脆弱であり、まさにこれらの構造的制約に依存していることを示唆している。

これらの結果は、CLH が QMA 完全であるかという非相対化された問題を解決するものではないが、構築されたオラクルに関してその命題が成立しないことから、そのような完全性を証明するには非相対化の手法が必要であることを確立している。