DEV Community

Cover image for Quantum Algorithm Implementation: Finding the Best Deals
Supreeth Mysore Venkatesh
Supreeth Mysore Venkatesh

Posted on

Quantum Algorithm Implementation: Finding the Best Deals

Introduction

The similarity between the rich and the poor is that both love a good bargain—just at different stores. Whether you’re shopping at Louis Vuitton or a local flea market, everyone is on the lookout for the best deals. But what if you could use cutting-edge technology to optimize your shopping experience?
Imagine trying to bundle purchases to maximize discounts, but the options are so numerous, forget about manually evaluating each one, it's impossible even for today's supercomputers. However, this problem can be tackled using quantum computing, specifically with the BILP-Q algorithm. Let's dive into how this works.

Understanding the Basics

What is the Problem?

Think of this as a shopping challenge. You have four items to buy: a webcam, shoes, headphones, and socks. Each item or combination of items has a different discount. The goal? Find the best combination of bundles to minimize your total cost.

Classical Approach vs. Quantum Approach:

Traditionally, solving this involves evaluating all possible combinations of items, which quickly becomes impractical as the number of items increases. This is a classical NP-Hard problem in AI called the Coalition Structure Generation (CSG) problem which has vital applications in cooperative game theory, multi-agent systems, and microeconomics.
Quantum computing, however, can handle this complexity more efficiently.

Introducing BILP-Q

What is BILP-Q?

BILP-Q stands for Binary Integer Linear Programming - Quantum. It transforms our shopping problem into a Quadratic Unconstrained Binary Optimization (QUBO) problem, which quantum computers can solve effectively using algorithms like Quantum Approximate Optimization Algorithm (QAOA).

Example Scenario

Imagine you want to buy four items: a webcam, shoes, headphones, and socks. Here’s how the discounts for different bundles look:

Single items:

  • Webcam: $30
  • Shoes: $40
  • Headphones: $25
  • Socks: $15

Bundles of two items:

  • Webcam & Shoes: $50
  • Webcam & Headphones: $40
  • Webcam & Socks: $50
  • Shoes & Headphones: $55
  • Shoes & Socks: $45
  • Headphones & Socks: $45

Bundles of three items:

  • Webcam, Shoes & Headphones: $90
  • Webcam, Shoes & Socks: $95
  • Webcam, Headphones & Socks: $75
  • Shoes, Headphones & Socks: $85

All four items:

  • Webcam, Shoes, Headphones & Socks: $105

Your goal is to buy all four items with the maximum discount.
For formal definitions of the problem and mathematical details, please refer to the original paper of BILP-Q.

Visual Representation of the solution space

The following diagram shows all possible ways to purchase the four items, along with their total costs. Each level represents a different number of groups (coalitions).

The blue-colored cell denotes the best option to buy as it has the least cost. In this example, the optimal way to purchase all items is by splitting them into two groups: {Shoes, Socks} and {Webcam, Headphones}, with a total cost of $85.

Manually checking each possible combination is tedious, so we use BILP-Q to find the optimal solution.

Walkthrough of the Example

Setting Up the Problem:

Install qiskit

pip install qiskit
pip install qiskit_optimization
Enter fullscreen mode Exit fullscreen mode

Clone/download the BILP-Q official repository and import the below python scripts:

import Utils_Solvers
import Utils_CSG
Enter fullscreen mode Exit fullscreen mode

Define the Problem Instance:

We will enumerate the items as follows:
1 for Webcam,
2 for Shoes,
3 for Headphones, and
4 for Socks.
Here’s how you can initialize the values of the bundles:

# Define the cost of each bundle
coalition_values = {
    '1': 30,
    '2': 40,
    '3': 25,
    '4': 15,
    '1,2': 50,
    '1,3': 40,
    '1,4': 50,
    '2,3': 55,
    '2,4': 45,
    '3,4': 45,
    '1,2,3': 90,
    '1,2,4': 95,
    '1,3,4': 75,
    '2,3,4': 85,
    '1,2,3,4': 105
}
Enter fullscreen mode Exit fullscreen mode

Convert to BILP:

