A program that uses quantum optimization to benefit from hometown tax payment

Prepare

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()