量子コンピュータでサイゼリヤチャレンジ #Python

はじめに

お魚学部出身、フロントやらIoTやらやっている「てぬ太」です。
最近気になっているFixstars Amplifyという量子アニーリングを扱えるクラウドプラットフォームを触ってみました。

サイゼリヤのグランドメニューのなかから、設定した金額を最大限満たす組み合わせを取得することを目指します。
python初心者なので間違っている箇所や高速な処理方法などあればご教示いただけますと幸いです。

目次
1. グランドメニューのデータを用意する
 2. バイナリ変数での実装
 3. サイゼリヤチャレンジ結果
 4. まとめ
 5. 参考リンク
 6. おまけ

1. グランドメニューのデータを用意する

深夜には非常にきつい作業でした。
サイゼリヤのグランドメニューをご紹介から見られるのは電子カタログのためスクレイピングができず全て手打ちで用意。

適当なルールを決めてそれぞれの料理に価格・カロリー・名前を設定しました。

前菜＆おつまみ：Wサイズでは、価格とカロリーは2倍とする
ピザ：Wチーズでは、+100円 +100kcalとする
パスタ：大盛では、カロリー = (通常カロリー * 大盛価格/通常価格)とする
いずれも四捨五入して整数で扱う
カロリー表示がないものまたはソースやドレッシングなどは考慮しない


# 2021/03/19 時点のサイゼリヤグランドメニュー
GRAND_MENU = [
    {"price":  350, "calorie":  161, "name": "ガーデンサラダ"},
    {"price":  500, "calorie":  243, "name": "ガーデンサラダ（Lサイズ）"},
    # 省略
    {"price":  100, "calorie":   40, "name": "フルーツソース（カシス＆ブルーベリー）"},
]

料理数を確認。今回は110の候補が用意できました。


# 料理数
GRAND_MENU_NUM = len(GRAND_MENU)
-> 110

フィールドごとにまとめます。


# 料理の名前リスト
GRAND_MENU_NAMES = []

# 料理の価格リスト
GRAND_MENU_PRICES = []

# 料理のカロリーリスト
GRAND_MENU_CALORIES = []

for i in range(GRAND_MENU_NUM):
    GRAND_MENU_NAMES.append(GRAND_MENU[i]["name"]) 
    GRAND_MENU_PRICES.append(GRAND_MENU[i]["price"])
    GRAND_MENU_CALORIES.append(GRAND_MENU[i]["calorie"])

2. バイナリ変数での実装

定式化にあたって、QUBO模型とイジング模型のどちらを使うか考えます。
今回は選択された料理のみ価格やカロリーを足していけばよさそうなので 0 or 1 で二値を表現するQUBO模型を採用します。

目指す合計金額を1000円として、定式は下記の通り
1000円との差がなるべく小さくなるように料理を選択していきます。
p：価格
q：バイナリ変数

$$
f = \left(1000 -\sum_{i=0}^{N-1}p_iq_i\right)^2
$$

実装はFixstars Amplifyチュートリアルを参考にしながら。

from amplify import(
    gen_symbols,
    BinaryPoly,
)

# バイナリ変数を生成
q = gen_symbols(BinaryPoly, GRAND_MENU_NUM)

# 目的関数の構築: バイナリ
f = BinaryPoly()

# 合計金額
TOTAL_AMOUNT = 1000

# 選択された料理の価格を足していく
for i in range(GRAND_MENU_NUM):
    f += GRAND_MENU_PRICES[i] * q[i]

f = TOTAL_AMOUNT - f
f = f ** 2

クライアントの設定を行います。
※client.token はアカウントのアクセストークンに置換してください

from amplify.client import FixstarsClient
from amplify import Solver
from amplify import decode_solution

# クライアントの設定
client = FixstarsClient()
client.parameters.timeout = 1000   # タイムアウト1秒
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # アクセストークンに置換 
client.parameters.outputs.duplicate = True  # 同じエネルギー値の解を列挙

solver = Solver(client)
result = solver.solve(f)

条件を満たす組み合わせが見つかったか確認します。

# 解が得られなかった場合、len(result) == 0
if len(result) == 0:
    raise RuntimeError("No solution was found")

energy = result[0].energy
values = result[0].values

# エネルギー値 (f の最小値) を確認
print(f"f = {energy}")
-> f = 0.0

3. サイゼリヤチャレンジ結果

結果を出力してみます...どきどき...

from amplify import decode_solution

solution = decode_solution(q, values)

print(solution)

# 注文する料理リスト
ORDER_GRAND_MENUS = []

# 注文する料理の価格合計
SUM_ORDER_GRAND_MENU_PRICES = 0

# 注文する料理のカロリー合計
SUM_ORDER_GRAND_MENU_CALORIES = 0

for i in range(len(solution)):
    if solution[i] == 1:
            ORDER_GRAND_MENUS.append(GRAND_MENU[i])
            SUM_ORDER_GRAND_MENU_PRICES += GRAND_MENU[i]["price"]
            SUM_ORDER_GRAND_MENU_CALORIES += GRAND_MENU[i]["calorie"]

# 結果出力
for i in range(len(ORDER_GRAND_MENUS)):
    print(("\\" + str(ORDER_GRAND_MENUS[i]["price"])).rjust(5) + str(ORDER_GRAND_MENUS[i]["calorie"]).rjust(5) + "kcal  " + str(ORDER_GRAND_MENUS[i]["name"]))

print("お会計は" + str(SUM_ORDER_GRAND_MENU_PRICES) + "円です。")

print("総カロリーは" + str(SUM_ORDER_GRAND_MENU_CALORIES) + "kcalです。")