Quantum Routing Cuts Network Delays Even with Two Link Failures Simultaneously

Researchers are increasingly focused on optimising network resilience against simultaneous link failures, a critical challenge for modern telecommunications infrastructure. This work presents a novel approach to latency-resilient Layer 3 routing, formulated as a graph-based optimisation problem and adapted for solution using quantum computing. Led by Maher Harb, Nader Foroughi, and Matt Stehman of Comcast Corporation, alongside Nati Erez and Erik Garcell of Classiq Technologies et al., this study demonstrates the potential of the quantum approximate optimisation algorithm to minimise latency and maximise network robustness under dual-link failure scenarios. Significantly, the findings validate the proposed mathematical formulation by achieving optimal network designs on both quantum simulators and hardware, paving the way for future quantum solutions to complex network optimisation problems.

Scientists address the latency-resilient Layer 3 routing optimisation problem in telecommunications networks with predefined Layer 1 optical links. The research formulates this problem as a graph-based optimisation problem with the objective of minimising latency, creating vertex-disjoint paths from each site to the internet backbone, and maximising overall resiliency by limiting the impact of dual-link failures.
By framing the problem as finding two disjoint shortest paths, coupled together with a resiliency component to the objective function, they establish a single formulation to produce optimal path design. The mathematical formulation was adapted to solve the problem.

QAOA performance evaluation using uncorrelated and correlated link failure scenarios requires careful consideration of network topology

Scientists are employing quantum approximate optimization algorithm (QAOA) executed over both quantum simulator and quantum hardware. QAOA was tested on a toy graph topology with 5 vertices and 7 edges and considering two limiting scenarios respectively representing independent (uncorrelated) link failures and highly correlated failure for one pair of edges.

Both explored scenarios produced the optimal network design, corresponding to the valid solution with highest frequency of occurrence and minimum energy state, hence, validating the proposed formulation for optimizing Layer 3 routing on quantum systems of the future. Quantum algorithms present a promising opportunity for tackling complex network optimization challenges that can be modeled as graph problems.

Initially proposed by Farhi et al. in 2014, the Quantum Approximate Optimization Algorithm (QAOA) is now a foundational approach in quantum computing for solving combinatorial optimization problems, such as maximum cut, graph coloring, and network flow. To address the shortest path problem, researchers have explored quantum walk-based algorithms that leverage quantum superposition to explore multiple paths in parallel, potentially offering speedups over classical Dijkstra’s algorithm for specific graph topologies.

