Using TitanQ to Find the Minimum Weighted Cycle in a Graph, With Applications in Currency Arbitrage

TitanQ is a powerful quantum-inspired optimization solver that is designed to handle large-scale, complex problems at high-speed that many classical solvers struggle with.

In particular, the currency arbitrage problem presents as a unique challenge due to the number of possible exchanges and the speed required to detect these arbitrage opportunities.

What is Currency Arbitrage?

The term arbitrage refers to the practice of buying and selling assets to take advantage of disparities in pricing among related assets and markets [1].

Arbitrage is relevant in High-Frequency Trading (HFT) applications, where a high volume of trades are conducted in a short period of time that act on brief market inefficiencies [2].

Historically, these HFT opportunities deliver some of the highest Sharpe ratios in the industry.

Beyond just finance, the concept of arbitrage plays an important role in domains such as supply chain logistics, energy markets, and e-commerce [1].

For example, a business may want to purchase goods at a lower price in foreign lower-cost markets and sell their products in a higher-cost area, providing them an edge against their competitors (otherwise known as comparative advantage) [3]. Or, an energy grid operator may want to purchase and store electricity when its production cost is lower for later use during periods of higher demand [4].

Currency arbitrage involves a series of currency transactions that exploit small price differences across foreign exchange (FX) markets.

The challenge? With n currencies, the number of exchange rates scales polynomially, with up to n(n-1) possible exchange rates.

This means that for just 20 currencies, there can be up to 20 * 19 = 380 possible exchanges that change in a matter of seconds. As the number of currencies increase and live data remains susceptible to inconsistencies, detecting a profitable series of exchanges becomes an increasingly difficult task.

The currency arbitrage problem can be posed as a minimum-weight cycle problem in a directed graph — a fundamental problem in combinatorial optimization. Currencies are represented as nodes with exchanges represented as weighted edges in the graph.

This problem goes beyond finance — minimum weight cycle detection has applications in network routing, trading, power grid optimization, and much more.

Fortunately, the TitanQ solver is built to handle problems just like this.

In just a matter of seconds, TitanQ can find and return profitable exchange cycles in an exchange market.

In an environment where every fraction of a second counts, TitanQ will give you the edge you need.

The Formulation

Recall the currency exchange market can be represented as a directed graph, drawn from the edge-based formulation [5].

Each currency i is encoded as a node with directed edge (i, j) representing the currency exchange rate between two currencies i and j. It is worth noting that the directed format is essential since the differences in bid and ask prices lie within those edges.

Nodes are encoded in set V and edges in set E.  For example:

Set decision variable x ∈ {0, 1} such that each xij represents if the edge (i, j) is included in the solution. Let cij be the exchange rate from currency i to currency j, represented as the weight of edge (i, j). The goal is to maximize the product of exchange rates.

Note cij only contributes to the product if it is included in the solution, i.e., xij = 1. This is an equivalent problem to the following:

Since log(x) is a strictly increasing function. Applying log rules, this can be re-expressed as a sum to simplify the problem:

To convert to a minimization problem for TitanQ, the objective is multiplied by –1. Thus, the final objective function is re-written as follows:

To restrict the solution to only include cycles, a flow constraint is implemented.

Additionally, there is a constraint that prevents trading with a node twice. This ensures all cycles returned use a distinct set of nodes.

A Simple Example

Taking an arbitrary example of 4 currencies below, we can empirically determine the most profitable cycle to be ('CAD/USD', 'USD/EUR', 'EUR/CAD') from the edge set ['CAD/USD', 'USD/EUR', 'EUR/CAD', 'EUR/CNY', 'CNY/CAD'] with a profit of 46.25 % (given that 0.9 1.25 1.3 = 1.4625).

Small examples like this are easy to solve manually but become exponentially more difficult when more nodes and exchange rates are introduced in real-life scenarios.

Testing on Real World Data

A dataset of over 126 currencies and 1175 actively traded currency pairs was taken from January 2, 2025. The data was sourced from Polygon.io and aggregated by minutes, where currency pairs were recorded based on transactions that occurred.

TitanQ found arbitrage opportunities in every one of the minute increments recorded.

The below graphs represent the minute-by-minute arbitrage opportunities found assuming transaction fees of 0.08 and 0.2 bps respectively. However, the formulation didn’t account for latency or currency restrictions, which could have an impact on the profitability of these trades in real-world conditions.

