quant-phAug 16, 2026

Resource-Efficient QUBO Formulation for Anchored Currency Arbitrage

Authors: Eric A. F. Reinhardt, Adam J. Hauser

Organizations: Department of Physics and Astronomy University of Alabama, Tuscaloosa, AL 35487, USA

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: Extreme dummy exchange rate matrix with profit inserted. Green indicates an exchange rate was perturbed upward and orange indicates an exchange rate was perturbed downward.
Figure 2: Decomposition of the connectivity graph of the QUBO for the example in Fig. 1 : column-clique couplings (a) and adjacent-step couplings (b).
Figure 3: Decomposition of the connectivity graph (continued): row-uniqueness couplings (a) and the full coupling graph (b).
EncodingLogical QubitsMaximal Connectivity
Mazzei et al.NKNK3N−13N-1
[ 12 ]
Deshpande–Das–MuellerN2N^{2}2N−42N-4
[ 11 ]
Roy et al.N(K+1)N(K+1)3N+K−33N+K-3
[ 13 ]
Table 1: Logical qubit count and maximal connectivity of the single most-connected qubit for existing CA QUBO solutions in the literature.
Figure 4: Logical qubit count (a) and physical qubit count after minor-embedding onto the Pegasus-16 graph (b) as a function of the number of currencies, for a maximum cycle length of six.
Figure 5: Logical qubit count (a) and physical qubit count after minor-embedding onto the Pegasus-16 graph (b) as a function of maximum cycle length, for 14 currencies.
Figure 6: Simulated-annealing hyperparameter sweeps for ten currencies with a maximum cycle length of six: profit vs annealing steps (a) and profit vs number of reads (b).
Figure 7: Profit vs monetary noise injected into the balanced currency matrix with ten currencies and a maximum cycle length of 6.
Figure 8: Simulated-annealing profit compared to the exact optimum as a function of the number of currencies, with 1280 reads (a) and 10240 reads (b).
Figure 9: Compute wall time for simulated annealing and the exact Held–Karp baseline, on the same CPU, as a function of the number of currencies, with 1280 reads (a) and 10240 reads (b).
Figure 10: Wall time (a) and profit (b) as a function of maximum cycle length for 14 currencies with 10240 reads.
Figure 11: Effect of the length-penalty coefficient γ\gamma on the found cycle length, colored by the discrepancy from the optimal cycle length (a) and by the ratio of found to maximum raw profit (b).
Figure 12: Gap in the fee-adjusted score between simulated annealing and the exact solution as a function of the length-penalty coefficient γ\gamma and the maximum cycle length. The score is the objective both solvers optimize, so the gap is nonnegative by construction.
EncodingVariables ↓\downarrowRuns ↓\downarrowScore gap ↓\downarrowSampler time (s) ↓\downarrowPer-run time (s) ↓\downarrow
Ours (N−1)(K−1)(N{-}1)(K{-}1)451010 anchors0 (exact)2.620.26
Ours - Worst of 104513.3×10−53.3\times 10^{-5}0.260.26
Roy et al. [ 13 ]7044 lengths3.8×10−63.8\times 10^{-6}0.870.22
1QBit node-based [ 14 ]6044 lengths8.0×10−68.0\times 10^{-6}0.730.18
Mazzei et al. [ 12 ]7011.4×10−51.4\times 10^{-5}0.160.16
Deshpande et al. [ 11 ]9013.7×10−53.7\times 10^{-5}0.530.53
Table 2: All encodings of Table 1 sampled by the same CPU simulated annealer at matched per-run settings (1280 reads, 160 sweeps) on the ten-currency, K=6K=6 benchmark instance with gauge-fixed inputs and validated penalty weights. The gap is measured in the fee-adjusted log-return against the exact optimum of 7.106×10−47.106\times 10^{-4} ; sampler time is the total sampling wall time over all runs for that encoding.
Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

