Identifying the best business applications for neutral atom quantum computers

New research from Capgemini’s Quantum Lab focuses on both industry challenges and quantum computing theories to define practical, scalable and cost-efficient applications for neutral atom quantum computers.

Neutral atom quantum computers are pushing the boundaries of quantum computing, allowing for more complex and higher-quality calculations. Exploring their potential and the most impactful use of this emerging tech is multifaceted and requires an understanding of its technological capabilities, industry-specific expertise, and a mastery of the quantum computing theory. Capgemini’s recent investment in Pasqal, a pioneer in quantum computing, known for creating innovative quantum processors using neutral atoms arranged in 2D and 3D structures, demonstrates the growing interest in the application of quantum computing to deliver clear business value. How do we move from the abstract and theoretical, and how exactly do we evaluate what may or may not be a good application?    

A good methodology to evaluate what good applications look like 

To evaluate whether an application is suitable for neutral atom quantum computers, one must consider the end-to-end algorithm, considering both classical and quantum calculations. For example, neutral atom quantum computers, when running in analog mode, solve a specific mathematical problem. That is to say that it finds a maximum independent set (MIS) [see definitions] in a unit disk graph (UDG) [see definitions]. Finding an MIS in a UDG means identifying the largest possible group of nodes within the graph that are not directly connected to each other by an edge, see Figure 1. The class of combinatorial optimization problems, however, is a lot bigger than just the class of MIS problems on a UDG. This means that not all combinatorial optimization problems can be solved by the neutral atom quantum computer natively. The problems must be mapped to a form that can be solved by the neutral atom quantum computer. This can add significant computational costs, which cannot be neglected but sometimes are. The result of cutting these costs can drastically favor the quantum computer, which is unfair. That is why end-to-end considerations must be made.  

Let’s look at an example as applied to banking. The mathematical problem of optimizing a portfolio of financial assets to minimize risk, called portfolio optimization, can be translated into a maximum clique problem [see definitions], which is equivalent to the MIS of the complement graph [see definitions], i.e., the graph where the nodes are connected if, and only if, they are not connected in the original graph. This complement graph is going to be very dense when starting from a sparse graph. In general, that means the complement graph is difficult to encode on a neutral atom quantum computer due to the physical constraints of a neutral atom quantum computer. The cost of mapping and scaling in comparison to classical systems, in addition to the overall integration of classical and quantum processes, are critical factors to assess. 

Within Capgemini’s Quantum Lab, we have begun two research projects to assess the suitability of neutral atom quantum computers for different applications. The first looks at how to map a problem so it can be run on a neutral atom quantum computer. As these computers can only solve a very specific class of problems – an MIS on a UDG – the challenge is to translate a business problem into an MIS on UDG in order to understand how commercial value can be derived. Several methods exist for this. One of which is a method published by QuEra that translates any MIS problem on a graph to an MIS problem that can be run on a neutral atom quantum computer.¹ The challenge with this approach is that it can lead to high overhead and only works if the quantum computer is able to find exact solutions. 

But do users always need exact solutions? Most of the time, the answer is no. A parcel delivery service does not need to know the exact best route. They just need a good route before the day starts. Even if there exists a route that improves the solution by 0.001%, that might not be worth spending hours or even days of compute power. 

That is why, in the second research project, we are considering the scaling of the quantum solutions compared to classical approximate optimization solvers. By using QUARK, an open-source benchmarking framework created by software engineers at BMW and an ever-growing community,² we will create random (unit-disk) graphs and let both the approximate classical algorithm and the (simulated) neutral atom quantum computer attempt to find large independent sets. Then, we measure the (estimated) runtime and quality of the solutions and extrapolate. The goal is to find structures of graphs where the classical methods suffer, but the quantum computer is still able to provide large independent sets.  

Finally, we will combine the two research projects and define a methodology to assess the potential of neutral atom quantum computers. We will focus on specific business problems, and we will consider the whole (end-to-end) algorithm. This includes translating it into a suitable format for the quantum computer, running the quantum algorithm, and interpreting and validating the results. We will compare the performance of a hybrid (quantum-classical) pipeline with a purely classical one. Factors such as accuracy, speed, scalability, and computational (classical) cost will all be considered. This will help us identify the domains and scenarios where neutral atom quantum computers can offer a significant advantage over classical methods. It will also reveal the challenges and limitations that need to be overcome to realize their full potential. 

