I'm currently working on a project for my thesis regarding BQM and CQM optimisation for a path problem.

Without going too much on the details, here's some info:

  • the structure is a tree, where all the nodes of a level are linked to all the nodes of the lower and upper level, exception is the leaf-level, which is structured as binary (every above node is linked to 2 leaves);
  • the leaves are servers, each one with a capacity;
  • the other nodes are switches;
  • links have their own capacity;
  • i have N virtual machines (N = number of server), each one with a cost, that have to be allocated to some server;
  • each vm has to communicate to another vm and can do so only if on the same server or linked by a path and a flow on that path;

My goal is find where to allocate each vm, decide which nodes have to be active, which links, which flow connects which server through which path. Obviously everything has it's own static/dynamic cost.

The problem was already elaborated by a previous publishment stating it as a CQM and after explaining the conversion to BQM.

The whole point of this is to demonstrate that with quantum computing we can obtain a better performance on an unconstrained binary model.

Now, I'm using the D'Wave system to test this, i've already modeled the problem as a CQM, it runs, returns the best option, cool. Then I proceed to convert the CQM to BQM using the dwave function, it runs, but returns worse energy once the tree has 3+ levels.

I've tried both full quantum BQM, which apparently is impossible to use because of the high number of variables, and the hybrid BQM, but can't obtain nothing good. I've even tried splitting the problem in 2 phases, first allocate vms and then find paths, using 2 different problem and solving them separately (using the first's results for the second) to reduce the number of variables but still no solution. I've even tried to modify the lagrange multiplier to both greater (100) and smaller (1) number but did not obtain nothing too relevant, same result for increasing the time limit to up to 400% of the BQM computation time.

I wonder if there's something i can do to optimize it even further, the samplers still take only the minimal time limit to solve the problem, so it makes it quite strange (at least for me) that the BQM can't find the best solution. Maybe i've just done something wrong and it's my fault or maybe the conversion function is not suitable for this project?

Here you can read the code: https://github.com/AmedeoB/Tesi/blob/master/decomposed_main.py



Your Answer

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