Home > Blog > プログラミング > QUBOLite入門: 軽量QUBOツールキットによる最適解の高速探索

QUBOLite入門: 軽量QUBOツールキットによる最適解の高速探索

複雑な組合せ最適化問題に直面したとき、どのようにすれば高速かつ効率的に最適解を見つけられるでしょうか。近年、この難問へのアプローチとして、2次非制約二値最適化（QUBO: Quadratic Unconstrained Binary Optimization）が注目を集めています。

QUBOは、バイナリベクトル \(\mathbf{z} \in {0, 1}^n\) を用いて2次擬似論理関数 \(E_{\mathbf{Q}}(\mathbf{z}) = \mathbf{z}^\top \mathbf{Q} \mathbf{z}\)（エネルギー関数とも呼ばれます）を最小化する問題として定義されます。その多用途性から、経済学、リソース割り当て、ルーティング、そして特に機械学習といった広範囲の分野に応用が可能です。また、QUBOのシンプルな構造は、量子アニーリング (Quantum Annealing) などの特殊用途のハードウェアソルバーにとって主要なターゲット問題となっています。

しかし、一般にQUBOはNP困難な問題であり、大規模なインスタンスを効率的に扱うためには、高度な解析、前処理、そして高速なソルバーが必要とされます。

今回、QUBOインスタンスの作成、操作、分析、および解決を目的とした軽量なPythonパッケージである QUBOLite を紹介します。QUBOLite は NumPy配列の薄いラッパーとして設計されており、高効率な数値演算と、QUBOインスタンスを扱うための高レベルの抽象化を組み合わせています。このツールキットは、最先端のアルゴリズムを統合し、量子最適化時代に向けた問題解決を強力にサポートします。

QUBOLiteのコア機能：設計思想と基本的な操作

QUBOLiteの設計思想の核心は、その名の通り「軽量性」にあります。具体的には、NumPy配列をベースとして使用している点に表れています。qubo クラスは、QUBOパラメーターを含むNumPy配列の浅いラッパーとして構築されています。この設計により、QUBOLiteは、NumPyの持つ高効率な数値演算能力と、QUBOインスタンスを扱うための便利な高レベルの抽象化を両立させています。

設計原則：数値レベルでの分析に集中

QUBOLiteは、QUBOインスタンスの基本的な機能を提供しますが、設計上、他の問題形式から重み行列を計算する機能（すなわち、QUBO問題の複雑な定式化のガイダンス）は提供していません。

このパッケージが焦点を当てているのは、既存のQUBOインスタンスを、その重み行列 \(\mathbf{Q}\) を唯一の特徴量として、数値レベルで分析、前処理、解決することです。このアプローチは、特定のソルバー（例えば量子アニーラー）向けにインスタンスを調整したい研究者やエンジニアにとって、特に有用なものとなります。

QUBOインスタンスの表現と生成

qubolite モジュールは、QUBOインスタンスの基本クラスとして qubo クラスを提供します。このクラスは、形状が \((n, n)\) のNumPy配列を重み行列としてラップします。QUBO関数の線形係数は、この重み行列の対角線上に配置されます。

QUBOインスタンスを生成する方法はいくつかあります。

  1. 既存のNumPy配列から生成する: 既存の重み行列をqubo()コンストラクタに渡すことができます。
  2. ランダムに生成する: qubo.random(n) メソッドを使用することで、指定されたサイズ \(n\) のランダムなQUBOインスタンスを簡単に生成できます。

なお、qubo クラスはデフォルトで上三角形式の重み行列を使用します。非三角行列が渡された場合、自動的に上三角形式に変換されます（下三角の要素を転置して上三角に追加します）。

図1. QUBOから最適解を得るイメージ（https://lamarr-institute.org/blog/qubolite-qubo/ より引用）

エネルギー評価のベクトル化

QUBOオブジェクトの強力な機能の一つが、エネルギー評価の効率性です。qubo オブジェクトはPythonの関数のように直接呼び出すことができ、入力としてバイナリベクトル \(\mathbf{x}\)（NumPy配列）を受け取ると、対応するエネルギー値 \(E_{\mathbf{Q}}(\mathbf{x})\) を返します。