CurrenciesLogical qubitsPhysical qubits
62577
730104
835147
940177
1045230
1150323
Appendix
Table 3: Data plotted in Figs. 4(a) and 4(b) : logical and Pegasus-16-embedded physical qubit counts vs number of currencies at a maximum cycle length of six.
Max lengthLogical qubitsPhysical qubitsMax chain
326975
4391927
5522867
66546111
77863112
89180614
Appendix
Table 4: Data plotted in Figs. 5(a) and 5(b) : logical and Pegasus-16-embedded physical qubit counts vs maximum cycle length for 14 currencies, with the maximum embedding chain length.
SweepsExact profitSimulated-anneal profit
107.11×10−47.11\times 10^{-4}6.74×10−46.74\times 10^{-4}
207.11×10−47.11\times 10^{-4}7.11×10−47.11\times 10^{-4}
407.11×10−47.11\times 10^{-4}7.07×10−47.07\times 10^{-4}
807.11×10−47.11\times 10^{-4}7.03×10−47.03\times 10^{-4}
1607.11×10−47.11\times 10^{-4}7.11×10−47.11\times 10^{-4}
3207.11×10−47.11\times 10^{-4}7.11×10−47.11\times 10^{-4}
Appendix
Table 5: Data plotted in Fig. 6(a) : profit vs number of simulated-anneal sweeps for ten currencies and a maximum cycle length of six.
ReadsExact profitSimulated-anneal profit
107.11×10−47.11\times 10^{-4}4.06×10−44.06\times 10^{-4}
207.11×10−47.11\times 10^{-4}4.46×10−44.46\times 10^{-4}
407.11×10−47.11\times 10^{-4}6.74×10−46.74\times 10^{-4}
807.11×10−47.11\times 10^{-4}6.74×10−46.74\times 10^{-4}
1607.11×10−47.11\times 10^{-4}6.74×10−46.74\times 10^{-4}
3207.11×10−47.11\times 10^{-4}6.74×10−46.74\times 10^{-4}
Appendix
Table 6: Data plotted in Fig. 6(b) : profit vs number of reads for ten currencies and a maximum cycle length of six.
NoiseExact profitSimulated-anneal profit
1.00×10−51.00\times 10^{-5}7.11×10−57.11\times 10^{-5}7.11×10−57.11\times 10^{-5}
1.00×10−41.00\times 10^{-4}7.11×10−47.11\times 10^{-4}7.11×10−47.11\times 10^{-4}
1.00×10−31.00\times 10^{-3}7.13×10−37.13\times 10^{-3}7.05×10−37.05\times 10^{-3}
1.00×10−21.00\times 10^{-2}7.37×10−27.37\times 10^{-2}7.32×10−27.32\times 10^{-2}
1.00×10−11.00\times 10^{-1}1.04×1001.04\times 10^{0}1.04×1001.04\times 10^{0}
Appendix
Table 7: Data plotted in Fig. 7 : profit vs monetary noise for ten currencies and a maximum cycle length of six.
CurrenciesExact profitSimulated-anneal profit
65.80×10−45.80\times 10^{-4}5.80×10−45.80\times 10^{-4}
76.72×10−46.72\times 10^{-4}6.72×10−46.72\times 10^{-4}
85.95×10−45.95\times 10^{-4}5.95×10−45.95\times 10^{-4}
97.93×10−47.93\times 10^{-4}7.93×10−47.93\times 10^{-4}
107.11×10−47.11\times 10^{-4}7.11×10−47.11\times 10^{-4}
118.60×10−48.60\times 10^{-4}8.60×10−48.60\times 10^{-4}
Appendix
Table 8: Data plotted in Fig. 8(a) : profit vs number of currencies with 1280 reads.
CurrenciesExact profitSimulated-anneal profit
65.80×10−45.80\times 10^{-4}5.80×10−45.80\times 10^{-4}
76.72×10−46.72\times 10^{-4}6.72×10−46.72\times 10^{-4}
85.95×10−45.95\times 10^{-4}5.95×10−45.95\times 10^{-4}
97.93×10−47.93\times 10^{-4}7.93×10−47.93\times 10^{-4}
107.11×10−47.11\times 10^{-4}7.11×10−47.11\times 10^{-4}
118.60×10−48.60\times 10^{-4}8.60×10−48.60\times 10^{-4}
Appendix
Table 9: Data plotted in Fig. 8(b) : profit vs number of currencies with 10240 reads.
CurrenciesExact (s)Simulated anneal (s)
60.010.66
70.020.92
80.041.27
90.081.73
100.142.27
110.262.90
Appendix
Table 10: Data plotted in Fig. 9(a) : wall time vs number of currencies with 1280 reads, on the same CPU.
CurrenciesExact (s)Simulated anneal (s)
60.015.12
70.027.40
80.0410.36
90.0714.07
100.1517.52
110.2522.96
Appendix
Table 11: Data plotted in Fig. 9(b) : wall time vs number of currencies with 10240 reads, on the same CPU.
Max lengthExact (s)Simulated anneal (s)Exact profitSimulated-anneal profit
30.0914.004.06×10−44.06\times 10^{-4}4.06×10−44.06\times 10^{-4}
40.1922.846.11×10−46.11\times 10^{-4}6.11×10−46.11\times 10^{-4}
50.4831.468.70×10−48.70\times 10^{-4}8.70×10−48.70\times 10^{-4}
61.0140.318.99×10−48.99\times 10^{-4}8.99×10−48.99\times 10^{-4}
71.9748.419.82×10−49.82\times 10^{-4}8.99×10−48.99\times 10^{-4}
83.1156.271.07×10−31.07\times 10^{-3}9.52×10−49.52\times 10^{-4}
Appendix
Table 12: Data plotted in Figs. 10(a) and 10(b) : wall time and profit vs maximum cycle length for 14 currencies with 10240 reads, on the same CPU.
Max lengthγ\gammaOptimal lengthFound lengthExact profitSimulated-anneal profitScore gap
35.00×10−55.00\times 10^{-5}334.62×10−44.62\times 10^{-4}4.62×10−44.62\times 10^{-4}8.88×10−168.88\times 10^{-16}
31.00×10−41.00\times 10^{-4}334.62×10−44.62\times 10^{-4}4.62×10−44.62\times 10^{-4}8.88×10−168.88\times 10^{-16}
32.00×10−42.00\times 10^{-4}334.62×10−44.62\times 10^{-4}4.62×10−44.62\times 10^{-4}8.88×10−168.88\times 10^{-16}
34.00×10−44.00\times 10^{-4}334.62×10−44.62\times 10^{-4}4.62×10−44.62\times 10^{-4}8.88×10−168.88\times 10^{-16}
45.00×10−55.00\times 10^{-5}446.07×10−46.07\times 10^{-4}6.07×10−46.07\times 10^{-4}8.88×10−168.88\times 10^{-16}
41.00×10−41.00\times 10^{-4}446.07×10−46.07\times 10^{-4}6.07×10−46.07\times 10^{-4}8.88×10−168.88\times 10^{-16}
Appendix
Table 13: Data plotted in Figs. 11(a) , 11(b) , and 12 : found and optimal cycle length, profits, and fee-adjusted score gap for each length penalty γ\gamma and maximum cycle length.
More in this topic

