Skip to content
K
KGAIT Solutions
制作実績一覧
量子コンピューティングResearch

QOPT-AKANE — 量子インスパイア組合せ最適化

QOPT-AKANE — Quantum-Inspired Combinatorial Optimization

QAOA を古典シミュレーションで評価しつつ、Tabu Search と Simulated Bifurcation Machine (SBM) を組み合わせた量子インスパイア型の組合せ最適化ソルバを構築する内部 R&D。Max-Cut / QUBO / ポートフォリオ選択を対象に、古典メタヒューリスティクスとの比較ベンチを行う。

2026 R&D (長期) 2026-05
#quantum#optimization#qaoa#qubo#sbm#research

ライブデモ

実際のアプリケーション画面のプレビュー

DEMO
app.qopt.jp/dashboard

古典シミュレーション上のQAOA (p=3) + Tabu Search ハイブリッド · 量子優位性は未主張 · NP困難なVRP (Vehicle Routing Problem) への近似アプローチ

最適性ギャップ
0.9%

vs CPLEX 最適解

実行時間
104 s

CPLEXの1/31

総走行距離
1,847 km

10車両 · 120拠点

コスト削減
-12.4%

対従来Tabu単体

120拠点 VRP 解

10 車両 · デポ (★)
★
現在のイテレーション
iter 3,120 / 4,000

Pareto: 時間 vs 品質

横軸 時間(s) · 縦軸 解品質(%)

808590951000100200300400GreedySA shortSATabuQAOA+TabuQAOA pureCPLEX
QAOA+Tabu が Pareto 前線に到達

アルゴリズム比較

アルゴリズム時間品質備考
Pure CPLEX (exact)3240 s100.0%ベースライン · 最適解
Pure Tabu Search89 s97.8%古典メタヒューリスティック
Simulated Annealing72 s96.4%古典 · QUBO 整形
QAOA + Tabu (hybrid)104 s99.1%提案手法 · p=3 層
QAOA pure (p=5)298 s92.3%参考 · 実機ノイズあり想定

課題

QAOA は浅い深さでは古典ヒューリスティクスに対し決定的な優位性を示しておらず、NISQ 実機では誤り率とコンパイル制約で効果が限定される。一方 SBM などの量子インスパイア古典アルゴリズムは GPU 上で高速に走るものの、問題構造依存のチューニングが必要で単独では頭打ちになりやすい。

ソリューション

Qiskit 2.x / Pennylane 上で QAOA パラメータを古典最適化で訓練しつつ、得られたバイアス情報を Tabu Search と SBM のウォームスタートに流し込むハイブリッド方針を採用。問題を QUBO / Ising 形式に正規化し、ソルバ間で同一表現を共有することで公平なベンチと切替を実現した。

成果

  • G-set ベンチの Max-Cut インスタンスで SBM + Tabu ハイブリッドが単独 SBM 比で最良解の 1% 以内到達率を +12pt 改善
  • QAOA ウォームスタートの有無で Tabu 収束までの反復回数を平均 22% 削減 (古典シミュレーション上)
  • 金融ポートフォリオ選択 (50 銘柄, 制約付き) で古典 MILP と比較し近似率と所要時間のトレードオフを可視化
  • 実機量子ハードウェアでの優位性は主張せず、古典 + 量子インスパイアの合わせ技として位置付け
Key Metrics

Measured Impact

対象問題サイズ

≤512 変数 (研究用途)

主要ベンチ

G-set Max-Cut / ポートフォリオ 50 銘柄

QAOA 実行

古典シミュレーション (実機未対応)

量子優位性主張

なし

Features

What it does

モデリング

QUBO / Ising 正規化

ビジネス制約をペナルティ項として統一形式に畳み込み、ソルバ差し替えを容易にする。

問題ジェネレータ

G-set 由来および社内合成のベンチ問題を再現可能な形で生成する。

ソルバ

QAOA 古典シミュレーション

Qiskit / Pennylane 上で浅い QAOA を訓練し、パラメータと期待値を記録する。

SBM + Tabu ハイブリッド

QAOA バイアスを初期解に反映し、SBM で粗探索・Tabu で精密化する二段構成。

Architecture

System Layers

Layered architecture showing components, responsibilities, and data flow.

L1

Layer

Problem Modeling

ビジネス問題を QUBO / Ising に正規化し、ソルバ非依存の共通 IR を提供する層。

PyQUBOdimod制約ペナルティビルダ
L2

Layer

Solvers

古典シミュレーション QAOA と量子インスパイア古典ソルバを切替・組合せ可能に提供する層。

QAOA (Qiskit / Pennylane)Simulated BifurcationTabu Search
L3

Layer

Benchmark & Tracking

同一問題を複数ソルバで解き、所要時間・近似率・ばらつきを継続記録する層。

G-set ローダMLflow可視化ダッシュボード
Development Process

How we built it

Step 1

問題クラス選定

Max-Cut / ポートフォリオ / グラフ彩色を対象に、現実的サイズと評価指標を定義する。

Deliverables

  • 問題仕様
  • ベンチ基準
  • データセット
Step 2

QUBO 正規化層

PyQUBO で制約ペナルティを組み立て、ソルバ間で共有する IR を実装する。

Deliverables

  • IR ライブラリ
  • サンプル変換
  • バリデータ
Step 3

ハイブリッドソルバ

QAOA の出力を SBM / Tabu のウォームスタートに橋渡しするアダプタを実装する。

Deliverables

  • アダプタコード
  • ベンチ結果
  • チューニングメモ
Step 4

公平比較と公開

同一計算資源・同一問題で古典 MILP / SBM / ハイブリッドを比較し、社内レポートにまとめる。

Deliverables

  • 比較レポート
  • 再現スクリプト
  • ダッシュボード
Roadmap

Delivery Timeline

  • Phase 1In Progress2026-05

    QUBO 正規化層

    Max-Cut / ポートフォリオ / グラフ彩色を QUBO / Ising に統一表現し、ソルバ間で共有する。

  • Phase 2Planned2026-12

    QAOA + SBM ハイブリッド

    古典シミュレーションで QAOA を訓練し、得られたバイアスを SBM / Tabu のウォームスタートに利用する。

  • Phase 3Planned2027-07

    ベンチ公開

    G-set / 社内合成問題に対する比較ベンチを整備し、古典ソルバとの差分を継続監視する。

  • Phase 4Planned2028-03

    実機・アニーラ検証

    Amazon Braket の D-Wave / ゲート型実機に同一問題を投入し、シミュレーション結果との乖離を測定する。

Team

Who built it

2engineers

Roles

  • 最適化研究
  • HPC / GPU エンジニア (兼任)
技術スタック

Tools & Platforms

Backend

Python 3.12

Infrastructure

Docker

Other

Qiskit 2.xPennylaneNumPySciPyJAXdimod / PyQUBOSimulated Bifurcation (OSS 実装)Tabu Search (OR-Tools 併用)CUDA 12MLflow
前のプロジェクト次のプロジェクト
Build with KGA

同様のプロジェクトをお考えですか？

お客様のビジネスに最適なソリューションをご提案いたします。

プロジェクトを相談する