Traditional QUBO vs D-Wave QUBOs Matrix

I'm new to this topic but seems that are several types of QUBO matrices, I want to know what type of QUBO matrix should be used at D-Wave (mainly in dwave-hybrid).

type 1) Traditional QUBO matrix is "full symmetric": linear coefficients "main diagonal terms", quadratic coefficients "all off-diagonal terms".

type 2) D-Wave QUBO matrix (A) is "upper triangular": linear coefficients "main diagonal terms", quadratic coefficients "upper off-diagonal terms".

type 3) D-Wave QUBO matrix (B) is "upper triangular with all diagonal entries equal to zero", linear coefficients separated in a dictionary, quadratic coefficients (from the upper off-diagonal terms) in another dictionary.

Some tests:
my_qubo_array = http://www.sharecsv.com/s/051ba20b9dcd3e50135315063b420ae1/qubo.csv # type 1 (full symmetric qubo)
bqm = convert_numpy_to_dictionary(my_qubo_array)
- work with QBsolv: QBSolv().sample_qubo(bqm, solver=sampler)
- won't work with Hybrid: State.from_sample(min_sample(bqm), bqm) # AttributeError: 'dict' object has no attribute 'vartype'

bqm = dimod.BinaryQuadraticModel.from_numpy_matrix(my_qubo_array)
- won't work in QBsolv # AttributeError: 'BinaryQuadraticModel' object has no attribute 'items'
- work with Hybrid

Converting a Full Symmetric QUBO matrix to dictionaries also won't work:
linear_dict = https://paste.debian.net/1072122/
quadratic_dict = https://paste.debian.net/1072125/
bqm = dimod.BinaryQuadraticModel(linear=linear_dict, quadratic=quadratic_dict, offset=1.0, vartype=dimod.Vartype.BINARY)
# ValueError: no self-loops allowed, therefore (0, 0) is not an allowed interaction

I believe that this "quadratic_dict" must be the type 3 (upper triangular with all diagonal entries equal to zero)

So my questions are:

a) what are the correct and best type of QUBO matrix to work in D-Wave applications (mainly dwave-hybrid)

b) is there some converter from type 1 (full symmetric) matrix to type 2 or 3 matrices?

c) if I have the type 2 matrix (upper triangular), what "dimod.BinaryQuadraticModel.function" will receive a numpy array and understand the linear on the diagonal terms and quadratic on the upper off-diagonal terms?

d) about the "off-diagonal terms", some docs say "nonzero off-diagonal terms". When transforming in a dictionary, if the position (1,2) is "0" I don't need to put in the dictionary? the dictionary will have only the "upper" "off-diagonal" "nonzero" terms?

Thank you

0

Comments

5 comments
  • Hello John,

    The answer to your question depends on your workflow. It is possible to solve QUBOs directly with many D-Wave tools (for example, DWaveSampler) through the "sample_qubo" function. In this case, the proper format is upper-triangular with linear terms included in the diagonal. For example:

    written in matrix format:

    [1 2 4
    2 3
    1]

    in context:

    from dwave_qbsolv import QBSolv
    QUBO = {(0,0):1, (0,1):2, (0,2):4, (1,1):2, (1,2):3, (2,2):1}
    response = QBSolv().sample_qubo(QUBO)

    There is also a more general way to write both QUBOs and Ising problems, referred to as a binary quadratic model (BQM). This format separates linear and quadratic terms. In this case, you can use the common "sample" function:

    same QUBO as above converted to BQM form:

    BinaryQuadraticModel({0: 0, 1: 1, 2: 1}, {(0, 1): 4, (0, 2): 6, (1, 2): 4}, 0.0, Vartype.BINARY)

    in context:

    from dimod import BinaryQuadraticModel
    from dwave_qbsolv import QBSolv
    BQM = BinaryQuadraticModel.from_qubo(QUBO)
    response = QBSolv().sample(BQM)

    The constructor BinaryQuadraticModel.from_qubo will automatically sum symmetric off-diagonal terms if present - this is a step towards how the variables will be actually programmed on the QPU. For example:

    {(0,1):1, (1,0):1} --> BinaryQuadraticModel.from_qubo --> {(0,1):2}

    Note that in both cases, terms equaling zero do not contribute to the objective function (calculation of the energy of each solution) so they can be omitted. 

    0
    Comment actions Permalink
  • Luca, Thank you very much, "QBSolv().sample(BQM)" works.

    0
    Comment actions Permalink
  • Hi Luca, i saw the discussion and thought i simply hop in. My question is, what does the solver do when you insert a non-symmetric matrix?

    0
    Comment actions Permalink
  • Hi Dominik,

    What Luca is mentioning is that if there are terms above and below the diagonal, it will add them together. 

    If we think of the rows and columns each representing different variables or nodes in a graph, we can think of the diagonal values in the matrix as being the linear terms or the node values in a graph, and the off-diagonal terms as being quadratic terms or the edges in a graph. 
    So for row 1, column 2, it is the quadratic term representing variable 1 correlating to variable 2 or the edge between node 1 and 2.

    Similarly row 2, column 1 would represent the same relationship; the quadratic term containing variable 2 and variable 1 or the edge between node 2 and node 1.
    If the graph was a directional graph, it would mean that each direction between two nodes could have a different value; i.e. the edge from node 1 to node 2 is not the same as the edge from node 2 to node 1. 
    This is not the case for the QPU, so the two cells (1, 2) and (2, 1) represent the same edge and are added together; i.e. there is no directionality on the edges in the graph.

    You could also imagine that this is also the case for asymmetrical triangular matrices.
    If (1, 2) has a value and (2, 1) is zero - or vice versa - adding the two values together will sum to the value, since any value plus zero is the value itself.

    I hope this was helpful and clarified things.
    Please feel free to ask more questions.

     

    0
    Comment actions Permalink
  • Hi David,

     

    indeed this clarified things. Thank you very much!

    1
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post