Parallelizing Computation Using D-Wave Processors Via Multiple Simultaneous Embeddings

D-Wave processors are graphs that contain qubits as vertices and couplers as edges. Depending on the processor, these graphs typically have thousands of qubits and tens of thousands of edges.

If we want to use a processor to solve a problem that is much smaller than the size of the hardware graph, one cool technique we can use is to find multiple non-overlapping ways to fit our problem into the hardware graph. These ‘fits’ are called embeddings. If you can find a bunch, then each time you call the processor, you get all of them solved for you at once. Not only does this give you a pretty big speed up (up to about 200-350x faster for the problems I’ll show you here), but it gives a neat way to average over certain types of noise in a processor.

Let’s take a look!

Embedding A Graph Into Another Graph

Let’s call the hardware graph G, where G has V vertices and E edges. This is a fixed graph given to us by the D-Wave folks.

Let’s call the graph holding the problem we want to solve H, where H has a much smaller set of vertices and edges. For us, H is the Tangled game board graph. We’ll look at the cases where H is the three- and four-vertex fully connected graphs.

An embedding of H into G is a map from the edges and vertices of H into the edges and vertices of G. Here’s an example, where H is the three vertex graph with vertices 0, 1, and 2, and edges (0, 1), (0, 2), and (1, 2), being mapped into the hardware graph vertices 301, 306 and 207, with edges (301, 306), (301, 307), and (306, 307).

