A competitive NISQ and qubit-efficient solver for the LABS problem

技術要約：LABS問題に対する競争力のあるNISQおよび量子ビット効率の高いソルバー

問題の定義
低自己相関バイナリ系列（LABS）問題は、エンジニアリング、通信、統計物理学に応用される、よく知られたNP困難な組合せ最適化の課題である。整数 $N$ が与えられたとき、目的は、$\ell > 0$ における二乗自己相関 $C_\ell(x)$ の総和として定義されるサイドローブエネルギー $E(x)$ を最小化するバイナリ系列 $x \in \{-1, +1\}^N$ を見つけることである。等価的に、メリットファクター $F(x) = N^2 / 2E(x)$ を最大化することが目標となる。この問題は、多数の局所解と孤立した大域的解を持つ「ゴルフコース」型の最適化ランドスケープによって特徴付けられる。$N \le 66$ までは厳密解が既知であるが、より大きな $N$ に対して最適解または高品質な近似解を見つけることは、古典的な総当たり手法では不可能であり、メメティック・タブー探索のような最先端のヒューリスティックですら、重大なスケーリングの課題に直面する。

手法：パウリ相関エンコーディング（PCE）
著者らは、パウリ相関エンコーディング（PCE）フレームワークに基づいた、量子ビット効率の高い変分量子ソルバーを提案している。1つの量子ビットにつき1つのバイナリ変数を必要とする標準的なエンコーディングとは異なり、PCEは $N$ 個のバイナリ変数を $n$ 個の量子ビットに圧縮する（ここで $N = \text{poly}(n)$ であり、具体的には $n \ll N$ である）。

• エンコーディング: バイナリ変数 $x_i$ は、$n$ 量子ビットのパウリ文字列 $\Pi = \{\Pi_i\}_{i \in [N]}$ の期待値の符号としてエンコードされる：
  $$x_i := \text{sgn}(\langle \Pi_i \rangle)$$
  ここで $\langle \Pi_i \rangle = \langle \Psi | \Pi_i | \Psi \rangle$ である。
• 最適化: 量子状態 $|\Psi\rangle$ は、パラメータ化されたブリックワーク回路によって生成される。パラメータは、非線形損失関数 $L$ を最小化するように古典的に最適化される。勾配ベースの最適化を容易にするため、バイナリ変数は双曲線正接関数を用いて緩和される：$\tilde{x}_i = \tanh(\alpha \langle \Pi_i \rangle)$。損失関数には、相関関数が消失するのを防ぐための正則化項が含まれる。
• パウリ集合の選択: 本研究では、$\Pi$ のための2つの異なる集合を評価している：
  1. $\Pi(C)$: ランダムに選択された、互いに可換なパウリ演算子の集合。
  2. $\Pi(NC)$: 互いに非可換なパウリ演算子の数を最大化するように設計された集合。著者らは、非可換性が互いに無相関な測定（mutually unbiased measurements）をもたらし、それによってエンコードされた変数の表現力と独立性を高めると仮定している。

主な貢献と結果

1. 数値シミュレーション ($N \le 45$):

   • 著者らは、$n=4$ 量子ビットおよび回路深さ15レイヤー（2量子ビットゲート30個、パラメータ150個）を用いてPCEソルバーをシミュレートした。
   • $\Pi(NC)$ バリアントは、可換バリアントを一貫して上回った。
   • スケーリング分析: 解を見つけるために必要なコスト関数評価回数として定義されるTime-to-Solution (TTS) を、QAOAおよびメメティック・タブー探索と比較してベンチマークした。
     • PCEのスケーリング: 偶数インスタンスに対して $O(1.330^N)$、奇数インスタンスに対して $O(1.326^N)$。
     • 比較: このスケーリングは、QAOAのスケーリング $O(1.46^N)$ を改善しており、最先端のタブー探索のスケーリング（偶数インスタンスで $O(1.34^N)$、奇数インスタンスで $O(1.409^N)$）よりもわずかに優れている。
   • 結果は、テストされた範囲内において、PCEが古典的なベースラインに対して冪乗則による優位性を持つことを示している。

2. 実験的デモンストレーション (IonQ Forte):

   • 著者らは、量子ハードウェア上で実証された中で最大となる、インスタンスサイズ $N=120$ のケースについて、IonQのForte量子プロセッサを用いた原理実証を行った。
   • 実験では、特定のハードウェアフレンドリーな $k$ 体相関（$k=2$）のセットが使用され、これには3つの測定セットアップのみが必要であった。
   • ノイズ耐性: 研究では、ショットノイズの影響は軽微（数千ショットのみで十分）であったが、ハードウェアノイズが最終的な解の質を著しく低下させることが判明した。しかし、学習プロセス自体は堅牢であり、これはエラー緩和またはより高い圧縮率が、近接将来の展開において重要であることを示唆している。

意義と主張
本論文は、PCEベースのソルバーが以下の2つの異なる経路において有望なアプローチであることを主張している：

1. 量子に着想を得た古典的ヒューリスティック: 古典的にシミュレートされる場合であっても、PCEフレームワークは、LABSのような困難な問題に対する主要な古典的ヒューリスティックと比較して、競争力のある、あるいは優れたスケーリングを提供し、強力な量子着想アルゴリズムとして機能する。
2. NISQリソースの削減: $N$ 個の変数を多項式オーダーでより少ない数の量子ビット（$n$）にエンコードすることで、PCEは近接将来のデバイスにおける量子ビット要件を劇的に削減する。著者らは、$n=8$ 量子ビットがあれば、理論的には厳密解が既知である $N=66$ までのインスタンスに対処でき、$n \le 20$ であれば古典的ヒューリスティックで解ける最大のインスタンスに挑戦できる可能性があると述べている。

著者らは「量子超越性」に関して控えめな立場をとっている。彼らは、フル量子状態ベクトルを古典的にシミュレートするオーバーヘッドが、真の量子実行時間の優位性が顕著になるクロスオーバーポイントを遅らせることを認めている。さらに、本手法は強力な性能を示す一方で、現時点では性能保証を欠いていることも指摘している。それにもかかわらず、$N=120$ のインスタンスを控えめなショット予算で解ける能力や、ノイズ耐性の観察は、実際の量子アルゴリズムにおけるリソース要件を削減するためのツールとしてのPCEの可能性を浮き彫りにしている。