☁️

量子コンピュータでマッチング問題を高速化：Amazon Braketで実現するリアルタイム最適化

2024/03/29に公開

AWS

量子コンピュータの優位性

現代社会において、効率的なマッチングはあらゆる分野で求められています。例えば、物流における配送ルートの最適化、人材派遣における求人者と企業のマッチング、オンラインデートにおける理想のパートナー探しなどが挙げられます。

これらのマッチング問題において、古典コンピュータは膨大な計算量を必要とし、リアルタイムでの最適化が難しいという課題があります。しかし、量子コンピュータの登場により、この課題を解決できる可能性が出てきました。

量子コンピュータがマッチング問題に与える革新

量子コンピュータは、量子ビットと呼ばれる特殊な情報単位を用いることで、古典コンピュータとは比べ物にならない計算能力を実現することができます。特に、組合せ爆発問題と呼ばれる、古典コンピュータでは処理が困難な問題に対して、量子コンピュータは圧倒的な速度で解を導き出すことが可能です。

マッチング問題はまさに組合せ爆発問題の典型であり、量子コンピュータの真価を発揮できる領域と言えます。量子コンピュータを用いることで、従来のアルゴリズムでは不可能だったリアルタイムでの最適化が可能となり、マッチングの精度と効率を大幅に向上させることができます。
古典コンピュータだと優先度の問題などで何らかの工夫を強いられたり、切り捨てざるを得なかったパラメータも有効に活用することができます。

Amazon Braket

Amazon Braketは、Amazon Web Services (AWS) が提供する量子コンピューティングサービスです。D-Wave Systems、IonQ、Rigetti Computingなどの量子ハードウェアベンダーの提供する量子コンピュータや量子シミュレータに、Jupyter Notebookを利用してアクセスすることができます。
また、SDKも提供されているため、柔軟性のあるシステム開発を行うことが可能です。

Amazon Braketを使用することの優位性

Amazon　Braketを利用することにより、ユーザーは以下のようなメリットを享受することができます。

豊富な量子ハードウェアへのアクセス: 複数の量子ハードウェアベンダーのサービスを利用できるため、用途や目的に合わせて最適な量子コンピュータを選択できます。
使い勝手の良い開発環境: ブラウザベースの開発環境により、特別なソフトウェアやハードウェアを準備することなく、量子コンピューティングを始めることができます。
従量課金制: 使用した時間や量子ビット数に応じて課金されるため、無駄なくコストを抑えることができます。
AWSとの統合: AWSの他のサービスと連携して、量子コンピューティングの成果をシームレスに活用することができます。

Amazon Braketで利用できる量子マシン

2024/3/28現在Amazon Braketでは下記のマシンを使用することができます。

IonQ トラップイオン量子コンピュータ
Oxford Quantum Circuits (OQC) 量子コンピュータ
QuEra 量子コンピュータ
Rigetti の量子プロセッサ
詳細はこちらをご覧ください
https://aws.amazon.com/jp/braket/quantum-computers/

コーディング

今回はQiskit provider for Amazon Braketを使用してコーディングを行います。
Qiskitの説明に関しては割愛いたします。興味のある方は下記リンクをご覧ください。

マッチングのためのデータ準備

マッチングのために使用するデータを準備します。
今回はシューティングゲームにおけるチーム分けのマッチングを題材としました。

コード

環境はBraketのノートブックを使用。
2024/03/31現在では、東京リージョンでリリースされていないため、北部バージニアリージョンで使用しました。
【インストール及びimport】
qiskitを再インストールする必要があります。詳しくはこちらをご覧ください。

%pip uninstall -y qiskit-terra
%pip uninstall -y qiskit
%pip install --upgrade qiskit
%pip install --upgrade qiskit-optimization
%pip install --upgrade qiskit-algorithms
%pip install --upgrade qiskit-visualization
%pip install --upgrade pyqubo
%pip install --upgrade numpy as np
%pip install --upgrade

import numpy as np
from pyqubo import Array
from typing import List, Tuple
from collections import defaultdict

from qiskit_algorithms.utils import algorithm_globals
from qiskit_optimization import QuadraticProgram
from qiskit_algorithms import QAOA, NumPyMinimumEigensolver
from qiskit_algorithms.optimizers import COBYLA
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from qiskit.primitives import BackendSampler
from qiskit_braket_provider import BraketProvider

【処理部】
今回はqubo作成のためpyquboを使用しました。

sampler = BackendSampler(
    backend=BraketProvider().get_backend("SV1"),
    options={"shots": 10},
)
# プレイヤー名テーブル
players=["PlayerA","PlayerB","PlayerC","PlayerD","PlayerE","PlayerF", "PlayerG", "PlayerH"]