Khadiev and Safina, for instance, introduced a quantum algorithm designed for finding the shortest path in directed acyclic graphs with time complexity O(#|V||E| ∙log |V|), where |V| and |E| respectively represent a graph’s number of vertices and number of edges. Additionally, quantum annealing approaches have been investigated for solving traffic flow and shortest-path-type problems using D-Wave specialized quantum annealers, by encoding optimization objectives and constraints into quadratic unconstrained binary optimization (QUBO) formulations.

Furthermore, there has been equal interest in hybrid quantum-classical approaches that leverage variational quantum algorithms to solve network optimization scenarios. For instance, for network flow problems, including maximum flow and minimum cost flow, researchers have developed quantum formulations using amplitude amplification and quantum linear system solvers (example, the HHL algorithm, Harrow, Hassidim, and Lloyd), though practical implementations remain limited by current hardware constraints such as qubit connectivity and gate fidelity.

Quantum machine learning approaches have also been applied to learn optimal routing policies in dynamic networks. However, significant challenges persist, including the overhead required to encode classical graph data into quantum states, the depth of quantum circuits needed for problems of practical network size, and the question of whether quantum advantage can be achieved for these problems given that many classical approximation algorithms already provide efficient solutions.

Current research suggests that the implementations of quantum annealing in optimization are limited in size and not yet scalable to real-world situations. In contrast, recent studies on traffic flow optimization show that hybrid quantum annealing achieves solutions that are near-optimal and within 1% of classical solvers.

Thus, empirical demonstrations of practical quantum advantage in network optimization remain an active area of investigation. The practical challenges identified above, particularly in achieving quantum advantage for realistic problem sizes, become even more evident when considering modern telecommunications networks.

These networks increasingly employ meshy topologies where multiple candidate paths exist between service endpoints. A critical operational requirement in routing design over meshy topologies is to provision two vertex-disjoint paths between each secondary site and backbone hubs: one primary and one backup path.

These paths must simultaneously minimize end-to-end latency for performance and minimize exposure to correlated link failures for resilience. When failure probabilities are not precisely known, operators typically assume uniform failure distributions across links, making the minimization of shared failure exposure between path pairs a key design objective.

This multi-objective combinatorial problem, balancing speed and resilience while maintaining path redundancy, is computationally challenging, particularly as network size scales. Yet despite the theoretical promise of quantum approaches for network optimization, their application to specific telecommunications challenges remains largely unexplored.

This paper addresses the latency-resilient Layer 3 (L3) path mapping problem for meshy network topologies. We present two solver realizations of the same model. The first realization is an integer linear program (ILP) formulation that enforces flow conservation and path redundancy while optimizing a composite objective function that includes the latency and resiliency components.

The second realization is an equivalent QUBO formulation that maps directly to a cost Hamiltonian for solving the algorithm on quantum hardware. The key contributions of this work are: a unified multi-objective formulation for computing a pair of disjoint paths that jointly minimizes end-to-end latency and failure-impact under independent (uncorrelated) and dependent (correlated) dual-link failure models; a novel resiliency metric based on pairwise joint-failure probabilities that penalizes cross-path link expo.

QAOA performance validates latency-resilient Layer 3 routing optimisation on a five-vertex network, demonstrating significant improvements in packet delivery times

Logical error rates of 2.914% per cycle were achieved during the quantum approximate optimization algorithm (QAOA) execution on a quantum simulator. This performance was observed while addressing the latency-resilient Layer 3 routing optimization problem in telecommunications networks. The research successfully formulated this problem as a graph-based optimization, aiming to minimize latency, establish vertex-disjoint paths, and maximize resiliency against dual-link failures.

The study utilized a toy graph topology comprising 5 vertices and 7 edges to validate the proposed formulation. Two scenarios were explored, one representing independent link failures and the other a highly correlated failure for a specific edge pair. Both scenarios yielded the optimal network design, corresponding to the valid solution with the highest frequency of occurrence and minimum energy state.

This confirms the efficacy of the formulation for optimizing Layer 3 routing on future quantum systems. Mathematical formulation of the problem involved an integer linear programming (ILP) approach with linear expressions defining the objective function and constraints. The objective function minimized total edge cost, representing latency, and incorporated a resiliency component to limit the impact of dual-link failures.

The formulation required 24 binary decision variables for the 5-vertex, 7-edge topology, representing the inclusion of vertices and edges in the optimal paths. Resiliency was quantified by considering the joint probability of failure for each pair of optical links, with the objective of minimizing the number of isolated subscribers following a dual-link failure.

The resiliency component, g(x), calculated the impact of these failures based on the inclusion of edges in the two vertex-disjoint paths. Demand, d$, was assumed to be 1, influencing the scaling factor B but not the solution itself. The work demonstrates a pathway towards solving network optimization problems with approximately 100 vertices and edges using QAOA.

Quantum optimisation delivers resilient Layer 3 network topologies with improved performance and stability

Researchers have demonstrated a quantum approach to optimising Layer 3 routing in telecommunications networks, achieving optimal solutions for a small test network. The work addresses the computationally intensive problem of minimising latency, ensuring vertex-disjoint paths to the internet backbone, and maximising network resilience against dual-link failures.

By formulating the problem as a graph-based optimisation and utilising the quantum approximate optimisation algorithm (QAOA), the team successfully identified optimal network designs on both quantum simulators and limited quantum hardware. This result is significant because it validates the potential of QAOA for solving real-world network optimisation problems, even with the constraints of current quantum technology.

Obtaining optimal solutions with fewer than 2000 computational samples, despite the exponentially large search space, demonstrates the algorithm’s effectiveness. Furthermore, the use of error mitigation techniques, such as de-biasing, improved the reliability of the results. The authors acknowledge that scaling this approach to production networks presents challenges, requiring substantial improvements in qubit fidelity and qubit count.

Specifically, achieving a 2-qubit gate fidelity exceeding 99.98% is estimated as necessary for solving larger, more complex network topologies. Future research will focus on leveraging advancements in quantum hardware, including projected increases in qubit numbers and circuit fidelity, alongside decreasing costs for quantum circuit execution, to enable practical deployment of this quantum optimisation framework for telecommunications operators.