Behavior of dwave-hybrid's Kerberos
Hi everyone,
I am trying to understand about the configuration of the hybrid framework through the Kerberos reference framework. I wrote Jupyter notebook for USA's map coloring through this link: https://docs.ocean.dwavesys.com/en/stable/examples/map_kerberos.html#map-kerberos
First, I don't use the min_vertex_coloring algorithm from dwave_networkx, I used the approach from this link: https://docs.ocean.dwavesys.com/en/stable/examples/map_coloring.html to get its BQM.
After getting the BQM form, I got the initial solution from TabuSampler() with its default parameters, whose energy is -102.00000867.
Then, I run Kerberos() (not KerberosSampler()) with its default parameters into this initial solution. I use the logging with DEBUG and INFO levels to see what information I have. They are the energy of each branch before coming to ArgMin() block.
1.
Identity Block
-102.00000867246558
Tabu Block
-102.00000867246558
SA Block
-102.0000086724682
QPU
-80.00000752995126
2.
Identity Block
-102.0000086724682
Tabu Block
-102.00000867246557
SA Block
-102.0000086724682
QPU
-86.00000808183542
3.
Identity Block
-102.0000086724682
Tabu Block
-102.00000867246557
SA Block
-102.0000086724682
QPU
-82.00000721458885
ArgMin min_idx=0
Loop Iteration(iterno=2, input_state_key=-102.0000086724682, output_state_key=-102.0000086724682)
4.
Identity Block (deep copy)
-102.0000086724682
Tabu Block (entire prob)
-102.00000867246557
SA Block (entire prob)
-102.0000086724682
QPU (subprob)
-84.00000709565366
ArgMin min_idx=0
Loop Iteration(iterno=3, input_state_key=-102.0000086724682, output_state_key=-102.0000086724682)
I see that after the first iteration, I got the optimal value is -102.0000086724682 and it will be the input of the next iteration (2nd iteration). After the 2nd iteration, the output of QPU is better than the previous iteration's QPU output value, but the output of the entire problem is not better than the previous iteration's entire output. And in the next two iterations, the output of QPU is worse, and the entire output of the other 3 branches does not change anything (I think with different subsamples from QPU, I will get the different entire outputs of QPU, and they will go in classical branches and these classical branches will change energy's values).
Someone can explain to me what is going on here? Is there any way to improve the quality of solutions?
Thank you!
Comments
It's difficult to say in this scenario why you are getting the energy readings from the QPU that you are, especially without implementation details, but I can explain what you are seeing from Kerberos.
At the end of each iteration, the ArgMin function takes the result with the lowest energy from any of the branches.
You can see that the best energy is found from the first iteration in the SA Block.
This problem formulation might be a difficult one for the QPU to perform well on.
An improvement on the results from any one branch doesn't correspond to an improvement overall.
ArgMin is just selecting the answer from the branch with the lowest energy.
The convergence parameter described in the Kerberos docs is the condition that stops execution if the same best result is returned the number of times indicated by convergence (default being 3).
For the behaviour that you are describing, you might be more interested in the Hybrid Solver Service (HSS).
You can use the LeapHybridSampler, which simply takes a time_limit parameter - indicating how long the sampler should run in seconds - in the sample function call.
I hope this was helpful! Please feel free to ask for more information or for clarification!
Yes, I want to see what is happening inside Kerberos().
But, I have one concern, that the output of the QPU branch will be processed to 2 classical branches (SA and Tabu) simultaneously or just one of these two? I saw Kerberos() use Race(), so I think one of these two classical branches will get the output of the quantum branch to make a sampling.
To check the quality of the solution from different problem formulations, I also try with the problem formulation from the min_vertex_coloring algorithm of the dwave-networkx. I see that with the problem formulation getting from this min_vertex_coloring, QPU performs quite well on and the energy of each branch in each iteration improves slowly. Maybe you're right about the problem formulation issue.
Thanks.
Hello,
Just to clarify, the branches (SA, Tabu, QPU) don't share any information except best solution at the end of each iteration.
The solution from any one branch is not guaranteed to improve, but as a whole, the single best solution from all branches for each iteration (ArgMin) is passed back into each branch on the subsequent iteration.
The branches race each other to find the best solution independently.
Thanks, David for your clarification,
So, what does the term "interrupted" stated in this statement? This statement made me think about the classical branch will take the sample from the quantum branch (after SplatComposer()) to run.
So, the behavior of the dwave-hybrid is separated from the behavior of qbsolv() (https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/), is it right?
Hello,
In this case, Interruptable means that once the other branches are ready, they will interrupt the Tabu sampler and check the result that it has reached.
Tabu can basically run indefinitely if desired.
You would want to interrupt it at some point to see what result it has come up with.
This happens when one of the other branches completes or when a timeout parameter is set.
At that point results are compared and the best result is used in the next iteration, according to ArgMin.
One difference in the default behaviour of Kerberos vs a standard dwave-hybrid workflow is that Kerberos uses a Breadth-First Search traversal (traversal = 'bfs') by default, while dwave-hybrid uses an Energy traversal (traversal = 'energy') traversal by default in the EnergyImpactDecomposer.
Check out this page for more details:
https://docs.ocean.dwavesys.com/projects/hybrid/en/latest/intro/using.html?highlight=bfs#flow-refining
Here is a link to the source for Kerberos that shows the bfs traversal:
https://docs.ocean.dwavesys.com/projects/hybrid/en/latest/_modules/hybrid/reference/kerberos.html
For a qbsolv-like implementation of dwave-hybrid, you can take a look at this example repo:
https://github.com/dwavesystems/dwave-hybrid/blob/master/examples/qbsolv-like.py
I hope this helps answer your questions!
Please feel free to ask follow up questions or for clarification!
Please sign in to leave a comment.