1
$\begingroup$

I have some combinatorial optimization problems which I would like to analyze using QAOA. These problems are coming from various applications in scientific computing such as solving PDEs. Some of these problems can be phrased as combinatorial optimization problems - in particular graph traversal problems - based on recent results in the research literature. The idea is to find the optimal path with the least cost.

What's the cost? The classical loss function is continuous. For instance, the loss function could be a least-squares loss function. Or a loss function given by some integrals and derivatives if we have a variational formulation of a PDE.

How do I even convert this loss function to a cost function of Boolean variables so I can convert it to a cost function for QUBO like problems? I am stumped. Are there any resources in the literature?

Improve this question
$\endgroup$
4
  • $\begingroup$ Try this paper: arxiv.org/abs/1302.5843 $\endgroup$
    – Martin Vesely
    May 3 at 16:54
  • $\begingroup$ @MartinVesely I've seen this paper. Not sure if it helps directly since it only deals with converting already combinatorial (binary, discrete, integer etc.) problems into Ising type problems. $\endgroup$
    – user82261
    May 3 at 18:16
  • $\begingroup$ You can easily binarize continuous variables: $w =\sum x_k 2^k$. However, based on number of bits employed, you naturally impose upper bound on the variable $w$. Moreover, even though the original problem was efficiently solvable, the binarized one is always in NP. But, provided that quantum computers could bring about exponential speed up for binary optimization (this is hypothesis), this no longer matters. $\endgroup$
    – Martin Vesely
    May 3 at 20:55
  • $\begingroup$ Please add the QUBO tag $\endgroup$
    – user1271772
    May 12 at 15:16

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.

Browse other questions tagged or ask your own question.