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

## はじめに
:fish:お魚学部:fish:出身、フロントやらIoTやらやっている「てぬ太」です。
最近気になっている[Fixstars Amplify](https://amplify.fixstars.com/)という量子アニーリングを扱えるクラウドプラットフォームを触ってみました。

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

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

## 1. グランドメニューのデータを用意する
深夜には非常にきつい作業でした。
[サイゼリヤのグランドメニューをご紹介](https://www.saizeriya.co.jp/menu/grandmenu.html)から見られるのは電子カタログのためスクレイピングができず全て手打ちで用意。


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

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

```python

# 2021/03/19 時点のサイゼリヤグランドメニュー
GRAND_MENU = [
    {"price":  350, "calorie":  161, "name": "ガーデンサラダ"},
    {"price":  500, "calorie":  243, "name": "ガーデンサラダ（Lサイズ）"},
    # 省略
    {"price":  100, "calorie":   40, "name": "フルーツソース（カシス＆ブルーベリー）"},
]
```
料理数を確認。今回は110の候補が用意できました。

```python

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

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

```python

# 料理の名前リスト
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](https://amplify.fixstars.com/)チュートリアルを参考にしながら。

```python
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 はアカウントのアクセストークンに置換してください

```python
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)
```

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

```python
# 解が得られなかった場合、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. サイゼリヤチャレンジ結果

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

```python
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です。")
```
![スクリーンショット 2021-03-19 060351.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1116978/6df666de-0e68-db14-f424-7fd636164098.png)
![スクリーンショット 2021-03-19 060420.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1116978/7f397fc8-53cd-5ecb-2338-9abc2723a86c.png)


できました！:cherry_blossom::cherry_blossom:

## 4. まとめ
初心者でも手軽に量子コンピュータを使った気になれる[Fixstars Amplify](https://amplify.fixstars.com/)でした。
チュートリアルには数独や画像のノイズ除去など眺めているだけでも面白い題材があるのでぜひ！

現在は条件を満たす組み合わせはかなりあるので、今後はカロリーに条件を設けるなどしてより最適化された組み合わせを取得してみたいですね。

## 5. 参考リンク
[サイゼリヤ1000円ガチャをつくってみた(Heroku + Flask + LINEbot)](https://qiita.com/marusho_summers/items/a2d3681fac863734ec8a)
[「サイゼリヤで1000円あれば最大何kcal摂れるのか」を制約論理プログラミングで解く](https://qiita.com/ichiban@github/items/a059151aace2fcb1559b)

## 6. おまけ
#####5000円の結果
![スクリーンショット 2021-03-19 052211.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1116978/d1df9d10-9fff-24e0-e0e1-666006ce8fcd.png)
![スクリーンショット 2021-03-19 052335.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1116978/094603c5-fa18-d02e-c3d3-2a135281db71.png)
#####10000円の結果
![スクリーンショット 2021-03-19 060628.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1116978/1f069262-1e5d-d251-406b-fc7d69ed93b9.png)
![スクリーンショット 2021-03-19 060716.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1116978/39b5bf51-6188-eb54-6201-446ff32aba6c.png)