# Prepare

- Google Colaboratory (*Jupyter Notebook is also OK)
- Distribution source code (*Not required if you want to start from scratch)

# Technology used

Python

Qiskit

# What we did

**Hometown Tax Ceiling Simulation × Rakuten API Integration × Quantum Computing × Optimization Problems**

Obtain a list of hometown tax return items from Rakuten API with "Hometown Tax Translation" and

solve one of

the combinatorial optimization problems Knapsack problem Quantum algorithm (QAOA: quantum approximation optimization algorithm

)

to find

the combination of return goods that will be the heaviest up to the maximum

deduction amount generated by simulation. Anyway, I set up a program to earn money from my hometown tax payment.

# Comments

As I will come out later,

the reason for including "with translation" in the search word of the Rakuten API is to amplify the feeling of stinginess.

We focus on users, businesses, and technology about

how to solve someone's problem with

math, algorithms, the latest technology, and data.

The quantum algorithm approach is currently useless, but

the classic (I have to say so for convenience) program seems to be useful.

However, the deduction limit detailed simulation is only reasonably accurate.

If you want to "do it right", you need not only Mr. Google but also a strong tax accountant.

(So much so that a tax accountant I know has to involve the director)

If you want accurate calculations and fast processing, you

can either become thoroughly familiar with the fundamentals of quantum computing and hometown tax payments, or

compromise on packages and simple simulations.

# About QAOA (Quantum Approximation Optimization Algorithm)

In quantum adiabatic computation (QAA), the final state (Hamiltonian leading to the optimal solution) is $C$, and the initial state (Hamiltonian in the ground energy state) is $B$.

Here, using gamma $ (γ) $ and beta $ (β) $ as arbitrary angle parameters, the unitary matrix for $C$ and $ γ$ is defined as $U (C, γ) $, and the unitary matrix for $B$ and $ β$ is defined as $U (B, β) $.

$$

U(C, γ) = e^{iγC}… ①

U(C, β) = e^{iγB}… ②

$$

Furthermore, the number of iterations using the above unitary matrix is the integer $p$, the vector having $ (γ1,γ2,…,γp)$ as an element is $γ, the vector having (β1,β2,…,βp)$ as an element is $β$, and the p-dimensional orthogonal basis vector is $|s〉$, and the following operator $|γ,β〉$ is defined.

$$

|γ, β> = U(B, β*p)U(C, γ_p)U(B, β*{p-1})U(C, γ_{p-1})… U(B, β_1)U(C, γ_1)|s>… ③

$$

Next, using the operator $|γ,β〉$ defined above, the expected value $Fp$ of the Hamiltonian $C$ that leads to the optimal solution is obtained as follows.

$$

F_p(γ, β) = <γ,β| C|γ,β>… ④

$$

Change the angle parameters $γ$ and $β$ to search for the maximum M_p that $F_p can take. $

$$

M_p = max_{γ,β}F_p(γ,β)… ⑤

$$

When the maximum value M_p is obtained, the γ and β at that time are determined, and the expected value of $ C$ is obtained for (4), and at the same time, the state of the combination that gives the optimal solution is obtained.

- Unitary matrix: Complex square matrix
- Hamiltonian: total energy of the system
- System: Some kind of cohesion
- Expected value: The predicted average
- Ising model: lattice model composed of two state lattice points

# About the knapsack problem

## Defined

$I={1,2,…,N}$ is the set of goods.

When

the weight of each item $i in I$ is $w_i$ value and the upper limit of the total weight of $ v_i$

item is $W$, the following is called the knapsack problem.

$$

max ∑*{i in I}v_iw_i s.t. ∑*{i in I}v_iw_ile W

xin mathbb{N}(forall in I)

$$

Here, $x_i$ represents the number of items to be put in the knapsack.

#### solution

The problem is that if you perform a total search, you will try two options of "select or not select items" for the number of items, and the computational complexity is $O(2^{| I|}) Become $. However, an efficient solution method by the greedy method is known, and the solution method is shown here. The recurrence formula in this problem is