このエネルギー評価プロセスは、完全にベクトル化されています。つまり、単一のバイナリベクトルだけでなく、複数のバイナリベクトルを格納した配列（形状 \((m, n)\)）を一度に渡した場合でも、NumPyの高速演算を最大限に活用し、それらすべてのエネルギー値を極めて効率的に評価できることを意味します。

QUBOとIsingモデルの相互変換

QUBOは、物理学や量子計算の分野で頻繁に用いられるIsing（イジング）モデルと計算上等価な関係にあります。QUBOLiteは、この変換をサポートするための組み込みメソッドを提供しています。

Q.to_ising() メソッドを使用すると、QUBOインスタンスをIsingモデルのパラメーターに変換できます。Isingモデルの表現では、バイナリ変数 \(\mathbf{x} \in {0, 1}^n\) がバイポーラ変数 \(\mathbf{s} \in {-1, +1}^n\) に置き換えられます。このメソッドは、Isingモデルのパラメーターである線形係数 \(\mathbf{h}\)（外部磁場）と2次係数 \(\mathbf{J}\)（相互作用）、および定数オフセット値をタプルとして返します。

最適化性能を向上させる前処理技術

組合せ最適化問題であるQUBOは、その一般形式においてNP困難な問題として知られています。特に問題サイズが大きくなると、最適解を効率的に見つけることは非常に困難になります。このため、QUBOインスタンスをソルバーにかける前に、その難易度を下げたり、特定のハードウェアに最適化したりする前処理が不可欠となります。

QUBOLiteは、この前処理に特化した強力な機能群を preprocessing サブモジュールを通じて提供しています。ここでは、主要な3つの前処理技術を紹介します。

部分的な変数割り当て (Partial Assignments / Clamping)

QUBOインスタンスのサイズ削減において最も基本的かつ重要な手法の一つが、部分的な変数割り当て、あるいはクランピング (Clamping)です。

QUBOLiteでは、partial_assignment クラスがこの処理を符号化するために使われます。このクラスを使用すると、特定の2値変数を定数（0または1）に固定したり、あるいはある変数の値を別の変数の値に結びつけたり（例：\(x_{12} = x_8\) や \(x_{13} \neq x_9\)）といった制約を設定できます。

クランピングのメリット

  • インスタンスのサイズ削減: partial_assignment オブジェクトをQUBOインスタンスに適用することで、固定された変数や結びつけられた変数を排除した、より小さなQUBOインスタンス \(\mathbf{Q}’\) を生成できます。これにより、探索空間が大幅に縮小され、ソルバーの負荷が軽減されます。
  • エネルギーの復元: サイズ削減された \(\mathbf{Q}’\) を解いて得られたエネルギー値に対し、クランピングによって除去された項に対応する定数オフセット値を加算することで、元のQUBOインスタンスにおける正確なエネルギー値を復元できます。

QPRO+アルゴリズムによる論理的なサイズ削減

QUBOLiteには、Gloverらによって開発されたQPRO+アルゴリズムの実装が含まれています。このアルゴリズムは、QUBOインスタンスの構造を分析し、特定の2値変数の値が最適解で必然的に0または1でなければならない条件や、変数のペアが同じ値を持つ（\(x_i = x_j\)）か反対の値を持つ（\(x_i \neq x_j\)）必要がある条件を特定します。

QPRO+を実行すると、その結果が partial_assignment オブジェクトとして返されます。これを元のQUBOインスタンスに適用することで、論理的に導出された情報を活用し、インスタンスのサイズを最大限に縮小することが可能です。

ダイナミックレンジ削減の重要性

QUBOパラメーターのダイナミックレンジ (Dynamic Range, DR)とは、QUBOの重み行列 \(\mathbf{Q}\) のユニークなパラメーター値間の最大差と最小差の対数比で定義されます。

最近の研究により、このダイナミックレンジが、重み \(Q_{ij}\) を低精度の浮動小数点で実装する量子アニーラ (Quantum Annealers)の解の質に大きな影響を与えることが示されました。高すぎるダイナミックレンジは、量子ハードウェアの持つ有限のビット精度によるエラー（摂動）を引き起こし、最適解ではない解を導くリスクを高めます。

QUBOLiteは、最適解を維持しながらダイナミックレンジを削減するヒューリスティックアルゴリズムを提供しています。この reduce_dynamic_range 機能は、量子アニーラ上でのパフォーマンスを向上させるために重要です。

