Algorithm settles financial transactions with fewer qubits

With millions of transactions executed in the financial markets every day, which should be settled first? CQT researchers and their collaborators see how quantum computers may tackle this problem.

Millions of transactions are executed in the financial markets every day, and finding an optimal way to settle them is a computationally heavy task. CQT Principal Investigator Dimitris Angelakis and his team think that noisy intermediate-scale quantum (NISQ) computers could help.

In a paper published in EPJ Quantum Technology on 14 August, Dimitris and his team report that a qubit-efficient optimisation algorithm they created in earlier work can tackle the financial transaction settlement problem. They solved a 128-transaction problem involving 41 parties using 19 qubits. 

The problem size exceeds the biggest previously tackled with NISQ hardware, which was just 7 transactions. The team’s trick is mapping the problem to the available qubits in a different way.

“We bridge the gap between what is possible with the hardware now to what the applications really require,” says Dimitris. 

For these trials, the researchers formulated problems based on data from Singapore Exchange (SGX), Asia’s most international, multi-asset exchange.

There is lots of interest in the potential of quantum computing for the finance industry. In July 2024, for example, the Monetary Authority of Singapore announced a quantum track under their Financial Sector Technology and Innovation Grant Scheme.

Dimitris’s team first introduced their optimisation approach in 2021 and have previously applied it to the vehicle routing problem, a common problem in logistics. “We think our approach will be very horizontal and many different industries can gain from our way of compressing the problem,” says Dimitris.

Dimitris’s co-authors on its application to financial settlement are former group members Elias Huber and Benjamin Tan, and Paul Griffin from Singapore Management University. Dimitris is also a Professor at the Technical University of Crete and founder of AngelQ, a quantum computing startup. The work was supported under Singapore’s Quantum Engineering Programme. 

Order matters

When parties buy and sell securities on the market, their trades are sent to what is known as the ‘clearinghouse’. The clearinghouse has to validate and settle as many transactions as possible within a given time window without any party falling below their credit limit.

While classical computers are sufficient for current transaction volumes, the difficulty of the settlement problem grows exponentially with volume. An increasing number of parties and securities involved in trading might therefore strain existing systems. 

Transaction settlement is a particularly challenging optimisation problem because the order of the transactions also matters. For example, consider the case that A has a balance of $1000. A’s ability to pay B $2000 for some amount of security could depend on A first receiving $1500 from C for some amount of another security. The transaction between A and B can only be settled if the transaction between A and C is settled first.

The researchers consider the financial transaction settlement problem as a ‘quadratic unconstrained binary optimisation’ or QUBO problem. QUBO problems involve binary variables. In the financial transaction settlement problem, the variables represent whether a transaction has been settled or not.

In other approaches such as quantum approximate optimisation algorithms (QAOA) and variational quantum algorithms, each variable is typically mapped to one qubit. Dimitris says, “For real-world applications, you quickly find that you require tens of thousands of qubits. But nobody has that number of operational, error-corrected qubits or is likely to get them in the next three to five years in my opinion.”

Leveraging fewer qubits 

The team uses a different mapping. The researchers split their qubits into two groups – ancilla and register qubits. The states of the register qubits encode labels for the variables. Instead of three qubits representing three variables, for example, the eight possible states of the three qubits would be labels identifying eight variables. The researchers then measure the ancilla qubits to find the values each variable would take.

The result is a logarithmic compression of the total number of qubits needed. “In principle, we could solve 10,000 transactions with 13 or 14 qubits – it is a huge boost,” says Dimitris.

The researchers generated three sets of 16-transaction problems with 10, 12 and 13 parties, and a 128-transaction problem with 41 parties. 

For the 16-transaction problems, they compared their qubit-efficient algorithm with QAOA, running the algorithms on a simulator. Their algorithm needed just 5 qubits while QAOA needed 16 qubits. They found their algorithm outperformed QAOA, even when executed on quantum processors from IBMQ and IonQ, which they accessed via the cloud. It also produced solutions with less variance.

Their algorithm required 19 qubits to solve the 128-transaction problem. The researchers obtained noisy results and noted that none of the results generated by simulation or quantum hardware fulfil all the constraints on security account balances. In other words, the results had parties having negative balances for cash or securities in their account. This highlighted the need for classical post-processing methods to improve performance.