$$

V(i,w)

=begin{cases}

{0quad if;i= 0,or,w = 0}

{V(i-1,w)quad if;w_i>w}

{max(V(i-1),V(i-1,w-w_i)+v_i)quad otherwise}

end{cases}

$$

Become. where $V(i, w)$ represents the maximum value of the total value that can be realized using goods with a subscript of $i$ or less if the sum of their weights is less than or equal to $w$. This formula is

- If "no items can be selected" or "the maximum weight is ${displaystyle 0}{displaystyle 0}$", the sum of the values of the selected items is ${displaystyle 0}{displaystyle 0}$ because there are no items to pack.
- If the weight of the item ${displaystyle i}$ exceeds ${displaystyle w}$, the item ${displaystyle i}$ cannot be added, so the total value is the maximum value of the item up to one previous subscript limit.
- If the weight of item ${displaystyle i}$ does not exceed ${displaystyle w}$, the item ${displaystyle i}$ should be the least less, either the maximum value of adding the item ${displaystyle i}$ or the maximum value of the addition of the item.

It shows that. The pseudocode is as follows. The maximum sum of values is $V(| It is obtained as I|, W)$. In addition, enumerating the selected items requires the addition of code.

- Recurrence formula: a term in the sequence represented by the previous term

# Formulation for solving knapsacks in the Ising model of quantum annealing

$ Definition of Hamiltonian when solving with the Ising model

$H = BBigl(W-sum_iw_ix_iBigl)^2-sum_iv_ix_i$*$B$

= hyperparameter

# Program

## Package Installation

```
!pip install matplotlib
!pip install seaborn
!pip install japanize-matplotlib
!pip install qiskit_optimization
!pip install qiskit-aer
!pip install ortoolpy
!pip install pulp
```

## Package Import

```
from typing import List
import math
from qiskit_optimization.applications import Knapsack
from qiskit.algorithms import QAOA, NumPyEigensolver, NumPyMinimumEigensolver
from qiskit.utils import QuantumInstance
from qiskit import Aer
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from typing import List
from ortoolpy import knapsack
from pulp import *
import requests
import numpy as np
import pandas as pd
import time
import japanize_matplotlib
import copy
import random
from IPython.display import HTML
%matplotlib inline
```

## Define a hometown tax deduction limit calculation class

```
class Calculator():
income: int = 0 # gross income
donation_amount: int = 0 # Donation amount
resident_tax: int = 0 # inhabitant tax amount
def __init__(self, income: int, donation_amount: int, resident_tax: int):
self.income = income
self.donation_amount = donation_amount
self.resident_tax = resident_tax
# Results of deduction amount of hometown tax payment considering the maximum deduction amount
def deduction_result(self):
# Deduction limit from income tax = 40% or less of gross income, deduction limit from basic inhabitant tax = 30% or less of gross income, deduction limit from special inhabitant tax = 20% of individual inhabitant tax income premium.
if (self.income_tax_deduction() <= self.income * 0.4) or (self.basic_resident_tax_deduction() <= self.income * 0.3) or (self.special_inhabitant_tax_deduction() <= self.income * 0.2):
return self.deduction_limit()
else:
return self.hometown_tax_deduction()
# Deduction limit
def deduction_limit(self):
# Individual inhabitant tax income rate ×20% / 100% - basic inhabitant tax 10% - (income tax rate× reconstruction tax rate 1.021) + contribution 2,000 yen
return (self.resident_tax * 0.2 / (1 - 0.1) - (self.income_tax_rate() * 1.021)) + 2000
# Deduction amount for hometown tax payment
def hometown_tax_deduction(self):
# Deduction for income tax + Deduction for basic inhabitant tax + Deduction for special inhabitant tax
return self.income_tax_deduction() + self.basic_resident_tax_deduction() + self.special_inhabitant_tax_deduction()
# Deduction for income tax
def income_tax_deduction(self):
# (Hometown tax donation amount - 2,000 yen)×(Income tax rate (0~45%)×1.021)
return (self.donation_amount - 2000) * (self.income_tax_rate() * 1.021)
# Deduction amount for basic inhabitant tax
def basic_resident_tax_deduction(self):
# (Donation amount of hometown tax payment - 2,000 yen)×10%
return (self.donation_amount - 2000) * 0.1
# Deduction amount for special inhabitant tax
def special_inhabitant_tax_deduction(self):
# (Hometown tax donation amount - 2,000 yen) × (90% - income tax rate ×1.021)*1
return (self.donation_amount - 2000) * (0.9 - (self.income_tax_rate() * 1.021))
# Income Tax Rate
def income_tax_rate(self):
tax_rate = [0.05, 0.10, 0.20, 0.23 ,0.33 , 0.40, 0.45]
borders = [i*10000 for i in [0, 195, 330, 695, 900, 1800, 4000, np.inf]]
deduction = [0, 97500, 427500, 636000, 1536000, 2796000, 4976000]
special_tax = 0.021
step = len(tax_rate)
answer = 0
i = 0
while i <= step:
if (self.income >= borders[i]) and (self.income < borders[i+1]):
answer = tax_rate[i]
i+=1
return answer
```

