1
$\begingroup$

I'm going through an article with title "Solving constrained quadratic binary problems via quantum adiabatic evolution" (reference 1). And there are several points confusing me a lot.

This article is aimed to solve the CBQP (constrained binary quadratic programming) with the following format.

\begin{align} &\min &x^{T}Qx \cr &\text{subject to} &Ax\leq b \end{align} and $x\in \lbrace0,1\rbrace^{n}$, where $Q\in Z^{n\times n}$ and $A\in Z^{m\times n}$. Let's call this optimization problem the problem $P$.

The outline is like this. Suppose there is a UBQP (Unconstrained binary quadratic programming) oracle, and with the successive application of LP(linear programming), the lagrangian dual of $P$ (or lower bound of $P$ can be provided) can be solved. And then with the branch-bound-approach, the problem $P$ can be solved.

I can understand almost of it until the section 5 counting the solution density on page 9. I'm not exactly sure how the branch-bound process is combined with the optimization process to finally tackle this problem. Could anyone point a direction or share some thoughts? Any comments would be greatly appreciated.

References

  1. Ronagh, P., Woods, B., & Iranmanesh, E. (2015). Solving constrained quadratic binary problems via quantum adiabatic evolution. arXiv preprint:1509.05001.
$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.