Quantum Approximation Complexity of Classical Optimization Problems

タイトル： 古典的最適化問題における量子近似複雑性
著者： Stuart Hadfield

問題提起

本論文は、量子最適化アルゴリズムにおける厳密な最悪ケースの性能保証の欠如に対処している。多くの量子手法（QAOA、DQIなど）は、特定のインスタンスに対して高いスコアを示したり、期待値（デコードされた平均値）に関する境界を提供したりするが、有界な誤差を持つすべての入力に対して特定の近似比を保証する一様なアルゴリズムを欠いていることが多い。本研究は、量子的な近似複雑性クラス（APX、PTAS、FPTAS）の量子版を形式的に定義し、量子計算が、要求された精度を達成するために必要な時間または保証された解の質において、ランダム化された古典的アルゴリズムを厳密に上回ることができるかどうかを判断することを目的としている。

手法

著者は、有界誤差量子アルゴリズムを含めるために、NP最適化（NPO）問題の枠組みを拡張している。

1. 量子クラスの定義： 本論文では、BQ-APX、BQ-PTAS、および BQ-FPTAS を定義する。これらのクラスへの所属には、すべての入力に対して、主張された近似比を少なくとも $2/3$ の確率で達成する実行可能な古典的解を返す「一様な」量子アルゴリズムが必要とされる。決定的なことに、実行時間は、パラメータ選択、状態準備、測定、デコード、および反復のすべてのステップを含む。解のスコアは、古典的に効率よく計算可能でなければならない。
2. デコード平均から出力への転送： 理論的な主要ツールである補題6および系7は、デコードされた解の「期待値」と、「有界誤差」の古典的出力保証との間の関係を確立している。これにより、期待値ベースの解析（量子文献で一般的である）を、クラス所属に求められる厳密な出力保証へと翻訳することが可能になる。
3. 条件付き分離： 本論文では、標準的な複雑性仮定（例：$NP \not\subseteq BQP$ および $Factor \notin FBPP$）の下で、量子クラスと古典クラスの間の厳密な包含関係を示すための特定の問題を構築している。これらの構成は、「サーチ・パディング（search padding）」と暗号学的困難性に依拠している。

主な貢献と結果

1. 量子近似クラスの形式的な階層
本論文は、$NP \not\subseteq BQP$ という仮定の下で、量子近似クラスの厳密な階層を確立している：
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
この階層は、以下の古典的問題によって示される：

• Max-E3SAT： 決定論的な定数比近似（APXに属する）を持つが、量子PTASは持たない。
• 平面グラフの頂点被覆（Planar Vertex Cover）： 決定論的なPTASを持つが、量子FPTASは持たない。
  これらの結果は、量子クラスが互いに区別されることを示しているが、これらの特定の問題については、量子とランダム化された古典的クラスをまだ分離していない。

2. 認定最大次数 (Certified Maximum Order: CMO): 強固な量子・古典分離
本論文では、要素 $N$ を法とする乗法的次数を、その次数の素因数分解によって認定する、**認定最大次数（CMO）**問題を導入している。

• 量子的な結果： 有界誤差量子アルゴリズムは、因数分解と周期発見を用いることで、多項式時間で正確な最適値（カーマイケル関数 $\lambda(N)$）を見つけることができる。したがって、$CMO \in BQ\text{-}FPTAS$ である。
• 古典的な障壁： 多項式因子による近似比さえも保証するランダム化多項式時間アルゴリズムがCMOに対して存在する場合、それはランダム化多項式時間での因数分解アルゴリズムを意味することになる。
• 結論： $Factor \notin FBPP$ と仮定すると、$CMO \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$ となる。これは、量子アルゴリズムが正確な解を提供する一方で、ランダム化された古典的アルゴリズムは多項式近似すら達成できないという、条件付きの分離を確立している。

3. 離散対数適合 (Discrete-Logarithm Fitting: DLog-Fit): 閾値分離
本論文では、離散対数に基づくサンプル上のラベルを予測する問題である DLog-Fit を定義している。

• 古典的なベースライン： 決定論的アルゴリズムは、$1/2$ 近似（多数派のラベルを予測すること）を達成する。
• 量子的優位性： 量子アルゴリズムは、完全な適合（正確な最適値）を見つけることができる。
• 古典的な障壁： $1/2$ の比率に対して固定された改善をランダム化された古典的アルゴリズムが行うことは、セーフプライムの部分群における離散対数問題を解くことを意味する。
• 結論： セーフプライムの離散対数が $FBPP$ に属さないという仮定の下で、$DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$ となる。これは、$1/2$ の近似閾値におけるギャップを示している。

4. 一般的なサーチ・パディング (Theorem 8)
本論文は、効率的に検証可能な証拠（witness）を持つあらゆる探索問題が、$1/2$ 近似閾値を持つNPO問題へと変換できることを示す一般的な構成を提供している。もし量子ソルバーが存在するがランダム化された古典的ソルバーが存在しない場合、得られる最適化問題は $BQ\text{-}FPTAS$ に属するが $R\text{-}PTAS$ の外側に位置することになる。

5. 既存の量子手法の分析
本論文は、既存のアルゴリズムにこれらの定義を適用している：

• QAOA： 3-正則MaxCutに対する固定深さのQAOAについて、本論文はデコード平均の転送を用いることで、反復によって有界誤差の出力保証（例：最適値の $2/3$ を超えること）が得られることを示し、この特定のグラフ族を $BQ\text{-}APX$ に分類している。
• デコード量子干渉法 (DQI)： DQIは（折り畳まれたOPIのような）特定のファミリにおいて期待スコアの向上を示すが、明示的な入力時間モデルにおいて分離を確立するには、ランダム化された古典的アルゴリズムが同じ比率を達成できないことを証明する必要があり、これは未解決の課題であることを本論文は指摘している。

意義と主張

本論文は、有界誤差量子近似クラスの厳密な定義を提供し、明示的な複雑性仮定の下で、量子計算がランダム化された古典的計算と比較して、最悪ケースの近似保証を厳密に改善できることを証明した最初の研究であると主張している。

• 限定的な範囲： 著者は、MaxCutやMaxSATのような一般的で制約のない問題については、量子・古典間の最悪ケースの出力比における量子・古典ギャップは依然として未解決であることを明記している。確立された分離は、特定の（しばしば暗号学的な）問題の構成（CMO、DLog-Fit）または制限されたグラフ族に基づいている。
• 理論的枠組み： 本研究は、ヒューリスティックな量子性能（多くの場合、期待値として測定される）と、厳密な複雑性理論（有界誤差出力保証）の間の溝を埋めるものである。スコアのベンチマークが高いことだけでは、一様性と実行時間の境界なしに、近似クラスへの所属を確立するには不十分であることを明確にしている。
• 今後の方向性： 標準的な問題（制約のないMaxCutなど）に対して、古典的な困難性の閾値を超える比率を保証する一様な量子アルゴリズムの探索が、この分野の中心的な未解決問題であると本論文は特定している。