# マッチングに使用するパラメータを定義
# 実際の数値は桁や単位がバラバラなことが多いため、標準化や重みづけを行う必要がある。
# ダメージテーブル
damage_rate = [1, 4, 3, 2, 5, 6, 10, 9]
# 射程
effective_range = [1, 2, 8, 4, 5, 10, 7, 2]
# レート
rating = [10, 9, 3, 2, 8, 2, 1, 4]

#プレイヤー数
N = len(players)
#チームの数
K = 2

x = Array.create(name='x', shape=(N,K), vartype='BINARY')
# コスト関数定義
damage_rate_cost = 1/K * sum((sum(damage_rate[i]*x[i,k] for i in range(N)) - 1/K * sum(sum(damage_rate[i]*x[i,k] for i in range(N)) for k in range(K)))**2 for k in range(K))
effective_range_cost = 1/K * sum((sum(effective_range[i]*x[i,k] for i in range(N)) - 1/K * sum(sum(effective_range[i]*x[i,k] for i in range(N)) for k in range(K)))**2 for k in range(K))
rating_cost = 1/K * sum((sum(rating[i]*x[i,k] for i in range(N)) - 1/K * sum(sum(rating[i]*x[i,k] for i in range(N)) for k in range(K)))**2 for k in range(K))

# ペナルティ関数定義
# Playerがどれか1チームに属するようにする。
# どのチームにも属さない、もしくは複数チームに属する場合にはペナルティを与えて、その組み合わせが選ばれないようにする。
lam = 500 # ペナルティ係数
penalty = lam * sum((sum(x[i,k] for k in range(K)) -1 )**2 for i in range(N))

# qubo作成
y = damage_rate_cost + effective_range_cost + rating_cost + penalty

model = y.compile()
quadratic, offset = model.to_qubo()

# 量子ビット定義
qubo = QuadraticProgram()
for i in range(N):
    for j in range(K):
        qubo.binary_var("x[{}][{}]".format(i, j))

# qiskit solve
with Tracker() as tracker:
    qubo.minimize(quadratic=quadratic)
    algorithm_globals.random_seed = 10598
    qaoa_mes = QAOA(sampler=sampler, optimizer=COBYLA(), initial_point=[0.0, 0.0])
    exact_mes = NumPyMinimumEigensolver()
    qaoa = MinimumEigenOptimizer(qaoa_mes)  # using QAOA
    exact = MinimumEigenOptimizer(
        exact_mes
    )  # using the exact classical numpy minimum eigen solver
    qaoa_result = exact.solve(qubo)
    result = qaoa_result.x
tracker.simulator_tasks_cost()

# 各チームのメンバーのリストを作成
players_in_team = defaultdict(list)
for i, player in enumerate(result):
    team_name = f"team_{i % K + 1}"
    if player == 1.0:
        player = players[int(i/K)]
        players_in_team[team_name].append(player)

# 結果を出力
for team_name, players in players_in_team.items():
    print(f"{team_name}: {players}")

実行結果

team_1: ['PlayerA', 'PlayerC', 'PlayerF', 'PlayerH']
team_2: ['PlayerB', 'PlayerD', 'PlayerE', 'PlayerG']

team_1　damege_rate 合計: 19
team_1　effective_range 合計: 21
team_1　rating 合計: 19
team_1全ステータス合計：　59

team_2　damege_rate 合計: 21
team_2　effective_range 合計: 18
team_2　rating 合計: 20
team_2全ステータス合計：　59

それっぽい結果になっています。

実行マシンの変更

用意されているさまざまなマシンから処理を実行できることもAmazon Braketの大きな魅力です。
先ほどSV1で動かしてみましたが、今度はTN1で実行してみましょう。
実行マシンの変更方法は以下の箇所を変更するだけです。
変更前

sampler = BackendSampler(
    backend=BraketProvider().get_backend("SV1"),
    options={"shots": 10},
)

変更後

sampler = BackendSampler(
    backend=BraketProvider().get_backend("TN1"),
    options={"shots": 10},
)

まとめ

今回はBraketを用いて、量子コンピュータでマッチング問題の処理をしてみました。
さらに
量子コンピュータはマッチング問題をはじめ、さまざまな分野で革新をもたらす可能性を秘めています。Amazon Braketは、量子コンピューティングをクラウドで手軽に利用できるサービスであり、リアルタイムマッチングの実現に貢献することができます。
興味を持った方はぜひ触ってみてください。

参考

qiskit-Braket provider: https://qiskit-community.github.io/qiskit-braket-provider/tutorials/3_tutorial_minimum_eigen_optimizer.html