# Define a detailed simulation class for the maximum limit of the hometown tax deduction

```
class Simulator():
my_income: int = 0 # your salary income
spouse_income: int = 0 # spousal salary income (husband or wife)
listed_capital_gain: int = 0 # Gain on transfer of shares (listed)
unlisted_capital_gain: int = 0 # Gain on transfer of shares (unlisted)
total_income: int = 0 # Total income
spouse: int = 0 # spouse
spouses: List[str] = ['none', 'yes (under 69)', 'yes (over 70)'] # marital status
widow: int = 0 # widow
widows: List[str] = ['Not applicable', 'Widow', 'Single Parent (Female)', 'Single Parent (Male)'] # Widow?
has_handicap: int = 0 # Disabled
handicap = { # disabled
"general": 0, # general (people)
"separated_special": 0, # Separation Special (person)
"together_special": 0 # Cohabitation Special (person)
}
has_support: int = 0 # dependents
support = { # Number of dependents (other than husband or wife)
"under_15": 0,
"from_16_to_18": 0,
"from_19_to_22": 0,
"from_23_to_69": 0,
"over_70": 0,
}
spouse_deduction: int = 0 # spousal deduction
widow_deduction: int = 0 # widowhood deduction
handicap_deduction: int = 0 # Disability Deduction
support_deduction: int = 0 # dependent deduction
basic_deduction: int = 0 # Basic deduction
social_insurance_premium: int = 0 # Amount of social insurance premiums, etc.
small_scale_enterprise_matual_aid_premium :int = 0 # Amount of Small Business Mutual Aid Allowance
life_insurance_premium_deduction: int = 0 # Life insurance premium deduction
earthquake_insurance_premium_deduction: int = 0 # Earthquake insurance premium deduction
medical_expense_deduction: int = 0 # amount of medical expense deduction
housing_loans_special_deduction: int = 0 # Special deduction for housing loans, etc.
income_deduction: int = 0 # Salary income deduction
total_deductin: int = 0 # total deductions
taxable_income: int = 0 # taxable income amount
resident_tax: int = 0 # inhabitant tax amount
donation_amount: int = 0 # Donation amount
def start(self):
print ('Hometown Tax Donation Limit Diagnosis ★'★)
print()
print(' * Enter 0 if there is no value to enter')
print()
print('salary')
self.income_section()
print()
print('Family Structure')
self.famiry_section()
print()
print ('insurance, deductibles, etc.')
self.insurance_and_deduction_section()
print()
self.total_deductin = self.social_insurance_premium + self.small_scale_enterprise_matual_aid_premium + self.life_insurance_premium_deduction + self.earthquake_insurance_ premium_deduction + self.earthquake_insurance_premium_deduction + self.medical_expense_deduction + self.housing_loans_special_deduction + self.income_deduction + self.spouse_ deduction + self.widow_deduction + self.handicap_deduction + self.support_deduction + self.basic_deduction
self.taxable_income = self.total_income - self.total_deductin
if self.taxable_income < 0:
self.taxable_income = 0
self.resident_tax = self.taxable_income * 0.1 # According to tax accountants, inhabitant tax is 10% of "roughly" income minus the amount of deductions, etc.
self.donation_amount = int(input('donation amount'))
print()
calculator = Calculator(self.my_income, self.donation_amount, self.resident_tax)
result = math.floor(calculator.deduction_limit())
return result
def income_section(self):
self.my_income = int(input('your salary income (yen)')
self.spouse_income = int(input("'spousal salary income (husband or wife) (yen)')))
self.listed_capital_gain = int(input("Gain on transfer of shares (listing) (yen)')))
self.unlisted_capital_gain = int(input('Gain on transfer of shares (unlisted) (yen)'))
self.total_income = self.my_income + self.spouse_income + self.listed_capital_gain + self.unlisted_capital_gain
def famiry_section(self):
self.__select_spouse()
self.__select_widow()
self.__select_handicap()
self.__select_support()
# Total income of the person
total_income = self.my_income + self.listed_capital_gain + self.unlisted_capital_gain
if self.spouse_income <= 480000:
# Spousal deduction
if self.spouse == 2:
if total_income <= 9000000:
self.spouse_deduction = 380000
elif (total_income > 9000000) and (total_income <= 9500000):
self.spouse_deduction = 260000
elif (total_income > 9500000) and (total_income <= 10000000):
self.spouse_deduction = 130000
else:
self.spouse_deduction = 0
elif self.spouse == 3:
if total_income <= 9000000:
self.spouse_deduction = 480000
elif (total_income > 9000000) and (total_income <= 9500000):
self.spouse_deduction = 320000
elif (total_income > 9500000) and (total_income <= 10000000):
self.spouse_deduction = 160000
else:
self.spouse_deduction = 0
else:
self.spouse_deduction = 0;
else:
# Special deduction for spouse
if total_income <= 9000000:
if (self.spouse_income > 480000) and (self.spouse_income <= 950000):
self.spouse_deduction = 380000
elif (self.spouse_income > 950000) and (self.spouse_income <= 1000000):
self.spouse_deduction = 360000
elif (self.spouse_income > 1000000) and (self.spouse_income <= 1050000):
self.spouse_deduction = 310000
elif (self.spouse_income > 1050000) and (self.spouse_income <= 1100000):
self.spouse_deduction = 260000
elif (self.spouse_income > 1100000) and (self.spouse_income <= 1150000):
self.spouse_deduction = 210000
elif (self.spouse_income > 1150000) and (self.spouse_income <= 1200000):
self.spouse_deduction = 160000
elif (self.spouse_income > 1200000) and (self.spouse_income <= 1250000):
self.spouse_deduction = 110000
elif (self.spouse_income > 1250000) and (self.spouse_income <= 1300000):
self.spouse_deduction = 60000
elif (self.spouse_income > 1300000) and (self.spouse_income <= 1330000):
self.spouse_deduction = 30000
else:
self.spouse_deduction = 0
elif (total_income > 9000000) and (total_income <= 9500000):
if (self.spouse_income > 480000) and (self.spouse_income <= 950000):
self.spouse_deduction = 260000
elif (self.spouse_income > 950000) and (self.spouse_income <= 1000000):
self.spouse_deduction = 240000
elif (self.spouse_income > 1000000) and (self.spouse_income <= 1050000):
self.spouse_deduction = 210000
elif (self.spouse_income > 1050000) and (self.spouse_income <= 1100000):
self.spouse_deduction = 180000
elif (self.spouse_income > 1100000) and (self.spouse_income <= 1150000):
self.spouse_deduction = 140000
elif (self.spouse_income > 1150000) and (self.spouse_income <= 1200000):
self.spouse_deduction = 110000
elif (self.spouse_income > 1200000) and (self.spouse_income <= 1250000):
self.spouse_deduction = 80000
elif (self.spouse_income > 1250000) and (self.spouse_income <= 1300000):
self.spouse_deduction = 40000
elif (self.spouse_income > 1300000) and (self.spouse_income <= 1330000):
self.spouse_deduction = 20000
else:
self.spouse_deduction = 0
elif (total_income > 9500000) and (total_income <= 10000000):
if (self.spouse_income > 480000) and (self.spouse_income <= 950000):
self.spouse_deduction = 130000
elif (self.spouse_income > 950000) and (self.spouse_income <= 1000000):
self.spouse_deduction = 120000
elif (self.spouse_income > 1000000) and (self.spouse_income <= 1050000):
self.spouse_deduction = 110000
elif (self.spouse_income > 1050000) and (self.spouse_income <= 1100000):
self.spouse_deduction = 90000
elif (self.spouse_income > 1100000) and (self.spouse_income <= 1150000):
self.spouse_deduction = 70000
elif (self.spouse_income > 1150000) and (self.spouse_income <= 1200000):
self.spouse_deduction = 60000
elif (self.spouse_income > 1200000) and (self.spouse_income <= 1250000):
self.spouse_deduction = 40000
elif (self.spouse_income > 1250000) and (self.spouse_income <= 1300000):
self.spouse_deduction = 20000
elif (self.spouse_income > 1300000) and (self.spouse_income <= 1330000):
self.spouse_deduction = 10000
else:
self.spouse_deduction = 0
else:
self.spouse_deduction = 0
if total_income <= 5000000:
# Widowhood deduction
if self.widow == 1:
self.widow_deduction = 270000
# Single parent deduction
elif (self.widow == 2) or (self.widow == 3):
self.widow_deduction = 350000
else:
self.widow_deduction = 0
else:
self.widow_deduction = 0
# Disability deduction
if self.has_handicap == 1:
self.handicap_deduction = 270000 * self.handicap['general'] + 400000 * self.handicap['separated_special'] + 750000 * self.handicap['together_special ']
else:
self.handicap_deduction = 0
# Dependent deduction
if self.has_support == 1:
self.support_deduction = 380000 * self.support['from_16_to_18'] + 630000 * self.support['from_19_to_22'] + 480000 * self.support['from_23_to_69'] + 580000 * self.support['over_70']
else:
self.support_deduction = 0
def insurance_and_deduction_section(self):
self.social_insurance_premium = int(input('amount of social insurance premiums, etc. (yen))
self.small_scale_enterprise_matual_aid_premium = int(input('amount of small business mutual aid premiums (yen)')
self.life_insurance_premium_deduction = int(input('life insurance premium deduction (yen)')
self.earthquake_insurance_premium_deduction = int(input("'earthquake insurance premium deduction (yen)')
self.medical_expense_deduction = int(input('amount of medical expense deduction (yen)'))
self.housing_loans_special_deduction = int(input('special deduction for housing loans, etc. (yen)')
# Income deduction
if self.total_income < 1625000:
self.income_deduction = 550000
elif (self.total_income >= 1625001) and (self.total_income < 1800000):
self.income_deduction = self.total_income * 0.4 - 100000
elif (self.total_income >= 1800001) and (self.total_income < 3600000):
self.income_deduction = self.total_income * 0.3 + 80000
elif (self.total_income >= 3600001) and (self.total_income < 6600000):
self.income_deduction = self.total_income * 0.2 + 440000
elif (self.total_income >= 6600001) and (self.total_income < 8500000):
self.income_deduction = self.total_income * 0.1 + 1100000
else:
self.income_deduction = 1950000
# Basic deduction
if self.total_income <= 24000000:
self.basic_deduction = 480000
elif (self.total_income > 24000000) and (self.total_income <= 24500000):
self.basic_deduction = 320000
elif (self.total_income > 24000000) and (self.total_income <= 25000000):
self.basic_deduction = 160000
else:
self.basic_deduction = 0
def __select_spouse(self):
print('marital status')
for i, sponse in enumerate(self.spouses):
print(str(i+1) + '. ' + sponse)
self.spouse = int(input(' pick a number. '))
def __select_widow(self):
print('Widow?) ')
for i, widow in enumerate(self.widows):
print(str(i+1) + '. ' + widow)
self.widow = int(input(' pick a number. '))
def __select_handicap(self):
self.has_handicap = int(input(' disabled 1. Yes, 2. None'))
if self.has_handicap == 1:
self.handicap['general'] = int(input('general disabled person)'))
self.handicap['separated_special'] = int(input('person/person with a special disability living separately)'))
self.handicap['together_special'] = int(input('special disabled person)'))
def __select_support(self):
self.has_support = int(input('dependents 1. Yes, 2. None'))
if self.has_support == 1:
self.support['under_15'] = int(input('15 years and under'))
self.support['from_16_to_18'] = int(input('16-18'))
self.support['from_19_to_22'] = int(input('19-22'))
self.support['from_23_to_69'] = int(input('23-69)))
self.support['over_70'] = int(input('over 70'))
```