Try It Yourself: Interactive Example

An interactive example is available on the TitanQ Examples Github. It includes an option to load a full forex dataset for a chosen day from Polygon.io, demonstrating TitanQ’s ability for discovering arbitrage opportunities in a matter of seconds. The example also contains smaller instances with 6 and 25 currencies.

In the 6-currency example, TitanQ finds an arbitrage opportunity in just 0.3 seconds with a profit of approximately 0.0113%.

From the 25 currencies example generated from February 17, 2025, TitanQ is able to find a solution that garners a profit of 18.44% in just 2 seconds*:

Take the above example. With up to two directed exchange rates between each currency pair, that’s up to 600 possible exchanges and an extremely large number of possible cycles.

In just 2 seconds, TitanQ is not only able to find multiple cycles that generate profit within the complex graph, but one with a notable profit margin.

*Many of the arbitrage opportunities detected by TitanQ are not executable in practice due to foreign exchange restrictions. While these solutions may not always be feasible in real-world markets, it still remains impressive that opportunities can be discovered across a wide set of currencies.

How Do We Put This Into Practice?

Of course, real-life arbitrage is limited by transaction costs, commissions, foreign exchange controls, and additional fees. There are restrictions on lot size (amount traded) due to liquidity constraints, and multiple trades can take place at once.

Edge weights must be adjusted to account for these factors, and cycles with higher risk, ie including more volatile exchanges, would be penalized accordingly. Some risk attribute dij would then be assigned to each edge (i, j) and a penalty term can be added to the objective function:

One way to measure risk is how much an exchange rate changes before the arbitrage detection is carried out. Longer cycles can also be penalized since longer chains of exchanges introduce more risk to the problem.

Thus, keeping the above in mind, the objective function can be reformulated as follows [5]:

Where M1 and M2 are constants impacting risk aversion.

The problem can then be extended to select the optimal combination of cycles so that total profit is maximized, while upholding lot size constraints for each trade. The formulation is flexible and can be easily modified for a wide range of your use cases.

By incorporating risk factors and more flexible formulations, TitanQ is a powerful tool that can be used to solve real-life complex problems.

Its speed and capabilities for finding quality solutions to difficult, large-scale problems opens a door of possibilities in not just financial trading — but in supply chains, energy markets, and beyond.

References

1.     Fernando, J. (2023, December 14). Arbitrage: How Arbitraging Works in Investing, With Examples. Investopedia. https://www.investopedia.com/terms/a/arbitrage.asp

2.     CFI Team. (2023, December 7). High-Frequency Trading (HFT). Corporate Finance Institute. https://corporatefinanceinstitute.com/resources/equities/high-frequency-trading-hft/

3.     Montevirgen, K. (2025, February 21). Comparative advantage. Encyclopedia Britannica. https://www.britannica.com/money/comparative-advantage

4.     Energy Arbitrage. gridX. (2024, October 29). https://www.gridx.ai/knowledge/what-is-energy-arbitrage 

5.     Rosenberg, G. (2016). Finding optimal arbitrage opportunities using a quantum annealer [White paper]. 1QBit. http://1qbit.com/files/white-papers/1QBit-White-Paper-%E2%80%93-Finding-Optimal-Arbitrage-Opportunities-Using-a-Quantum-Annealer.pdf

About the Authors

Rebecca He

Rebecca is a Mathematical Algorithms Developer on the Algorithms team at InfinityQ Technology, on her 4-month co-operative term from the University of Waterloo.

She is currently pursuing an undergraduate degree in Computational Mathematics.

Before InfinityQ, she worked as an Energy Performance Analyst where she performed data analysis for energy saving initiatives in buildings across Canada.

Brian Mao, MMath

Brian is Head of Algorithms at InfinityQ Technology, with a background in both mechanical engineering and applied mathematics.

Prior to InfinityQ, he was the Path Planning and Controls Lead at MIT Driverless where he led multiple sub-teams to program a race car to drive fully autonomously at over 240 km/h.

He also worked at Apple Inc. under the Metal Tooling team where he developed an internal iOS app and created simulations of various manufacturing processes.

Brian continues to pursue the intersection between engineering and mathematics through finding solutions to many different mathematical optimization problems at InfinityQ.