Patent Description:
In telecommunications, <NUM> is the fifth generation technology standard for broadband cellular networks. In <NUM> networks, the service area is divided into small geographical areas called cells. All <NUM> wireless devices in a cell are connected to the Internet and telephone network by radio waves through a local antenna in the cell. <NUM> networks will have greater bandwidth, giving higher download speeds. To achieve this greater bandwidth and higher download speeds, <NUM> networks are expected to hugely increase network densification. For example, ultra-dense deployment of small cells or Dense Nets (with a few tens of meters inter-site distance) are expected to be one of the main approaches used to reach coverage and throughput requirements.

Root cause analysis (RCA) is a method for identifying root causes of causal chains of events that lead to faults or problems. RCA is a common and recurring task performed by operators of cellular networks. RCA enables a provider to maintain a quality of offered services and minimize or even eliminate root causes of faults in cellular networks.

<NPL>) discloses local vertex measures of entropy and the establishment of properties that vertex entropy must have for identifying critical nodes.

Document <CIT> discloses a method for solving a minimum connected dominating set problem using quantum annealing for distance optimization.

This specification describes methods and systems for root cause analysis in communication networks using quantum computing. In general, one innovative aspect of the subject matter described in this specification can be implemented in a method for root cause analysis in a communication network, the method as defined in independent claim <NUM>.

An additional aspect includes a corresponding system according to independent claim <NUM>.

Advantageous implementations are set out in the dependent claims as appended.

The subject matter described in this specification can be implemented in particular ways so as to realize one or more of the following advantages.

A system implementing the presently described techniques can provide real time analysis of root cause failures in a network and achieve faster fault identification, reduced fault resolution time and improved operational efficiency and stability of the network.

In addition, the real time analysis of root cause failures does not require that each network device is monitored - instead only a subset of network devices needs to be monitored. Accordingly, the computational resources associated with network device monitoring and the logging and processing of alarm data is reduced.

In addition, the presently described techniques are scalable and can be applied to large, dynamic and multi-dimensional networks, e.g., <NUM> networks with billions of devices such as large-scale Internet of Things and Machine to Machine communications.

In addition, a system implementing the presently described techniques can identify root causes of failures in a network without using historical data.

This specification describes techniques for root cause analysis in a complex and dynamic communication network, e.g., a <NUM> network.

A first technique includes determining a subset of network devices for root cause analysis. Under the assumption that an alarm is located at each network device, a quantum computing resource computes a representative subset of network devices by solving for a minimum dominating set or minimum vertex cover of a graph representing the communication network. This subset of network devices is smaller than the complete set of network devices, however, by construction, monitoring the subset of network devices produces information which, when used for root cause analysis, produces accurate and complete results.

A second technique includes performing root cause analysis on alarm data generated by monitoring all or a subset of network devices. The alarm data includes a collection of sets of data, where each set includes data identifying a failing network device and alarms that monitor the failing network device. A quantum computing resource solves for a minimum set cover of the alarm data. The minimum set cover represents a minimum set of root cause devices that triggered the observed alarms. The first and second techniques can be combined or implemented separately.

<FIG> shows a conceptual block diagram of an example classical-quantum computing system <NUM> for root cause analysis of communication networks. The example system <NUM> includes a classical processor <NUM> and quantum computing device <NUM>. The classical processor <NUM> and quantum computing device <NUM> can exchange electronic communications over one or more networks, or can exchange communications in another way, such as over one or more wired or wireless connections.

The classical processor <NUM> is configured to perform classical computations. Generally, the classical computing components included in example system <NUM> can be implemented as one or more classical computers having physical hardware like that described with respect to <FIG>.

The quantum computing device <NUM> is configured to perform quantum computations. For convenience, the classical processor <NUM> and quantum computing device <NUM> are illustrated as separate entities. However, in some implementations the classical processor <NUM> can be included in the quantum computing device <NUM>. That is, the quantum computing device <NUM> can include components for performing classical computing operations. In addition, in some implementations the quantum computing device <NUM> may be a remote system, e.g., external to the system <NUM>, that is in data communication with the classical processor <NUM>.

The system <NUM> is configured to receive network inventory data <NUM> as input. The network inventory data <NUM> includes a list of network devices, e.g., computers, routers, servers, included in a communication network, e.g., <NUM> network <NUM>. The network inventory data <NUM> can further include properties of the network devices in the communication network, e.g., device locations, device connections, a list of alarms that monitor the devices. In some implementations an alarm can be located at each network device.

The classical processor <NUM> includes a network topology generation module <NUM>, a quadratic unconstrained binary optimization (QUBO) formulation module <NUM>, and a post processing module <NUM>. The network topology generation module <NUM> is configured to process the received network inventory data <NUM> to create a network topology for the communication network. Example operations performed by the network topology generation module <NUM> are described below with reference to <FIG>.

