Noise-Directed Adaptive Remapping for Integer Optimization: from qubits to (encoded) qudits

技術要約：整数最適化のためのノイズ指向型適応再マッピング（NDAR）

問題提起
本論文は、近未来の量子ハードウェアにおける離散整数ドメインの最適化という課題に取り組んでいる。具体的には、ノイズを計算リソースとして利用することでバイナリ問題の性能を向上させることが実証されてきた「ノイズ指向型適応再マッピング（NDAR）」メタアルゴリズムを、従来の制約のないバイナリ最適化の範囲を超えて拡張するものである。NDARは以前、バイナリ問題において性能を向上させることが示されていたが、整数問題（ドメイン $\mathbb{Z}_d^n$）や非バイナリ・エンコーディング（クディットや量子ビットでエンコードされた整数など）への適用については未開拓であった。核心となる困難さは、整数最適化がしばしばハード制約（例：グラフ問題における有効な彩色）を伴い、かつ多様なエンコーディングスキーム（バイナリ、ワンホット、ドメインウォール、ネイティブ・クディット）が、ハードウェアノイズやゲージ変換と異なる形で相互作用することにある。著者らは、これらの設定に対してNDARをどのように一般化するかを調査し、実現可能性、ゲージ選択、および回路の実装可能性に関する特定の要件を特定している。

手法
著者らは、整数最適化問題（$\mathbb{Z}_d^n$）を扱うためにNDARフレームワークを一般化している。その手法は、高次元システムに適応した4つの主要コンポーネントで構成される：

1. ノイズ・アトラクタの特定： フレームワークは、ハードウェアノイズ（例：振幅減衰）によって駆動される既知の古典的な「アトラクタ」状態の存在を仮定している。クディットの場合、著者らは一般化された振幅減衰チャネルをモデル化し、ゼロまたは有限温度において、システムが低励起状態（典型的には $|00\dots0\rangle$）へと自然に緩和することを示している。これは、量子ビットにおける全ゼロのアトラクタと同様である。
2. 実現可能性と制約： 制約のないバイナリ最適化とは異なり、整数問題はしばしばハード制約（例：有効な色の割り当て）を伴う。著者らは、アトラクタ状態が実現可能な解をエンコードするようにNDARを拡張した。彼らは様々なエンコーディングを分析し、$|00\dots0\rangle$ 状態が有効であるか、および実現可能な状態の集合が選択されたゲージ群の下で推移的な軌道を形成するかどうかを判断している。
3. ゲージ変換の選択： バイナリ最適化では、ビット反転操作によってアトラクタを任意のターゲット文字列へ一意にマッピングできる。しかし、クディット（$d>2$）やエンコードされた量子ビットでは、この一対一の対応関係が崩れ、指数関数的に大きな互換性のあるゲージ変換のファミリーが生じる。著者らは、現在のイテレーションで見つかった最良の候補解にアトラクタをマッピングしつつ、量子回路（アンザッツ）の構造を維持するような、特定のゲージ変換（例：巡回シフト、プレフィックス反転、ドメインウォール・エンコーディング）を選択することを提案している。
4. 適応型再マッピング・ループ： アルゴリズムは、量子オプティマイザ（例：QAOA）を反復的に実行し、解をサンプリングし、最も実現可能な候補を選択し、コスト・ハミルトニアンと制約にゲージ変換を適用する。これにより、ノイズ・アトラクタを高品質な解に整合させ、次回のイテレーションにおいてシステムをより良い解へと駆動するように、効果的にノイズを利用する。

研究では、Max-k-colorable subgraph問題をランニング例として用い、これらの基準を以下のエンコーディングスキームにわたって評価している：

• ネイティブ・クディット・エンコーディング： $d$ レベル系への直接的なマッピング。
• バイナリ・エンコーディング： 整数を $\lceil \log_2 d \rceil$ 個の量子ビットにマッピング。
• ワンホット・エンコーディング： 変数ごとに $d$ 個の量子ビットを使用（ハミング重み1）。
• 01-Hot エンコーディング： 全ゼロ状態を含む拡張されたワンホット。
• ドメインウォール・エンコーディング： 変数ごとに $d-1$ 個の量子ビットを使用し、特定の境界条件を持つ。

主な貢献

