Analog processors based on neutral atoms can solve optimization problems relevant to a range of industries. The most natural optimization problem to solve is the Maximal Independent Set problem (MIS). The Maximal Independent Set of a graph is the largest subset of vertices such that none of the vertices share an edge. Finding such a set is an NP-hard problem. For general graphs, even approximate solutions may be beyond efficient analysis by classical algorithms. Many industrial problems can be formulated as an MIS problem such as footprint optimization for store locations (see sidebar).
When two neutral atoms that are close to each other are simultaneously excited to Rydberg states, the so-called Rydberg blockade effect can happen, allowing only one atom to reach the excited state. One can use this effect to find the MIS of a graph, by encoding the graph into an array of neutral atoms. This encoding needs to be such that each two vertices of the graph that share an edge correspond to two atoms that are within the Rydberg radius from each other. When the total energy in the system is raised high enough to excite the maximum amount of atoms, the overall system state corresponds to a maximal independent set. One extracts the solution by measuring which atoms are excited and which are not. The set of excited atoms is an MIS. Read more about the Rydberg blockade and computation with Rydberg states.
Solving the MIS problem on a neutral atom processor requires minimal overhead, as it takes advantage of the natural behavior of the atoms. If the graph of interest is a Unit Disk Graph (UDG), one can encode MIS problems with 256 variables on our 256 qubits. For certain graphs, analog neutral atom processors can find MIS efficiently. A comparison with classical simulated annealing, a classical benchmark specifically designed for MIS, shows that the neutral atom processor scales more favorable with the size of the problem for a precisely defined set of graphs. To learn more about the performance and this hardness parameter, read the publication of the result, or this blog post.
Solutions to MIS can give rise to solutions of other, related optimization problems, as described here. Using a range of algorithmic techniques, including quantum sampling, quantum memory encoding, quantum machine learning, variational optimization such as QAA and QAOA, our machines can solve a range of other problems:
The Weighted Maximum Independent Sets of a weighted graph can also be encoded on analog neutral atom quantum computers, by increasing the energy for certain atoms more than others. As described here, this gives rise to further optimization problems
Through clever encodings, these problems can also be translated to MIS problems on larger graphs, scaling at most quadratically in the number of qubits.
Interested in learning more?
- Watch our Nov 21, 2022 Webinar on optimization
- Watch our "Results with QuEra" Mar 7, 2023 on "Quantum optimization with arbitrary connectivity using neutral atoms
- Read our store placement application note
- contact us to discuss your optimization requirements with our world-class solutions team.