0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.