The QUBO formulation module <NUM> is configured to determine QUBO formulations of computational tasks to be solved, e.g., a QUBO formulation <NUM> of the task of determining a dominating set, e.g., minimum dominating set, of vertices for a graph included in a network topology created by the network topology generation module <NUM>, a QUBO formulation of the task of determining a vertex cover , e.g., minimum vertex cover, for a graph included in a network topology created by the network topology generation module <NUM>, or a QUBO formulation <NUM> of the task of determining a set cover, e.g., minimum set cover, for alarm data <NUM> received from alarms located at network devices in the <NUM> network <NUM>. Example operations performed by the QUBO formulation module <NUM> are described below with reference to <FIG>.

The classical processor <NUM> is configured to transmit QUBO formulations of computational tasks to be solved to the quantum computing device <NUM>.

In some implementations the quantum computing device <NUM> can be a quantum annealer. A quantum annealer is a device configured to perform quantum annealing - a procedure for finding the global minimum of a given objective function over a given set of candidate states using quantum tunneling. Quantum tunneling is a quantum mechanical phenomenon where a quantum mechanical system overcomes localized barriers in the energy landscape which cannot be overcome by a classically described system. Some quantum annealer devices perform a subclass of quantum annealing called adiabatic quantum computing, which relies on the adiabatic theorem to perform computations.

Quantum annealer devices can solve problems if they are formulated in an acceptable format. For example, quantum annealer devices can solve some QUBO formulations of problems by mapping the QUBO formulation into a qubit network of a quantum annealer device.

In other implementations the quantum computing device <NUM> can be a quantum gate processor. A quantum gate processor includes one or more quantum circuits, i.e., models for quantum computation in which a computation is performed using a sequence of quantum logic gates, operating on a number of qubits (quantum bits).

Quantum gate processors can be used to solve certain optimization problems, e.g., problems that can be formulated as a QUBO problem. For example, some quantum gate processors can solve QUBO problems by simulating a corresponding adiabatic quantum annealing process using a gate model. This can be advantageous, e.g., compared to performing directly the corresponding adiabatic quantum annealing process using a quantum annealer device, since not all quantum annealer devices can realize physical quantum systems that represent an optimization problem. For example, some quantum annealer devices may not provide the physical interactions necessary to solve an optimization problem. In these examples, a Hamiltonian describing the optimization problem can be decomposed into a sequence of single or multi-qubit quantum gates, and a solution to the optimization problem can be obtained through application of the sequence of single or multi-qubit gates on a register of qubits and subsequent measurement of the register of qubits.

The quantum computing device <NUM> is configured to perform the computational tasks specified by the QUBO formulations received from the classical processor <NUM> and to return data representing solutions to the computational tasks, e.g., data <NUM> representing a minimum dominating set of a graph or data <NUM> representing a minimum set cover for alarm data. Example operations performed by the quantum computing device <NUM> are described below with reference to <FIG>.

The post processing module <NUM> is configured to process data received from the quantum computing device <NUM>. For example, the post processing module <NUM> can use data representing a minimum dominating set <NUM> or minimum vertex cover received from the quantum computing device <NUM> to determine a subset of network devices in the <NUM> network <NUM> that corresponds to the minimum dominating set or minimum vertex cover. The post processing module <NUM> can then cause the network devices in this subset to be monitored by requesting alarm data <NUM> from the network devices in the subset. As another example, the post processing module <NUM> can use data representing a minimum set cover <NUM> corresponding to alarm data <NUM> to determine a set of potential root cause devices <NUM> in the <NUM> network <NUM>. Example operations performed by the post processing module <NUM> are described below with reference to <FIG>.

The classical processor <NUM> can provide the set of potential root cause devices <NUM> as output. For example, the classical processor <NUM> can provide the set of potential root cause devices <NUM> to, or can include, a broker that initiates actions based on the output data. For example, the broker can initiate an investigation of the potential root cause devices and determine corrective actions if faults or problems are found.

<FIG> is a flowchart of a first example process <NUM> for root cause analysis in a communication network that includes multiple network devices. For convenience, the process <NUM> will be described as being performed by a system of one or more classical and/or quantum computers located in one or more locations. For example, example system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The system provides a quantum computing resource with input data requesting determination of a subset of network devices in the communication network to be monitored (step <NUM>), e.g., for failure detection. The input data includes (e.g., is generated by the system based on) data representing a topology of the communication network. The topology includes a graph G = (V, E) of vertices V and edges E, where the vertices represent network devices and the edges represent respective connections between network devices. The network topology can provide a physical or logical description of how network devices and communication paths are set up to relate to each other. For example, a physical network topology describes physical connections and interconnections between network devices, e.g., based on physical wires, cables, etc. A logical network topology provides a conceptual understanding of how and why the network is arranged the way it is, and how data moves through it. An example communication network topology is illustrated and described below with reference to <FIG>.

