search

dwavesystems / minorminer

minorminer is a heuristic tool for minor embedding: given a minor and target graph, it tries to find a mapping that embeds the minor into the target.
https://docs.ocean.dwavesys.com/en/stable/docs_minorminer/source/sdk_index.html
Apache License 2.0
48 stars 40 forks source link

Large ndarrays not supported for find_embedding method #241

Closed LopezBanos closed 11 months ago

LopezBanos commented 11 months ago

Description If you have a big QUBO matrix Q of your problem in ndarray format, the find_embedding method throws an error. This does not happen if you send the same Qubo matrix Q in dict format (eg{(0,1): 1, {1,2}: 0 ....}.

To Reproduce

# Connect with D-Wave
from dwave.system import DWaveSampler
def _connect_dwave_annealer(token):
    """ Connect with the D-Wave Annealer if a token is found """
    embedding_sampler = None
    if token:
        dw_sampler = DWaveSampler(token=token,
                                  solver='Advantage_system5.4',
                                  endpoint='https://eu-central-1.cloud.dwavesys.com/sapi/v2/'
                                  )
        return dw_sampler
dw_sampler = _connect_dwave_annealer(token)

# Create a QUBO matrix in dict format
q_dict = dict = {(0, 0): -32796381.0, (0, 1): 8.0, (0, 2): 16.0, (0, 3): 32.0, (0, 4): 64.0, (0, 5): 128.0, (0, 6): 256.0, (0, 7): 512.0, (0, 8): 1024.0, (0, 9): 2048.0, (0, 10): 4096.0, (0, 11): 8192.0, (0, 12): 16384.0, (0, 13): 32768.0, (0, 14): 65536.0, (0, 15): 131072.0, (0, 16): 262144.0, (0, 17): 524288.0, (0, 18): 1048576.0, (0, 19): 2097152.0, (0, 20): 4194304.0, (0, 21): 8388608.0, (0, 22): 16019172.0, (0, 23): -160732.0, (1, 0): 0.0, (1, 1): -65592758.0, (1, 2): 32.0, (1, 3): 64.0, (1, 4): 128.0, (1, 5): 256.0, (1, 6): 512.0, (1, 7): 1024.0, (1, 8): 2048.0, (1, 9): 4096.0, (1, 10): 8192.0, (1, 11): 16384.0, (1, 12): 32768.0, (1, 13): 65536.0, (1, 14): 131072.0, (1, 15): 262144.0, (1, 16): 524288.0, (1, 17): 1048576.0, (1, 18): 2097152.0, (1, 19): 4194304.0, (1, 20): 8388608.0, (1, 21): 16777216.0, (1, 22): 32038344.0, (1, 23): -321464.0, (2, 0): 0.0, (2, 1): 0.0, (2, 2): -131185500.0, (2, 3): 128.0, (2, 4): 256.0, (2, 5): 512.0, (2, 6): 1024.0, (2, 7): 2048.0, (2, 8): 4096.0, (2, 9): 8192.0, (2, 10): 16384.0, (2, 11): 32768.0, (2, 12): 65536.0, (2, 13): 131072.0, (2, 14): 262144.0, (2, 15): 524288.0, (2, 16): 1048576.0, (2, 17): 2097152.0, (2, 18): 4194304.0, (2, 19): 8388608.0, (2, 20): 16777216.0, (2, 21): 33554432.0, (2, 22): 64076688.0, (2, 23): -642928.0, (3, 0): 0.0, (3, 1): 0.0, (3, 2): 0.0, (3, 3): -262370936.0, (3, 4): 512.0, (3, 5): 1024.0, (3, 6): 2048.0, (3, 7): 4096.0, (3, 8): 8192.0, (3, 9): 16384.0, (3, 10): 32768.0, (3, 11): 65536.0, (3, 12): 131072.0, (3, 13): 262144.0, (3, 14): 524288.0, (3, 15): 1048576.0, (3, 16): 2097152.0, (3, 17): 4194304.0, (3, 18): 8388608.0, (3, 19): 16777216.0, (3, 20): 33554432.0, (3, 21): 67108864.0, (3, 22): 128153376.0, (3, 23): -1285856.0, (4, 0): 0.0, (4, 1): 0.0, (4, 2): 0.0, (4, 3): 0.0, (4, 4): -524741616.0, (4, 5): 2048.0, (4, 6): 4096.0, (4, 7): 8192.0, (4, 8): 16384.0, (4, 9): 32768.0, (4, 10): 65536.0, (4, 11): 131072.0, (4, 12): 262144.0, (4, 13): 524288.0, (4, 14): 1048576.0, (4, 15): 2097152.0, (4, 16): 4194304.0, (4, 17): 8388608.0, (4, 18): 16777216.0, (4, 19): 33554432.0, (4, 20): 67108864.0, (4, 21): 134217728.0, (4, 22): 256306752.0, (4, 23): -2571712.0, (5, 0): 0.0, (5, 1): 0.0, (5, 2): 0.0, (5, 3): 0.0, (5, 4): 0.0, (5, 5): -1049482208.0, (5, 6): 8192.0, (5, 7): 16384.0, (5, 8): 32768.0, (5, 9): 65536.0, (5, 10): 131072.0, (5, 11): 262144.0, (5, 12): 524288.0, (5, 13): 1048576.0, (5, 14): 2097152.0, (5, 15): 4194304.0, (5, 16): 8388608.0, (5, 17): 16777216.0, (5, 18): 33554432.0, (5, 19): 67108864.0, (5, 20): 134217728.0, (5, 21): 268435456.0, (5, 22): 512613504.0, (5, 23): -5143424.0, (6, 0): 0.0, (6, 1): 0.0, (6, 2): 0.0, (6, 3): 0.0, (6, 4): 0.0, (6, 5): 0.0, (6, 6): -2098960320.0, (6, 7): 32768.0, (6, 8): 65536.0, (6, 9): 131072.0, (6, 10): 262144.0, (6, 11): 524288.0, (6, 12): 1048576.0, (6, 13): 2097152.0, (6, 14): 4194304.0, (6, 15): 8388608.0, (6, 16): 16777216.0, (6, 17): 33554432.0, (6, 18): 67108864.0, (6, 19): 134217728.0, (6, 20): 268435456.0, (6, 21): 536870912.0, (6, 22): 1025227008.0, (6, 23): -10286848.0, (7, 0): 0.0, (7, 1): 0.0, (7, 2): 0.0, (7, 3): 0.0, (7, 4): 0.0, (7, 5): 0.0, (7, 6): 0.0, (7, 7): -4197904256.0, (7, 8): 131072.0, (7, 9): 262144.0, (7, 10): 524288.0, (7, 11): 1048576.0, (7, 12): 2097152.0, (7, 13): 4194304.0, (7, 14): 8388608.0, (7, 15): 16777216.0, (7, 16): 33554432.0, (7, 17): 67108864.0, (7, 18): 134217728.0, (7, 19): 268435456.0, (7, 20): 536870912.0, (7, 21): 1073741824.0, (7, 22): 2050454016.0, (7, 23): -20573696.0, (8, 0): 0.0, (8, 1): 0.0, (8, 2): 0.0, (8, 3): 0.0, (8, 4): 0.0, (8, 5): 0.0, (8, 6): 0.0, (8, 7): 0.0, (8, 8): -8395742976.0, (8, 9): 524288.0, (8, 10): 1048576.0, (8, 11): 2097152.0, (8, 12): 4194304.0, (8, 13): 8388608.0, (8, 14): 16777216.0, (8, 15): 33554432.0, (8, 16): 67108864.0, (8, 17): 134217728.0, (8, 18): 268435456.0, (8, 19): 536870912.0, (8, 20): 1073741824.0, (8, 21): 2147483648.0, (8, 22): 4100908032.0, (8, 23): -41147392.0, (9, 0): 0.0, (9, 1): 0.0, (9, 2): 0.0, (9, 3): 0.0, (9, 4): 0.0, (9, 5): 0.0, (9, 6): 0.0, (9, 7): 0.0, (9, 8): 0.0, (9, 9): -16791223808.0, (9, 10): 2097152.0, (9, 11): 4194304.0, (9, 12): 8388608.0, (9, 13): 16777216.0, (9, 14): 33554432.0, (9, 15): 67108864.0, (9, 16): 134217728.0, (9, 17): 268435456.0, (9, 18): 536870912.0, (9, 19): 1073741824.0, (9, 20): 2147483648.0, (9, 21): 4294967296.0, (9, 22): 8201816064.0, (9, 23): -82294784.0, (10, 0): 0.0, (10, 1): 0.0, (10, 2): 0.0, (10, 3): 0.0, (10, 4): 0.0, (10, 5): 0.0, (10, 6): 0.0, (10, 7): 0.0, (10, 8): 0.0, (10, 9): 0.0, (10, 10): -33581399040.0, (10, 11): 8388608.0, (10, 12): 16777216.0, (10, 13): 33554432.0, (10, 14): 67108864.0, (10, 15): 134217728.0, (10, 16): 268435456.0, (10, 17): 536870912.0, (10, 18): 1073741824.0, (10, 19): 2147483648.0, (10, 20): 4294967296.0, (10, 21): 8589934592.0, (10, 22): 16403632128.0, (10, 23): -164589568.0, (11, 0): 0.0, (11, 1): 0.0, (11, 2): 0.0, (11, 3): 0.0, (11, 4): 0.0, (11, 5): 0.0, (11, 6): 0.0, (11, 7): 0.0, (11, 8): 0.0, (11, 9): 0.0, (11, 10): 0.0, (11, 11): -67158603776.0, (11, 12): 33554432.0, (11, 13): 67108864.0, (11, 14): 134217728.0, (11, 15): 268435456.0, (11, 16): 536870912.0, (11, 17): 1073741824.0, (11, 18): 2147483648.0, (11, 19): 4294967296.0, (11, 20): 8589934592.0, (11, 21): 17179869184.0, (11, 22): 32807264256.0, (11, 23): -329179136.0, (12, 0): 0.0, (12, 1): 0.0, (12, 2): 0.0, (12, 3): 0.0, (12, 4): 0.0, (12, 5): 0.0, (12, 6): 0.0, (12, 7): 0.0, (12, 8): 0.0, (12, 9): 0.0, (12, 10): 0.0, (12, 11): 0.0, (12, 12): -134300430336.0, (12, 13): 134217728.0, (12, 14): 268435456.0, (12, 15): 536870912.0, (12, 16): 1073741824.0, (12, 17): 2147483648.0, (12, 18): 4294967296.0, (12, 19): 8589934592.0, (12, 20): 17179869184.0, (12, 21): 34359738368.0, (12, 22): 65614528512.0, (12, 23): -658358272.0, (13, 0): 0.0, (13, 1): 0.0, (13, 2): 0.0, (13, 3): 0.0, (13, 4): 0.0, (13, 5): 0.0, (13, 6): 0.0, (13, 7): 0.0, (13, 8): 0.0, (13, 9): 0.0, (13, 10): 0.0, (13, 11): 0.0, (13, 12): 0.0, (13, 13): -268533751808.0, (13, 14): 536870912.0, (13, 15): 1073741824.0, (13, 16): 2147483648.0, (13, 17): 4294967296.0, (13, 18): 8589934592.0, (13, 19): 17179869184.0, (13, 20): 34359738368.0, (13, 21): 68719476736.0, (13, 22): 131229057024.0, (13, 23): -1316716544.0, (14, 0): 0.0, (14, 1): 0.0, (14, 2): 0.0, (14, 3): 0.0, (14, 4): 0.0, (14, 5): 0.0, (14, 6): 0.0, (14, 7): 0.0, (14, 8): 0.0, (14, 9): 0.0, (14, 10): 0.0, (14, 11): 0.0, (14, 12): 0.0, (14, 13): 0.0, (14, 14): -536799068160.0, (14, 15): 2147483648.0, (14, 16): 4294967296.0, (14, 17): 8589934592.0, (14, 18): 17179869184.0, (14, 19): 34359738368.0, (14, 20): 68719476736.0, (14, 21): 137438953472.0, (14, 22): 262458114048.0, (14, 23): -2633433088.0, (15, 0): 0.0, (15, 1): 0.0, (15, 2): 0.0, (15, 3): 0.0, (15, 4): 0.0, (15, 5): 0.0, (15, 6): 0.0, (15, 7): 0.0, (15, 8): 0.0, (15, 9): 0.0, (15, 10): 0.0, (15, 11): 0.0, (15, 12): 0.0, (15, 13): 0.0, (15, 14): 0.0, (15, 15): -1072524394496.0, (15, 16): 8589934592.0, (15, 17): 17179869184.0, (15, 18): 34359738368.0, (15, 19): 68719476736.0, (15, 20): 137438953472.0, (15, 21): 274877906944.0, (15, 22): 524916228096.0, (15, 23): -5266866176.0, (16, 0): 0.0, (16, 1): 0.0, (16, 2): 0.0, (16, 3): 0.0, (16, 4): 0.0, (16, 5): 0.0, (16, 6): 0.0, (16, 7): 0.0, (16, 8): 0.0, (16, 9): 0.0, (16, 10): 0.0, (16, 11): 0.0, (16, 12): 0.0, (16, 13): 0.0, (16, 14): 0.0, (16, 15): 0.0, (16, 16): -2140753821696.0, (16, 17): 34359738368.0, (16, 18): 68719476736.0, (16, 19): 137438953472.0, (16, 20): 274877906944.0, (16, 21): 549755813888.0, (16, 22): 1049832456192.0, (16, 23): -10533732352.0, (17, 0): 0.0, (17, 1): 0.0, (17, 2): 0.0, (17, 3): 0.0, (17, 4): 0.0, (17, 5): 0.0, (17, 6): 0.0, (17, 7): 0.0, (17, 8): 0.0, (17, 9): 0.0, (17, 10): 0.0, (17, 11): 0.0, (17, 12): 0.0, (17, 13): 0.0, (17, 14): 0.0, (17, 15): 0.0, (17, 16): 0.0, (17, 17): -4264327774208.0, (17, 18): 137438953472.0, (17, 19): 274877906944.0, (17, 20): 549755813888.0, (17, 21): 1099511627776.0, (17, 22): 2099664912384.0, (17, 23): -21067464704.0, (18, 0): 0.0, (18, 1): 0.0, (18, 2): 0.0, (18, 3): 0.0, (18, 4): 0.0, (18, 5): 0.0, (18, 6): 0.0, (18, 7): 0.0, (18, 8): 0.0, (18, 9): 0.0, (18, 10): 0.0, (18, 11): 0.0, (18, 12): 0.0, (18, 13): 0.0, (18, 14): 0.0, (18, 15): 0.0, (18, 16): 0.0, (18, 17): 0.0, (18, 18): -8459936071680.0, (18, 19): 549755813888.0, (18, 20): 1099511627776.0, (18, 21): 2199023255552.0, (18, 22): 4199329824768.0, (18, 23): -42134929408.0, (19, 0): 0.0, (19, 1): 0.0, (19, 2): 0.0, (19, 3): 0.0, (19, 4): 0.0, (19, 5): 0.0, (19, 6): 0.0, (19, 7): 0.0, (19, 8): 0.0, (19, 9): 0.0, (19, 10): 0.0, (19, 11): 0.0, (19, 12): 0.0, (19, 13): 0.0, (19, 14): 0.0, (19, 15): 0.0, (19, 16): 0.0, (19, 17): 0.0, (19, 18): 0.0, (19, 19): -16644994236416.0, (19, 20): 2199023255552.0, (19, 21): 4398046511104.0, (19, 22): 8398659649536.0, (19, 23): -84269858816.0, (20, 0): 0.0, (20, 1): 0.0, (20, 2): 0.0, (20, 3): 0.0, (20, 4): 0.0, (20, 5): 0.0, (20, 6): 0.0, (20, 7): 0.0, (20, 8): 0.0, (20, 9): 0.0, (20, 10): 0.0, (20, 11): 0.0, (20, 12): 0.0, (20, 13): 0.0, (20, 14): 0.0, (20, 15): 0.0, (20, 16): 0.0, (20, 17): 0.0, (20, 18): 0.0, (20, 19): 0.0, (20, 20): -32190476845056.0, (20, 21): 8796093022208.0, (20, 22): 16797319299072.0, (20, 23): -168539717632.0, (21, 0): 0.0, (21, 1): 0.0, (21, 2): 0.0, (21, 3): 0.0, (21, 4): 0.0, (21, 5): 0.0, (21, 6): 0.0, (21, 7): 0.0, (21, 8): 0.0, (21, 9): 0.0, (21, 10): 0.0, (21, 11): 0.0, (21, 12): 0.0, (21, 13): 0.0, (21, 14): 0.0, (21, 15): 0.0, (21, 16): 0.0, (21, 17): 0.0, (21, 18): 0.0, (21, 19): 0.0, (21, 20): 0.0, (21, 21): -59982907179008.0, (21, 22): 33594638598144.0, (21, 23): -337079435264.0, (22, 0): 0.0, (22, 1): 0.0, (22, 2): 0.0, (22, 3): 0.0, (22, 4): 0.0, (22, 5): 0.0, (22, 6): 0.0, (22, 7): 0.0, (22, 8): 0.0, (22, 9): 0.0, (22, 10): 0.0, (22, 11): 0.0, (22, 12): 0.0, (22, 13): 0.0, (22, 14): 0.0, (22, 15): 0.0, (22, 16): 0.0, (22, 17): 0.0, (22, 18): 0.0, (22, 19): 0.0, (22, 20): 0.0, (22, 21): 0.0, (22, 22): -99265991118021.0, (22, 23): -643698388476.0, (23, 0): 0.0, (23, 1): 0.0, (23, 2): 0.0, (23, 3): 0.0, (23, 4): 0.0, (23, 5): 0.0, (23, 6): 0.0, (23, 7): 0.0, (23, 8): 0.0, (23, 9): 0.0, (23, 10): 0.0, (23, 11): 0.0, (23, 12): 0.0, (23, 13): 0.0, (23, 14): 0.0, (23, 15): 0.0, (23, 16): 0.0, (23, 17): 0.0, (23, 18): 0.0, (23, 19): 0.0, (23, 20): 0.0, (23, 21): 0.0, (23, 22): 0.0, (23, 23): 1321086445250.0}

# Compute the Embedding of dict
from minorminer import find_embedding
node_list, target_edgelist, target_adjacency = dw_sampler.structure
embedding = find_embedding(q_dict, target_edgelist) #Embedding is Computed

# Translate the QUBO dict to ndarray
import numpy as np
def dict_to_matrix(q_dict):
    rows, cols = (24, 24)  # 24x24 elements in q_dict
    _dict = q_dict 
    matrix = np.empty([24, 24])
    for row in range(rows):
        for col in range(cols):
            matrix[row][col] = _dict[(row, col)]
    return matrix
Q_matrix = dict_to_matrix(dict)

# Compute the Embedding of ndarray
node_list, target_edgelist, target_adjacency = dw_sampler.structure
embedding = find_embedding(q_dict, target_edgelist)
""" Throws the following error:
3 embedding = find_embedding(Q_matrix, target_edgelist)

     21 @__wraps(__find_embedding)
     22 def find_embedding(S, T,
     23                    max_no_improvement=10,
   (...)
     39                    suspend_chains=(),
     40                    ):
---> 41     return __find_embedding(S, T,
     42                             max_no_improvement=max_no_improvement,
     43                             random_seed=random_seed,
     44                             timeout=timeout,
     45                             max_beta=max_beta,
     46                             tries=tries,
     47                             inner_rounds=inner_rounds,
     48                             chainlength_patience=chainlength_patience,
     49                             max_fill=max_fill,
     50                             threads=threads,
     51                             return_overlap=return_overlap,
     52                             skip_initialization=skip_initialization,
     53                             verbose=verbose,
     54                             interactive=interactive,
     55                             initial_chains=initial_chains,
     56                             fixed_chains=fixed_chains,
     57                             restrict_chains=restrict_chains,
     58                             suspend_chains=suspend_chains,
     59                             )

File minorminer/_minorminer.pyx:287, in minorminer._minorminer.find_embedding()

File minorminer/_minorminer.pyx:399, in minorminer._minorminer._input_parser.__init__()

File minorminer/_minorminer.pyx:714, in minorminer._minorminer._read_graph()

ValueError: too many values to unpack (expected 2)

"""

Expected behavior Since the EmddingComposite allows qubo matrices in ndarray format. I expected that minorminer admits it too for large matrices as this one with large numbers.

Environment:

boothby commented 11 months ago

Please review the documentation of find_embedding -- the function accepts either an iterable of edges or a NetworkX graph. As you note, iteration over q_dict provides a list of edges suitable for use in find_embedding without translation to QUBO.