optimization problems in R^N (opinion wanted)

[jmsellier]

Hello,

I have been thinking a little bit about qbsolv and I came up with a reasoning which might interest this community. As far as I understood, qbsolv is concerned with problems which unknown is defined over the discrete space {0,1}^N, where N is an integer. In other words the values of a N-dimensional unknown X can have only components which are either 0 or 1.

Now, could we use it qbsolv to deal with problems which are defined over the space R^N? (i.e. defined over the space of N-dimensional real vectors) Personally, I think the answer must be positive, at least for a certain class of problems. In fact, one can always write a real number in base 2. Therefore, there must be a class of optimization problems in R^N which, once rewritten in base 2, coincides with a quadratic (unconstrained) binary optimization problem.

I think it would be interesting to understand what classes of continuum optimization problems could eventually be transformed in a binary problem and, thus, be solved by qbsolv. At that point, one could think of a simple extra layer to add to qbsolv which could automatically transform a continuum problem into a binary problem.

As I find this reasoning quite interesting and, most of all useful, it would be great to hear about your opinion. I hope this, somehow, contribute to this exciting project.

Thanks!

[aidanproy]

Hi Jean,

Thanks for your interest in qbsolv. It's true that any real variable can be written in binary up to a certain precision, allowing a continuous optimization problem to be cast as a discrete one. There are a couple reasons why we haven't focused on that direction. First, continuous optimization techniques like gradient descent are extremely effective - in most cases much more effective than their discrete counterparts. Second, our goal with qbsolv is to take advantage of quantum annealing hardware, and the performance of current quantum annealing hardware degrades as the precision requirements of the problem increase.

That being said, there may be certain classes on continuous optimization problems where translating into discrete variables is effective. If you find a problem that you can solve faster with qbsolv than with a continuous optimization solver, we'd very much like to here about it!

Aidan

[jmsellier]

Hi Aidan,

Thank you for your fast and detailed answer. Now things are clearer to me. Still I'd like to explore this direction and see what one can get. May be there is something interesting to be found out. If I find something, I will keep you updated for sure!

JM

[sabladmin1]

Hi JM,

There is a large class of problems which where only some elements of X are Real and the rest are {0,1}. These are often described as "mixed-integer linear problems", MILP. On classical computing, MILP are challenging but well addressed with commercial grade solvers.

If you are looking into making use of D-wave/qbsolv then I propose you look at solving MILP by combining a traditional quasi-Newton method (to look after the Real valued elements) and D-wave/qbsolv (to look after combinatorial pairs of the {0,1} elements). A high level strategy for doing this is described as an "alternating direction method of multipliers" or proximal algorithm.

Let me know if you need any more details...I am willing to contribute code as well.

Simon

[jmsellier]

Hi Simon,

Many thanks for your very interesting answer! Could you, please, share some link to some review paper on MILPs and "alternating direction method of multipliers"/proximal algorithms? It would be nice to have these links here so that other people can read them too.

If the papers are clear enough I am definitely willing to code these approaches into qbsolv and make my first contribution to this amazing project.

Thanks a lot,

JM

[sabladmin1]

Hi JM

This is a review paper on Proximal Algorithms: https://arxiv.org/pdf/1502.03175v3.pdf ADMM is discussed in section 4.

For MILP there should be lots of material written to be accessible to people with some computer science or operations research background. I don't have any review papers in mind...but any book that introduces linear programming (LP) would likely cover MILP as both have similar a formulation except for the restriction of some variables to integers in the case of MILP.

Simon

[sabladmin1]

As an interesting additional point regarding MILP, this paper from D-wave (https://arxiv.org/pdf/1603.03111v1.pdf) describes how MILP formulation is used in their own system for embedding and keeping the chain-size low (doing this looks like being critical to the realised performance of the hardware).

[jmsellier]

Thanks a lot Simon! These are very interesting papers and I will definitely read them!

JM

[Mark-kraM]

Keep in mind that when modeling a real number (or more likely an integer) that you need at least 2n binary bits to represent the range of numbers from -n to n. Thus - 8 to 8 would require 6 bits and for a better model you would want one bit for every possible number you are considering, but then you need interaction effects between the bits to disallow selecting two possibly conflicting "answers". It gets complicated!

[sabladmin1]

Hi JM, This is an article describing ADMM was used with D-wave: https://arxiv.org/pdf/1704.01605.pdf It also has a very interesting discussion of the performance of Qbsolv relative to D-wave hardware, as well as the commercial Gurobi solver.

[jmsellier]

Hi Simon,

Many thanks for sharing this paper! I read it and found it very interesting. So, it seems that my initial idea wasn't so bad after all.. I am glad that these people from LANL made this preliminary work. It shows a new direction to use a D-Wave machine for a more general class of problems.

The next step, in my opinion, would be to apply this approach to other classes of meaningful/practical problems. Personally, I would be more than happy to do it for the time-dependent simulation of quantum systems (in order to access the excited states of molecules - a problem of huge impact if solved for real-life/practical molecules in the chemistry community). My gut feeling is that a D-Wave machine might have some advantage over a classical computer in this case. After all, the problem would consist of using a quantum machine to simulate a quantum system.

I would do it myself if only I had access to one of these machines.. ;-)

JM

[sabladmin1]

Hi JM, "...I would do it myself if only I had access to one of these machines..."

The point about Qbsolv is to allow you to already start addressing these classes of problems without the D-wave (in its current limits) hardware.

However, the barrier for quantum chemistry (from my understanding) would be that it is not (or cannot be?) formulated as a quadratic binary optimisation. This pretty much rules out D-wave and you will have to wait for the more challenging to make quantum gate computers to be developed.

[jmsellier]

Hi Simon,

I would say that, as a first approach, one could try to recast the time-dependent Schroedinger equation in terms of an expanded wave function w.r.t. some given basis (as usually done in many papers). This would drastically reduce the complexity of the equation. Then, one obtains a system of linear equation which solution can be found by solving a corresponding optimization problem. May be, this system can be somehow formulated as a quadratic binary optimization problem by introducing some acceptable physical approximation and/or by utilizing some convenient expansion basis. This might actually work with a little bit of "luck"..

I will give it a try once I have some spare time using qbsolv.

JM

[sabladmin1]

Hi JM, I think I understand your approach. A bit like "reduced-order modelling". Calculate some point solutions to your PDE. These then form a basis that you use together with something like quadratic binary optimisation to find the best combination that approximates the solution in other regions. Maybe as a way to find a good starting point to then run a classical PDE solver.

[jmsellier]

Hi Simon,

Essentially the goal is to reduce the complexity of the problem as much as possible. By expanding a wave function in terms of some given/fixed basis (accurately chosen to obtain some new interesting/useful mathematical property of the reduced problem), one drastically reduce the complexity of the initial problem (this is, for example, a very common practice in the DFT community). This might bring to a final corresponding optimization problem which, in my opinion, should be solvable on a DWave machine. I think this could have some chance to work.

JM

[redundanceredundance]

Can you put any constraints on your problem? I mean every integrable constraint reduces the dimensionality of the problem by 1.