The system can generate the input data based on a local failure-alarm model for the communication network. The local failure-alarm model represents the propagation of triggered alarms in the communication network. More specifically, under the local failure-alarm model, it is assumed that a failure on one network device triggers an alarm on the network device itself and on at least one other network device within a local neighborhood of the network device, e.g., on other network devices directly connected to the network device or within a predetermined number of connections from the network device.

Under the local failure-alarm model, in order to observe a failure event in the communication network, each network device alarm does not need to be monitored. Instead, a smaller number of network device alarms can be monitored. To determine a smaller or smallest set of network devices to monitor such that any failure in the communication network is detected, the system can generate input data that instructs the quantum computing resource to determine either a dominating set, e.g., a minimum dominating set, of vertices for the graph included in the network topology or a vertex cover, e.g., a minimum vertex cover, for the graph included in the network topology, e.g., by generating a formulation of either task based on the data representing the topology of the communication network and in a format that is accepted by the quantum computing resource. Both the task of determining a minimum dominating set for a graph and the task of determining a minimum vertex cover of a graph are NP-Hard problems, which no known classical algorithms can solve efficiently asymptotically.

For example, in some implementations the quantum computing resource may include a quantum computing resource, e.g., an annealer, that is configured to solve quadratic unconstrained binary optimization (QUBO) problems. Therefore, to instruct the quantum computing resource to determine a minimum dominating set of vertices for the graph included in the network topology or a minimum vertex cover for the graph included in the network topology, the system can generate a QUBO formulation of the task of determining a minimum dominating set of vertices for the graph or a minimum vertex cover for the graph based on the data representing the topology of the communication network. The system can then provide the quantum computing resource with input data representing the generated QUBO formulation.

In a QUBO problem, variables take binary values and the objective function is at most a quadratic (second-order) polynomial. Problem constraints are mapped to penalty terms which are added to the QUBO objective function. In cases where the problem constraints include equality constraints, each equality constraint can be included in the QUBO objective function by expressing the constraint as an equation equal to zero, squaring the equation, multiplying the squared equation by a penalty constant and adding it to the QUBO objective function. In cases where the problem constraints include inequality constraints, each inequality constraint can be mapped to a respective equality constraint through the use of slack variables.

For example, let <MAT> and assume an integer variable y takes values in the range <MAT> Let ai ∈ {<NUM>,<NUM>} for <MAT> be binary variables such that <MAT> in which the ai form a binary representation of y. The expression for y given by Equation (<NUM>) automatically satisfies the inequality <NUM> ≤ y in Equation (<NUM>). If M = <NUM>k - <NUM> for some <MAT>, then the inequality y ≤ M in Equation (<NUM>) also holds, and the inequality of Equation (<NUM>) has been accurately mapped to the equality of Equation (<NUM>). However, in general M ≠ <NUM>k - <NUM> for any <MAT> and therefore the RHS of Equation (<NUM>) can take values larger than M. In this case, to enforce the inequality <MAT> another set of binary slack variables of the same size bi ∈ {<NUM>,<NUM>} for <MAT> can be introduced to enforce the equality constraint <MAT> Since <MAT>, it holds that <MAT> and <MAT> in which <MAT>. Therefore, by introducing the two sets of slack binary variables ai and bi, the inequality constraint given in Equation (<NUM>) is satisfied, i.e., <MAT> To summarize, the slack binary variables ai are introduced to handle the ≥ <NUM> inequality, the slack binary variables bi are introduced to handle the ≤ M inequality, and if M = <NUM>k - <NUM> for some k ∈ N the binary variables bi do not need to be introduced.

Techniques for generating a QUBO formulation of the task of determining a minimum dominating set of vertices for a graph or the task of determining a minimum vertex cover for a graph are described below.

The task of determining a minimum dominating set for a graph G = (V, E) is the task of identifying a minimum subset of vertices V̂ ∈ V such that, for each vertex v not in the subset, there exists a vertex u in the subset such that an edge between the vertices v and u exists in the graph G, e.g., <MAT>.

Let N = |V| represent the number of vertices in the graph, let V = {vi:i = <NUM>,. , N - <NUM>} and let <IMG> = {vj: (vi, vj) ∈ E, j = <NUM>,. , N - <NUM>} represent the set of vertices adjacent to vertex vi. The task of determining the minimum dominating set for the graph can then be formulated as the following optimization problem: <MAT> <MAT> where the variables xi take the value <NUM> if the vertex i is in the minimum dominating set and take the value <NUM> otherwise.

The inequality constraints given by Equation (<NUM>) can be mapped to the standard forms: <MAT> in which the RHS of each Equation (<NUM>) is an upper bound. Therefore, the first inequality is constrained through introduction of <MAT> binary variables <MAT> and replacement of the inequality constraint with the equality constraint: <MAT>.

