A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation

Titos Matsakos, Adrian Lomas · 2025

Read A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation by Titos Matsakos, Adrian Lomas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-14645.txt.

Introduction

Titos Matsakos and Adrian Lomas design a quantum search method for picking the best option from a discrete set, in a 2025 paper. Many hard tasks, from scheduling to finance, ask for the input that makes a function hit its peak or its zero. Classic search must test options one by one, which grows costly fast.

Their algorithm first recasts the goal as a yes-no oracle that flags only the winning input. Grover’s quantum search then finds the flagged input with a quadratic speed-up over classic search. The cost of building the oracle sets the accuracy and overall gain. As a worked case, they apply the method to portfolio choice, picking a mix of assets. The paper maps where the quantum edge holds and where it fades.

Catalog record

CREATORTitos Matsakos, Adrian Lomas
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-14645

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation Titos Matsakos, Adrian Lomas Abstract We propose a quantum unstructured search algorithm to find the extrema or roots of discrete functions, f ⁡ ( 𝐱 ) f(\mathbf{x}) , such as the objective functions in combinatorial and other discrete optimisation problems. The first step of the Quantum Search for Extrema and Roots Algorithm (QSERA) is to translate conditions of the form f ⁡ ( 𝐱 ∗ ) ≃ f ∗ f(\mathbf{x}_{*})\simeq f_{*} , where f ∗ f_{*} is the extremum or zero, to an unstructured search problem for 𝐱 ∗ \mathbf{x}_{*} . This is achieved by mapping f ⁡ ( 𝐱 ) f(\mathbf{x}) to a function u ⁡ ( z ) u(z) to create a quantum oracle, such that u ⁡ ( z ∗ ) = 1 u(z_{*})=1 and u ⁡ ( z ≠ z ∗ ) = 0 u(z\neq z_{*})=0 . The next step is to employ Grover’s algorithm to find z ∗ z_{*} , which offers a quadratic speed-up over classical algorithms. The number of operations needed to map f ⁡ ( 𝐱 ) f(\mathbf{x}) to u ⁡ ( z ) u(z) determines the accuracy of the result and the circuit depth. We describe the implementation of QSERA by assembling a quantum circuit for portfolio optimisation, which can be formulated as a combinatorial problem. QSERA can handle objective functions with higher order terms than the commonly-used Quadratic Unconstrained Binary Optimisation (QUBO) framework. Moreover, while QSERA requires some a priori knowledge of the extrema of f ⁡ ( 𝐱 ) f(\mathbf{x}) , it can still find approximate solutions even if the conditions are not exactly satisfied. 1 Introduction 1.1 Quantum optimisation Quantum computing has several applications in finance [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , for reviews, see] . Two of the most promising areas are Monte Carlo simulations (e.g. derivative pricing [ 10 , 11 , 12 , 13 , 14 , 15 , 16 ] and risk management [ 17 , 18 , 19 , 20 , 21 , 22 ] ) and optimisation problems (e.g. portfolio optimisation [ 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 ] and transaction settlement optimisation [ 37 ] ). Optimisation problems are prevalent across scientific fields and they are also at the core of most machine learning models. When the objective function depends on continuous variables, gradient descent algorithms are among the commonly-used approaches. Two of the challenges using such algorithms are the presence of constraints and the convergence to a local extremum rather than the global one. These algorithms, however, are not applicable when the variables are binary and derivatives cannot be defined, as in the case of combinatorial optimisation; these are NP-hard problems even without constraints [see 5 , 7 , for reviews] . Many such problems can be formulated using the Quadratic Unconstrained Binary Optimisation (QUBO) framework or the equivalent Ising model, both of which model the individual contribution of each variable (first order terms) as well as their pair-wise interactions (second order terms). Constraints can be included as two possible types: either as “soft”, which adds terms to the objective function but cannot guarantee they are exactly satisfied, or as “hard”, which represent additional (in)equalities [ 31 ] . Depending on the form of the objective function and potential constraints, there are several families of quantum optimisation algorithms available, such as Quantum Adiabatic Algorithms (QAA) [ 38 , e.g.] , Variational Quantum Algorithms (VQAs) [ 39 , 40 , e.g.] , Quantum Linear System Algorithms (QLSAs) [ 41 , 42 , e.g.] , and Quantum Search Algorithms (QSA) [ 43 , 44 , 45 , e.g.] (see [ 46 ] for a review of quantum optimisation). In QAA, the objective function is represented by a Hamiltonian, \mathcal{H}_{\mathrm{c}} , and its minimum by the corresponding ground state. The quantum computer is initialised in the known ground state of another Hamiltonian, \mathcal{H}_{0} , which is then evolved towards \mathcal{H}_{\mathrm{c}} slowly enough such that the system remains at the ground state. Measuring the final state returns the minimum value of the objective function, see App. A.1 . In VQAs, on the other hand, the values of the objective function are represented by parametrised states. Such algorithms can be implemented in hybrid systems where: i) a parametrised state is initialised and measured in a quantum computer, ii) a classical computer processes the output and updates the state initialisation parameters such that the next iteration gets closer to the optimal value, and iii) these steps are repeated until convergence. VQAs are promising for near-term quantum applications because splitting out the parameter optimisation steps (classical computation) from the estimation of the objective function (quantum computation) keeps the quantum circuit depth shallow, thus mitigating the effects of noise. Among VQAs is the Variational Quantum Eigensolver (VQE) [ 39 ] , which searches for the eigenstate that corresponds to the optimum of the objective function (see App. A.2 ), and the Quantum Approximate Optimisation Algorithm (QAOA) [ 40 ] , whose quantum operators resemble QAA but which are parametrised such that the ground state can be found with a variational approach (see App. A.3 and [ 47 ] for a recent review). QSAs are based on Grover’s algorithm — hereafter Quantum Unstructured Search Algorithm (QUSA) — which finds the desired state by flagging it with a quantum oracle and amplifying its amplitude [ 48 ] . The corresponding optimisation algorithms, the family of Grover Adaptive Search (GAS) algorithms, are based on the following steps: i) set a threshold value, ii) use an oracle to identify all states less/greater than the threshold value, iii) amplify the amplitude of these states, iv) update the threshold value from one of them, and iv) repeat the steps until the optimum is found [ 43 , 44 , 45 ] (see also [ 49 , 50 ] for some recent extensions). QSERA, which is described in the next section, belongs to the QSA family but is not a GAS algorithm. 1.2 Portfolio optimisation Consider a pool of N_{\mathrm{a}} assets, with the annual expected return and volatility of asset i denoted with \mu_{i} and \sigma_{i} , respectively. Suppose that we have an amount v_{\mathrm{p}} to invest to construct a portfolio of N_{\mathrm{p}}\leq N_{\mathrm{a}} assets, with v_{i} the investment in asset i . The portfolio expected return, \mu_{\mathrm{p}} , and volatility, \sigma_{\mathrm{p}} , are: \displaystyle\mu_{\mathrm{p}} \displaystyle=\sum_{i=0}^{N_{\mathrm{a}}-1}\frac{v_{i}}{v_{\mathrm{p}}}\mu_{i}\,, (1) \displaystyle\sigma_{\mathrm{p}}^{2} \displaystyle=\sum_{i_{1}=0}^{N_{\mathrm{a}}-1}\sum_{i_{2}=0}^{N_{\mathrm{a}}-1}\frac{v_{i_{1}}}{v_{\mathrm{p}}}\frac{v_{i_{2}}}{v_{\mathrm{p}}}\sigma_{i_{1}}\sigma_{i_{2}}\rho_{i_{1}i_{2}}\,, (2) where \sum_{i}v_{i}=v_{\mathrm{p}} . Limiting the pool of assets to publicly-listed equities and bonds, the number of available assets is on the order of N_{\mathrm{a}}\sim 10^{5} . Portfolio optimisation [ 51 ] aims to find the optimal allocation, i.e. the values of the continuous variables v_{i} that optimise an objective function under the constraint \sum_{i}v_{i}=v_{\mathrm{p}} ; or, more generally, \sum_{i}v_{i}\leq v_{\mathrm{p}} . This is achieved either by setting a target \mu_{\mathrm{p}} and finding the allocation that minimises \sigma_{\mathrm{p}}^{2} , or by setting a target \sigma_{\mathrm{p}}^{2} — representing the risk appetite of the investor — and maximising \mu_{\mathrm{p}} .

Read the complete text