QUBO formulation of a discrete-variable Genetic Algorithm optimization problem

Question

I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic real-valued function $f$ depending on a set of parameters $ \theta\in\mathbb{Z}^N$ in a non linear way.

The goal is to find $\theta^* \in \mathbb{Z}^N $ corresponding to the minimum of the function. Because of the properties of $f$, I decided to deal with this problem with a Genetic Algorithm optimization technique.

Now, recent quantum annealing techniques allow to take advantage of quantum effects to solve computationally hard optimization problems. Quantum annealers are designed to minimize Quadratic Unconstrained Binary Optimization (QUBO) Problems, i.e. the cost function is of the form

$F(x)=\sum_{i<j}J_{i,j}x_ix_j+\sum_i h_i x_i$

with $x\in\{0,1\}^n$ and $J_{i,j},h_i\in\mathbb{R}$.

The question is: how to remap my problem into a QUBO problem? I can associate each configuration of my discrete problem into a binary number, but what does the matrix $J$ represents in this context? What about my non function $f$ which has to be minimized? Have you seen before a similar attempt?

Thank you

Marco

Answer 1

The binary encoding trick requires you to actually bound the $N$ parameters. Suppose that $m$ bits suffice for each of the $N$ parameters. Then you have $L=2^{mN}$ bits in your QUBO. Even then, you can't formulate an arbitrary optimization problem in QUBO form:

Since the function $f$ can have specified values at each of $2^{L}$ bit patterns, you can construct a system of $2^{L}$ equations involving $L(L+1)/2$ coefficients in $J$ and $h$. Since this system is overdetermined and can have any right-hand side, there must be functions $f$ that can't be represented in this way.