Weighted Max Cut for 1000 Vertex Graph

• 

  Tanjid I  (Report)

  May 01, 2023 16:55

  Hi Suman,

  Thank you for using D-Wave Services. For your specific case, you can formulate your problem as BQM, which may be sufficient to handle 1000 variables for the vertex weighted undirected graphs. 
  
  Here are some resources that may help you for your solution:

  1. Max-Cut on the D-Wave System: https://github.com/dwave-examples/maximum-cut
     Example of python code snippet that demonstrates how to formulate problem as a BQM

  2. Graph Partitioning on D-Wave: https://github.com/dwave-examples/graph-partitioning
     Example of another python code snippet that demonstrates how to solve the graph partitioning problem, which is closely related to the max-cut problem.

  There could be several reasons for your answer not coming same as the exact solution. One possibility is that the D-Wave quantum annealer may not have found global optimal solution due to noise or other factors. Another possibility is that there may be errors or inaccuracies in your BQM formulation. To address these issues, you can try increasing the number of reads or tweaking the annealing parameters to improve the sampling process. 
  
  I hope this helps. 
  
  Best Regards,

  Tanjid

  0

  Comment actions Permalink
• 

  robert l  (Report)

  June 06, 2023 08:59 (Edited June 06, 2023 09:00)

  Hi SUMAN KUMAR R and @...,

  I'm wondering if you were able to get any positive results from your 1000 vertex max cut attempt?

  From my end, I am attempting to solve just a 100-vertex max cut graph by adjusting the given max-cut code (https://github.com/dwave-examples/maximum-cut) and inserting my own pre-built matrix, but even after increasing numruns to 3000 and chain_strength to 8, I am only getting a response that is 89.4% accurate after about ~25 seconds of run time.

  Meanwhile, using Dwave's simulated annealing program (https://docs.ocean.dwavesys.com/projects/neal/en/latest/reference/sampler.html) to solve the same matrix, I get a response that is 100% accurate after just 0.01 seconds.

  Is this the optimal response we could expect from using Leap Advantage for a 100-vertex graph (i.e. <100% accuracy), or does my quantum annealing code need further tweaking? Are there other solvers or methods I should consider using?

  For reference, I am using the ```sample_ising()``` solver to solve the quantum problem. 

  Thanks,

  Rob

  0

  Comment actions Permalink

Please sign in to leave a comment.