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?

  • $\begingroup$ Try this paper: arxiv.org/abs/1302.5843 $\endgroup$ Commented May 3, 2023 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
    Commented May 3, 2023 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$ Commented May 3, 2023 at 20:55
  • $\begingroup$ Please add the QUBO tag $\endgroup$ Commented May 12, 2023 at 15:16


Your Answer

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

Browse other questions tagged or ask your own question.