An update on using quantum computing for operations research
The Knapsack problem with OpenQAOA
Randy D
Amazon Employee
Published Jan 2, 2025
In 2021 I wrote an article describing some new approaches to solve optimization problems from the operations research (OR) space on AWS. These included using reinforcement learning (RL) and using quantum computing approaches. At the time, RL seemed the most promising, but it requires a careful construction of the RL problem space, making the solution hard to generalize.
After monitoring the recent progress in quantum computing algorithms like quantum approximate optimization algorithms (QAOA), I decided to revisit my sample OR problem. As a brief recap:
Let’s start with a reference problem and solve it with a traditional solver. We’ll tackle an inventory management issue (see Figure 2). We have a sales depot that supplies products for local sales outlets. For the depot’s Region, there are seven weeks of historical sales data for each product. We also know how much each product costs and for how much it can be sold. Finally, we know the overall weekly capacity of the depot. This depends on logistical constraints like the size of the warehouse and transportation availability. This scenario is loosely based on the Grupo Bimbo retailer’s Kaggle competition and dataset.
I decided to use OpenQAOA this time around. It has built-in formulations for common optimization problems, including the knapsack problem. OpenQAOA has a variant that supports a knapsack formulation that doesn't require slack variables, which makes it more efficient in terms of qubit utilization. (See this article for a description of the slack-free formulation.)
To start with, I initialize the
SlackFreeKnapsack problem with my items. I use a small subset of the available items for now.Next I create a quantum device to use. In this case I use the
sv1 simulator from Amazon Braket, but I could instead use a real device. The code below includes some typical initialization copied from the OpenQAOA examples.Running the circuit is simple.
Now we can access the most likely bitstring and see which items were selected.
I'm most concerned with how many items we can run, given the limitation on the number of qubits on available quantum devices today. Most of the simulators and devices available in Braket are in the 20-30 qubit range, although there are newer devices available with over 200. In the knapsack problem, we need one qubit for each item, and the number of items in our problem formulation is actually higher than the real number of items. (We need to represent each item as a 'yes' or 'no' option, so we encode the real items as a series of power-of-2 selections.)
Running a subset of 10 items on the
sv1 simulator completed in about 30 seconds, while 20 items took about 90 seconds. I was not able to run 30 or more items on the sv1 simulator.At the present time, while libraries like OpenQAOA have certainly made it easier to approach OR problems with quantum algorithms, the devices haven't caught up. There are quantum annealing approaches that can likely handle more items than the QAOA algorithm, but real problems have thousands of items to deal with. I'm looking forward to trying this experiment again when the next generation of devices are ready.
Any opinions in this post are those of the individual author and may not reflect the opinions of AWS.