The equality constraints given by Equation (<NUM>) can be added to the objective function given by Equation (<NUM>) above to obtain a QUBO formulation of the task: <MAT> where P » <NUM> represents a penalty constant.

Therefore, to obtain a minimum dominating set for the graph included in the topology of the communication network from the quantum computing resource, the system can generate a QUBO formulation of the task (according to Equation (<NUM>)) using the data representing the topology of the communication network. The system can then provide the generated QUBO formulation of the task to the quantum computing resource for processing. Alternatively, the system can provide the quantum computing resource with the data representing the topology of the communication network and data requesting that the quantum computing resource compute a minimum dominating set for the graph included in the topology. In these implementations the quantum computing resource can generate a QUBO formulation of the task (according to Equation (<NUM>)) using the data representing the topology of the communication network.

The task of determining a minimum vertex cover of a graph G = (V, E) is the task of identifying a smallest set (or "cover") of vertices such that each edge in the graph G has at least one member of the set as an end point.

Let N = |V| represent the number of vertices in the graph, let V = {vi: i = <NUM>,. , N - <NUM>} and let each edge in E be expressed as a set of the two indices of its endpoints, e.g., <MAT>.

The task of determining the minimum vertex cover for the graph can then be formulated as the following optimization problem <MAT> <MAT> where the variables xi take the value <NUM> if the vertex i is in the minimum vertex cover and take the value <NUM> otherwise.

The inequality constraints given by Equation (<NUM>) can be mapped to equality constraints by introducing binary variables bi,j ∈ {<NUM>,<NUM>} and replacing each inequality constraint with a respective equality constraint: <MAT>.

Therefore, to obtain a minimum vertex cover for the graph included in the topology of the communication network from the quantum computing resource, the system can generate a QUBO formulation of the task (according to Equation (<NUM>)) using the data representing the topology of the communication network. The system can then provide the generated QUBO formulation of the task to the quantum computing resource for processing. Alternatively, the system can provide the quantum computing resource with the data representing the topology of the communication network and data requesting that the quantum computing resource compute a minimum vertex cover for the graph included in the topology. In these implementations the quantum computing resource can generate a QUBO formulation of the task (according to Equation (<NUM>)) using the data representing the topology of the communication network.

The system can determine whether to instruct the quantum computing resource to determine a dominating set of vertices for the graph included in the network topology or a vertex cover for the graph included in the network topology based on the assumed failure-alarm model. For example, in implementations where the local failure-alarm model described above is assumed, the system can instruct the quantum computing resource to determine a dominating set of vertices for the graph. As another example, in implementations where a more demanding local failure-alarm model is assumed, e.g., a model whereby a failure on a connection between two network devices (in other words on an edge of the graph) can trigger alarms on the two network devices, the system can instruct the quantum computing resource to determine a vertex cover for the graph.

Returning to <FIG>, the system receives, from the quantum computing resource, data representing a first subset of network devices in the communication network (step <NUM>). The first subset of network devices includes network devices that represent a minimum dominating set of vertices for the graph included in the topology of the communication network or a minimum vertex cover for the graph included in the topology of the communication network (depending on which was requested by the system at step <NUM>). An example minimum dominating set and minimum vertex cover for the communication network topology <NUM> of <FIG> are illustrated and described below with reference to <FIG>.

The system monitors network devices in the first subset of network devices to generate alarm data representing triggered network device alarms (step <NUM>). Under the local failure-alarm model, a failure on a network device in the first subset of network devices will trigger an alarm on the network device. However, a failure on a neighboring network device - which may or may not be included in the first subset of network devices - can also trigger an alarm on the network device.

Therefore, to generate the alarm data, the system can monitor the network devices in the first subset to identify one or more network devices in the first subset with triggered alarms. For each network device in the first subset with a triggered alarm, the system can identify neighboring network devices of the network device based on the topology of the communication network and the assumed local failure-alarm model. For example, the system can maintain a look-up table that stores an alarm-failure relationship for the communication network, e.g., where elements in the look-up table indicate whether an alarm at one network device can be caused by a failure of another network device (and vice versa). The system can query the look-up table to identify neighboring network devices of the network device. The neighboring network devices can include network devices included in the first subset or generally any network device in the communication network, e.g., network devices included in the complement of the first subset.

For each identified neighboring network device, the system can further determine whether the neighboring device is a candidate point of failure by determining, e.g., using the look-up table, whether alarms triggered by the neighboring device in the case of failure match the observed triggered alarms in the first subset. For example, suppose an alarm of a first network device included in the first subset is triggered and an alarm of a second network device included in the first subset is not triggered. Suppose the first network device is connected to a third and fourth network device, and the second network device is connected to the third network device. The alarm on the first network device could be caused by the first, third or fourth network device. However, if the third network device fails, an alarm would also be triggered on the second network device, which is not the case. Therefore, the candidate point of failures for the first network device include the first and fourth network devices.