さらに、この前処理は量子ハードウェアに限定されません。パラメータのビット精度が制限されている古典的なハードウェアソルバー（例えば、IAIS Evo Annealer）の性能向上にも非常に効果的であることが知られています。低精度ソルバーを使用する実務においては、このダイナミックレンジ削減技術は解の品質を確保するための強力な武器となります。

高速な最適解探索と機械学習への応用例

QUBO問題の最適解を探索する方法は、問題の規模や必要な解の精度によって使い分ける必要があります。QUBOLiteは、そのための様々なソルバー (Solver)を solving サブモジュールを通じて提供しています。

最適解を探索するためのソルバー群

一般に大規模なQUBOインスタンスでは厳密解を見つけることが難しいため、QUBOLiteでは近似解法が充実しています。

  • シミュレーテッドアニーリング (Simulated Annealing): 物理現象を模倣し、局所解に陥るのを避けながら、より良い近似解を探索する手法です。
  • 居所探索法 (Local Search): 探索開始点から近傍を探索し、エネルギーが改善する方向へ貪欲に移動するヒューリスティックです。QUBOLiteでは、1変数のフリップ（1-近傍探索 local_descent） や、2変数のフリップ（2-近傍探索 local2_descent） を用いた手法が利用できます。

また、小規模なQUBOインスタンスのテストや研究目的のためには、厳密解法も提供されています。変数が約30以下のインスタンスを対象とした ブルートフォースソルバー (Brute Force Solver) は、Grayコードを使用してエネルギー計算を効率化した、高速な並列C言語実装として実装されています。

実問題のQUBO埋め込みと機械学習への応用

QUBOが多用途である最大の理由は、様々な組合せ最適化問題をQUBO形式に変換（埋め込み：Embedding）できる点にあります。QUBOLiteの embedding サブモジュールは、他の最適化問題からQUBOインスタンスを簡単に作成するためのツールを提供します。

特に機械学習の分野において、QUBOは強力なツールとなり得ます。QUBOLiteは、クラスタリングや分類といった機械学習タスクの埋め込みを提供しています。

  • クラスタリング: Kernel 2-Means Clustering や K-Medoids のような問題をQUBOとして定式化できます。
  • 分類: Kernel Support Vector Machine (Kernel SVM) もQUBO埋め込みが可能です。
図2. QUBOを利用したクラスタリグの例（https://lamarr-institute.org/blog/qubolite-qubo/ より引用）

さらに、一般的な組合せ最適化問題であるMax 2-SAT問題 や部分和問題 (Subset Sum) の埋め込みもサポートされています。

たとえば、データセットに対してKernel 2-Means Clusteringを実行し、得られたQUBOインスタンスをソルバーにかけることで、データに対する最適なクラスタリング解を探索し、導出することが可能です。このように、QUBOLiteは、複雑な実務問題を量子最適化のフレームワークに統合するための橋渡し役を担っています。

サンプルコードの紹介

このセクションでは、QUBOLite を使って実際にQUBOインスタンスを生成し、いくつかの異なるソルバーで最適解を探索するプロセスをステップごとに紹介します。

パッケージのインストール

まず、QUBOLite とその関連パッケージをインストールします。以下のコマンドをターミナルで実行してください。

$ pip install qubolite "numpy<2.0" scikit-learn igraph portion

QUBOインスタンスの準備

はじめに、最適化対象となるQUBOインスタンスを作成します。ここでは、qubolite が提供する random メソッドを使い、16変数のランダムなQUBOインスタンスを生成してみます。

import numpy as np
from qubolite import qubo

# Define the number of variables (n).
# Brute force is feasible for up to about 30 variables.
N = 16 

# Generate a random QUBO instance with Gaussian-distributed weights
# using the qubo.random() method.
Q = qubo.random(N, distr='normal', density=0.8)
print(f"QUBO instance size (number of variables n): {Q.n}")

厳密解法による最適解の探索

まずは、小規模な問題で有効なブルートフォース（全探索）ソルバーを使い、厳密な最適解を求めます。この方法は、考えられるすべての解の組み合わせを評価するため、解が最適であることを保証しますが、変数の数が増えると計算時間が爆発的に増加します。

from qubolite.solving import brute_force

