Methods and systems to find a solution to a maximum independent set problem of a graph

A method to find a solution to a maximum independent set problem of an input graph (12) comprising main nodes (201-205) and main edges (211-216) directly connecting said main nodes, the method comprising:

• using a processing unit for rearranging said input graph onto a 3D orthogonal grid comprising grid edges (230) and grid nodes (220), wherein each main node of the input graph is arranged on a grid node such that no two nodes have the same coordinates, thereby resulting in a rearranged graph (13);
• using the processing unit for determining, in the rearranged graph, for each pair of main nodes (202, 204) that are directly connected by a main edge (214), an ancillary path between said main nodes, using a pathfinding algorithm, wherein said ancillary path is arranged along grid edges, such that ancillary paths do not cross each other;
• using the processing unit for generating an augmented 3D graph (14) by adding, along each ancillary path of the rearranged graph (13), an even number of ancillary nodes (221-224);
• using an optical trapping means for producing a 3D array of neutral atoms comprising main atoms and ancillary atoms arranged to reflect said augmented 3D graph (14) wherein,
• the main atoms have a same resonance frequency and the ancillary atoms have a same initial resonance frequency identical to the resonance frequency of the main atoms;
• the main atoms are arranged at positions that reflect the positions of the mains nodes;
• the ancillary atoms are arranged at positions that reflect the positions of the ancillary nodes;
• any distance between ancillary atoms reflecting directly connected ancillary nodes is inferior or equal to a Rydberg blockade radius of said neutral atoms;
• any distance between an ancillary atom and a main atom reflecting an ancillary node and a main node that are directly connected is inferior or equal to the Rydberg blockade radius of said neutral atoms;
• any distance between ancillary atoms reflecting indirectly connected or unconnected ancillary nodes is superior to a Rydberg blockade radius of said neutral atoms;
• and
• any distance between an ancillary atom and a main atom reflecting an ancillary node and a main node that are indirectly connected or unconnected is superior to the Rydberg blockade radius of said neutral atoms;
• using laser emitting means for applying a light shift pulse to the ancillary atoms in order to introduce at least one predetermined detuning of the resonance frequency of the ancillary atoms, so that each ancillary atom has a detuned resonance frequency that is different from the resonance frequency of the main atoms;
• using the laser emitting means for applying a driving light pulse to all main atoms and all ancillary atoms during a predetermined driving time, wherein the driving light pulse has a Rabi frequency parameter and a frequency with a detuning with respect to the resonance frequency, and wherein the Rabi frequency parameter, the detuning, and the predetermined driving time are configured to drive the 3D array of neutral atoms towards a predetermined final state, wherein the driving light pulse is configured to excite at least one of the main atoms to a Rydberg state;
• and
• using a detection unit for detecting, in said predetermined final state, the main atoms that have been excited by the driving light pulse in order to obtain an independent set of the input graph, the independent set being an approximate or exact solution to the maximum independent set problem of the input graph.