We convert the CSG problem to a Binary Integer Linear Programming (BILP) problem:

c, S, b = Utils_CSG.convert_to_BILP(coalition_values)
Enter fullscreen mode Exit fullscreen mode

Convert to QUBO:

Next, we convert the BILP problem to a Quadratic Unconstrained Binary Optimization (QUBO) problem:

import numpy as np

qubo_penalty = 50 * -1
linear, quadratic = Utils_CSG.get_QUBO_coeffs(c, S, b, qubo_penalty)

Q = np.zeros([len(linear), len(linear)])

# Diagonal elements
for key, value in linear.items():
    Q[int(key.split('_')[1]), int(key.split('_')[1])] = value

# Non-diagonal elements
for key, value in quadratic.items():
    Q[int(key[0].split('_')[1]), int(key[1].split('_')[1])] = value / 2
    Q[int(key[1].split('_')[1]), int(key[0].split('_')[1])] = value / 2
Enter fullscreen mode Exit fullscreen mode

Solving QUBO Using QAOA:

We use QAOA to solve the QUBO problem:

#@title Default title text
backend = BasicAer.get_backend('qasm_simulator') 
optimizer = COBYLA(maxiter=100, rhobeg=2, tol=1.5)
qubo = create_QUBO(linear, quadratic)

p=1
init = [0.,0.]

qaoa_mes = QAOA(optimizer=optimizer, reps=p, quantum_instance=backend, initial_point=init)
qaoa = MinimumEigenOptimizer(qaoa_mes)  # using QAOA
qaoa_result = qaoa.solve(qubo)

solution = qaoa_result.x
print(f'Solution: {solution}')
Enter fullscreen mode Exit fullscreen mode

Decoding the Solution:

The solution x is a binary string of size 2n12^n - 1 , where each bit represents a non-empty subset of the items and the positions marked 1 will be considered. For four items, the subsets are:

  1. Webcam
  2. Shoes
  3. Headphones
  4. Socks
  5. Webcam, Shoes
  6. Webcam, Headphones
  7. Webcam, Socks
  8. Shoes, Headphones
  9. Shoes, Socks
  10. Headphones, Socks
  11. Webcam, Shoes, Headphones
  12. Webcam, Shoes, Socks
  13. Webcam, Headphones, Socks
  14. Shoes, Headphones, Socks
  15. Webcam, Shoes, Headphones, Socks

For example, the solution is obtained will look like 000001001000000.
Parsing the binary string from left to right, we select the 6th subset {Webcam, Headphones} and the 9th subset {Shoes, Socks} as the optimal bundles to purchase.

Visualizing the Quantum Circuit

Finally, display the quantum circuit used in QAOA:

qaoa_mes.get_optimal_circuit().draw('mpl')
Enter fullscreen mode Exit fullscreen mode

The Challenge of the Problem

Although this is a very hard problem, the size of the input is also exponential compared to the number of agents (items in this case). For n=4n=4 items, the input was a dictionary of prices for each possible bundle, which totals 2n1=241=152^n−1 = 2^4−1=15 .

Thus, in the next post, we will explore induced subgraph games, where the problem setting is more practical, but the complexity of finding the optimal solution is still hard for classical computers.

Conclusion

In this post, we explored how a quantum algorithm can tackle complex optimization problems efficiently. We have modeled a very primitive scenario while the actual problem is based on intelligent agents and typically not items. There are more realistic coalition formation use-cases that can be implemented such as peer-to-peer energy trading, logistics, wireless sensor networks and see how quantum computing can simplify the decision-making process.

Quantum computing is still emerging, but its potential to solve complex optimization problems is immense. As quantum technology advances, we can expect more efficient solutions to problems that are currently infeasible for classical computers.

References

Join the Discussion

I wrote this post to make the concepts of quantum computing more accessible and to showcase its real-world applications. Whether you're a seasoned tech enthusiast or just curious about new technologies, I believe there's something valuable for everyone here.

Feel free to leave your questions, thoughts, or feedback in the comments below. I'd love to hear about your experiences, any challenges you face with optimization problems or other topics you’d like to learn more about.

Top comments (0)