Two exact quantum queries use at most six variables

技術要約：2回の正確な量子クエリは最大6つの変数を使用する

問題の定義
本論文は、全Boolean関数に対する正確な量子クエリ複雑性（exact quantum query complexity）を取り扱う。$F: \{+1, -1\}^n \to \{+1, -1\}$ を全Boolean関数とする。正確な量子クエリ複雑性 $QE(F)$ は、すべての入力 $x$ に対して確率1で $F(x)$ を出力するために必要な最小のオラクルクエリ数である。中心となる問いは、あるクエリ複雑量の制限が与えられたとき、関数が依存し得る関連入力変数の最大数 $rv(F)$を決定することである。具体的には、本論文は$JE(2) \le 6$、すなわち$JE(k) = \max {rv(F) : QE(F) \le k}$ であることを証明することを目的としている。

多項式法（polynomial method）は $\deg(F) \le 2QE(F)$ を確立しており、その後の境界値は次数と関連する変数の数を結びつけているが、これらの一般的な境界では $JE(2) \le 6$ をタイトに証明するには不十分である。$k=2$ のケースに関する先行研究は、半正定値プログラミング（SDP）ソルバーを用いた最大4変数までのBoolean関数の数値的分類に依存していた。ここに大きなギャップが存在した。すなわち、数値的なSDPの結果の正当性に依存しない、無条件かつ解析的な証明である。

手法
著者は、「剛性のあるサポート・アンド・ブランチ分解（rigid support-and-branch decomposition）」を用いた直接的な解析的証明を提供する。証明は、矛盾による背理法を用いて進められる。すなわち、$QE(F) \le 2$ かつ $rv(F) \ge 7$ である関数 $F$ が存在すると仮定する。議論は主に2つのステップで構成される。

1. 第1クエリ・サポートの境界設定:
   著者は、直接形式 $|\phi_2(x)\rangle = O^P_x O^Q_x |\phi\rangle$（ここで $O^P_x$ と $O^Q_x$ はヒルベルト空間の直交分解に対する位相オラクルである）における2クエリ・アルゴリズムの構造を分析する。彼らは「第1クエリ・サポート」$S$ を、クエリ・パスの重み $q_j = \|Q_j|\phi\rangle\|^2$ が正となる物理座標 $j$ の集合として定義する。
   次数の低減（degree-reduction）の議論を用いることで、任意の座標 $j \in S$ について、反転された関数 $x_j F(x)$ の次数が高々3であることを示す。これにより、もし $rv(F) \ge 5$ であれば、第1クエリ・サポートのサイズは $|S| \le 4$ に制限されるという結論が導かれる。したがって、もし $rv(F) \ge 7$ であれば、第1クエリ・サポートの外側に少なくとも3つの関連座標が存在しなければならない（$Z = \text{Rel}(F) \setminus S$ とすると $|Z| \ge 3$）。

2. 1クエリ・ブランチの構造分析:
   著者は、$S$ における座標の割り当てを固定することで、アルゴリズムの「ブランチ（枝）」を作成する。$S$ への固定された割り当て $\epsilon$ に対して、残りのアルゴリズムは、残りの変数 $y$ に対する正確な1クエリ・アルゴリズムとして機能する。

• ブランチの型（Branch Types）: 各ブランチは、制限された関数 $F_\epsilon(y)$ を計算する。補題3.1によれば、任意の正確な1クエリ関数は高々2つの変数に依存する。これらの変数の集合を「型（type）」$T_\epsilon$ と呼ぶ。
• 直交制約: 2クエリの場合の決定的な困難は、クエリ・パス・ベクトルが必ずしも互いに直交するとは限らないことであり、単純なスカラー重みのカウント議論を妨げる点にある。著者は、もし2つのブランチが異なる型（$T_\epsilon \neq T_{\epsilon'}$）を持つならば、それらに対応する最終状態はすべての入力に対して直交するということを確立することで、これを克服する。
• セル分解（Cell Decomposition）: 著者は「型セル（type cells）」$C_T = \{\epsilon : T_\epsilon = T\}$ を定義する。彼らは、発生する任意の非定数な型は、$S$ の割り当ての空間において少なくとも $1/2$ の密度を持つセルを持つことを証明する。さらに、2つの異なる非定数な型が発生する場合、それらのセルは相補的な「ショート・ハーフキューブ（short halfcubes）」（単一の線形制約または2変数のパリティによって定義される集合）でなければならない。
• 次数の低減: これらのセルに対応する部分空間への投影を用いることで、各セルに制限された関数は、残りの変数のフルキューブ上での正確な1クエリ・アルゴリズムによって計算可能であることを示す。これは、各ブランチにおける関連変数の数が高々2であることを意味する。

主な貢献と結果

• 定理 1.1: 本論文は $JE(2) \le 6$ を証明する。MukherjeeとMaitraによる既知の下界構成（$QE(F)=2$ に対して $rv(F)=6$を達成するもの）と組み合わせることで、これにより$JE(2) = 6$ が確立される。
• 無条件の証明: $n \le 4$ における数値的なSDP分類に依存していた従来の導出とは異なり、この証明は純粋に解析的であり、無条件である。
• 構造的分解: 本論文は、2クエリ・アルゴリズムのための「サポート・アンド・ブランチ分解」を導入している。第1クエリ・サポートを固定することで、問題が、ブランチ間の相互作用が型の厳格な直交条件によって制御される、一連の正確な1クエリ・ブランチへと還元されることを示している。
• 干渉の処理: 本研究は、2クエリ・アルゴリズムにおいてクエリ・パス・ベクトルが必ずしも互いに直交していないという困難に明示的に対処している。著者は、干渉が制約されており、異なる型がアルゴリズムのサポートを相補的なショート・ハーフキューブへと分解させることを示すことで、これを解決している。

意義と主張
本論文は、最大2回の正確な量子クエリで計算可能なすべての全Boolean関数が、高々6つの入力変数に依存するという、最初の無条件の証明を提供すると主張している。著者は、関数 $G_2(x_1, \dots, x_6) = \frac{1+x_1x_2}{2}x_3x_4 + \frac{1-x_1x_2}{2}x_5x_6$ が正確なクエリ複雑量2と6つの関連変数を持つことから、この境界がシャープ（最適）であることを指摘している。

2クエリ・アルゴリズムの構造的記述（特に、相補的なショート・ハーフキューブ・サポートを持つブランチへの剛性のある分解）は、独立した関心を持つ結果として提示されている。著者は、この構造的理解が、より高いクエリ複雑性へと結果を拡張するために必要となる可能性があると示唆しており、$k=3$ のケース（$QE(F) \le 3$ ならば $rv(F) \le 14$ かどうか）は未解決のままであると述べている。論文は最後に、すべての正の整数 $k$ に対して $JE(k) = 2^{k+1} - 2$ であるという予想1.2を提案して締めくくっている。