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

Technical Summary: A Quantum Unstructured Search Algorithm for Discrete Optimisation

Problem Statement
The paper addresses the challenge of solving discrete optimisation problems, specifically combinatorial optimisation, where variables are binary and derivatives cannot be defined. While gradient-based methods are effective for continuous variables, they fail in discrete spaces, which are often NP-hard. Existing quantum approaches, such as the Quadratic Unconstrained Binary Optimisation (QUBO) framework, are limited to objective functions containing only first and second-order terms. Furthermore, many current quantum optimisation algorithms (e.g., Variational Quantum Algorithms) rely on hybrid classical-quantum loops that may suffer from noise or require deep circuits. The authors propose a method to find the extrema or roots of general discrete functions, $f(x)$, which may contain higher-order terms beyond the quadratic limit of QUBO.

Methodology: The QSERA Algorithm
The authors introduce the Quantum Search for Extrema and Roots Algorithm (QSERA), a member of the Quantum Search Algorithm (QSA) family based on Grover's algorithm. The methodology proceeds in two primary steps:

1. Oracle Construction ($f(x) \to u(z)$):
   The first step involves mapping the condition of finding an extremum (or root) $f(x^*) \approx f^*$ to an unstructured search problem for a binary string $z^*$.

   • Rescaling: The objective function $f(x)$ is rescaled to a function $g(x) \in [0, 1]$. For maximisation, $g(x) = (f(x) - f_{min}) / (f_{max} - f_{min})$; for minimisation, $g(x) = (f_{max} - f(x)) / (f_{max} - f_{min})$; and for root finding, a specific transformation is applied. This requires a priori knowledge or estimates of the global minimum ($f_{min}$) and maximum ($f_{max}$).
   • Amplification: To create a binary oracle $u(z)$ where $u(z^*) = 1$ and $u(z \neq z^*) = 0$, the function $g(x)$ is raised to a large power $n$ (i.e., $u_n(z) \equiv g(x)^n$). As $n \to \infty$, $u_n(z)$ approaches the ideal oracle.
   • Generalization: The paper notes that $f(x)$ can be a general polynomial with terms up to order $K$ (Eq. 10), allowing for objective functions more complex than the standard QUBO form.
   • Gate Implementation: The authors derive the quantum circuit for the oracle. They define self-adjoint operators $B_k$ corresponding to binary variables and construct a unitary operator $G$ such that $G|z\rangle = g(x)|z\rangle$. The oracle operator $Q^*$ is then defined as $e^{i\pi G^n}$. This is decomposed into a product of unitary operators $Q^*_j$ for each order of terms (zeroth, first, second, etc.), implemented using ancilla qubits and phase shift gates.

2. Search Execution:
   Once the oracle $Q^*$ is constructed, the algorithm employs Grover's diffusion operator ($Q_+$) and the oracle ($Q^*$) in an iterative loop. The state is initialized in a uniform superposition, and the operator $(Q_+ Q^*)$ is applied $m_{opt} \approx (\pi\sqrt{N} - 2)/4$ times to amplify the amplitude of the target state $|z^*\rangle$.

Key Contributions

• Generalization beyond QUBO: Unlike many quantum optimisation methods restricted to quadratic forms, QSERA can handle objective functions with higher-order terms (cubic, quartic, etc.), making it applicable to a broader class of combinatorial problems.
• Explicit Circuit Construction: The paper provides a detailed mathematical derivation for constructing the quantum oracle gates for arbitrary polynomial orders, including the recursive calculation of coefficients required for the circuit parameters.
• Handling Approximate Bounds: The authors analyze the scenario where $f_{min}$ and $f_{max}$ are not known exactly. They demonstrate that while the algorithm can still function with estimates, the probability of finding the exact optimum depends on the choice of the power parameter $n$. If $n$ is too large, the oracle signal may vanish; if too small, the signal is not distinct enough. An optimal $n$ exists to balance these factors.

Results: Portfolio Optimisation Case Study
The authors validate QSERA using a portfolio optimisation problem with $N_a = 4$ assets, resulting in $N=16$ possible portfolios.

• Setup: The goal was to find a portfolio of 2 assets that minimises the distance to a benchmark return and volatility. The objective function included terms up to the fourth order.
• Implementation: A quantum circuit was assembled using 4 qubits for the portfolio states, 2 ancilla qubits for AND operations, and 1 ancilla for phase tracking.
• Performance:
  • With the optimal number of Grover iterations ($m_{opt} = 2$) and a carefully chosen power $n \approx 24$, the algorithm successfully identified the optimal portfolio (state $|1001\rangle$) with the highest probability.
  • The second-best portfolio ($|0101\rangle$) also showed a relatively high probability, reflecting the fact that the algorithm found the solution closest to the estimated bounds.
  • The study confirmed that if $f_{min}$ and $f_{max}$ are estimated rather than exact, the probability of measuring the true optimum is less than 1, necessitating multiple "shots" (repeated executions) to distinguish the true optimum from near-optimal solutions.
  • The relationship between the power $n$ and success probability was visualised, showing a peak probability for intermediate $n$ values, with performance degrading if $n$ is too large (signal suppression) or too small (insufficient discrimination).

Significance and Claims
The paper claims that QSERA offers a quadratic speed-up ($O(\sqrt{N})$) over classical brute-force search for finding extrema or roots of discrete functions. Its primary significance lies in its ability to:

1. Solve optimisation problems with higher-order objective functions that are incompatible with standard QUBO formulations.
2. Operate without the need for hybrid classical-quantum parameter optimisation loops (unlike VQAs), relying instead on a single-shot quantum execution (though multiple shots may be needed for statistical confidence if bounds are approximate).
3. Potentially address "noisy" or steep-gradient continuous functions (after discretisation) where gradient-based methods might fail, although the authors note that structured search is generally more efficient for continuous variables.

The authors conclude that while the algorithm requires knowledge of function bounds for guaranteed success, it remains a robust tool for discrete optimisation, particularly when the objective function structure exceeds the capabilities of current QUBO-based approaches.