## Define different ways to solve knapsack problems

```
class KnapsackProblem():
values: List[int] = []
weights: List[int] = []
max_weight: int = 0
def __init__(self, values, weights, max_weight):
self.values = values
self.weights = weights
self.max_weight = max_weight
def solve_by_qaoa(self):
problem = Knapsack(values=self.values, weights=self.weights, max_weight=self.max_weight)
quadratic_program = problem.to_quadratic_program()
backend = Aer.get_backend('aer_simulator')
quantum_instance = QuantumInstance(backend=backend, shots=800, seed_simulator=99)
min_eigen_optimizer = MinimumEigenOptimizer(min_eigen_solver=QAOA(reps=1, quantum_instance=quantum_instance))
solved = min_eigen_optimizer.solve(quadratic_program)
result = problem.interpret(solved)
print(result)
return result
def solve_by_numpy_eigensolver(self):
problem = Knapsack(values=self.values, weights=self.weights, max_weight=self.max_weight)
quadratic_program = problem.to_quadratic_program()
min_eigen_optimizer = MinimumEigenOptimizer(min_eigen_solver=NumPyMinimumEigensolver())
solved = min_eigen_optimizer.solve(quadratic_program)
result = problem.interpret(solved)
print(result)
return result
def solve_by_ortoolpy(self):
result = knapsack(self.weights, self.values, self.max_weight)
print(result)
return result
def solve_by_pulp(self):
ran = range(len(self.values))
problem = LpProblem(sense=LpMaximize)
var = [LpVariable('x%d'%i, cat=LpBinary) for i in ran]
problem += lpDot(self.weights, var)
problem += lpDot(self.values, var) <= self.max_weight
problem.solve()
result = (value(problem.objective), [i for i in ran if value(var[i]) > 0.5])
print(result)
return result
def solve_by_greedy_algorithm(self):
N = len(self.values)
W = self.max_weight
w = self.weights
v = self.values
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
for j in range(W+1):
if j < w[i]:
dp[i+1][j] = dp[i][j]
else:
dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
result = dp[N][W]
print(result)
return result
def solve_by_ising_model(self):
def Hamiltonian(x):
B = 10
W = self.max_weight
w_sum = 0
v_sum = 0
for i, w in enumerate(self.weights):
w_sum += w*x[i]
for i, v in enumerate(self.values):
v_sum += v*x[i]
H = B*(W-w_sum)**2-v_sum
return H
def run(H):
N = len(self.values)
T = self.max_weight
ite = 1000
targetT = 0.02
red = 0.97
q = [random.randint(0,1) for i in range(N)]
# q = [1,1,1,1,0,0,0,0,0,0]
while T>targetT:
x_list = np.random.randint(0, N, ite)
for x in x_list:
q2 = copy.copy(q)
y = np.random.randint(0, N)
q2[x] = q[y]
q2[y] = q[x]
dE = H(q2) - H(q)
if np.exp(-dE/T) > np.random.random_sample():
q[x] = q2[x]
q[y] = q2[y]
T *= red
return q
answer = run(Hamiltonian)
result = []
for i, a in enumerate(answer):
if a == 1:
result.append(i)
print(result)
return
```

