Quantum computing in root cause analysis of 5G and subsequent generations of communication networks

A system comprising:

• one or more computers;
• and one or more non-transitory computer-readable media coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
• generating, as input data, (1) data representing a topology of a communication network, the topology comprising a graph of vertices representing network devices and edges representing connections between the network devices, and (11) a quadratic unconstrained binary optimization (QUBO) formulation of a task of determining a minimum dominating set of the vertices for the graph is given by
• min
• x
• i
• ∈
• {
• 0
• ,
• 1
• }
• ∑
• i
• =
• 0
• N
• -
• 1
• x
• i
• +
• P
• ⁢
• ∑
• u
• =
• 0
• n
• -
• 1
• (
• 1
• -
• ∑
• j
• :
• u
• ∈
• V
• j
• x
• j
• +
• ∑
• k
• =
• 0
• ⌈
• log
• 2
• ⁢
• N
• ⌉
• -
• 1
• b
• u
• ,
• k
• ⁢
• 2
• k
• )
• 2
• where N represents the number of vertices in the graph, Ni represents a set of vertices adjacent to vertex i, P represents a penalty constant, xi represent binary variables that take the value 1 if vertex i is in the minimum dominating set and take the value 0 otherwise, and bi,k represent binary variables;
• providing a quantum computing resource with the input data comprising (i) the data representing the topology of the communication network and (ii) the input data comprising the QUBO formulation of the task of determining the minimum dominating set of the vertices of the graph;
• 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 of vertices for the graph or ii) a vertex cover for the graph;
• monitoring network devices in the first subset to generate alarm data representing triggered network device alarms;
• providing the alarm data to a quantum computing resource;
• and receiving, from the quantum computing resource, data representing a second subset of network devices in the communication network, wherein i) the second subset comprises a set cover for the alarm data and 11) the network devices in the second subset comprise diagnosed sources of failures in the communication network.

A computer-implemented method for root cause analysis in a communication network, the method comprising:

• generating, as input data, (i) data representing a topology of the communication network, the topology comprising a graph of vertices representing network devices and edges representing connections between the network devices, and (ii) a quadratic unconstrained binary optimization (QUBO) formulation of a task of determining a minimum dominating set of the vertices of the graph, wherein the QUBO formulation of the task of determining a minimum dominating set of vertices for the graph is given by
• min
• x
• i
• ∈
• {
• 0
• ,
• 1
• }
• ∑
• i
• =
• 0
• N
• -
• 1
• x
• i
• +
• P
• ⁢
• ∑
• i
• =
• 0
• N
• -
• 1
• (
• 1
• -
• x
• i
• -
• ∑
• j
• :
• v
• j
• ∈
• 𝒩
• i
• x
• j
• +
• ∑
• k
• =
• 0
• ⌈
• log
• 2
• (
• ❘
• "\[LeftBracketingBar]"
• 𝒩
• i
• ❘
• "\[RightBracketingBar]"
• +
• 1
• )
• ⌉
• -
• 1
• b
• i
• ,
• k
• ⁢
• 2
• k
• )
• 2
• where N represents the number of vertices in the graph, Ni represents a set of vertices adjacent to vertex i, P represents a penalty constant, xi represent binary variables that take the value 1 if vertex i is in the minimum dominating set and take the value 0 otherwise, and bi,k represent binary variables. binary variables;
• providing a quantum computing resource with the input data comprising (i) the data representing the topology of the communication network and (ii) the input data comprising the QUBO formulation of the task of determining the minimum dominating set of the vertices of the graph;
• 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 of vertices for the graph or (ii) a vertex cover for the graph;
• monitoring network devices in the first subset to generate alarm data representing triggered network device alarms;
• determining, based on the alarm data, root-cause failures in the communication network.

A system comprising:

• one or more computers;
• and one or more non-transitory computer-readable media coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
• generating, as input data, (i) data representing a topology of the communication network, the topology comprising a graph of vertices representing network devices and edges representing connections between the network devices, and (ii) a quadratic unconstrained binary optimization (QUBO) formulation of a task of determining a minimum dominating set of the vertices of the graph, wherein the QUBO formulation of the task of determining a minimum dominating set of vertices for the graph is given by
• min
• x
• i
• ∈
• {
• 0
• ,
• 1
• }
• ∑
• i
• =
• 0
• N
• -
• 1
• x
• i
• +
• P
• ⁢
• ∑
• i
• =
• 0
• N
• -
• 1
• (
• 1
• -
• x
• i
• -
• ∑
• j
• :
• v
• j
• ∈
• 𝒩
• i
• x
• j
• +
• ∑
• k
• =
• 0
• ⌈
• log
• 2
• (
• ❘
• "\[LeftBracketingBar]"
• 𝒩
• i
• ❘
• "\[RightBracketingBar]"
• +
• 1
• )
• ⌉
• -
• 1
• b
• i
• ,
• k
• ⁢
• 2
• k
• )
• 2
• where N represents the number of vertices in the graph, Ni represents a set of vertices adjacent to vertex i, P represents a penalty constant, xi represent binary variables that take the value 1 if vertex i is in the minimum dominating set and take the value 0 otherwise, and bi,k represent binary variables;
• providing a quantum computing resource with the input data comprising (i) the data representing the topology of the communication network and (ii) the input data comprising the QUBO formulation of the task of determining the minimum dominating set of the vertices of the graph;
• 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 of vertices for the graph or ii) a vertex cover 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.