1. NDARの一般化： 本論文は、整数ドメインおよびハード制約に対してNDARを適用するための統一されたフレームワークを提供し、アルゴリズムが効果的に機能するための条件（特にアトラクタの実現可能性と効率的なゲージ変換の存在）を定式化した。
2. クディットにおけるゲージ自由度の分析： 著者らは、ネイティブ・クディット・システムが量子ビットと比較して著しく多くのゲージ自由度（$(d-1)!^n$）を提供することを実証した。この余剰な自由度は設計上のレバーとして特定されており、特定のハードウェア・ゲートセット（例：巡回シフト vs 任意の置換）に最も適合するゲージ変換を選択することで、回路のオーバーヘッドを最小限に抑えることができる。
3. エンコーディングの比較分析： NDARの観点から、ネイティブ・クディット・エンコーディングを、バイナリおよびユニナリ（ワンホット、ドメインウォール）量子ビット・エンコーディングと比較している。主な知見は以下の通りである：
   • ネイティブ・クディット： 最も好ましい特性を提供している（1変数あたり1クディット、有効な文字列の確率 $q=1$、追加のハード制約なし、実現可能な $|00\dots0\rangle$ アトラクタ、および2-local コスト・ハミルトニアン）。
   • バイナリ・エンコーディング： スペース効率は高いが、コスト・ハミルトニアンと位相演算子に対して高い局所性（$2\lceil \log_2 d \rceil$-local）を必要とする。
   • ユニナリ・エンコーディング： ドメインウォールおよび01-hot エンコーディングは実現可能なアトラクタをサポートできるが、コスト・ハミルトニアンに非自明な変換を導入したり、ノイズによるリークのために不実現なアトラクタ（標準的なワンホットの場合）を招いたりすることが多い。
4. ハードウェアとの整合性： 本研究は、NDARの理論的要件を、新興の超伝導キャビティ・クディット・ハードウェアに結びつけている。これらのシステムにおける振幅減衰ノイズは、NDARアトラクタ・モデルと自然に一致している。

結果

• エンコーディングのトレードオフ： 論文の表Iは、ネイティブ・クディット・エンコーディングが「カテゴリー内でのベスト」の組み合わせを提供することを示している：1変数あたり1クディット、有効な文字列の確率 $q=1$、追加のハード制約なし、実現可能な $|00\dots0\rangle$ アトラクタ、および2-local コスト・ハミルトニアン。対照的に、量子ビットベースのエンコーディングは、多くの場合、追加のハード制約を必要とし、$q < 1$（ノイズによる）となり、あるいはより高い局所性の演算子をもたらす。
• アトラクタの実現可能性： 本研究は、標準的なワンホット・エンコーディングでは自然なノイズ・アトラクタ（$|00\dots0\rangle$）が無効であり、標準的なNDARを修正なしには適用できないことを特定した。逆に、ドメインウォールおよび01-hot エンコーディングは、実現可能なアトラクタを持つように構造化できるが、コスト・ハミルトニアンの局所性を変化させる可能性がある。
• 回路の複雑性： 著者らは、バイナリ・エンコーディングはスペース効率が高いものの、注意深く選択しなければ、要求されるゲージ変換が複雑な回路構造（例：マルチ制御ゲートを必要とするもの）を導入することを示す。ネイティブ・クディット・エンコーディングは、QAOAアンザッツの2-local 構造を維持する単純なゲージ変換（例：シフト）を可能にする。

意義と主張
本論文は、NDARに導かれたノイズの考慮が、デバイスレベルのエンコーディング選択を比較するための新しい基準を提供すると主張している。エンコーディングの選択は単なるリソース数（量子ビット vs クディット）の問題ではなく、アルゴリズムがノイズを活用する能力に根本的な影響を与える。

著者らは以下のように断言している：

1. ネイティブ・クディット実装のNDARは、比較対象となる量子ビットベースのエンコーディングに対して明確な利点を持っており、特にノイズ誘起のダイナミクスが解のランドスケープとどのように相互作用するかという点で優れている。
2. クディット・システムにおけるゲージの多重性はバグではなく機能であり、特定のハードウェア制約に合わせた変換のカスタマイズを可能にする。
3. 本フレームワークは、実験的に関連性が高い。これは、ノイズ特性（振幅減衰）とゲート能力（CSUM, ECD）がNDARの要件とよく一致する、新興の超伝導キャビティ・クディット・デバイス（例：SQMS Centerのもの）において顕著である。

本論文は、超伝導クディット・デバイスにおける実験的実現に向けた方向性を概説して締めくくられており、NDARアプローチをフルに活用するためには、高忠実度の2-クディットもつれゲートとエラー抑制技術が必要であることを強調している。本研究は、実用的な最適化タスクに向けて、拡大する非量子ビット型量子プロセッサのクラスを利用するための不可欠なステップとして位置づけられている。