A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation

技術要約：離散最適化のための量子非構造化探索アルゴリズム

問題提起
本論文は、変数がバイナリであり、微分が定義できない離散最適化問題、特に組合せ最適化問題を解く際の課題に取り組んでいる。勾配ベースの手法は連続変数に対しては効果的であるが、NP困難であることが多い離散空間では機能しない。既存の量子アプローチ（QUBO：二次無制約バイナリ最適化フレームワークなど）は、第1次および第2次の項のみを含む目的関数に限定されている。さらに、多くの現在の量子最適化アルゴリズム（変分量子アルゴリズムなど）は、ノイズの影響を受けたり深い回路を必要としたりする可能性があるハイブリッドな古典・量子ループに依存している。著者らは、QUBOの二次形式の限界を超えた高次の項を含む可能性のある、一般的な離散関数 $f(x)$ の極値または根を見つけるための手法を提案している。

手法：QSERAアルゴリズム
著者らは、グローバーのアルゴリズムに基づく量子探索アルゴリズム（QSA）ファミリーの一員である**量子極値および根探索アルゴリズム（QSERA）**を導入している。その手法は、主に以下の2つのステップで構成される：

1. オラクルの構築 ($f(x) \to u(z)$):
   最初のステップでは、極値（または根）を見つける条件 $f(x^*) \approx f^*$ を、バイナリストリング $z^*$ に対する非構造化探索問題へとマッピングする。

   • 再スケーリング: 目的関数 $f(x)$ は、関数 $g(x) \in [0, 1]$ へと再スケーリングされる。最大化の場合は $g(x) = (f(x) - f_{min}) / (f_{max} - f_{min})$、最小化の場合は $g(x) = (f_{max} - f(x)) / (f_{max} - f_{min})$ となり、根探索の場合は特定の変換が適用される。これには、$f_{min}$（大域的最小値）および $f_{max}$（大域的最大値）の事前知識または推定値が必要となる。
   • 増幅: $u(z^*) = 1$ かつ $u(z \neq z^*) = 1$ となるバイナリオラクル $u(z)$ を作成するために、関数 $g(x)$ は大きな累乗 $n$ （すなわち $u_n(z) \equiv g(x)^n$）でべき乗される。$n \to \infty$ となるにつれ、$u_n(z)$ は理想的なオラクルに近づく。
   • 一般化: 本論文では、$f(x)$ は項の次数が $K$ までの一般的な多項式（式10）になり得ることを述べており、標準的なQUBO形式よりも複雑な目的関数を扱うことが可能である。
   • ゲートの実装: 著者らは、オラクルの量子回路を導出している。まず、バイナリ変数に対応する自己随伴演算子 $B_k$ を定義し、$G|z\rangle = g(x)|z\rangle$ となるユニタリ演算子 $G$ を構築する。そして、オラクル演算子 $Q^*$ を $e^{i\pi G^n}$ と定義する。これは、各次数の項（0次、1次、2次など）に対するユニタリ演算子の積 $Q^*_j$ に分解され、アンシラ量子ビットと位相シフトゲートを用いて実装される。

2. 探索の実行:
   オラクル $Q^*$ が構築された後、アルゴリズムはグローバーの拡散演算子 ($Q_+$) とオラクル ($Q^*$) を用いた反復ループを採用する。状態は一様重ね合わせ状態で初期化され、ターゲット状態 $|z^*\rangle$ の振幅を増幅するために、演算子 $(Q_+ Q^*)$ が $m_{opt} \approx (\pi\sqrt{N} - 2)/4$ 回適用される。

主な貢献

• QUBOを超えた一般化: 二次形式に限定される多くの量子最適化手法とは異なり、QSERAは高次の項（3次、4次など）を持つ目的関数を扱うことができ、より幅広い組合せ問題への適用を可能にする。
• 明示的な回路構築: 本論文は、任意の多項式の次数に対して量子オラクルゲートを構築するための詳細な数学的導出を提供しており、これには回路パラメータに必要な係数の再帰的な計算が含まれる。
• 近似的な境界の処理: 著者らは、$f_{min}$ および $f_{max}$ が正確に判明していないシナリオについても分析している。アルゴリズムは推定値を用いても機能することを示しているが、正確な最適解を見つける確率は、べき乗パラメータ $n$ の選択に依存する。$n$ が大きすぎるとオラクルの信号が消失し、$n$ が小さすぎると信号が十分に識別できなくなる。これらをバランスさせるための最適な $n$ が存在する。

結果：ポートフォリオ最適化のケーススタディ
著者らは、$N_a = 4$ 個の資産、すなわち $N=16$ 通りのポートフォリオが存在するポートフォリオ最適化問題を用いてQSERAを検証した。

• 設定: 目標は、ベンチマークのリターンとボラティリティへの距離を最小化する2資産のポートフォリオを見つけることである。目的関数には4次までの項が含まれている。
• 実装: ポートフォリオの状態用に4個の量子ビット、AND演算用に2個のアンシラ量子ビット、および位相追跡用に1個のアンシラを用いて、量子回路を組み立てた。
• パフォーマンス:
  • 最適なグローバー反復回数 ($m_{opt} = 2$) と、慎重に選択された $n \approx 24$ というべき乗を用いることで、アルゴリズムは最も高い確率で最適なポートフォリオ（状態 $|1001\rangle$）を特定することに成功した。
  • 2番目に優れたポートフォリオ（$|0101\rangle$）も比較的高い確率を示したが、これはアルゴリズムが推定された境界に最も近い解を見つけたことを反映している。
  • 本研究により、$f_{min}$ および $f_{max}$ が正確ではなく推定値である場合、真の最適解を測定する確率は1未満となり、真の最適解と準最適解を区別するために複数の「ショット」（繰り返し実行）が必要になることが確認された。
  • べき乗 $n$ と成功確率の関係を可視化したところ、中間的な $n$ の値で確率がピークに達し、$n$ が大きすぎると（信号抑制）、あるいは小さすぎると（識別力不足）、パフォーマンスが低下することが示された。

意義と主張
QSERAは、離散関数の極値または根を見つけるために、古典的な総当たり探索に対して二次的な加速 ($O(\sqrt{N})$) を提供すると主張されている。その主な意義は、以下の点にある：

1. 標準的なQUBO定式化とは互換性のない高次の目的関数を持つ最適化問題を解決できること。
2. VQA（変分量子アルゴリズム）とは異なり、ハイブリッドな古典・量子パラメータ最適化ループを必要とせず、単発の量子実行（ただし、統計的な信頼性のために複数のショットが必要になる場合がある）に依存すること。
3. 勾配ベースの手法が失敗する可能性のある「ノイズの多い」または「急峻な勾配を持つ」連続関数（離散化後）に対処できる可能性がある（ただし、構造化探索は連続変数に対しては一般に効率的であると著者らは述べている）。

著者らは、アルゴリズムが保証された成功のために関数の境界に関する知識を必要とするものの、特に目的関数の構造が現在のQUBOベースのアプローチの能力を超える場合において、離散最適化のための堅牢なツールとして残る、と結論付けている。