# The brute_force solver finds the exact solution to a QUBO instance,
# but it becomes computationally infeasible for larger sizes.
try:
    # Use return_value=True to get both the minimizing vector and the minimum energy value.
    x_min_bf, energy_min_bf = brute_force(Q, max_threads=256)
    
    print("\n--- Brute Force Results ---")
    print(f"Minimum energy: {energy_min_bf}")
    # The minimizing binary vector x.
    print(f"Optimal solution x: {x_min_bf}") 

except ValueError as e:
    # This may occur if the QUBO size is too large.
    print(f"\nBrute force error: {e}") 
    print("Could not run brute force solver because the QUBO size is too large.")

近似解法①：シミュレーテッドアニーリング

大規模な問題では、厳密解の代わりに高速に良質な近似解を見つけるヒューリスティック手法が有効です。ここでは、代表的な手法であるシミュレーテッドアニーリングを試します。複数のアニーリングを並列で実行し、その中で最もエネルギーが低かったものを解として採用します。

from qubolite.solving import simulated_annealing

# Run simulated annealing to approximate the minimum energy and the corresponding vector.
# We perform 10 parallel annealing runs (n_parallel=10) for 100,000 steps each.
x_sa, y_sa = simulated_annealing(Q, steps=100000, n_parallel=10)

print("\n--- Simulated Annealing Results ---")
# The results are returned as a tuple of bit vectors with shape (n_parallel, n)
# and energies with shape (n_parallel,).
# We find the minimum energy among the runs and print the corresponding solution.
best_index_sa = np.argmin(y_sa)
print(f"Minimum energy (SA approximation): {y_sa[best_index_sa]}") 
print(f"Approximate optimal solution x: {x_sa[best_index_sa]}")

近似解法②：局所探索

最後に、もう一つのヒューリスティック手法である局所探索を試してみましょう。このソルバーは、ランダムな初期解から出発し、近傍の解を探索してエネルギーを貪欲に下げていく処理を繰り返すことで、局所最適解を見つけます。

from qubolite.solving import local_descent_search

# local_descent_search performs a local search with multiple starts
# and returns the bit vector with the lowest observed energy.
# Here, we use a 1-neighborhood search.
x_ld, energy_ld = local_descent_search(Q, steps=1000)

print("\n--- Local Descent Search Results ---")
print(f"Minimum energy (LD approximation): {energy_ld}")
print(f"Approximate optimal solution x: {x_ld}")

おわりに

今回は、軽量QUBOツールキットであるQUBOLiteの主要な機能と、その設計思想について解説してきました。

QUBOLiteの最大の特長は、NumPyの上に構築された軽量性と、それにより実現される高効率な数値演算です。特に、エネルギー評価が完全にベクトル化されているため、大規模なデータセットの分析においても高速な処理が可能です。

さらに、QUBO問題が持つNP困難性を克服するため、QUBOLiteは高度な前処理機能を統合しています。GloverらによるQPRO+アルゴリズム や、ダイナミックレンジ削減は、最適化性能を向上させる上で不可欠なツールです。

この前処理アルゴリズムをはじめとする機能は、最先端の研究成果をリアルタイムでパッケージに組み込んだものであり、特に量子アニーリングなどの低精度ハードウェア や、パラメータ精度が制限された古典的なソルバーを使用する際に、具体的な解の品質向上というメリットを提供します。

QUBOLiteは、PyPIおよびGitHubで公開されているため、簡単に導入しすぐに使い始めることができます。最先端の研究成果が詰まったこの強力なツールキットを、ぜひ組合せ最適化問題の高速探索にご活用ください。

More Information

関連記事

DEAP入門：Pythonによる進化的計算の事始め

近年、深層学習（Deep Learning, DL）や大規模言語モデル（Large Language Models, LLM）といったAIシステムが目覚ましい進化を遂げています。しかし、それに伴い、これらの複雑なモデルの […]

CMA-ES入門: 進化戦略によるブラックボックス最適化

現代のエンジニアリングにおいて、最適な解を見つけ出す「最適化」は常に重要な課題です。しかし、目的関数の内部構造が不明確である、あるいは解析的に勾配を計算できない場合、その問題はブラックボックス最適化（Black-Box […]

Pythonによる粒子群最適化

数理最適化を応用した最適化問題の解決には、微分不可能な関数にも対応可能なメタヒューリスティック手法が広く利用されています。その中でも、生物の群れ行動を模倣した群知能は、複雑な問題に対して高い適応性を示します。今回は、代表 […]