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.
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.
Currency arbitrage leverages price discrepancies in currency exchange rates across different currency pairs to gain risk-free profits. It involves multiple trading, where short-lived price discrepancies require real-time, high-speed processing of vast solution space, posing challenges for classical computing. In this work, we formulate an enhanced mathematical model for the currency arbitrage problem by adding simple cycle preservation constraints, which guarantee trading cycle validity and eliminate redundant or infeasible substructures. To solve this model, we use and benchmark various solvers, including Quantum Annealing (QA), gate-based quantum approaches such as Variational Quantum Algorithm with Adaptive Cost Encoding (ACE), as well as classical solvers such as Gurobi and classical meta heuristics such as Tabu Search (TS). We propose a classical multi-bit swap post-processing to improve the solution generated by ACE. Using real-world currency exchange data, we compare these methods in terms of both arbitrage profit and execution time, the two key performance metrics. Our results give insight into the current capabilities and limitations of quantum methods for real-time financial use cases.
Combinatorial problems pose significant challenges, especially for large-scale instances. A promising approach to addressing these challenges involves quadratic unconstrained binary optimization (QUBO) models, a key framework in quantum computing. QUBO formulations require tailored approaches owing to their unique characteristics and the hardware constraints of quantum systems. This paper focuses on the QUBO formulations of the Hamiltonian cycle problem (HCP). We analyse three QUBO formulations for the HCP, including two inspired by Lagrangian relaxation techniques, where penalties may result in negative costs for certain solutions but are balanced within the model. A preprocessing methodology is also introduced. To evaluate these models, we employ D-Wave quantum annealers, which feature a fixed qubit topology and impose strict resource constraints. The mapping of QUBOs on to this architecture highlights the importance of efficient model design. Through experimental studies, we analyse the performance of the proposed QUBOs with and without preprocessing. This article is part of the theme issue 'Quantum theory and topology in models of decision making (Part 2)'.
Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in t|ket$\rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.
We test whether quantum-inspired optimization, specifically Quadratic Unconstrained Binary Optimization (QUBO) solved via simulated annealing, can improve implementable portfolio performance compared to classical baselines when realistic frictions are included. Our experimental design uses daily returns from the Center for Research in Security Prices (CRSP) for S&P500 constituents spanning 2014–2025, with monthly rebalancing, explicit transaction costs, and turnover accounting. We compare QUBO portfolios against equal-weight and convex mean–variance portfolios across multiple universe sizes (20, 50, 67 assets), lookback windows, and transaction-cost levels. Statistical significance is assessed via paired moving-block bootstrap on out-of-sample net returns. A hyperparameter sweep over encoding depth, penalty coefficients, and turnover reveals 19 of 81 QUBO configurations beat the equal-weight baseline, with the best achieving a Sharpe of 1.59 versus 1.42. However, under a fair walk forward model-selection protocol that eliminates look-ahead bias, the QUBO strategy does not achieve statistically significant superiority over either classical benchmark (∆Sharpe vs. equal weight: −0.13, 95% CI [−0.46,0.16]; vs. mean–variance: −0.29, 95% CI [−0.63,0.06]). Excessive turnover (averaging ∼1.0 per rebalance) is identified as the primary bottleneck. We conclude that current QUBO formulations with simulated annealing do not yet deliver a robust, implementable edge over well-tuned convex optimizers, though the framework remains a promising research direction as quantum hardware and hybrid solvers mature.