Where to look for good applications 

So, where do we start to find these applications to assess? Assessment generally begins with either a technology or industry approach. Typically, quantum computing companies start with the technology because they focus first on what they know about quantum computers. Let’s take a deeper dive into this and look at three problem formulations: maximum independent set, graph coloring [see definitions], and minimum vertex cover. 

Using a technology approach to find applications 

Maximum independent set 

It is natural to start with the maximum independent set problem on the unit disk graph that’s been mentioned previously. The goal of the MIS problem is to find the largest set of nodes in a graph that have no connection to each other. An application of this mathematical formulation, for example, is finding the best placement for antennae so that their signals do not interfere with each other. The challenge, though, is to reframe other problems in a similar way. For example, one could try to formulate a traffic optimization issue as an MIS by creating an abstract graph where traffic routes are nodes that share an edge where the routes share a road. The challenge is that this very specific traffic problem is mapped to MIS-UDG, potentially creating high overhead results in the need for more and better qubits to find a solution. These extra qubits don’t contribute to solving a ‘larger’ problem; they are only necessary to map the problem. Furthermore, solutions to the mapped problem might not be actual solutions to the actual problem. This is especially true for the approximate solutions to the mapped problem.  So our challenge is to find formulations of business problems that fit MIS as close as possible. 

Sometimes, the problem does not require finding one set of nodes but many sets of nodes that are all independent of each other. An example of this would be planning in a production plant, where different tasks can happen at the same time, but not two tasks that require the same resource (e.g., a specialized machine). In this case, the solution to the planning problem is a collection of sets of nodes that don’t share edges. This is an example of graph coloring, wherein a specific color is assigned to all nodes, such that no two connected nodes have the same color as depicted in the figure above. 

To find a coloring with a neutral atom quantum computer, the problem once again has to be translated into an MIS problem. There are multiple ways to then solve the problem, but they mostly rely on the fact one color is an independent set and that the optimal coloring contains large independent sets. With a classical optimizer and the results from the quantum computer, a classical computer can find a “good” coloring with high probability.³ To reinforce this approach, Capgemini’s Quantum Lab built a demonstration that solves a planning problem using neutral atom computers: Link to Demo

Minimum vertex cover 

In some cases, you do not want all solutions to be independent from each other; rather, you want every node to be connected to at least one other node in a set. A good use case would be immunization, where not everyone needs to be inoculated to stop transmission. Instead, those who are not inoculated need to be surrounded by those who are immune, as seen in the figure from Wurtz et al.⁴. This is called a minimum vertex cover problem. Luckily, the problem is equivalent to the MIS-problem. The opposite of a maximum independent set is a minimum vertex cover. Thus, a neutral atom quantum computer can assist in finding a solution. A challenge now is that usually, the minimum vertex cover only becomes interesting in large graphs. For example, a healthcare organization developing an immunization strategy for a country would require a minimum vertex cover on a graph of millions of nodes. That is much larger than can be embedded on the neutral atom computers.  

The risk in taking a technology-approach, is that the focus in on the specific tool (quantum computing) may lead to proposing cumbersome algorithms, like in the traffic optimization example above. A mathematician might view ‘a constant overhead’ as a small problem, but in practice, this might make the quantum approach unfeasible. Furthermore, focusing on the technology may push to ignore other possible solutions through classical computing. 

Using an industry approach to find applications 

Good applications of neutral atom quantum computers can also be discovered by leveraging industry expertise, which is the most common approach for industry leaders. However, focusing solely on bespoke challenges within specific industries and then trying to fit in quantum technology as an afterthought could risk not taking ample account of the technological constraints. This is why ‘quantum Gen AI’, ‘massive parallel computing’, and ‘quantum big data’, make no sense from a technology perspective. 

A more refined industry approach in the context of neutral atom quantum computing is to look for optimization problems in an industry (e.g., known NP-hard problems) and see if there exists a way to transform them to MIS on UDG. However, this method also has a flaw, albeit more subtle and often overlooked, which is that there could be a structure in the problem that could be exploited by classical computers. This exploitation can result in a good (sometimes approximate) solution in sub-exponential time with a classical computer, which means that the problem is solved. In these cases, trying to tackle a problem with a quantum computer will almost certainly not result in the favorable performance for the quantum computer. While this might result in solving their problem, there might not be a quantum advantage.  

