Tackling graph-based problems with Pasqal and Nvidia technology

Finding the most efficient and safest route for drones while delivering goods, understanding user interactions on social media, and investigating chemicals for toxicity prediction are entirely different problems. However, they all share an interesting feature: they are best represented by graphs.

 

A graph is a simple drawing composed of dots (called nodes) and lines (called edges), where the nodes represent entities, and the edges represent the relationships between the entities. Let’s take the drones’ logistic problem as an example. In this case, the nodes represent targets for delivery and the edges represent the routes linking these targets. Using graphs to find an efficient route and optimizing the arrival time to their destination can significantly decrease resource costs and carbon footprint​.

 

 

 

 

Indeed, a drawing with dots and lines offers a clever way to visualize and understand relationships between entities; however, tackling graph-based problems is more complex than it sounds. Graph-based data can be tremendously challenging to manipulate: the number of options that need to be considered can be huge, and the relationships between entities can be intricate.

 

 

 

 

Over the years, researchers have explored classical machine learning algorithms to tackle graph-based problems with a certain degree of success. Still, these methods are very costly and exhibit several limitations. At PASQAL we are introducing a novel hybrid quantum/classical algorithm for graph machine learning that is showing many promising advantages over classical methods effectively learning and extracting information from graph structures.  

 

Finding an efficient and reliable computational method to handle graphs

 

Widely used classical computational methods to process information from graphs usually evaluate their local properties; that is, these methods look at each node and their interaction with their immediate neighbors. A critical drawback of this approach is that essential global information may be lost, and different graphs may be considered the same graph. This is crucial, for example, when understanding the chemistry of a molecule. In that case, global structure of the molecule is related to function in a biological process in a cell. Another drawback is that these techniques may encounter serious difficulties when the graph comprises nodes characterizing different features (heterophilic data). For example, when nodes represent distinct kinds of people connecting, such as sellers connecting with buyers in a market under study.

 

 

 

The ideal scenario is to be able to represent all the nodes and their relationships in the entire graph or parts of it so that each node and edge is assigned a unique representation. The research community has recently proposed novel classical methods that help reach beyond the nearest neighbors called Graph Transformers. The problem with these novel classical techniques is that they rely on a vast amount of data and time for training, making this method extremely expensive. A less expensive alternative has been proposed within this method, but again, losing important global features of the graphs.

 

Hybrid quantum/classical computing for graph machine learning 

 

The rapid development of quantum computers in recent years provides the opportunity to investigate new ways of tackling graph-based problems. At PASQAL, we have been able to represent graphs in a tremendously efficient way using the analog approach to quantum computing. We combine our quantum techniques with state-of-the-art classical machine learning architectures by incorporating the output from our quantum system into a classical Graph Transformers algorithm. With our technology, we can investigate global structural features of graphs that would be otherwise intractable by classical methods only. Furthermore, our hybrid approach holds the potential to enhance the model’s quality, reduce training and time, and decrease energy consumption while benefiting from the power of NVIDIA’s Tensor Core GPUs.

 

“The importance of this study is that we are competing—and sometimes beating—with the state-of-the-art graph machine learning approaches,” says Loic Henriet CTO at PASQAL. “The method we are proposing is one of the first that truly highlights the power of the hybrid quantum/classical with strong classical participation and with the quantum part boosting the model, which is aligned with the current developments of quantum computing.”

 

“The rapid development of quantum solutions is reshaping ways to investigate increasingly complex graph-based problems,” said Timothy Costa, Director of High Performance Computing and Quantum at NVIDIA. “PASQAL’s novel hybrid quantum-classical algorithm and quantum processors, coupled with NVIDIA Tensor Core GPU acceleration in graph machine learning, could unlock a new age of quantum graph-based research.”

 

In a new paper shared in the arxiv , we explain our novel methods in detail and compare our hybrid quantum/classical technique to other classical-only methods using seven datasets—including extensive datasets—that are standard to compare the performance of computational models. Our results match in accuracy the top classical methods, surpassing many of the widely used classical algorithms.

 

The success of our method depends on the right choice of the classical architecture. For this reason, we selected NVIDIA’s Tensor Core GPUs, which can significantly reduce the time and resources required for graphs-based calculation, compared with high performance computers based on CPUs. The parallel architecture of GPUs is more efficient at handling the necessary computations to tackle graphs-based problems with quantum and classical methods, where we need to deal with large matrices and train neural networks with extensive datasets.

 

For the quantum computing phase, we leverage the natural capacity of neutral atom quantum computing to emulate the position of all nodes and their relationships in entire graphs or essential parts of them.

 

In the following section, we’ll show that a neutral atom quantum processing unit is the natural technology to represent graph-based problems.

 

Graph-based problems recreated in neutral atom devices

 

Neutral atoms quantum devices use highly focused lasers, so-called optical tweezers, to trap and manipulate neutral atoms individually to create 2D and 3D arrays in arbitrary configurations. In these architectures, each qubit is represented by a two-level atomic energy state, usually a ground state and a Rydberg state, a very high energy state. In the Rydberg state, the atoms are polarized, inducing van der Waals interactions.

 

Combining these two neutral atom devices’ features, the ability to create arbitrary geometries in 2D or 3D with the qubits and the use of programmable interactions between these qubits makes our platform the ideal setting to represent and extract essential information from graphs-based problems. With this technique, each qubit represents a node in the graph and their Van der Waals interactions represent the relationships between the nodes, or the edges, via a mechanism that forbid two atoms to be in the Rydberg state simultaneously if they are too close to each other, a phenomenon called Rydberg blockade.  Moreover, Van der Waals-type interactions are characterized by a sharp decay with the distance between qubits, allowing us to neglect second (and further) neighbor interactions, enabling us to mimic the connectivity of graph nodes with good precision. In this way, the system directly represents graph structures, and we can tackle graphs-based problems using analog or digital-analog methods.

 

With our quantum method, we extract essential features from each graph, otherwise intractable, preserving its structure and avoiding the introduction of explicit ordering or labelling of the nodes and edges. Let’s take, for example, molecular dynamics, which is the basis for drug discovery and toxicity prediction. In this case, our quantum approach is able to evaluate the presence and precise structure of cycles in a molecule.

 

 

Graph machine learning with quantum methods outlook

 

Graph-based problems are intrinsic to many scientific, engineering, and real-world scenarios. They are used to understand social networks, satellite deployment, and molecular processes in drug discovery. The ability to extract graphs’ structure with their underlying, often intricate, relationships between entities offers a fertile ground for innovative hybrid quantum/classical computational approaches.

 

This year, enterprises are starting to use PASQAL quantum processors, one of the world’s first commercially available quantum processors, together with our NVIDIA GPU cluster, to run tasks for industrial and scientific applications using graphs. These enterprises are finding optimal ways to smart charge electric cars, understanding materials for designing batteries, and for urban traffic optimization, as you read this blog. We will post about all these implementations on our commercial quantum device soon. Stay tuned!

 

References

 

• Slimane Thabet, Romain Fouilland, Mehdi Djellabi, Igor Sokolov, Sachin Kasture Louis-Paul Henry, and Loïc Henriet. (2023). Enhancing Graph Neural Networks with Quantum Computed Encodings. Available at: https://arxiv.org/abs/2310.20519

• Henriet, L. et. al. (2023). Graph algorithms with analog neutral atom quantum processors. In preparation.

 

Would you like to learn more about these techniques on a neutral atom quantum computer? Get familiar with quantum computing, our platform, and algorithms with Quantum Discovery.