Quadratic Unconstrained Binary Optimization

Quadratic unconstrained binary optimization (QUBO) encodes discrete decisions as binary quadratic objectives for classical and quantum-inspired solvers.

See all 21 papers

Explore similar work

CardsList

  1. QuantumQUBO Agent: Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language

    Sep 9, 2026Niloy Kumar Mondal, Md Rizwan ParvezMulti-Agent LLM SystemsLarge Language Model-Guided Optimization

    Bangladesh University of Engineering and Technology · Qatar Computing Research Institute, HBKU, Doha, Qatar.

  2. LC-Implicit-QAOA: Active-Workspace-Capped Exact Objective-and-Gradient Evaluation for Training over Bounded QUBO Light Cones

    Aug 6, 2026Chih-Chung HsuQuadratic Unconstrained Binary OptimizationVariational Quantum Circuits

    Institute of Smart Industry and Green Energy, National Yang Ming Chiao Tung University, Hsinchu, Taiwan

  3. Task-Aware QUBO Allocation for Mixed-Precision Quantization

    Sep 4, 2026Osama Orabi, Artur Zagitov, Hadi Salloum +2Mixed-Precision QuantizationCost-Aware Inference

    Laboratory of Quantum Computing, Innopolis University, 420500 Innopolis, Russia · Q Deep, Laboratory of Quantum Computing, 420502 Innopolis, Russia · Moscow Independent Research Institute of Artificial Intelligence (MIRAI), 117218 Moscow, Russia +2