## Get a product list from Rakuten API

```
REQUEST_URL = "https://app.rakuten.co.jp/services/api/IchibaItem/Search/20170706"
APP_ID="< Rakuten API App ID >"
serch_keyword = 'Hometown tax payment with translation'
serch_params = {
"format" : "json",
"keyword" : serch_keyword,
"applicationId" : [APP_ID],
"availability" : 0,
"hits" : 30,
"sort" : "standard",
"postageFlag" : 1
}
item_list = []
max_page = 10
for page in range(1, max_page+1):
response = requests.get(REQUEST_URL, serch_params)
result = response.json()
item_key = ['itemName', 'itemPrice', 'itemCaption', 'shopName', 'shopUrl', 'itemUrl']
for i in range(0, len(result['Items'])):
time.sleep(1)
tmp_item = {}
item = result['Items'][i]['Item']
for key, value in item.items():
if key in item_key:
tmp_item[key] = value
item_list.append(tmp_item.copy())
df = pd. DataFrame(item_list)
df.drop_duplicates(subset=['itemUrl'], inplace=True) # Remove duplicates
df = df.reindex(columns=['itemName', 'itemPrice', 'itemCaption', 'itemUrl', 'shopName', 'shopUrl'])
df.columns = ['product name', 'product price', 'product description', 'product URL', 'store name', 'store URL']
df.index = df.index + 1
# Extract only products whose quantity is known
weight = df['product name'].str.contains('kg')
df = df[weight]
df['kg'] = df['product name'].str.extract('([0-9]+)kg')
df = df.reindex(columns=['product name', 'kg', 'product price', 'product description', 'product URL', 'store name', 'store URL']
```

