Solving optimization problems
with neutral atoms

Analog processors based on neutral atoms can solve optimization problems relevant to a range of industries. The most natural optimization problem to solve on these processors 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).

Finding the Maximum Independent Set

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.

Rydberg blockade
Left: A maximal set of excited atoms, constrained by the Rydberg blockade.
Right: Highlighted in red: a maximal independent set of a graph (a maximal subset of vertices, so that none of the vertices share an edge).
Industrial Applications of MIS
Antenna placement (Maximum Independent Set)
Maximizing coverage of telecom services requires a placing a high density of antennas in a given space. Signal interference, however, introduces a constraint to this problem: coverage areas cannot overlap, and standards for minimal distances between antennas are often regulated by the government. Among all possible location sites (blue), the optimal choice of antenna placements corresponds to a maximum independent set, where no two coverage areas overlap (red).

This problem can be further elaborated; by maximizing ‘weights’ attached to each antenna representing, for example, total area or number of customers covered. The same concepts can also be extrapolated to other related problems, such as sensor-placing for IoT applications or footprint optimization for the location of stores or distribution centers.

An efficient solution

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.

Portfolio optimization (Maximum clique)
In the financial industry, optimization of portfolios of assets, such as stocks or bonds can increase returns. In general, MISs and their complement, maximum cliques, are useful for generating nontrivial insight into the correlation properties of any large datasets. This can inform the pursuit of strategies for hedging and diversification.

One can create a ‘market graph’, where stocks correspond to vertices and vertices are connected when their correlations θij exceed a threshold Θ.  For example, setting θij<Θ<0 and looking for graph cliques generates collections of assets mutually anti-correlated, maximizing returns while minimizing risk. Cliques obeying the opposite limit  θij>Θ>0 generate portfolios of positively-correlated assets whose prices follow each other, as may happen for assets within a same market.

Encoding a wide range of optimization problems

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:

  • Maximum Clique
  • Maximum vertex cover
  • Minimum dominating set
  • Graph coloring

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

  • Quadratic Unconstraint Binary Optimization (QUBO)
  • Integer factorization

Through clever encodings, these problems can also be translated to MIS problems  on larger graphs, scaling at most quadratically in the number of qubits.

5G Networks (Minimum Dominating Set)
5G architectures are applied for device to device (D2D) communication networks between cellphones or network-connected cars and more. Examples include phones in a crowd at a concert or in dense traffic on a highway. Nodes may communicate with each other using short-range protocols (e.g., Bluetooth), as when adjacent autonomous cars communicate. In contrast, they may also communicate with the broader wireless network of cell towers, as when people upload of pictures of the concert. Connecting every single node to the broader network of cellphone towers, however, may overload them.

To circumvent this problem, one can choose a subset of nodes to serve as the gateway nodes and connect only those with the cell network. Every other node in the area may connect to the broader internet through a direct connection to an in-range gateway node, reducing the cell tower bandwidth to a manageable level.

Requiring that every node needs to be a gateway, or within range of a gateway, naturally forms a dominating set constraint on the set of gateway nodes. It is natural to want small dominating sets, which minimize the number of connections to the cell network and thus minimize their load.

Additional examples of industrial applications and details on how to encode them in Rydberg atoms can be found here.