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
Sep 9, 2026

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

Quadratic Unconstrained Binary Optimization (QUBO) is a central formulation for combinatorial optimization and has gained increasing attention due to its compatibility with quantum, hybrid quantum-classical, and quantum-inspired solvers. However, translating natural-language problem descriptions into correct QUBO formulations remains difficult, requiring the identification of binary variables, constraints, objective functions, penalty terms, and suitable penalty weights. This process is time-consuming and often demands substantial domain expertise. To address this challenge, we propose an end-to-end multi-agent framework that automatically generates QUBO formulations from natural-language problem descriptions, supported by structured or unstructured test cases. To evaluate its performance, We also introduce QUBOBench, a benchmark containing 100 combinatorial optimization problems across 12 application domains, curated from peer-reviewed literature, competitions, and canonical NP-hard problems. Experimental results show that our framework achieves 68% accuracy on QUBOBench, outperforming a direct single-call baseline by 22%. Further analysis identifies iterative self-repair as the most important component contributing to improved performance. The data and code are open-sourced at https://quitttcat.github.io/QuantumQUBOAgent.

Niloy Kumar Mondal, Md Rizwan Parvez

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

Multi-Agent LLM SystemsLarge Language Model-Guided OptimizationQuadratic Unconstrained Binary OptimizationNatural Language to Optimization Modeling
AskPDF
Aug 6, 2026

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

QAOA training repeatedly queries an objective and all shared gradients, making exact evaluation a feasibility bottleneck even when QUBO terms have bounded causal cones. Building on established causal-cone restriction and adjoint differentiation, LC-Implicit-QAOA profiles cone structure and induced-edge counts before local-amplitude and named-workspace allocation, then jointly selects equal-size microbatches and checkpoint schedules under a named active-evaluator workspace budget. "Implicit" means omitting both global state and global cost table, not implicit differentiation; infeasible requests are rejected before those allocations. An independently implemented complex128/float64 dense adjoint agrees with LC over 1,800 graph-angle comparisons, with a worst relative gradient error of 1.56 x 10^-13. LC completes all 104 target requests in a p=2 bounded-cone grid; under a prespecified n <= 24 validation cap, the matched state-plus-cost reference is executed for 28 requests and deliberately not run on 76. Across 80 budgeted requests, measured allocated evaluator memory stays within budget, reaching at most 0.797 of it. On 3-regular n=512, p=2, the adjoint reaches the same finite-budget endpoint in 101 objective-equivalent calls and 189 s, versus 909 calls and 1,565 s for central differences. LC targets fixed-depth one- and two-local diagonal QUBO costs with a transverse-field mixer; it provides neither global states, sampling, nor a hardware-independent fastest-backend rule.

Chih-Chung Hsu

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

Quadratic Unconstrained Binary OptimizationVariational Quantum CircuitsQuantum Approximate Optimization Algorithm
AskPDF
Sep 4, 2026

Task-Aware QUBO Allocation for Mixed-Precision Quantization

Mixed-precision quantization requires discrete allocation of weight and activation bit-widths, followed by recovery of the selected network. We develop a task-aware quadratic unconstrained binary optimization (QUBO) surrogate with separate weight and activation profiles, a bit-operation (BOP) cost, and selected structural priors. QUBO provides a network-wide allocation that can be refined through direct validation-based PROTES search. On a compact NAFBlock-based denoiser, the refined route achieves 37.192 dB after LSQ+ at 4.035% routed-layer BOPs, versus 37.092 dB at 4.101% for a HAWQ-style baseline. The repeated-search primary experiment shows that LSQ+ largely closes the quality gap between QUBO allocation and expensive direct refinement. An additional restoration architecture retains a larger recovered gain, indicating that refinement's value depends on architecture and recovery. We evaluate quality, achieved cost, routing stability and optimization expense together. Deployment measurements characterize a fake-quantized floating-point implementation; BOP reductions describe analytical allocation savings.

Osama Orabi, Artur Zagitov, Hadi Salloum +2

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

Mixed-Precision QuantizationCost-Aware InferenceQuadratic Unconstrained Binary Optimization
AskPDF