On the right in the background is the hardware graph G in grey (it's big and complicated!) where vertices 301, 306 and 307 form a triangle with the same pattern as the graph H we started with (with vertices 0, 1, and 2). The map of H into G is called an embedding into the hardware.

Because the hardware graph is large, we can do this embedding thing more than once, like this for example:

In addition to the original embedding, we add one to hardware vertices 591, 596, and 597. Now we have two copies of the original problem in the hardware at the same time, so one run gives us two answers!

We can keep doing this until we use up as many of the vertices and edges as we can! In my case, I modified some D-Wave code to find multiple embeddings and found 346 simultaneous embeddings of the three-vertex game graph. Here is what that looks like:

346 embeddings of the three-vertex H into the D-Wave Advantage2.4 processor.

Try this for yourself! Here’s the code snippet that generated the previous image. To see fewer embeddings, just include fewer in the embeddings list.

from dwave.system import DWaveSampler
import dwave.inspector

sampler = DWaveSampler(solver='Advantage2_prototype2.4')
embeddings = [[301, 306, 307], [591, 596, 597], [1071, 1077, 340], [807, 813, 373], [104, 949, 954], [247, 854, 860], [125, 131, 1177], [601, 607, 803], [565, 571, 809], [1093, 1098, 136], [1025, 1030, 1031], [808, 814, 469], [79, 816, 822], [1163, 617, 623], [831, 837, 367], [574, 1109, 1115], [1227, 1232, 1233], [516, 665, 670], [144, 661, 667], [1190, 1196, 245], [686, 692, 252], [3, 9, 960], [1059, 1065, 364], [939, 945, 380], [711, 717, 348], [1049, 1055, 544], [49, 54, 744], [1156, 1162, 449], [1117, 1122, 1123], [346, 1131, 1137], [820, 826, 475], [1008, 1009, 1014], [207, 213, 991], [650, 656, 276], [370, 1143, 1149], [86, 92, 900], [257, 1130, 1136], [700, 706, 456], [1107, 1113, 358], [563, 1217, 1223], [1106, 1111, 1112], [1037, 1043, 568], [400, 405, 406], [443, 1240, 1246], [1160, 329, 335], [603, 609, 995], [291, 297, 992], [67, 828, 834], [137, 143, 1189], [832, 838, 463], [527, 1205, 1210], [844, 850, 451], [284, 938, 944], [687, 693, 360], [184, 189, 190], [629, 634, 635], [68, 912, 918], [754, 481, 486], [14, 20, 864], [0, 1, 6], [729, 385, 390], [698, 704, 264], [40, 46, 1080], [905, 911, 542], [951, 957, 344], [1195, 221, 227], [962, 968, 255], [206, 212, 895], [256, 262, 1058], [721, 726, 727], [272, 950, 956], [471, 477, 1000], [533, 1145, 1151], [550, 1121, 1127], [558, 725, 731], [1068, 1074, 88], [1191, 1197, 365], [281, 1178, 287], [548, 953, 959], [758, 764, 265], [170, 176, 865], [84, 90, 708], [163, 853, 859], [167, 1213, 1219], [65, 71, 1188], [263, 1238, 1244], [1154, 209, 215], [576, 582, 707], [735, 741, 337], [230, 236, 871], [1142, 250, 1148], [641, 646, 504], [1027, 153, 1021], [679, 228, 234], [1028, 316, 321], [134, 140, 870], [145, 150, 733], [917, 922, 923], [123, 129, 985], [555, 561, 989], [1203, 1208, 1209], [25, 30, 720], [107, 1225, 1230], [1214, 1220, 251], [85, 732, 738], [1064, 328, 334], [181, 186, 757], [1029, 381, 1023], [899, 530, 536], [350, 867, 356], [999, 1005, 375], [292, 298, 1088], [267, 273, 974], [963, 969, 351], [389, 394, 395], [1083, 1089, 352], [514, 1102, 508], [747, 753, 349], [108, 114, 685], [1165, 1171, 173], [1056, 1062, 76], [1026, 57, 1020], [1201, 1206, 1207], [53, 1164, 1170], [156, 157, 162], [903, 909, 338], [543, 549, 977], [1167, 1173, 341], [175, 841, 847], [554, 560, 869], [1228, 1234, 467], [15, 21, 972], [579, 585, 1007], [1169, 1175, 545], [1118, 1119, 1124], [638, 643, 644], [128, 925, 930], [515, 1174, 509], [304, 1076, 310], [182, 188, 901], [898, 434, 440], [74, 80, 882], [929, 934, 935], [742, 505, 510], [1157, 485, 491], [454, 1108, 1114], [303, 308, 309], [843, 849, 355], [672, 673, 678], [27, 32, 33], [551, 1229, 1235], [688, 694, 444], [602, 608, 887], [529, 534, 737], [1078, 484, 490], [1036, 1042, 460], [564, 570, 713], [195, 201, 1003], [1079, 604, 610], [539, 1241, 1247], [111, 117, 973], [734, 739, 740], [746, 752, 253], [231, 237, 967], [760, 766, 433], [625, 630, 631], [1057, 160, 166], [132, 138, 709], [703, 204, 210], [1016, 1010, 1015], [699, 705, 372], [897, 374, 891], [362, 879, 368], [627, 632, 633], [102, 745, 750], [5, 11, 1152], [1066, 496, 502], [1129, 1135, 178], [649, 655, 180], [600, 606, 695], [1099, 196, 202], [952, 958, 452], [192, 193, 198], [280, 286, 1082], [1184, 305, 311], [345, 1011, 1017], [271, 830, 836], [541, 546, 761], [856, 862, 439], [691, 216, 222], [518, 524, 874], [538, 1133, 1139], [827, 590, 595], [89, 95, 1176], [982, 483, 489], [12, 13, 18], [1081, 1086, 124], [613, 619, 815], [268, 274, 1070], [64, 69, 70], [424, 429, 430], [676, 682, 432], [776, 325, 331], [58, 1128, 1134], [566, 572, 881], [194, 200, 907], [664, 669, 396], [422, 428, 873], [680, 312, 318], [317, 322, 323], [1063, 232, 238], [927, 933, 339], [382, 1095, 1101], [1033, 1039, 165], [72, 78, 696], [279, 285, 986], [1153, 1159, 185], [97, 103, 769], [520, 526, 1090], [447, 964, 453], [1047, 1053, 357], [588, 589, 594], [1172, 293, 299], [28, 34, 1092], [458, 464, 868], [581, 586, 587], [519, 525, 970], [289, 294, 295], [436, 1012, 1018], [926, 931, 932], [716, 324, 330], [168, 169, 174], [512, 886, 506], [473, 478, 479], [517, 522, 523], [109, 115, 781], [99, 105, 961], [187, 829, 835], [260, 878, 884], [1067, 616, 622], [788, 313, 319], [1091, 592, 598], [387, 392, 393], [106, 1141, 1146], [61, 66, 756], [146, 152, 889], [975, 981, 363], [155, 1237, 1243], [261, 998, 1004], [269, 1166, 275], [217, 223, 787], [796, 802, 457], [120, 126, 697], [1179, 1185, 353], [482, 487, 488], [158, 164, 877], [1186, 497, 503], [435, 441, 988], [60, 648, 654], [640, 645, 384], [614, 875, 620], [801, 421, 427], [1216, 1222, 455], [553, 559, 797], [806, 811, 812], [1155, 1161, 377], [920, 315, 320], [712, 718, 468], [819, 825, 379], [1193, 1199, 569], [896, 326, 332], [855, 343, 861], [759, 765, 361], [37, 42, 43], [1044, 1045, 1050], [1226, 203, 1231], [50, 56, 894], [652, 657, 658], [777, 409, 415], [941, 946, 947], [556, 1097, 1103], [1094, 1100, 244], [412, 417, 418], [466, 1120, 1126], [552, 653, 659], [83, 1212, 1218], [722, 728, 241], [218, 224, 883], [730, 493, 498], [442, 1132, 1138], [459, 976, 465], [87, 93, 996], [121, 127, 793], [1048, 1054, 448], [133, 139, 805], [818, 824, 254], [1181, 1187, 557], [1046, 1051, 1052], [1215, 1221, 383], [219, 225, 979], [532, 1013, 1019], [531, 965, 971], [1035, 1040, 1041], [135, 141, 997], [902, 908, 278], [1183, 233, 239], [171, 172, 177], [994, 495, 501], [243, 248, 249], [983, 615, 621], [91, 840, 846], [1105, 1110, 142], [612, 618, 683], [470, 476, 880], [77, 1104, 82], [662, 668, 240], [116, 937, 942], [1087, 208, 214], [75, 81, 984], [39, 44, 45], [1069, 148, 154], [327, 333, 980], [151, 817, 823], [2, 8, 876], [229, 235, 775], [48, 660, 666], [675, 681, 336], [113, 118, 119], [1192, 1198, 461], [96, 637, 642], [784, 790, 445], [567, 573, 1001], [55, 852, 858], [1075, 220, 226], [789, 397, 403], [866, 872, 242], [399, 404, 921], [277, 794, 283], [205, 211, 799], [259, 842, 848], [513, 1006, 507], [59, 1236, 1242], [1239, 347, 1245], [410, 416, 885], [910, 494, 500], [535, 857, 863]]

h = {}
J = {}
for each in embeddings:
    J[(each[0], each[1])] = 1
    J[(each[0], each[2])] = -1
    J[(each[1], each[2])] = 1

response = sampler.sample_ising(h, J, num_reads=100)
dwave.inspector.show(response)

You might wonder why I want to do this — isn’t all we want to solve a problem? Why do we need it solved more than once? There are several reasons.

The first is that ‘solving a problem’ in the D-Wave paradigm means drawing samples from a probability distribution (like tossing a coin). You don’t always get the same answer! So the more problems we can embed the more samples we get. Each embedding gives us a sample, so more at the same time means more samples and therefore a speed-up of a factor of P, where P is the number of simultaneous embeddings we use. So for the example above, since we use 346 embeddings, we sped up the collection of samples by a factor of 346 times! This is a massive speedup — it’s about the difference between a year and a day in compute time.

A second reason is that there is always a small amount of location-specific noise in this type of processor. If I only used, say, qubits 301, 306, and 307 to get samples, in general I will get slightly different statistics than say qubits 591, 596, and 597. If I use many embeddings, the results I get back will tend to average over some kinds of noise, and the overall statistics of the samples will be better.

So not only does this multiple embeddings approach speed things up massively, but it will also improve the quality of the results! It’s worth the little bit of extra work.

Embedding The Four-Vertex Game Graph Into The Same Processor

We can do the same thing when H is the four-vertex fully connected graph. Here’s the most I could squeeze in (this is 219 simultaneous embeddings):

Here’s the code for this one.

from dwave.system import DWaveSampler
import dwave.inspector

sampler = DWaveSampler(solver='Advantage2_prototype2.4')

embeddings = [[897, 386, 392, 892], [1057, 1062, 136, 142], [903, 909, 350, 356], [566, 572, 869, 875], [1121, 1126, 485, 490], [687, 692, 324, 330], [121, 126, 745, 750], [268, 273, 1010, 1016], [99, 105, 961, 966], [1082, 1088, 244, 250], [1033, 1039, 184, 189], [521, 526, 1109, 1114], [110, 115, 853, 858], [514, 1073, 1078, 508], [758, 764, 265, 270], [51, 57, 984, 990], [711, 717, 360, 366], [866, 872, 242, 248], [807, 813, 361, 367], [784, 789, 421, 427], [435, 441, 988, 994], [532, 538, 1085, 1091], [722, 728, 253, 258], [1132, 1138, 473, 478], [1081, 1087, 148, 154], [1027, 196, 201, 1022], [896, 290, 296, 891], [422, 428, 880, 885], [470, 476, 868, 874], [1118, 1123, 209, 214], [279, 285, 986, 992], [266, 271, 830, 836], [1155, 1160, 329, 335], [241, 247, 794, 800], [77, 82, 1128, 1134], [1025, 1030, 520, 525], [771, 776, 289, 295], [387, 393, 964, 969], [867, 873, 362, 368], [1024, 1029, 400, 405], [259, 818, 824, 254], [460, 465, 1012, 1018], [735, 740, 301, 306], [1167, 1172, 293, 299], [1165, 1171, 173, 179], [1141, 1146, 125, 130], [819, 825, 338, 343], [327, 333, 975, 980], [170, 175, 817, 823], [795, 801, 349, 355], [424, 430, 1072, 1077], [544, 549, 1013, 1019], [52, 1080, 58, 1086], [229, 235, 782, 787], [111, 116, 937, 942], [97, 103, 769, 774], [471, 477, 1000, 1006], [760, 766, 445, 450], [87, 93, 996, 1002], [314, 319, 855, 860], [1070, 1075, 220, 226], [133, 139, 781, 786], [89, 95, 1188, 1194], [205, 210, 746, 751], [410, 415, 856, 861], [147, 153, 985, 991], [512, 905, 910, 506], [1093, 1099, 160, 166], [950, 955, 207, 212], [519, 524, 941, 946], [832, 838, 458, 463], [808, 814, 469, 475], [182, 187, 829, 835], [61, 66, 756, 762], [1049, 1054, 484, 489], [927, 933, 375, 380], [1156, 1161, 425, 431], [302, 307, 843, 848], [953, 958, 483, 488], [1169, 1174, 497, 503], [541, 546, 761, 767], [217, 223, 770, 775], [568, 574, 1097, 1103], [122, 127, 841, 846], [677, 682, 480, 486], [230, 236, 878, 883], [518, 523, 845, 850], [172, 177, 1009, 1015], [134, 140, 889, 894], [857, 862, 482, 487], [158, 164, 901, 907], [1142, 1148, 269, 274], [1105, 1110, 101, 106], [149, 1177, 155, 1183], [411, 416, 952, 957], [531, 536, 929, 935], [1045, 1050, 112, 117], [1034, 1040, 256, 261], [676, 681, 384, 390], [1058, 1063, 232, 238], [1191, 1197, 365, 371], [291, 297, 963, 968], [1153, 1158, 137, 143], [181, 186, 757, 763], [1036, 1042, 448, 453], [1106, 1111, 197, 202], [783, 788, 325, 331], [567, 573, 1001, 1007], [193, 198, 734, 739], [1117, 1122, 113, 118], [569, 575, 1193, 1199], [962, 967, 219, 225], [553, 559, 797, 803], [674, 679, 228, 234], [974, 979, 231, 237], [785, 790, 505, 511], [893, 898, 494, 500], [1190, 1196, 281, 287], [915, 921, 339, 344], [132, 138, 673, 678], [1130, 1136, 257, 262], [723, 729, 337, 342], [98, 104, 877, 882], [326, 332, 879, 884], [565, 571, 809, 815], [277, 283, 806, 812], [1092, 1098, 88, 94], [85, 91, 804, 810], [902, 908, 278, 284], [736, 741, 397, 402], [564, 570, 713, 719], [206, 211, 854, 859], [75, 80, 912, 918], [388, 394, 1060, 1065], [1178, 1184, 245, 251], [159, 165, 997, 1003], [423, 429, 976, 981], [747, 752, 313, 318], [1061, 1066, 496, 502], [109, 114, 733, 738], [545, 550, 1133, 1139], [543, 548, 917, 923], [938, 943, 195, 200], [1095, 1101, 364, 370], [84, 90, 708, 714], [1059, 292, 1064, 298], [700, 706, 432, 438], [1047, 1052, 316, 321], [76, 81, 1008, 1014], [529, 535, 773, 779], [686, 691, 216, 222], [796, 802, 433, 439], [135, 141, 973, 978], [1094, 1100, 280, 286], [533, 539, 1157, 1163], [689, 694, 504, 510], [1108, 1113, 401, 406], [1107, 1112, 305, 310], [1129, 1135, 185, 190], [965, 970, 495, 501], [772, 777, 385, 391], [999, 363, 1005, 369], [1179, 1185, 353, 359], [1071, 1076, 328, 334], [1154, 1159, 233, 239], [145, 151, 793, 799], [712, 718, 468, 474], [737, 742, 493, 498], [194, 199, 842, 847], [951, 315, 956, 320], [1046, 1051, 208, 213], [928, 934, 459, 464], [699, 705, 348, 354], [1035, 1041, 340, 345], [998, 1004, 243, 249], [161, 1189, 167, 1195], [436, 442, 1096, 1102], [267, 272, 926, 932], [675, 680, 288, 294], [916, 922, 447, 452], [1048, 412, 1053, 417], [1026, 124, 129, 1021], [1143, 1149, 377, 382], [157, 163, 805, 811], [1120, 1125, 413, 418], [399, 404, 940, 945], [724, 730, 457, 462], [123, 128, 949, 954], [65, 71, 1176, 1182], [144, 150, 697, 703], [183, 188, 925, 931], [1119, 1124, 317, 322], [1131, 1137, 341, 346], [48, 54, 696, 702], [554, 560, 881, 887], [552, 558, 701, 707], [146, 152, 865, 871], [831, 837, 379, 374], [1068, 1074, 64, 70], [49, 55, 792, 798], [1083, 1089, 352, 358], [50, 56, 864, 870], [156, 162, 709, 715], [710, 716, 240, 246], [1192, 1198, 437, 443], [169, 174, 721, 727], [53, 59, 1164, 1170], [72, 78, 684, 690], [759, 765, 373, 378], [939, 303, 944, 308], [515, 1181, 1186, 509], [74, 79, 828, 834], [1011, 381, 376, 1017], [1028, 304, 309, 1023], [748, 753, 409, 414], [513, 977, 982, 507], [555, 561, 989, 995], [688, 693, 420, 426], [86, 92, 900, 906]]

h = {}
J = {}
for each in embeddings:
    J[(each[0], each[1])] = 1
    J[(each[0], each[2])] = 1
    J[(each[0], each[3])] = 1
    J[(each[1], each[2])] = 1
    J[(each[1], each[3])] = 1
    J[(each[2], each[3])] = 1

response = sampler.sample_ising(h, J, num_reads=100)
dwave.inspector.show(response)

By the way, the D-Wave problem inspector visualizer is AWESOME, super useful!

Data From Running the D-Wave Quantum Computer on All Unique Terminal States For Both Three- and Four-Vertex Graphs

Here’s some quantum computer data!!!

These are python pickle files so just download them and open them using

with open(path_to_downloaded_file, "rb") as fp:
     results = pickle.load(fp)

They each contain a dictionary whose keys are the unique terminal states as strings, and whose values are a three-item list: [correlation matrix with zeros on the diagonal, influence, a list of N=1,000 samples from hardware].

Here is the three vertex data for the 27 unique terminal states of the three-vertex game graph, and here is the four vertex data for the 729 unique terminal states of the four-vertex game graph.