Capgemini’s Quantum Lab approach 

Given that the technology approach often overlooks the industry’s needs and that the industry approach often overlooks the technological constraints (of classical and quantum computers), there is a chasm between the two worlds. Capgemini’s Quantum Lab tries to bridge that gap by explicitly looking for classically hard problems where a solution will deliver value. Capgemini’s strong industry expertise and close relationship with industry leaders allows us to test our applications continuously.  

Closing 

In conclusion, the journey to finding good applications for neutral atom quantum computers is iterative and collaborative. It requires a deep dive into both industry challenges and quantum computing theories, with a focus on practicality, scalability, and cost-effectiveness. While the use cases are not fully known, ongoing research and collaboration between industry and quantum computing experts are vital for uncovering them. Establishing a robust ecosystem is crucial for the development and identification of practical quantum applications. The partnership between Capgemini and Pasqal exemplifies the commitment to this exploration and the promise it holds for the future of computing. 

Definitions

• Maximum independent set problem: The maximum independent set (MIS) problem is a combinatorial optimization problem that asks for the largest subset of nodes in a graph such that no two nodes in the subset are adjacent. This problem has applications in various domains, such as wireless network design, social network analysis, and bioinformatics. However, finding the maximum independent set of a large graph is computationally hard, and classical algorithms may take exponential time to solve it. Neutral atom quantum computers offer a potential speedup for this problem by exploiting the dynamics of the Rydberg blockade.
• Rydberg blockade: The Rydberg blockade is a quantum phenomenon that arises when atoms are excited to a highly excited state called a Rydberg state. In this state, the atoms have a very large electric dipole moment and experience a strong dipole-dipole interaction. This interaction creates an energy shift that depends on the interatomic distance and the angular momentum of the Rydberg state. As a result, two atoms cannot be excited to the same Rydberg state within a certain distance, which is called the blockade radius. Thus, the excitation of one atom to a Rydberg state blocks the excitation of nearby atoms. This effect can be exploited to create entanglement and implement quantum gates between atoms. 
• Unit disk graph: A unit disk graph (UDG) is a type of geometric graph where the nodes represent points in the plane, and two nodes are connected by an edge if and only if the distance between them is at most one. UDGs can be used to model wireless networks, where each node has a fixed transmission range of one unit. Neutral atom quantum computers can find MISs on a UDG by using the Rydberg blockade, because two atoms cannot be in the Rydberg state at the same time if they are close to each other. 
• Maximum clique problem: The problem of finding the largest subset of nodes in a graph that are all connected to each other. 
• Complement graph: A complement graph of a given graph is a graph that has the same set of nodes but the opposite set of edges. That is, two nodes are connected by an edge in the complement graph if and only if they are not connected by an edge in the original graph. 
• Graph coloring problem: A graph coloring problem is a combinatorial optimization problem that asks for the minimum number of colors needed to assign a color to each node of a graph such that no two adjacent nodes have the same color. Graph coloring problems have many applications in scheduling, map coloring, register allocation, and Sudoku puzzles. Finding the optimal coloring of a graph is NP-hard, which means that there is no efficient algorithm that can solve it in polynomial time for any graph. 

Nguyen, M.-T. et al. Quantum Optimization with Arbitrary Connectivity Using Rydberg Atom Arrays. PRX Quantum 4, 010316 (2023).

Finžgar, J. R., Ross, P., Hölscher, L., Klepsch, J. & Luckow, A. QUARK: A Framework for Quantum Computing Application Benchmarking. 2022 {IEEE} International Conference on Quantum Computing and Engineering ({QCE}) (2022) doi:10.1109/qce53715.2022.00042.

da Silva Coelho, W., Henriet, L. & Henry, L.-P. Quantum pricing-based column-generation framework for hard combinatorial problems. Phys. Rev. A 107, 032426 (2023).

Wurtz, J., Lopes, P. L. S., Gemelke, N., Keesling, A. & Wang, S. Industry applications of neutral-atom quantum computing solving independent set problems. Preprint at http://arxiv.org/abs/2205.08500 (2022).