Optimizing sensor placement for water leak detection

[Re]generative Quantum Challenge

In the context of the Blaise Pascal [re]Generative Quantum Challenge, from which Sigma Reply teams ranked among the 10 finalists, we proposed a solution to find an optimal placement of sensors within a water distribution network to efficiently detect leaks. Our approach leverages the unique properties of quantum mechanics, especially neutral atoms, for the maintenance and repair of urban infrastructures.


The challenge

Pipeline network is a fundamental element for ensuring the transportation of water, gas, oil and liquids. In many domains, they are the backbone to ensure infrastructure purpose and safety thought cities for water distribution, in nuclear power plants for cooling systems, or at the core of datacenters to name a few. However, over time, construction faults, corrosion, or external pressure can lead to leaks, resulting in the loss of valuable resources, environmental damage, and high repair costs. In addition, the absence of early and accurate detection can exacerbate the damage, making subsequent repairs even more costly and labor-intensive.

Pinpointing these leaks is challenging due to the vastness of underground networks and the complexity of piping systems.

The solution

Optimizing sensor placement


Thus, the problem can be resumed as follows: finding the best placement of sensors in a water distribution network. Imagine a map with several points of interest connected by lines. Each point has a certain "risk value," and you have a limited number of labels you can place on these points. Your goal is to cover the map as efficiently as possible with these labels, focusing on the most important points.

The best placement of these labels is what we call a Maximum Weighted Independent Set, which is nothing more than the most important points, but not too close to each other. It's a bit like choosing the best seats in a theater to get an optimal view without blocking others' views.

Instead of deciding everything at once, we proceed in multiple steps: at each step, we remove some less important points from the map and recalculate to adjust the positions of the remaining labels, seeking to maximize the coverage of the map.

So why quantum computing?


Imagine having to cross the Atlantic on a boat. To guide yourself, you can either rely on a GPS that instantly and precisely locates you, or you can navigate using a paper map and a compass. The second option will get you somewhere, but not necessarily where you want to go. For computers, exploring a problem is like crossing the ocean. Without sufficiently advanced tools, they can get lost.

Therefore, the usage of a quantum computer turns out to be relevant when it comes to solving this kind of problem. In fact, by relying on neutral atoms we managed to extract properties that natively guide us to the best solution with computational advantage and less energy consumption.

Outlook

Even though our solution is ideal for finding the best placement of sensors in a water distribution system, it can be used in other use cases that involve placement of elements. As an example, finding the best localization of retail stores in a city, or the maximal coverage of antenna in a telecommunication network.

Problem of retail stores placement

Resource allocation and planning problems in telecommunications

Vaccination center's locations to manage a health crisis

Watch the video

[1] Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in physics, 2, 5.
[2] Speziali, S., Bianchi, F., Marini, A., Menculini, L., Proietti, M., Termite, L. F., ... & Delogu, A. (2021, October). Solving sensor placement problems in real water distribution networks using adiabatic quantum computation. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) (pp. 463-464). IEEE
[3] Martin J. A. Schuetz Christian B. Mendl Helmut G. Katzgraber Jernej Rudi Finˇzgar,Aron Kerschbaumer. Quantum-informed recursive optimization algorithms, 2023
[4] Alexandra de Castro. Quantum computing in the roadmap to greener calculations.
[5] Jonathan Wurtz, Pedro L. S. Lopes, Nathan Gemelke, Alexander Keesling, Shengtao Wang. Industry applications of neutral-atom quantum computing solving independent set problems.


  • strip-0

    Sigma Reply is the Reply group company offering answers in the field of Quantum Computing. We support the business to adapt to this new revolution and deliver cutting-edge solutions to a wide range of problems faced by the industry, i.e. combinatorial optimisation, encryption and security, machine learning, simulation processes, chemistry and strategic consulting for Quantum adoption and implementation.

Contactez-nous

Before filling out the registration form, please read the Privacy notice pursuant to Article 13 of EU Regulation 2016/679
Invalid Input
Invalid Input
Invalid Input
Invalid Input
Invalid Input
Invalid Input

Privacy

I declare that I have read and fully understood the Privacy Notice and I hereby express my consent to the processing of my personal data by Reply SpA for marketing purposes, in particular to receive promotional and commercial communications or information regarding company events or webinars, using automated contact means (e.g. SMS, MMS, fax, email and web applications) or traditional methods (e.g. phone calls and paper mail).