Quantum Computing Achieves Scalable Multiway Cut Optimisation for Telecommunication Networks

The minimum edge multiway cut problem, crucial for assessing the robustness of telecommunication networks, receives fresh attention in new research exploring the potential of quantum computation. Ali Abbassi, Yann Dujardin and Eric Gourdin, all from Orange Research, alongside Philippe Lacomme of LIMOS – UMR CNRS 6158, Université Clermont Auvergne, and Caroline Prodhon from LIST3N, University of Technology of Troyes, benchmarked solutions using three distinct quantum and classical approaches. The team compared performance on a D-Wave annealer, simulated photonic circuits on Quandela’s Perceval platform, and IBM’s gate-based Approximate Optimization Algorithm (QAOA). This work is significant as it provides a practical comparison of these emerging technologies for tackling complex network resilience challenges, offering valuable guidance on where to focus development efforts for future optimisation workflows.

Researchers assess the comparative feasibility of these approaches for early-stage quantum optimisation, with a particular focus on identifying trade-offs inherent in circuit constraints, encoding overhead, and scalability. Findings suggest that quantum annealing currently delivers the most scalable performance for this class of problems, although photonic and gate-based approaches offer unique advantages in terms of circuit flexibility and potential for future development.

Quantum Approaches to Multiway Cut Problems Researchers have

This research paper presents a comparative study of three different quantum computing paradigms , D-Wave quantum annealing, gate-based QAOA (implemented on a simulator), and photonic variational quantum circuits (simulated using Perceval) , applied to the Minimum Edge Multiway Cut (MEMC) problem. The goal isn’t to demonstrate quantum advantage, but rather to assess the feasibility and identify scalability bottlenecks of each approach. The MEMC problem is chosen due to its relevance to telecom network resilience, where finding critical edges to protect against failure is crucial. The authors use a single QUBO (Quadratic Unconstrained Binary Optimization) formulation of the MEMC problem, allowing for a consistent comparison across the three quantum platforms.

The study identifies limitations in each approach as problem size increases, with D-Wave being the most mature at scale but suffering from embedding overhead, while QAOA and photonic circuits face challenges related to circuit depth and complexity. This paper connects the abstract problem of MEMC to a practical industrial application, providing context for the research and offering a cross-paradigm comparison, one of the first studies to directly compare these three quantum computing modalities on the same problem. D-Wave quantum annealing is currently the most scalable, but limited by the need for minor-embedding, which introduces overhead. Gate-Based QAOA, simulated, offers flexibility but is limited by the exponential growth of state vector size with qubit count, with the depth of the QAOA circuit being a key constraint.

Photonic variational quantum circuits are simulated using a shot-based approach, facing challenges in managing Fock state encoding and optimizing parameters within the photonic circuit. The paper concludes that while quantum annealing currently offers the most mature option at scale, further research is needed to improve the expressiveness of encodings, develop noise-resilient QAOA circuits, and physically deploy photonic models. The study highlights the importance of considering both algorithmic and hardware limitations when evaluating quantum optimization approaches for real-world problems.

Telecommunication Network Resilience Across Quantum Platforms

Scientists have achieved significant results in evaluating the resilience of telecommunication networks by benchmarking the minimum edge multiway cut problem across three distinct computing paradigms. Experiments revealed a consistent problem encoding using a Quadratic Unconstrained Binary Optimization (QUBO) formulation, allowing for direct comparison of each approach’s capabilities. The study focused on quantifying performance metrics for early-stage optimization, with particular attention paid to circuit constraints, encoding overhead, and scalability.

Measurements confirm that quantum annealing currently delivers the most scalable performance for this class of problems, successfully tackling instances where other methods falter. Researchers mapped the QUBO model to an Ising formulation for execution on the D-Wave platform and employed it as the cost Hamiltonian for both QAOA and photonic variational circuits, ensuring a unified approach to problem modelling. Numerical results were obtained on small graph instances, providing detailed insights into annealing behaviour, QAOA convergence trends, and bitstring sampling accuracy within photonic circuits. The team formulated the Minimum Edge Multiway Cut (MEMC) problem, an NP-hard graph partitioning task, with applications in network security and resilience.

Given an undirected graph and a set of k terminals, the objective is to identify a minimum-weight set of edges whose removal ensures no two terminals remain connected. For k equal to 2, the problem reduces to a classical min-cut, solvable in polynomial time, but for k greater than or equal to 3, the problem’s complexity increases significantly. The QUBO formulation incorporates a Hamiltonian with terms enforcing single terminal assignment per node, preventing conflicting terminal overlaps, and accumulating the cost of cutting edges between differently assigned vertices. The effectiveness of the QUBO formulation in translating the MEMC problem into a format suitable for quantum solvers was demonstrated.

The team implemented quantum annealing by mapping the QUBO to an Ising energy function and promoting it to a diagonal quantum Hamiltonian, leveraging D-Wave’s native support for QUBO-based annealing. This approach utilizes minor embedding to address hardware connectivity constraints, allowing the system to evolve towards a minimum-energy configuration representing a low-cost solution. This delivers actionable insights for designing quantum workflows targeting combinatorial optimization in telecom security and resilience analysis, paving the way for more robust and secure communication networks.

Scalability and Performance on Network Resilience Problems

This work presents a comparative analysis of three quantum computing paradigms , quantum annealing, photonic variational circuits, and gate-based QAOA , applied to the minimum edge multiway cut problem, a key challenge in network resilience. Researchers successfully implemented a unified QUBO formulation across all three platforms, enabling a direct assessment of their relative strengths and weaknesses for early-stage optimization tasks. Results demonstrate that, for small problem instances, all methods achieve optimal solutions, establishing a baseline for compatibility and performance. Notably, D-Wave’s quantum annealing approach exhibited the greatest scalability, effectively solving larger graphs despite the overhead associated with embedding the problem onto the hardware. While QAOA and photonic circuits showed promise on toy examples, their performance diminished rapidly as problem size increased, limited by factors such as circuit depth, barren plateaus, and constraints inherent in current photonic encoding methods. The authors acknowledge limitations including the absence of modeled decoherence and photon loss, and suggest future research should explore more expressive encodings like qudit systems and noise-resilient QAOA circuits to further enhance performance and address current constraints.