## Data Verification

`df.head()`

`df.plot(title='relationship between weight and price')`

## Practical solution (resort to ortoolpy)

```
def practical_solution():
simulator = Simulator()
weights = [int(data) for i, data in enumerate(df['kg'])]
prices = [int(data) for i, data in enumerate(df['commodity price'])]
deduction_limit = simulator.start()
# In the case of knapsacks, the price of the thing is the value, and there are restrictions due to weight. In this case, there is a price limit, taking the weight of the thing as the value.
knapsack_problem = KnapsackProblem(values=weights, weights=prices, max_weight=deduction_limit)
result = knapsack_problem.solve_by_ortoolpy()
print(f'deduction limit is {deduction_limit} yen')
HTML(df.to_html(render_links=True, escape=False))
def make_clickable(val):
return f'<a target="_blank" href="{val}">{val}</a>'
return df.iloc[result[1]].style.format({'Product URL': make_clickable, 'Store URL': make_clickable})
```

## Quantum Algorithm Solution (QAOA)

```
def futurism_solution():
simulator = Simulator()
weights = [int(data) for i, data in enumerate(df['kg'])][0:10] # The current performance of Colab memory and quantum computers limits 10 (10 is not enough, please forgive me)
prices = [int(data) for i, data in enumerate(df['commodity price'])][0:10] # and so on
deduction_limit = simulator.start()
# In the case of knapsacks, the price of the thing is the value, and there are restrictions due to weight. In this case, there is a price limit, taking the weight of the thing as the value.
knapsack_problem = KnapsackProblem(values=weights, weights=prices, max_weight=deduction_limit)
result = knapsack_problem.solve_by_qaoa()
print(f'deduction limit is {deduction_limit} yen')
HTML(df.to_html(render_links=True, escape=False))
def make_clickable(val):
return f'<a target="_blank" href="{val}">{val}</a>'
return df.iloc[result].style.format({'Product URL': make_clickable, 'Store URL': make_clickable})
```

## execution

#### Results of practical solutions (they choose the heavy ones within the deduction limit)

`practical_solution()`

#### The result of the solution method by quantum algorithm (it takes 30 minutes ~ 1 hour from the start to the end of execution) (the heavy one is selected within the deduction limit)

`futurism_solution()`