Source-linked AI summary
Resource-Efficient QUBO Formulation for Anchored Currency Arbitrage
Eric A. F. Reinhardt, Adam J. Hauser
TL;DR
Finding profitable currency-arbitrage cycles is costly and prior QUBO encodings omit realistic anchoring and trading fees. This paper introduces a smaller anchored, fee-aware formulation with coefficient reweighting, and it uniquely recovers the exact fee-adjusted optimum in matched-budget tests.
Problem
Prior currency-arbitrage QUBOs omit fixed starting currencies and per-transaction fees, while optimal-cycle identification remains computationally expensive and analog hardware faces coefficient-scale mismatch.
Method
The paper formulates anchored, fee-aware arbitrage as a QUBO, derives sufficient penalties, and applies exact anchor-gauge reweighting to compress coefficients to the arbitrage scale.
Results
In matched-budget tests, the proposed encoding was the only one to recover the exact fee-adjusted optimum, while using the lowest logical-variable count.
Takeaways & Limitations
The formulation provides a resource-efficient QUBO encoding that incorporates reserve-currency anchoring, trading fees, and unchanged optimal cycles after coefficient reweighting.
Takeaways & Limitations
Reported profit points use single sampler seeds, and the sampler’s random stream depends on its thread count.
Abstract
from arXiv · showhide
Currency arbitrage (CA) involves trading currencies in cycles to exploit discrepancies in market valuations. Quadratic unconstrained binary optimization (QUBO) involves minimizing a quadratic cost (energy) function of binary variables. Previous works have explored the use of QUBO to solve CA problems. We build on these previous works by introducing realistic constraints such as beginning cycles from a held currency and accounting for per-transaction trading fees. We show that this formulation requires fewer logical variables (qubits) than previous QUBO encodings in the literature. We derive provably sufficient penalty weights for its constraint terms. We also introduce an exact anchor-gauge reweighting of the exchange rates that compresses the QUBO coefficient range from the rate scale to the arbitrage scale, addressing the finite analog precision of annealing hardware. We demonstrate the efficacy of this formulation using classical simulated annealing against an exact Held-Karp baseline on the same CPU and show that it can effectively find profitable cycles and account for trading fees. Finally, we benchmark faithful implementations of five prior QUBO encodings at matched sampler budgets and show that the proposed encoding is the only one to recover the exact fee-adjusted optimum.
1 Introduction
Currency-arbitrage cycle search is computationally difficult, motivating QUBO encodings that use annealing to seek optimal solutions. This work introduces an anchored formulation that uses fewer logical variables than prior encodings while more closely matching practical trading constraints.
- Motivation: Currency arbitrage identifies profitable cycles from discrepancies in currency valuations across markets or exchanges.Real-world strategies may use forecasts, valuation latency, or both.
- Computational challenge: Brute-force search scales as O(N^3) for triangular arbitrage and up to O(N!), while Held–Karp scales as O(2^(N−1)N^2) time and O(2^(N−1)N) memory.N denotes the number of currencies considered.
- QUBO framework: In QUBO, a quadratic cost function over binary decision variables is constructed so its global minimum represents the target solution.Annealing algorithms search for this optimum; quantum annealing maps the QUBO to an equivalent Ising Hamiltonian whose ground state encodes the solution.
- Prior QUBO encodings: Prior QUBO representations for currency arbitrage use O(N^2) or O(KN) binary variables.K is the maximum allowed cycle length.
- Contribution: The proposed anchored currency-arbitrage QUBO formulation uses fewer logical variables than prior encodings and offers competitive per-variable connectivity.It is designed to more closely match practical trading constraints.
2 Understanding the Currency Arbitrage Problem
Currency arbitrage seeks profitable trading cycles created by exchange-rate imbalances, whereas balanced rates would return the starting amount minus trading fees. Existing QUBO approaches optimize profitability with different cycle-length objectives, while this paper emphasizes realistic per-transaction fee constraints.
- Currency arbitrage problem: In a perfectly balanced exchange-rate system, arbitrary currency trades returning to the starting currency yield the initial amount minus trading fees.The paper illustrates the problem using a dummy exchange-rate matrix with intentionally shifted rates creating imbalances.
- Prior QUBO approaches: Existing QUBO formulations target maximally profitable cycles either without restricting cycle length or with an upper limit and a reward for shorter cycles.The section also notes that related QUBO currency-arbitrage solutions have been explored in the literature.
- Real-world constraints: This paper addresses a real-world constraint by adding fixed trading fees for each additional transaction.The authors identify per-transaction trading fees as one constraint beyond finding the maximally profitable trading cycle.
3 A QUBO Solution for Currency Arbitrage
The proposed QUBO encodes a nonempty, anchored, contiguous, non-repeating currency cycle while maximizing fee-adjusted log-return under a cycle-length limit. Exact anchor-gauge reweighting compresses coefficient scales, while the encoding uses fewer logical qubits than prior solutions.
- Hamiltonian construction: The Hamiltonian separates into constraint terms Hc and profit terms Hp, enforcing valid cycle structure while optimizing profitability.Hp comprises Hstep1, Hclose, Hcontinue, Htruncate, and Hlen.
- Correctness of the encoding: For sufficiently large Arow, Acol, Acontig, and Astart, ground states encode nonempty, anchored, contiguous, simple cycles.The constraint terms prevent repeated currencies, multiple currencies at one step, detached cycles, and cycles that fail to start at the first step.
- Fee-adjusted objective: Minimizing the feasible Hamiltonian maximizes cycle log-return with a fixed length penalty of γ/α per selected non-start currency.This penalty is equivalent to a fixed per-transaction penalty up to a constant offset from the final return-to-start exchange.
- Correctness of the encoding: Each constraint-violation class admits a local repair move that strictly lowers energy, so infeasible configurations are not local minima under these moves.The repair moves are ordered so each step relies only on violation classes already excluded, supporting annealing behavior.
- Anchor-gauge reweighting: Gauge fixing reduces the largest QUBO coefficient from 25.3 to 1.9 × 10−2 on the ten-currency, K = 6 benchmark instance.The Johnson-style reweighting preserves every closed cycle’s log-return and moves transformed rates to the arbitrage scale.
- Resource requirements: The anchored formulation uses fewer logical qubits than existing literature solutions, while hardware connectivity can exceed that of modern quantum annealers.Prior O(NK) encodings could also replace N with N −1 by anchoring to a fixed start position.
4 Results of Simulated Annealing for Currency Arbitrage
Simulated annealing matches the exact fee-adjusted optimum on small anchored currency-arbitrage instances but requires more reads as the number of currencies grows. Across matched sampler budgets, the proposed encoding uniquely recovers the exact optimum, while prior encodings expose structural limitations.
- Hyperparameter sensitivity: 80–320 steps and at least 1280 reads achieve identical profit to the exact solution for ten currencies with maximum cycle length six.The result also holds for minimal market imbalances; the default monetary noise is 1 × 10^-4.
- Scaling with currencies: For twelve currencies and above, additional reads are required to match the exact optimum.The comparison reports results at 1280 and 10240 reads.
- Runtime comparison: The exact Held–Karp solver is one to two orders of magnitude faster at 1280 reads and two to three orders faster at 10240 reads across the tested currency range.Both methods are evaluated on the same CPU, with annealing time measuring sampler calls summed over anchor runs.
- Scaling with cycle length: At 14 currencies, the exact solver remains one to two orders of magnitude faster for every maximum cycle length up to eleven, while annealed profit ceases to be optimal beyond length five.No runtime crossover is observed in the tested range.
- Comparison with prior encodings: The proposed encoding is the only matched-budget formulation to recover the exact optimal cycle with zero score gap and the fewest logical variables.The benchmark uses 1280 reads and 160 sweeps on the ten-currency, K = 6 instance, whose exact fee-adjusted optimum is 7.106 × 10^-4.
- Structural limitations: Mazzei et al.’s Hamiltonian permits non-adjacent currency revisits, producing closed walks that may repeatedly traverse profitable sub-cycles instead of simple cycles.Such samples must be discarded when the task requires a simple cycle.
5 Discussion and Future Work
The discussion emphasizes that the proposed anchored, fee-aware QUBO is resource-competitive, supports feasible hardware embeddings, and can recover profitable or exact fee-adjusted cycles under tested conditions. It also identifies classical simulated annealing’s limits relative to exact search and proposes extensions to cost-aware shipping-route optimization.
- Contributions: The formulation enforces fixed reserve-currency endpoints, incorporates per-transaction trading fees, uses sufficient constraint penalties, and preserves the optimal cycle under anchor-gauge reweighting.Anchor-gauge reweighting reduces the QUBO coefficient range to the arbitrage scale without changing the optimal cycle.
- Resource requirements: The formulation is competitive in variable count and connectivity, and embedding results suggest hardware tests are feasible for sizes challenging exact enumeration.The discussion specifically considers embedding on the D-Wave Advantage Pegasus-16 graph.
- Numerical evaluation: 10240 reads recovered the exact constrained-cycle optimum through thirteen currencies, with a residual miss at fourteen.Simulated annealing remained accurate at profits of a tenth of a penny per dollar per cycle.
- Numerical evaluation: Classical simulated annealing did not outperform Held–Karp anywhere in the tested range, but generally found profitable solutions with optimal-scale profits.When maximum cycle length grows with the number of currencies, exact search requires O(2N−1N 2) time and exponential memory.
- Trading-fee behavior: Increasing the fee coefficient γ consistently shortened found cycles, with fee-adjusted optima collapsing toward shortest cycles when fees exceeded all available per-edge profits.The annealer’s objective was evaluated against the exact fee-adjusted objective.
- Future work: Future work includes adapting the representation to offline optimization and finding profitable shipping routes while accounting for fuel usage and costs.The proposed shipping-route extension would require minimal model changes.
6 Conclusion
The proposed anchored, fee-aware QUBO formulation uses fewer logical qubits than prior encodings while identifying profitable fee-adjusted cycles, including exact optima in matched-budget tests. Future hardware-annealing studies are motivated by embeddings that fit 17 currencies and maximum cycle length 14 on D-Wave Advantage Pegasus-16.
- 6 Conclusion: The formulation anchors cycles to a fixed start currency, includes fixed trading fees, and uses fewer logical qubits than previous solutions.Its maximal connectivity is competitive with other O(NK) encodings and lower for short maximum cycle lengths.
- 6 Conclusion: At 10240 reads, simulated annealing recovered maximally profitable cycles in every tested instance with up to thirteen currencies and maximum cycle length six.The result covers all tested instances within those size limits.
- 6 Conclusion: In matched-budget tests against five faithful prior QUBO encodings, the proposed encoding alone recovered the exact fee-adjusted optimum, at the lowest logical-variable count.The five prior encodings were individually validated implementations listed in Table 1.
- 6 Conclusion: The trading-fee length-penalty term constrains maximum sequence length when its penalty outweighs potential profit.This behavior was observed as expected in the formulation.
- 6 Conclusion: 17 currencies with maximum cycle length 14 can fit on the D-Wave Advantage Pegasus-16 architecture, motivating future hardware quantum-annealing work.The naive exact-enumeration baseline would check over 59 trillion permutations, while Held–Karp solves the problem in under a minute on one CPU core.
AI Use Statement
The authors used Claude models for simulated review, criticism, spell-checking, grammar editing, coding assistance, debugging, code refactoring, and plot formatting.
- AI Use Statement: Claude Opus 4.8 supported simulated review, criticism, spell-checking, and grammar editing.
- AI Use Statement: Claude Opus 4.6-5.0 assisted with debugging, final code refactoring, and plot formatting.
A Data tables for the figures
This appendix tabulates the numerical data underlying the paper’s figures, using the same conventions as their axes. The tables cover qubit counts, profit, noise and sampling effects, runtime, and penalty-dependent cycle outcomes.
- Qubit counts: Tables 3 and 4 report logical and Pegasus-16-embedded physical qubit counts across currency counts and maximum cycle lengths.Table 3 fixes the maximum cycle length at six; Table 4 uses 14 currencies and includes maximum embedding chain length.
- Profit and sampling: Tables 5–9 tabulate profit against simulated-anneal sweeps, reads, monetary noise, and currency counts under specified sampling budgets.The datasets use ten currencies and maximum cycle length six for Tables 5–7, while Tables 8 and 9 compare 1280 and 10240 reads across currency counts.
- Runtime: Tables 10–12 report same-CPU wall time, with Table 12 also reporting profit as maximum cycle length varies.Tables 10 and 11 use 1280 and 10240 reads, respectively; Table 12 uses 14 currencies and 10240 reads.
- Penalty effects: Table 13 records found and optimal cycle lengths, profits, and fee-adjusted score gaps for each length penalty γ and maximum cycle length.These quantities are plotted in Figs. 11a, 11b, and 12.