The system can then generate a set of alarm data for the network device, where the set of alarm data includes <NUM>) data identifying the network device and <NUM>) data identifying neighboring network devices that are determined to be candidate points of failure. Accordingly, the generated alarm data can include multiple sets of alarm data, where each set corresponds to a triggered network device in the first subset of network devices and includes data identifying the triggered network device and data identifying other network devices in the communication network that could have caused the network device's alarm to be triggered, e.g., neighboring network devices under the local failure-alarm model. The union of the generated alarm data produces a set of network devices that are candidate points of failures, e.g., candidate root cause failures in the network.

The system provides the generated alarm data to a quantum computing resource and instructs the quantum computing resource to compute a solution to the root cause identification problem using the alarm data (step <NUM>). Due to the structure of the local failure-alarm model and structure of the generated alarm data, the root cause identification problem can be formulated as a minimum set cover problem.

For example, let the communication network include N network devices represented by a collection of vertices V = {<NUM>,. Let the network include a set of M alarms A = {<NUM>,. , M}, in which under the local failure-alarm model the m-th alarm monitors a subset of network devices Vm ⊂ V. That is, a failure on any network device in the subset of network devices Vm triggers the m-th alarm. The state of the m-th alarm can be represented by am and can take the value <NUM> if the alarm is triggered or <NUM> otherwise. Under the local failure-alarm model, the state of the m-th alarm can therefore take the value <NUM> if there exists a failing network device in the subset of network devices that the alarm monitors and take the value <NUM> otherwise, e.g., <MAT> In addition, under the local failure-alarm model, a set of alarms Ai is triggered when network device i fails, e.g., Ai = {m ∈ A : alarm m is triggered if device i fails}. The generated alarm data therefore takes the form Ô = {m ∈ A : am = <NUM>}.

Therefore, given alarm data generated by monitoring the network devices in the first subset of network devices, the task of computing a solution to the root cause identification problem using the alarm data is the task of computing a smallest set of root-cause failures that reproduces the alarm data. This task is equivalent to determining a minimum set cover of the alarms Ai on V given Ô, i.e., determining a smallest V̂ ⊂ V such that Ô =Ui∈V̂ Ai. The task of determining a minimum set cover is an NP-Hard problem, for which there are no known classical algorithms that can solve it efficiently asymptotically.

As described above, in some implementations the quantum computing resource may include a quantum computing resource, e.g., an annealer, that is configured to solve quadratic unconstrained binary optimization (QUBO) problems. Therefore, to instruct the quantum computing resource to determine a minimum set cover, the system can generate a QUBO formulation of the task and provide the quantum computing resource with data representing the generated QUBO formulation. Techniques for generating a QUBO formulation of the task of determining a minimum set cover of alarm data are described below.

Let U = {<NUM>,<NUM>,. , n - <NUM>} represent a set of <MAT> elements and let S = {Vi: i = <NUM>,. , N - <NUM>} represent a collection of <MAT> sets whose union is equal to U, i.e., <MAT>. The task of determining the minimum set cover can be formulated as the following optimization problem <MAT> <MAT> where the variables xi take the value <NUM> if the set Vi is in the minimum set cover and take the value <NUM> otherwise.

The inequality constraints given by Equation (<NUM>) can be expressed as <NUM> ≤ ∑j:u∈Vj xi ≤ N, Vu and therefore can be expressed in standard form: <MAT> in which the RHS of each Equation (<NUM>) is an upper bound. Therefore, the first inequality is constrained through introduction of <MAT> binary variables <MAT> and replacement of the inequality constraint with the equality constraint: <MAT>.

Therefore, to obtain a minimum set cover for the alarm data from the quantum computing resource, the system can generate a QUBO formulation of the task (according to Equation (<NUM>)) using the alarm data. The system can then provide the generated QUBO formulation of the task to the quantum computing resource for processing. Alternatively, the system can provide the quantum computing resource with the alarm data and data requesting that the quantum computing resource compute a minimum set cover for the alarm data. In these implementations the quantum computing resource can generate a QUBO formulation of the task (according to Equation (<NUM>)) using the alarm data.

Returning to <FIG>, the system receives data representing a second subset of network devices in the communication network (step <NUM>). The second subset includes network devices that correspond to a minimum set cover for the alarm data, where sources of failures in the communication network are likely attributable to network devices in the second subset. An example minimum set cover for alarm data generated by monitoring the minimum vertex cover <NUM> of <FIG> is described below with reference to <FIG>.

The system can investigate network devices in the second subset to identify root causes of failures in the communication network. When a root cause of a problem is identified, the system can determine corrective actions which, when implemented, address the identified root cause. For example, the system can determine that a particular network device suffered a system crash or unexpectedly shut down. In these implementations the system can cause the network device to restart. As another example, the system can determine that a particular network device failed due to environmental changes, a voltage fluctuation or an excess load. In these implementations the system can reduce the impact of such factors on network devices in the network by building in redundancy to prevent a single point of failure from disrupting large portions of the network or the whole network and maintaining a threshold value for each network element. As another example, the system can determine that a particular network device was misconfigured. In these implementations the system can perform checks, tests and validations, e.g., after a network change, to detect and correct misconfigurations.

In some implementations the techniques described above with reference to example process <NUM> of <FIG> can be applied separately. For example, in some implementations it may be advantageous to use the quantum computing resource to compute a minimum dominating set or minimum vertex cover only, and use a classical computer to compute the minimum set cover. In other implementations the process may not require computation of the minimum set cover. In some implementations it may be advantageous to use the quantum computing resource to compute the minimum set cover only, and use a classical computer to compute the minimum dominating set or minimum vertex cover. In other implementations the process may not require the computation of the minimum dominating set or minimum vertex cover. Two additional example processes for root cause analysis in a communication network are described below.

<FIG> is a flowchart of a second example process <NUM> for root cause analysis in a communication network. For convenience, the process <NUM> will be described as being performed by a system of one or more classical and quantum computers located in one or more locations. For example, example system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The system provides a quantum computing resource with input data requesting determination of a minimum subset of network devices in the communication network to be monitored (step <NUM>). Step <NUM> is similar to step <NUM> of example process <NUM> described above with reference to <FIG>, and for brevity details are not repeated.

The system receives, from the quantum computing resource, data representing a first subset of network devices in the communication network. Step <NUM> is similar to step <NUM> of example process <NUM> described above with reference to <FIG>, and for brevity details are not repeated.

The system monitors network devices in the first subset of network devices to generate alarm data representing triggered network device alarms (step <NUM>). Step <NUM> can be similar to step <NUM> of example process <NUM> described above with reference to <FIG>. For brevity details are not repeated.

In either case, the system can use the generated alarm data to determine root-cause failures in the network. For example, the system can compute a union of the alarm data to determine a subset of network devices, where network devices in the subset include diagnosed sources of failures in the communication network. The system can then investigate the network devices in the subset to identify root cause failures and determine corrective actions that address the root cause failures. Implementing example process <NUM> reduces the number of alarms that need to be monitored and therefore reduces root cause analysis resource requirements, e.g., compared to processes that require a whole network to be monitored, particularly when the monitoring is to be repeatedly performed over a long period of time. Example process <NUM> can be particularly beneficial for densely connected and large networks.

<FIG> is a flowchart of a fourth example process <NUM> for root cause analysis in a communication network. For convenience, the process <NUM> will be described as being performed by a system of one or more classical and quantum computers located in one or more locations. For example, example system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The system monitors network devices in the communication network to generate alarm data representing triggered network device alarms (step <NUM>). Step <NUM> is similar to step <NUM> of example process <NUM> described above with reference to <FIG>, except all network devices are monitored instead of only a subset of network devices. For brevity details are not repeated.

The system provides the generated alarm data to a quantum computing resource and instructs the quantum computing resource to compute a solution to the root cause identification problem using the alarm data (step <NUM>). Step <NUM> is similar to step <NUM> of example process <NUM> described above with reference to <FIG>, and for brevity details are not repeated.

The system receives data representing a subset of network devices in the communication network from the quantum computing resource, where the subset includes a minimum set cover for the alarm data (step <NUM>). Step <NUM> is similar to step <NUM> of example process <NUM> described above with reference to <FIG>, and for brevity details are not repeated.

Example process <NUM> can be particularly beneficial for root cause analysis under more general failure-alarm models, e.g., exact failure-alarm models where an alarm is triggered when any device in a particular and fixed set of devices fails.

<FIG> shows an example communication network topology <NUM>. The example communication network topology <NUM> is an illustrative example and for the sake of clarity represents a communication network with <NUM> network devices. However, in real-world applications the number of network devices can include a significantly larger number of devices, particularly in implementations where the communication network is a <NUM> network.

The example network topology <NUM> includes a graph of <NUM> vertices representing the <NUM> network devices, e.g., vertex <NUM> representing network device <NUM>, and edges between vertices representing respective connections between network devices, e.g., edge <NUM> representing a connection between network devices <NUM> and <NUM>. As described above with reference to step <NUM> of example process <NUM>, under a local failure-alarm model it is assumed that a failure on one network device triggers an alarm on the network device itself and on other network devices within a local neighborhood of the network device, e.g., on other network devices directly connected to the network device or within a predetermined number of connections from the network device. For example, under a nearest-neighbor failure-alarm model, a failure on network device <NUM> triggers an alarm on network device <NUM> itself and on network devices directly connected to network device <NUM>, e.g., network devices <NUM> and <NUM>.

<FIG> shows an example minimum dominating set <NUM> and an example minimum vertex cover <NUM> for the communication network topology <NUM> of <FIG>. The minimum dominating set <NUM> includes <NUM> vertices corresponding to network devices <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and <NUM>. That is, under the assumption of the local alarm-failure model, the system can monitor <NUM> out of the <NUM> network devices and still obtain alarm data that represents failures that can occur anywhere in the entire communication network. The minimum vertex cover <NUM> includes <NUM> vertices corresponding to network devices <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. That is, under the assumption of the local alarm-failure model, the system can monitor <NUM> out of the <NUM> network devices and still obtain alarm data that represents failures that can occur anywhere in the entire communication network.

<FIG> shows example triggered alarms <NUM> and candidate network device failures <NUM> obtained after monitoring network devices in the example minimum vertex cover <NUM> shown in <FIG>. The example triggered alarms <NUM> include <NUM> triggered alarms on network devices <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and <NUM>. The candidate network device failures <NUM> can be computed using the techniques described above with reference to step <NUM> of example process <NUM> of <FIG>, and includes network devices <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and <NUM>.

<FIG> shows an example minimum set cover <NUM> for alarm data generated based on the example triggered alarms <NUM> of <FIG>. The minimum set cover <NUM> includes <NUM> vertices corresponding to root cause failure network devices <NUM>, <NUM>, <NUM> and <NUM>. <FIG> shows how monitoring a subset of network devices, e.g., in a minimum vertex cover, enables the identification root cause failures in the whole network, e.g., outside of the monitored subset. For example, network device <NUM> is identified as a root cause device however was not included in the minimum vertex cover and therefore not monitored.

<FIG> illustrates a schematic diagram of an exemplary generic classical processor system <NUM>. The system <NUM> can be used for the classical operations described in this specification according to some implementations. The system <NUM> is intended to represent various forms of digital computers, such as laptops, desktops, workstations, personal digital assistants, servers, blade servers, mainframes, mobile devices and other appropriate computers. The components shown here, their connections and relationships, and their functions, are exemplary only, and do not limit implementations of the inventions described and/or claimed in this document.

The system <NUM> includes a processor <NUM>, a memory <NUM>, a storage device <NUM>, and an input/output device <NUM>. Each of the components <NUM>, <NUM>, <NUM>, and <NUM> are interconnected using a system bus <NUM>. The processor <NUM> may be enabled for processing instructions for execution within the system <NUM>. In one implementation, the processor <NUM> is a single-threaded processor. In another implementation, the processor <NUM> is a multi-threaded processor. The processor <NUM> may be enabled for processing instructions stored in the memory <NUM> or on the storage device <NUM> to display graphical information for a user interface on the input/output device <NUM>.

In another implementation, the memory <NUM> is a nonvolatile memory unit.

The storage device <NUM> may be enabled for providing mass storage for the system <NUM>.

Implementations of the digital and/or quantum subject matter and the digital functional operations and quantum operations described in this specification can be implemented in digital electronic circuitry, suitable quantum circuitry or, more generally, quantum computational systems, in tangibly-embodied digital and/or quantum computer software or firmware, in digital and/or quantum computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. The term "quantum computing device" may include, but is not limited to, quantum computers, quantum information processing systems, quantum cryptography systems, or quantum simulators.

Implementations of the digital and/or quantum subject matter described in this specification can be implemented as one or more digital and/or quantum computer programs, i.e., one or more modules of digital and/or quantum computer program instructions encoded on a tangible non-transitory storage medium for execution by, or to control the operation of, data processing apparatus. The digital and/or quantum computer storage medium can be a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, one or more qubits, or a combination of one or more of them. Alternatively or in addition, the program instructions can be encoded on an artificially-generated propagated signal that is capable of encoding digital and/or quantum information, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode digital and/or quantum information for transmission to suitable receiver apparatus for execution by a data processing apparatus.

The term "data processing apparatus" refers to digital and/or quantum data processing hardware and encompasses all kinds of apparatus, devices, and machines for processing digital and/or quantum data, including by way of example a programmable digital processor, a programmable quantum processor, a digital computer, a quantum computer, multiple digital and quantum processors or computers, and combinations thereof. The apparatus can also be, or further include, special purpose logic circuitry, e.g., an FPGA (field programmable gate array), an ASIC (application-specific integrated circuit), or a quantum simulator, i.e., a quantum data processing apparatus that is designed to simulate or produce information about a specific quantum system. In particular, a quantum simulator is a special purpose quantum computer that does not have the capability to perform universal quantum computation. The apparatus can optionally include, in addition to hardware, code that creates an execution environment for digital and/or quantum computer programs, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.

A digital and/or quantum computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a mark-up language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g., files that store one or more modules, sub-programs, or portions of code. A digital and/or quantum computer program can be deployed to be executed on one digital or one quantum computer or on multiple digital and/or quantum computers that are located at one site or distributed across multiple sites and interconnected by a digital and/or quantum data communication network. A quantum data communication network is understood to be a network that may transmit quantum data using quantum systems, e.g. qubits. Generally, a digital data communication network cannot transmit quantum data, however a quantum data communication network may transmit both quantum data and digital data.

The processes and logic flows described in this specification can be performed by one or more programmable digital and/or quantum computers, operating with one or more digital and/or quantum processors, as appropriate, executing one or more digital and/or quantum computer programs to perform functions by operating on input digital and quantum data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA or an ASIC, or a quantum simulator, or by a combination of special purpose logic circuitry or quantum simulators and one or more programmed digital and/or quantum computers.

For a system of one or more digital and/or quantum computers to be "configured to" perform particular operations or actions means that the system has installed on it software, firmware, hardware, or a combination of them that in operation cause the system to perform the operations or actions. For one or more digital and/or quantum computer programs to be configured to perform particular operations or actions means that the one or more programs include instructions that, when executed by digital and/or quantum data processing apparatus, cause the apparatus to perform the operations or actions. A quantum computer may receive instructions from a digital computer that, when executed by the quantum computing apparatus, cause the apparatus to perform the operations or actions.

Digital and/or quantum computers suitable for the execution of a digital and/or quantum computer program can be based on general or special purpose digital and/or quantum processors or both, or any other kind of central digital and/or quantum processing unit. Generally, a central digital and/or quantum processing unit will receive instructions and digital and/or quantum data from a read-only memory, a random access memory, or quantum systems suitable for transmitting quantum data, e.g. photons, or combinations thereof.

The essential elements of a digital and/or quantum computer are a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and digital and/or quantum data. The central processing unit and the memory can be supplemented by, or incorporated in, special purpose logic circuitry or quantum simulators. Generally, a digital and/or quantum computer will also include, or be operatively coupled to receive digital and/or quantum data from or transfer digital and/or quantum data to, or both, one or more mass storage devices for storing digital and/or quantum data, e.g., magnetic, magneto-optical disks, optical disks, or quantum systems suitable for storing quantum information. However, a digital and/or quantum computer need not have such devices.

Digital and/or quantum computer-readable media suitable for storing digital and/or quantum computer program instructions and digital and/or quantum data include all forms of nonvolatile digital and/or quantum memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; CD-ROM and DVD-ROM disks; and quantum systems, e.g., trapped atoms or electrons. It is understood that quantum memories are devices that can store quantum data for a long time with high fidelity and efficiency, e.g., light-matter interfaces where light is used for transmission and matter for storing and preserving the quantum features of quantum data such as superposition or quantum coherence.

Control of the various systems described in this specification, or portions of them, can be implemented in a digital and/or quantum computer program product that includes instructions that are stored on one or more non-transitory machine-readable storage media, and that are executable on one or more digital and/or quantum processing devices. The systems described in this specification, or portions of them, can each be implemented as an apparatus, method, or system that may include one or more digital and/or quantum processing devices and memory to store executable instructions to perform the operations described in this specification.

While this specification contains many specific implementation details, these should not be construed as limitations on the scope of what may be claimed, but rather as descriptions of features that may be specific to particular implementations. Conversely, various features that are described in the context of a single implementation can also be implemented in multiple implementations separately or in any suitable sub-combination. The invention is defined in the independent claims as appended.

Moreover, the separation of various system modules and components in the implementations described above should not be understood as requiring such separation in all implementations, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

Claim 1:
A computer-implemented method for root cause analysis in a communication network (<NUM>), the method comprising:
generating, as input data, (i) data representing a topology (<NUM>) of the communication network, the topology comprising a graph of vertices (<NUM>) representing network devices and edges (<NUM>) representing connections between network devices, and (ii) a quadratic unconstrained binary optimization (QUBO) formulation of a task of determining a minimum dominating set of vertices for the graph or a minimum vertex cover of the graph , wherein the QUBO formulation of the task of determining a minimum dominating set of vertices for the graph is given by <MAT> where N represents the number of vertices in the graph, <IMG> represents a set of vertices adjacent to vertex i, P represents a penalty constant, xi represent binary variables that take the value <NUM> if vertex i is in the minimum dominating set and take the value <NUM> otherwise, and bi,k represent binary variables;
providing a quantum computing resource (<NUM>) with the input data comprising (i) the data representing the topology of the communication network, and (ii) the QUBO formulation of the task;
receiving, from the quantum computing resource, data representing a first subset of network devices in the communication network, wherein the first subset comprises i) the minimum dominating set (<NUM>) of vertices for the graph or ii) the minimum vertex cover (<NUM>) for the graph;
monitoring network devices in the first subset to generate alarm data representing triggered network device alarms; and
determining, based on the alarm data, root-cause failures in the communication network.