1
$\begingroup$

I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic non-linear real-valued function $f:S \to \mathbb{R}$ which takes values on a certain set $S \subseteq \mathbb{Z}^9$. The goal is to find $\theta^* \in \mathbb{Z}^9$ corresponding to the minimum of the function. The total number of possible configuration of the system is high but finite ($\sim10^7$).

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_{ij}x_ix_j+\sum_{i}h_{i}x_i$$

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

How do I 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$ represent in this context? What about my non-analytic function $f$ which has to be minimized? Has anyone attempted this in a similar way and how?

Here https://www.hindawi.com/journals/complexity/2017/8404231/ I found the best formalization of the issue.

Improve this question
$\endgroup$
3
  • $\begingroup$ Cross-posted from physics. $\endgroup$
    – E.P.
    Nov 2, 2017 at 15:49
  • $\begingroup$ What properties does $f$ have? Is it differentiable? Does it have any structure or other properties? How large is $N$? Genetic algorithms aren't the only approach, and aren't necessarily the best (indeed, my sense is that it's rare that they are the best). Anyway, I don't know what your comments about genetic algorithms have to do with your desire to map this onto QUBO; that seems orthogonal. I don't think your question about QUBO is answerable in its current form: without telling us anything about $f$, how are we supposed to tell you how to formulate it as a QUBO instance? $\endgroup$
    – D.W.
    Nov 5, 2017 at 17:32
  • $\begingroup$ Thank you for the additional information. However, I still don't think this question is meaningfully answerable in the absence of any information about the structure of $f$, and you still haven't given us anything useful about the structure of $f$. As it stands $f$ could be an arbitrary function. There is no optimization algorithm that will be effective for arbitrary functions. Instead, we usually need to take advantage of the structure of $f$ somehow. (Also, it's not clear why QUBO would be better than all of the other frameworks for mathematical optimization.) $\endgroup$
    – D.W.
    Nov 7, 2017 at 23:47

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.