Quantum Payment Optimization Chapter 1 — Let the Cat Out of the Bag (Leaving it in at the Same Time)
Chris McMahon — Director of Quantum & AI, GoodLabs Studio
Combinatorial optimization problems are infamously hard to solve. But they’re also really useful and frequently crop up in finance, engineering, logistics, science… even in everyday life. A great example is the knapsack problem which can be formulated as finding the most optimal collection of things that you can stuff into a finite-sized bag. Each chosen object comes with an inherent cost (like its weight or volume) but also a reward (say, how much you like it). With a constraint on the total cost that you can accommodate, the goal is to maximize the total reward. I like this problem because even though you might run into it in esoteric contexts like cryptography or asset-backed securitization, you’re bound to encounter it far more often just whenever you go on a trip. I know that after I’ve spent a couple of hours packing up the minivan for a weekend at the in-laws, I get special satisfaction in knowing all that effort was actually spent solving an NP-hard problem.
Through our research at Goodlabs into how payment systems can be made more efficient, we recently came across a multi-objective knapsack problem, which has the added complexity of multiple cost metrics that each have their own independent limits. Consider a settlement system where participants spend the day adding payment requests to a common ledger. At the end of the day, a central banker attempts to settle all of the payments without letting any participant’s account run into the red. If this can’t be done, the banker has to resort to solving a knapsack problem by determining which payments to settle such that the total value that moves between participants is maximized?
Finding an exact solution to this problem is a daunting task. Using a simple brute-force method, you’d be facing n! summations, where n is the number of payment requests. Of course, you can end each summation early when you reach the cost limits, and you can find efficiencies by grouping together summations with similar starting sequences since the final terms are likely to be discarded. Still, the best-known algorithms for a regular (one cost, one reward per item) knapsack problem execute as O(nW), where W is the cost limit. Clearly, this can get large for large n, but we should remember that W can get very large, too, especially in a financial context where it may be of order 109 or higher. Furthermore, the multi-objective nature of our problem makes things even more cumbersome. While an approximate solution to the regular knapsack problem can be solved using a polynomial-time approximation scheme, no such scheme has been discovered yet that can apply to a multidimensional knapsack problem, even with just two dimensions.
However, the knapsack problem (and its variants) serves as a great practical demonstration of the power of quantum computing. Using the property of superposition, a quantum state can explore every choice of items simultaneously. Even the most clever classical algorithm can’t escape the necessity of having to consider individual choices for what to put in the knapsack one at a time, but a quantum system can literally check them all in one go.
The most common quantum hardware today relies on physical systems described by Ising Hamiltonians, where qubits made up of quantum particles can exist in a binary state such as spin-up/spin-down. It is the job of a quantum software engineer to map the problem onto such a Hamiltonian before execution on the QPU, and then later to map the output back to interpret the answer. For our knapsack problem, we can assign a binary qubit, xi, to every payment request. A value of 1 (say, spin-down) means that the request gets settled, and 0 (spin-up) means it doesn’t. The problem can be solved this way by maximizing an objective function that is simply a sum of each xi multiplied by its reward, the value of the payment vi. To this, we also have to add the constraints that no account dips into the negative; which can be done using quadratic penalty terms and slack variables (to accommodate the constraint’s inequality). We simply add one penalty term for every participant, and the Hamiltonian is ready for execution.
Of course, the field of quantum computing is far from mature, and state-of-the-art systems today still suffer from issues with connectivity, noise, and long overhead times. To achieve ultimate performance when solving a knapsack problem, classical systems — especially with custom hardware and extreme parallelization — are competitive with quantum systems now, and will likely continue to be so in the near future. However, the promise of quantum computation remains clear. In the next few chapters, we will provide more detail in our journey on how we attempt to use quantum to optimize payment processing.
Chapter 2 is here! Faceoff Xanadu. Qiskit. D-Wave.
The original post can be found here: https://www.goodlabs.studio/blog/let-the-cat-out-of-the-bag
