MINIMUM CONNECTED DOMINATING SET PROBLEM USING QUANTUM ANNEALING FOR DISTANCE OPTIMIZATION AND USE THEREOF

FIELD

This invention relates to computing. More precisely, this invention pertains to a method and system for solving a minimum connected dominating set problem using quantum annealing for distance optimization and use thereof.

BACKGROUND

Most interesting combinatorial optimization problems are hard to solve. To name a few, the maximum common subgraph, graph partitioning, graph colouring, and travelling salesman problems are among those combinatorial optimization problems which have been proved to be NP-hard. Some of these problems have significant real-world applications which make them especially interesting. For example, the minimum dominating set problem is an interesting problem used in the analysis of social networks.

A social network can be interpreted as a graph of relationships and interactions between a set of people. Nodes of a social network can represent individuals and organizations, and two nodes are adjacent if there is some kind of relationship between them.

Finding the minimum number of people in a social network who are familiar to the whole set of individuals is an interesting problem. This is because we can interpret these people as being the most influential individuals in the network. Finding the most influential individuals in the network can be done by solving an instance of the minimum dominating set problem for the graph representing the social network.

An interesting example of a social network is a web graph. A web graph is defined as a directed graph whose nodes are the pages of the World Wide Web, and there is a directed edge between, say webpage X to webpage Y, if there is a hyperlink on page X referring to page Y. A variant of the minimum dominating set problem is the minimum connected dominating set problem. Aside from its application in the study of social networks, this problem can be used for designing mobile ad-hoc networks or also even for identifying at least one biologically central protein in a protein-protein interaction network.

For instance, a mobile ad-hoc network is a self-configuring wireless network of mobile devices which are connected without wires and over an infrastructure-less network, i.e., there is no central administration in the network.

Usually, each node in a wireless network is a computing device with a limited energy source such as a battery. The energy consumed for transmitting a message increases super-linearly with transmission distance.

Fortunately, extending the idea of constructing a backbone-like structure in conventional wired networks, such as the Internet, to wireless networks through the notion of a virtual backbone is quite feasible.

Exploiting a virtual backbone has important immediate benefits. By incorporating only the nodes forming the backbone in the routing procedures, the telecommunications overhead is reduced, the bandwidth efficiency is increased, and the overall energy consumption is decreased. This advantage becomes more pronounced as the size of the backbone becomes smaller. Hence, people are motivated to find the smallest-sized possible virtual backbone.

Another real-world example of an application of the minimum connected dominating set problem is in the development of optical telecommunications networks due in part to exponentially growing demands of users.

One of the main problems that these networks must overcome is the deterioration of the optical signal as the distance from the source increases. Therefore, signals must be regenerated periodically using regenerators. In practice, the network is designed so that regenerators are placed at nodes of the network in a way such that all nodes of the network can communicate without significant signal impairments. These regenerators can be said to form the backbone of the network. One can see that designing a smallest-sized backbone as well as finding the minimum number of regenerators in an optical telecommunications network is a matter of solving a minimum connected dominating set problem.

Features of the invention will be apparent from review of the disclosure, drawings, and description of the invention below.

BRIEF SUMMARY

According to a broad aspect, there is disclosed a method for determining a minimum connected dominating set in a graph, the method comprising obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes; generating a corresponding constrained binary quadratic programming problem using the distance generated distance table; providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver; obtaining at least one approximate solution from the quantum annealing solver; post-processing the at least one approximate solution and providing the post-processed at least one approximate solution.

According to one embodiment, the quantum annealing solver is an unconstrained quantum annealing solver; the providing of the corresponding constrained binary quadratic programming problem comprises generating an unconstrained binary quadratic programming problem using the generated constrained binary quadratic programming problem; and providing the generated unconstrained binary quadratic programming problem to the unconstrained quantum annealing solver; and the at least one approximate solution is obtained from the unconstrained quantum annealing solver.

According to one embodiment, the quantum annealing solver is a constrained quantum annealing solver; the providing of the corresponding constrained binary quadratic programming problem comprises obtaining a corresponding solver subroutine and solving the generated constrained binary quadratic programming problem using the solver subroutine, and the at least one approximate solution is obtained from the solver subroutine.

According to a broad aspect, there is disclosed a method for determining a minimum connected dominating set in a graph, the method comprising obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges; obtaining an indication of a solver to use for determining a minimum connected dominating set; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes; generating a corresponding constrained binary quadratic programming problem using the generated distance table; if the indication of a solver comprises an unconstrained quantum annealing solver generating an unconstrained binary quadratic programming problem using the generated constrained binary quadratic programming problem, providing the unconstrained binary quadratic programming problem to the unconstrained quantum annealing solver, obtaining at least one approximate solution from the unconstrained quantum annealing solver, if the indication of a solver comprises a constrained quantum annealing solver obtaining a corresponding solver subroutine, solving the generated constrained binary quadratic programming problem using the solver subroutine, and obtaining at least one approximate solution from the solver subroutine, post-processing the at least one approximate solution and providing the post-processed at least one approximate solution.

In accordance with an embodiment, the indication of an input graph is obtained from at least one of a user interacting with a digital computer, a computer operatively connected to the digital computer, a software package, and an intelligent agent.

In accordance with an embodiment, the post-processed at least one approximate solution is provided to at least one of a user interacting with a digital computer, a computer operatively connected to the digital computer, a software package, and an intelligent agent. According to a broad aspect, there is disclosed a non-transitory computer- readable storage medium for storing computer-executable instructions which, when executed, cause a digital computer to perform a method for determining a minimum connected dominating set in a graph, the method comprising obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes; generating a corresponding constrained binary quadratic programming problem using the generated distance table; providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver; obtaining at least one approximate solution from the quantum annealing solver; post-processing the at least one approximate solution and providing the post-processed at least one approximate solution.

In accordance with a broad aspect, there is disclosed a digital computer comprising a central processing unit; a display device; a communication port for operatively connecting the digital computer to a quantum annealing solver; a memory unit comprising an application for determining a minimum connected dominating set in a graph, the application comprising instructions for obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges; instructions for generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes; instructions for generating a corresponding constrained binary quadratic programming problem using the generated distance table; instructions for providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver; instructions for obtaining at least one approximate solution from the quantum annealing solver; instructions for post-processing the at least one approximate solution and instructions for providing the post-processed at least one approximate solution and a data bus for interconnecting the central processing unit, the display device, the communication port, and the memory unit. In accordance with a broad aspect, there is disclosed a method for determining a minimum connected dominating set in a graph, the method comprising use of a processing unit for obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges; use of a processing unit generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes; use of a processing unit generating a corresponding constrained binary quadratic programming problem using the generated distance table; use of a processing unit providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver; use of a processing unit obtaining at least one approximate solution from the quantum annealing solver; use of a processing unit post-processing the at least one approximate solution; and use of a processing unit providing the post-processed at least one approximate solution.

According to a broad aspect, there is disclosed a method for determining a solution to an NP hard combinatorial optimization problem, the method comprising obtaining an indication of the NP hard combinatorial optimization problem to solve; generating a matrix, wherein the generated matrix is one of a distance table and an adjacency matrix of an auxiliary graph depending on a structure of the NP hard combinatorial optimization problem; generating a corresponding quadratic unconstrained binary optimization problem using the generated matrix; providing the corresponding quadratic unconstrained binary optimization problem to a solver, wherein the solver is a quadratic unconstrained binary optimization solver; obtaining an approximate solution to the corresponding quadratic unconstrained binary optimization problem; converting the approximate solution to the corresponding quadratic unconstrained binary optimization problem into a near-optimal solution to the NP hard combinatorial optimization problem and providing the near-optimal solution to the NP hard combinatorial optimization problem.

According to a broad aspect, there is disclosed a method for identifying at least one biologically central protein in a protein-protein interaction network comprising a plurality of proteins, the method comprising obtaining an indication of an input graph indicative of a protein-protein interaction network, the input graph comprising a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a given protein and each edge of the input graph is representative of a physical interaction between two given proteins; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes; generating a corresponding constrained binary quadratic programming problem using the generated distance table; providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver; obtaining at least one approximate solution from the quantum annealing solver; postprocessing the at least one approximate solution and providing the post-processed at least one approximate solution to thereby provide an indication of at least one biologically central protein in the protein-protein interaction network.

In accordance with an embodiment, there is disclosed a use of the method disclosed above for identifying at least one biologically central protein in a protein- protein interaction network comprising a plurality of proteins, wherein the input graph comprises a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a given protein and each edge of the input graph is representative of a physical interaction between two given proteins.

In accordance with a broad aspect, there is disclosed a method for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices, the method comprising obtaining an indication of an input graph indicative of a mobile ad-hoc network, the input graph comprising a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a given mobile device having a corresponding energy source and each edge is representative of a wireless connection between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes; generating a corresponding constrained binary quadratic programming problem using the generated distance table; providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver; obtaining at least one approximate solution from the quantum annealing solver; post-processing the at least one approximate solution and providing the post-processed at least one approximate solution to thereby provide an indication of a virtual backbone in the mobile ad-hoc network.

In accordance with an embodiment, there is disclosed a use of the method disclosed above for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices, wherein the input graph is comprised of a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a given mobile device having a corresponding energy source and each edge is representative of a wireless connection between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes.

According to a broad aspect, there is disclosed a method for identifying a backbone in an optical telecommunication network comprising a plurality of users and hubs, the method comprising obtaining an indication of an input graph indicative of an optical telecommunication network, the input graph comprising a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a user or a hub and each edge is representative of a connection via a fiber optic cable between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes; generating a corresponding constrained binary quadratic programming problem using the generated distance table; providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver; obtaining at least one approximate solution from the quantum annealing solver; post-processing the at least one approximate solution and providing the post-processed at least one approximate solution to thereby provide an indication of a backbone in the optical telecommunication network.

According to an embodiment, there is disclosed a use of the method disclosed herein above for identifying a backbone in an optical telecommunication network comprising a plurality of users and hubs, wherein the input graph is comprised of a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a user or a hub and each edge is representative of a connection via a fiber optic cable between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes.

An advantage of the method disclosed is that it provides a near-optimal solution to a minimum connected dominating set problem for many problem instances in less time compared to prior-art methods. It will be appreciated that the solving of the minimum connected dominating set problem in a graph in an exact optimum way is a hard problem with a non-obvious solution because an exponential number of constraints, along with dominating conditions, are involved.

BRIEF DESCRIPTION OF THE DRAWINGS

In order that the invention may be readily understood, embodiments of the invention are illustrated by way of example in the accompanying drawings.

Figure 1 is a flowchart which shows an embodiment of a method for determining a minimum connected dominating set in a graph.

Figure 2 is a flowchart which shows a first embodiment for providing a constrained binary quadratic programming problem to a quantum annealing solver, wherein the quantum annealing solver is an unconstrained quantum annealing solver.

Figure 3 is a flowchart which shows a second embodiment for providing a constrained binary quadratic programming problem to a quantum annealing solver, wherein the quantum annealing solver is a constrained quantum annealing solver.

Figure 4 is a flowchart which shows an embodiment for performing a post- processing of at least one approximate solution provided by the quantum annealing solver.

Figure 5 is a block diagram which shows an embodiment of a system for determining a minimum connected dominating set in a graph; the system comprises a digital computer and a quantum annealing solver. Figure 6 is a block diagram which shows an embodiment of a digital computer used in a system for determining a minimum connected dominating set in a graph.

Figure 7a-i is a diagram which shows an embodiment of a graph for which a minimum connected dominating set may be determined.

Figure 7a-ii is a diagram which shows an embodiment of the adjacency matrix of the graph shown in Fig. 7a-i.

Figure 7b shows an embodiment of a distance matrix illustrating, for each node of the graph disclosed in Fig. 7a-i, a distance between the given node and the other nodes of the graph.

Figure 7c shows an embodiment of a corresponding constrained binary quadratic problem generated using the adjacency matrix disclosed in Fig. 7a-ii and the distance matrix disclosed in Fig. 7b.

Figure 7d shows at least one approximate solution generated by a quantum annealing solver.

Figure 7e is a diagram which illustrates the result of a post-processing performed on the at least one approximate solution generated by the quantum annealing solver.

Figure 8 is a flowchart which shows an embodiment of a method for determining a solution to an NP hard combinatorial optimization problem.

Further details of the invention and its advantages will be apparent from the detailed description included below.

DETAILED DESCRIPTION

In the following description of the embodiments, references to the accompanying drawings are by way of illustration of an example by which the invention may be practiced.

Terms

The term "invention" and the like mean "the one or more inventions disclosed in this application," unless expressly specified otherwise. The terms "an aspect," "an embodiment," "embodiment," "embodiments," "the embodiment," "the embodiments," "one or more embodiments," "some embodiments," "certain embodiments," "one embodiment," "another embodiment," and the like mean "one or more (but not all) embodiments of the disclosed invention(s)," unless expressly specified otherwise.

A reference to "another embodiment" or "another aspect" in describing an embodiment does not imply that the referenced embodiment is mutually exclusive with another embodiment (e.g., an embodiment described before the referenced embodiment), unless expressly specified otherwise.

The terms "including," "comprising," and variations thereof mean "including but not limited to," unless expressly specified otherwise.

The terms "a," "an," and "the" mean "one or more," unless expressly specified otherwise.

The term "plurality" means "two or more," unless expressly specified otherwise.

The term "herein" means "in the present application, including anything which may be incorporated by reference," unless expressly specified otherwise.

The term "whereby" is used herein only to precede a clause or other set of words that express only the intended result, objective, or consequence of something that is previously and explicitly recited. Thus, when the term "whereby" is used in a claim, the clause or other words that the term "whereby" modifies do not establish specific further limitations of the claim or otherwise restricts the meaning or scope of the claim.

The term "e.g." and like terms mean "for example," and thus do not limit the terms or phrases they explain. For example, in a sentence "the computer sends data (e.g., instructions, a data structure) over the Internet," the term "e.g." explains that "instructions" are an example of "data" that the computer may send over the Internet, and also explains that "a data structure" is an example of "data" that the computer may send over the Internet. However, both "instructions" and "a data structure" are merely examples of "data," and other things besides "instructions" and "a data structure" can be "data."

The term "i.e." and like terms mean "that is," and thus limit the terms or phrases they explain.

The term "quantum annealer," "quantum annealing solver," and like terms mean a system consisting of one or many types of hardware that can find optimal or sub-optimal solutions to an unconstrained binary quadratic programming problem. An example of this is a system consisting of a digital computer embedding a binary quadratic programming problem as an Ising spin model, attached to an analogue computer that carries optimization of a configuration of spins in an Ising spin model using quantum annealing as described, for example, in Farhi, E. et al., "Quantum Adiabatic Evolution Algorithms versus Simulated Annealing," arXiv.org:quant- ph/0201031 (2002), pp. 1-16. An embodiment of such analogue computer is disclosed by McGeoch, Catherine C, and Cong Wang, (2013), "Experimental Evaluation of an Adiabatic Quantum System for Combinatorial Optimization," Computing Frontiers, May 14-16, 2013 (http://www.cs.amherst.edu/ccm/cf14- mcgeoch.pdf) and also disclosed in U.S. Patent Application Publication No. US2006/0225165. It will be appreciated that the "quantum annealer" may also comprise "classical components," such as a classical computer. Accordingly, a "quantum annealer" may be entirely analogue or an analogue-classical hybrid.

The term "embedding" of a binary optimization problem, and the like, refer to an assignment of a set of the quantum bits to each binary variable x _t . Specifications of the role of such an embedding in solving an unconstrained binary quadratic programming problem and presentation of an efficient algorithm for it are disclosed for instance in "A practical heuristic for finding graph minors" - Jun Cai, William G. Macready, Aidan Roy, in U.S. Patent Application Publication No. US2008/0218519 and in U.S. Patent No. US8,655,828 B2.

The term "graph" and like terms mean an ordered pair G = (V, E) comprising a set V of nodes and a set E of edges. In one embodiment, graph G is a graph representing an optical telecommunications network. The nodes of G are users and hubs, and the edges of G are the fiber-optic cables connecting them.

The term "connected subgraph" and like terms mean a subset of nodes in the graph G such that every node in the subgraph is reachable from every other node in the subgraph through a sequence of incident edges.

In one embodiment, a subgraph of an optical telecommunications network is connected if there is a sequence of fiber-optic cables connecting all pairs of nodes in that subgraph.

The term "dominating set" and like terms mean that for a subset of nodes in graph G, every node not in the subset is adjacent to at least one node in the subset.

In one embodiment, a set of regenerators in an optical telecommunications network is a dominating set.

The term "minimum dominating set" and like terms mean a dominating set of minimum size.

In one embodiment, a set of regenerators in an optical telecommunications network is a dominating set of minimum size.

The term "minimum connected dominating set" and like terms mean a minimum dominating set which is a connected subgraph of an original graph.

In one embodiment, a set of signal regenerators in an optical telecommunications network is a connected dominating set of minimum size.

The term "result" and like terms mean an optimal or suboptimal solution to the following integer programming problem.

Let where n denotes the number of nodes of the input graph G. Then Xj is 1 if node i is in the dominating set and 0 otherwise. Furthermore, let N(i) denote the set of nodes of G which are adjacent to node i. It will be appreciated that the minimum connected dominating set is the solution to:

for all nodes i e V,

G[x] is connected,

where G[x] denotes the induced subgraph represented by x.

The term "path" and like terms mean a sequence of distinct adjacent nodes in graph G. The length of a path is the number of edges in the sequence. The term "shortest path" and like terms mean a path between two nodes with the minimum number of edges. In one embodiment, a shortest path in an optical telecommunications network is a shortest sequence of fiber-optic cables.

The term "distance matrix" and like terms mean an n by n matrix D of a graph G, where n is the number of nodes of G, and where D _ij is the length of a shortest path between nodes i and j. D _ij is the distance between nodes i and j.

In one embodiment, the distance matrix of an optical telecommunications network contains the shortest distances between pairs of nodes.

Neither the Title nor the Abstract is to be taken as limiting in any way the scope of the disclosed invention(s). The title of the present application and headings of sections provided in the present application are for convenience only, and are not to be taken as limiting the disclosure in any way.

Numerous embodiments are described in the present application, and are presented for illustrative purposes only. The described embodiments are not, and are not intended to be, limiting in any sense. The presently disclosed invention(s) are widely applicable to numerous embodiments, as is readily apparent from the disclosure. One of ordinary skill in the art will recognize that the disclosed invention(s) may be practiced with various modifications and alterations, such as structural and logical modifications. Although particular features of the disclosed invention(s) may be described with reference to one or more particular embodiments and/or drawings, it should be understood that such features are not limited to usage in the one or more particular embodiments or drawings with reference to which they are described, unless expressly specified otherwise.

It will be appreciated that the invention may be implemented in numerous ways, including as a method, a system, a computer readable medium such as a computer-readable storage medium. In this specification, these implementations, or any other form that the invention may take, may be referred to as systems or techniques. A component such as a processor or memory described as being configured to perform a task includes both a general component that is temporarily configured to perform the task at a given time or a specific component that is manufactured to perform the task.

With all of this in mind, the present application is directed to a method and a system for determining a minimum connected dominating set problem in a graph and its use for solving various applications.

As mentioned previously, it will be appreciated that the method may be used in various applications, such as, for instance, building and analyzing telecommunication networks as explained further below. More precisely, one can see that designing a smallest-sized backbone as well as finding the minimum number of regenerators in an optical telecommunications network is a matter of solving a minimum connected dominating set problem. Also disclosed further below is the application of the method disclosed herein for identifying at least one biologically central protein in a protein-protein interaction (PPI) network.

Now referring to Fig. 5, there is shown an embodiment of a system 400 in which an embodiment of the method for determining a minimum connected dominating set problem in a graph may be implemented.

The system 500 comprises a digital computer 502 and a quantum annealer 504.

The digital computer 502 receives an indication of a graph for which a minimum connected dominating set has to be determined and provides an indication of at least one minimum connected dominating set in the graph.

It will be appreciated that the indication of the graph for which at least one minimum connected dominating set problem has to be determined may be provided according to various embodiments.

In one embodiment, the indication of a graph for which at least one minimum connected dominating set problem has to be determined is provided by a user interacting with the digital computer 502. Alternatively, the indication of a graph for which at least one minimum connected dominating set problem has to be determined is provided by another computer, not shown, operatively connected to the digital computer 502.

Alternatively, the indication of a graph for which at least one minimum connected dominating set problem has to be determined is provided by an independent software package.

Alternatively, the indication of a graph for which at least one minimum connected dominating set problem has to be determined is provided by an intelligent agent.

Similarly, it will be appreciated that the indication of at least one minimum connected dominating set in the graph may be provided according to various embodiments.

In accordance with an embodiment, the indication of at least one minimum connected dominating set in the graph is provided to the user interacting with the digital computer 502.

Alternatively, the indication of at least one minimum connected dominating set in the graph solution is provided to another computer operatively connected to the digital computer 502.

In fact, it will be appreciated by the skilled addressee that the digital computer 502 may be any type of computer.

In one embodiment, the digital computer 502 is selected from a group consisting of desktop computers, laptop computers, tablet PCs, servers, smartphones, etc.

Now referring back to Fig. 5, it will be appreciated that the quantum annealer 504 is operatively connected to the digital computer 502.

It will be appreciated that the coupling of the quantum annealer 504 to the digital computer 502 may be achieved according to various embodiments.

In one embodiment, the coupling of the quantum annealer 504 to the digital computer 502 is achieved via a data network.

It will be appreciated that the quantum annealer 504 may be of various types. In one embodiment, the quantum annealer 504 is manufactured by D-Wave Systems Inc. More information on this embodiment of a quantum annealer applicable to 504 can be found at http://www.dwavesys.com. The skilled addressee will appreciate that various alternative embodiments may be provided for the quantum annealer 504.

More precisely, the quantum annealer 504 receives an unconstrained binary quadratic programming problem from the digital computer 502.

The quantum annealer 504 is capable of solving the unconstrained binary quadratic programming problems and of providing at least one corresponding approximate solution. In the case where a plurality of corresponding approximate solutions is provided, the plurality of corresponding approximate solutions may comprise optimal and suboptimal solutions.

The at least one corresponding approximate solution is provided by the quantum annealer 504 to the digital computer 502.

Now referring to Fig. 1 , there is shown an embodiment of a method for determining a minimum connected dominating set in a graph.

According to processing step 102, an input graph is obtained.

It will be appreciated that the input graph may be obtained according to various embodiments.

It will be appreciated that the input graph comprises a plurality of nodes and a plurality of edges.

Now referring to Fig. 7a-i, there is shown an embodiment of an input graph comprises a plurality of nodes and a plurality of edges. An embodiment of an adjacency matrix corresponding to the input graph is shown in Fig. 7a-ii.

In one embodiment, in indication of the input graph is obtained from a user interacting with the digital computer 402.

Alternatively, the indication of the input graph is obtained from another computer operatively connected to the digital computer 502.

In another alternative embodiment, the indication of the input graph is obtained from an independent software package. In a further alternative embodiment, the indication of the input graph input graph is obtained from an intelligent agent.

It will be appreciated that in an alternative embodiment, an indication of a quantum annealing solver to use for determining a minimum connected dominating set in a graph may further be optionally provided together with the indication of the input graph.

It will be appreciated, as further explained below, that the quantum annealing solver to use may be an unconstrained quantum annealing solver in a first embodiment while it may be a constrained quantum annealing solver in another embodiment.

It will also be appreciated that the solver type may be of another different type from the unconstrained quantum annealing solver or the constrained quantum annealing solver. For instance, another classical simulated annealing-based solver may also be used to solve this problem.

Still referring to Fig. 1 and according to processing step 104, a distance table is generated.

More precisely, the distance table comprises for each node of the input graph an indication of a distance between the given node and each of the other nodes of the plurality of nodes.

In one embodiment, the distance table is a distance matrix.

Now referring to Fig. 7b, there is shown an embodiment of a distance matrix for the input graph shown in Fig. 7a-i and corresponding adjacency matrix A shown in Fig. 7a-ii.

More precisely, the generating of the distance table comprises computing the shortest paths between every pair of nodes and subsequently generating the distance table D accordingly.

It will be appreciated that the shortest paths between every pair of nodes may computed according to various embodiments. In one embodiment, Johnson's Algorithm is used to find all-pair shortest paths (Johnson, Donald B. (1977), "Efficient algorithms for shortest paths in sparse networks," Journal of the ACM, 24 (1 ): 1-13, doi: 10.1 145/321992.321993).

The skilled addressee will appreciate that various alternative embodiments may be possible.

Still referring to Fig. 1 and according to processing step 106, a constrained binary quadratic programming problem is generated.

It will be appreciated that the constrained binary quadratic programming problem is generated using the distance matrix D generated according to processing step 104. For the input graph shown in Fig. 7a-i with adjacency matrix A shown in Fig. 7a-ii, the constrained binary quadratic programming problem is formed as follows:

According to processing step 108, the constrained binary quadratic programming problem is provided to a quantum annealing solver.

It will be appreciated that the constrained binary quadratic programming problem may be provided to the quantum annealing solver according to various embodiments.

Now referring to Fig. 2, there is shown a first embodiment for providing the constrained binary quadratic programming problem to the quantum annealing solver.

In this embodiment, the quantum annealing solver is an unconstrained quantum annealing solver.

According to processing step 202, an unconstrained binary quadratic problem is generated.

In one embodiment, the constrained binary quadratic programming problem is converted into an unconstrained binary quadratic programming problem using an appropriate penalty-based method by introducing slack variables and penalty coefficients (D-Wave Systems, Inc. Programming with QUBOs. Technical report, D-Wave Systems, Inc., 2015, Release 2.1 , 09-1002A-B). The skilled addressee will appreciated that various alternative embodiments may be possible.

Now referring to Fig. 7c, there is shown an embodiment of an unconstrained binary quadratic problem corresponding to the distance matrix shown in Fig. 7b.

Still referring to Fig. 2 and according to processing step 204, the generated unconstrained binary quadratic problem is provided to the unconstrained quantum annealing solver.

It will be appreciated that the generated unconstrained binary quadratic problem is provided to the unconstrained quantum annealing solver for the purpose of solving it.

It will be appreciated that the solving of the generated unconstrained binary quadratic problem by the unconstrained quantum annealing solver may be performed according to various embodiments.

In one embodiment, having formed the unconstrained binary quadratic programming, the solve_ubqp subroutine is called and the result is provided. The following code snippet is an embodiment of how the solve_ubqp subroutine can be implemented using D-Wave SAPI 2.0 (see D-Wave Systems, Inc. Developer Guide for Python, Programming guide, D-Wave Systems, Inc., 2016, Release 2.3, 09-1024A-A).

The subroutine solve_ubqp receives an object of type ubqp representative of an unconstrained binary quadratic programming problem and returns an object of type ubqp_result representative of a vector with binary entries. It will be appreciated that all the functions and types used in this snippet are supported by SAPI 2.0 except two auxiliary functions qubo_to_ising and spin_to_binary. The former function changes an unconstrained binary quadratic programming problem of type ubqp, to an Ising spin problem of type sapi_problem by a change of variables s = 2x - 1. The second function receives an array of vectors in {-1,1} and returns binary vectors by applying the inverse transformation

Now referring to Fig. 7d, there is shown an example of the at least one approximate solution, that is, nodes 4, 5, and 7, shown in black, to the constrained binary quadratic problem shown in Fig. 7c for the distance matrix shown in Fig. 7b. This solution is a disconnected solution with two connected components, nodes 4 and 7, the connection indicated using a heavy black edge.

Now referring to Fig. 3, there is shown another embodiment for providing the constrained binary quadratic programming problem to a quantum annealing solver. In this embodiment, the quantum annealing solver is an unconstrained quantum annealing solver.

According to processing step 302, a solver subroutine is obtained.

It will be appreciated that the solver subroutine, also referred to as an input constrained binary quadratic programming solver subroutine, may be obtained according to various embodiments.

In one embodiment, the solver subroutine is obtained from a user.

In one embodiment, the input constrained binary quadratic programming solver subroutine is a branch and bound procedure using Lagrangian dual bounds generated by a quantum annealer (Ronagh, Pooya; Iranmanesh, Ehsan; and Woods, Brad, 2015, Canadian Patent Application No. 2,881 ,033, filed February 3, 2015).

In an alternative embodiment, the input constrained binary quadratic programming solver subroutine is the commercial solver IBM ILOG CPLEX Optimization Studio manufactured by IBM.

In an alternative embodiment, the input constrained binary quadratic programming solver subroutine is the commercial solver Gurobi Optimizer manufactured by Gurobi Optimization.

It will be appreciated that various alternative constrained binary quadratic programming solver subroutines may be input by the user.

It will be appreciated that the result from the execution of the solver subroutine is at least one approximate solution. Now referring back to Fig. 1 and according to processing step 1 10, at least one approximate solution is obtained.

It will be appreciated that in the embodiment where the quantum annealing solver is a constrained quantum annealing solver, the at least one approximate solution is obtained from the constrained quantum annealing solver.

It will be further appreciated that in the embodiment where the quantum annealing solver is an unconstrained quantum annealing solver, the at least one approximate solution is obtained from the unconstrained quantum annealing solver.

It will be appreciated that the at least one approximate solution to the minimum connected dominating set problem is a minimum dominating set whose constituent nodes are as close together as possible.

According to processing step 1 12, a post-processing is performed on the at least one approximate solution to the minimum connected dominating set problem obtained.

Now referring to Fig. 4, there is shown an embodiment for performing a postprocessing of the at least one approximate solution to the minimum connected dominating set problem obtained.

According to processing step 400, at least one approximate solution is provided.

According to processing step 402, the at least one approximate solution is made to be connected. It will be appreciated that the purpose of processing step 402 is to provide a connected dominating set, since the at least one approximate solution may not necessarily be a connected subgraph.

In one embodiment, a connected dominating set is provided using a greedy algorithm. For example, first all of the connected components indicated by the approximate solution are found. Then the nodes of the graph which are not in any of the connected components are sorted decreasingly according to the number of nodes in the components which are adjacent to them. Then the first node in the sorted list is added to the approximate solution, and the connected components are updated. This procedure is repeated until the updated approximate solution induces a connected subgraph of the input graph.

It will be appreciated by the skilled addressee that another algorithm may be used to make the at least one approximate solution to the minimum connected dominating set problem. It will be appreciated by the skilled addressee that another algorithm may be used to make the at least one approximate solution to the minimum connected dominating set problem. For example, a Steiner tree-based approach may be used (Min, Manki, Du, Hongwei, Jia, Xiaohua, Huang, Christina Xiao, Huang, Scott C.-H., and Wu, Weili, Improving Construction for Connected Dominating Set with Steiner Tree in Wireless Sensor Networks, Journal of Global Optimization, vol. 35, no. 1 , pp.1 1 1 -1 19, http://dx.doi.org/10.1007/s10898-005- 8466-1 ).

Still referring to Fig. 4 and according to processing step 404, a test is performed in order find out if there is at least one redundant node in the at least one approximate solution.

In the case where there is at least one redundant node and according to processing step 406, a node of the at least one redundant node is selected.

According to processing step 408, a test is performed in order to find out if the removal of the selected redundant node leaves a connected dominating set and if the remaining nodes dominate the entire graph.

If this is the case and according to processing step 410, the selected redundant node is removed from the at least one approximate solution.

According to processing step 412, a test is performed in order to find out if there is at least one redundant node left. In the case where there is at least one redundant node left and according to processing step 406, a redundant node is selected.

In the case where there is not at least one redundant node left and according to processing step 414, at least one post-processed solution is stored. It will be appreciated that the storing of the at least one post-processed solution is optional. Now referring to Fig. 7e, there is shown an example of post-processing performed on the at least one approximate solution shown in Fig. 7d. Considering this example, one can check that although the approximate solution, that is, nodes 4, 5, and 7, are dominating the whole graph and are as close together as possible, they do not induce a connected subgraph. The post-processing step adds node 8 to the approximate solution. In the example, after performing the post-processing step, no redundant nodes are found, so the result consists of nodes 4, 5, 7, and 8, whose connection is shown with heavy black edges connecting these nodes in the graph.

The skilled addressee will appreciate that another algorithm may be used for post-processing the at least one approximate solution.

Now referring back to Fig. 1 and according to processing step 1 14, the at least one post-processed solution is provided.

Now referring to Fig. 6, there is shown an embodiment of a digital computer 502. It will be appreciated that the digital computer 502 may also be broadly referred to as a processing unit.

In this embodiment, the digital computer 502 comprises a central processing unit (CPU) 602, also referred to as a microprocessor, a display device 604, input devices 606, communication ports 608, a data bus 610, and a memory unit 612.

The CPU 602 is used for processing computer instructions. The skilled addressee will appreciate that various embodiments of the CPU 602 may be provided.

In one embodiment, the CPU 602 is a CPU Core i7-3820 running at 3.6 GHz and manufactured by lntel ^(TM) .

The display device 604 is used for displaying data to a user. The skilled addressee will appreciate that various types of display device 604 may be used.

In one embodiment, the display device 604 is a standard liquid-crystal display (LCD) monitor.

The communication ports 608 are used for sharing data with the digital computer 502. The communication ports 608 may comprise for instance a universal serial bus (USB) port for connecting a keyboard and a mouse to the digital computer 502.

The communication ports 608 may further comprise a data network communication port such as an IEEE 802.3 (Ethernet) port for enabling a connection of the digital computer 502 with another computer via a data network. The skilled addressee will appreciate that various alternative embodiments of the communication ports 608 may be provided.

In one embodiment, the communication ports 608 comprise an Ethernet port and a mouse port (e.g., Logitech ^(TM) ).

The memory unit 612 is used for storing computer-executable instructions.

It will be appreciated that the memory unit 612 comprises, in one embodiment, an operating system module 614. It will be appreciated by the skilled addressee that the operating system module 614 may be of various types.

In an embodiment, the operating system module 614 is Windows(™) manufactured by Microsoft ^(TM) .

The memory unit 612 further comprises an application for determining a minimum connected dominating set in a graph 616.

The application for determining a minimum connected dominating set in a graph 616 comprises instructions for obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges.

The application for determining a minimum connected dominating set in a graph 616 further comprises instructions for generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes.

The application for determining a minimum connected dominating set in a graph 616 further comprises instructions for generating a corresponding constrained binary quadratic programming problem using the generated distance table.

The application for determining a minimum connected dominating set in a graph 616 further comprises instructions for providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver. The application for determining a minimum connected dominating set in a graph 616 further comprises instructions for obtaining at least one approximate solution from the quantum annealing solver.

The application for determining a minimum connected dominating set in a graph 616 further comprises instructions for post-processing the at least one approximate solution.

The application for determining a minimum connected dominating set in a graph 616 further comprises instructions for providing the post-processed at least one approximate solution.

Each of the CPU 602, the display device 604, the input devices 606, the communication ports 608, and the memory unit 612 is interconnected via the data bus 610.

It will be appreciated that a non-transitory computer-readable storage medium is further disclosed. The non-transitory computer-readable storage medium is used for storing computer-executable instructions which, when executed, cause a digital computer to perform a method for determining a minimum connected dominating set in a graph. The method comprises obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes; generating a corresponding constrained binary quadratic programming problem using the generated distance table; providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver; obtaining at least one approximate solution from the quantum annealing solver; post- processing the at least one approximate solution and providing the post-processed at least one approximate solution.

Now referring to Fig. 8, there is disclosed an embodiment of a method for determining a solution to an NP hard combinatorial optimization problem. It will be appreciated by the skilled addressee that this method is used for finding a solution to a problem for which a usable quadratic unconstrained binary optimization problem does not exist. In this embodiment, a quadratic unconstrained binary optimization problem related to the original problem is first found and a solution is then determined.

More precisely and according to processing step 800, an indication of the NP hard combinatorial optimization problem to solve is obtained.

It will be appreciated that the indication of the NP hard combinatorial optimization problem to solve may be obtained according to various embodiments. In one embodiment, the indication of the NP hard combinatorial optimization problem to solve is obtained using a digital computer.

According to processing step 802, a matrix is generated. It will be appreciated that the generated matrix is one of a distance table and an adjacency matrix of an auxiliary graph depending on a structure of the NP hard combinatorial optimization problem. More precisely, a distance table may be used when solutions to the NP hard combinatorial optimization problem can be improved through distance optimization while an adjacency matrix may be used when the auxiliary graph is a conflict graph. In one embodiment, the matrix is generated using the digital computer.

According to processing step 804, a corresponding quadratic unconstrained binary optimization problem is generated using the generated matrix. It will be appreciated that when the NP hard combinatorial optimization problem is the minimum connected dominating set problem, the corresponding quadratic unconstrained binary optimization problem is the problem which minimizes the sum of distances and contains the domination constraints, penalized, and moved into the objective function. In one embodiment, the corresponding quadratic unconstrained binary optimization problem is generated using the digital computer.

According to processing step 806, the corresponding quadratic unconstrained binary optimization problem is provided to a solver. It will be appreciated that the solver is a quadratic unconstrained binary optimization solver. In one embodiment, the corresponding quadratic unconstrained binary optimization problem is provided to the solver using the digital computer. According to processing step 808, an approximate solution to the corresponding quadratic unconstrained binary optimization problem is obtained. It will be appreciated that the approximate solution to the corresponding quadratic unconstrained binary optimization problem is obtained from the solver using the digital computer.

According to processing step 810, the approximate solution to the corresponding quadratic unconstrained binary optimization problem is converted into a near-optimal solution to the NP hard combinatorial optimization problem. It will be appreciated that when the NP hard combinatorial optimization problem is the minimum connected dominating set problem, and the corresponding quadratic unconstrained binary optimization problem is as described above, the approximate solution is a minimum dominating set such that sum of distances is minimal. The approximate solution is modified, through a post-processing routine to convert the solution into a connected minimum dominating set. In one embodiment, the approximate solution to the corresponding quadratic unconstrained binary optimization problem is converted into the near-optimal solution to the NP hard combinatorial optimization problem using the digital computer.

According to processing step 812, the near-optimal solution to the NP hard combinatorial optimization problem is provided. It will be appreciated that the near- optimal solution to the NP hard combinatorial optimization problem may be provided according to various embodiments. In one embodiment, the near-optimal solution to the NP hard combinatorial optimization problem is provided using the digital computer.

It will be appreciated that an advantage of the method disclosed herein is that it enables the determining of a near-optimal solution to a minimum connected dominating set problem for many problem instances in less time compared to an exact classical algorithm.

It will be further appreciated that the method disclosed herein is capable of determining a near optimal solution to a minimum connected dominating set problem involving a large graph thanks to the use of the quantum annealing solver. Prior-art classical solvers are not capable of determining a near optimal solution to a minimum connected dominating set problem involving a large graph.

It will be appreciated that the method disclosed herein does not rely on an exact solution to the constrained binary quadratic programming problem. As a consequence, the inherently probabilistic (or "noisy") nature of solutions provided by current quantum annealers is not necessarily detrimental to the solving of the minimum connected dominating set problem involving the minimum connected dominating set algorithm.

It will be appreciated that the method disclosed herein may be used advantageously in various applications.

Application of the Method Disclosed Herein in a Protein-Protein Interaction Network

An example of an application of the method is with a protein-protein interaction network. More precisely, this application pertains to identifying at least one biologically central protein in a protein-protein interaction (PPI) network.

As known to the skilled addressee, proteins are vital biomolecules that facilitate cellular functions through molecular interactions. In fact, diverse molecular processes within a cell are carried out through physical interactions between proteins or are mediated by proteins (i.e., protein-ligand interactions).

Given the many, complex relationships between proteins, network-based approaches are natural candidates to provide a deeper insight into proteins and their interaction network.

Certain proteins play a more central role in a given protein-protein interaction due to the fact they interact with a high number of other proteins in the network. This makes these biologically central proteins important in the sense that a minor change in their functionality, or activity, can lead to a significant impact on the function of the entire protein-protein interaction network. This makes biologically central proteins promising candidates as targets for novel drugs. Hence there is motivation to identify biologically central proteins in a protein-protein interaction network as they may have significant therapeutic potential. It has been demonstrated that a minimum dominating set of a protein-protein interaction network captures biologically vital proteins (see Milenkovic et al - https://www.ncbi.nlm.nih.gov/pubmed/21887225, and Zhang et al https://bmcbioinformatics.biomedcentral.eom/articles/10.1 186/s12859-015-0591 -3). Noting the topologically central role of nodes in a minimum dominating set of a graph, it has been shown that an appropriate dominating set algorithm is able to capture a set of proteins in a protein-protein interaction network that are involved in important biological processes and mechanisms crucial for cell vitality. Particularly, a minimum dominating set of a protein-protein interaction network would contain biologically central (BC) proteins and signaling pathways (SPs). Furthermore, since signaling pathways are connected to each other, obtaining connected dominating sets in a protein-protein interaction network is an effective way for recognizing signaling pathways and the signaling pathway proteins that intermediate such connections.

In fact, the application of dominating set algorithms to human protein-protein interaction networks has shown to be useful as disclosed above. Experimental studies show that the enrichment of genes of biologically central proteins and signaling pathways genes of nodes of dominating sets are much higher than the enrichment of the nodes which are not in dominating sets (see Milenkovic et al - https://www.ncbi.nlm.nih.gov/pubmed/21887225). Furthermore, biologically central proteins and signaling pathways genes that are in dominating sets have much higher and statistically significant enrichment in known drug targets than biologically central proteins and signaling pathway genes that do not exist in dominating sets. Hence, dominating sets capture proteins of biological relevance to disease states and drug targets.

Accordingly, the method disclosed herein may be therefore advantageously used for identifying at least one biologically central protein in a protein-protein interaction network comprising a plurality of proteins. In such embodiment, the input graph is indicative of the protein-protein interaction network. More precisely, the method for identifying at least one biologically central protein in a protein-protein interaction network comprises obtaining an indication of an input graph indicative of a protein-protein interaction network, the input graph comprising a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a given protein and each edge of the input graph is representative of a physical interaction between two given proteins. The method for identifying at least one biologically central protein in a protein-protein interaction network further comprises generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes. The method for identifying at least one biologically central protein in a protein-protein interaction network further comprises generating a corresponding constrained binary quadratic programming problem using the generated distance table. The method for identifying at least one biologically central protein in a protein- protein interaction network further comprises providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver. The method for identifying at least one biologically central protein in a protein-protein interaction network further comprises obtaining at least one approximate solution from the quantum annealing solver. The method for identifying at least one biologically central protein in a protein-protein interaction network further comprises post-processing the at least one approximate solution and providing the post- processed at least one approximate solution to thereby provide an indication of at least one biologically central protein in the protein-protein interaction network.

Application of the Method Disclosed Herein in a Mobile Ad-Hoc Network

Another application in which the method disclosed herein may be advantageously used is for designing a mobile ad-hoc network.

As mentioned previously, the mobile ad-hoc network is comprised of nodes wherein each node is a mobile device with a limited energy source. The goal is to find a virtual backbone which will have the smallest size possible and the nodes of which will be used in the routing procedures. The method will therefore be used for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices.

In such embodiment, the input graph is indicative of a mobile ad-hoc network. The input graph comprises a plurality of nodes and a plurality of edges. Each node of the input graph is representative of a given mobile device having a corresponding energy source and each edge is representative of a wireless connection between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes.

The method for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices comprises obtaining an indication of an input graph indicative of a mobile ad-hoc network, the input graph comprising a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a given mobile device having a corresponding energy source and each edge is representative of a wireless connection between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes. The method for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices further comprises generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes. The method for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices further comprises generating a corresponding constrained binary quadratic programming problem using the generated distance table. The method for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices further comprises providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver. The method for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices further comprises obtaining at least one approximate solution from the quantum annealing solver. The method for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices further comprises post-processing the at least one approximate solution and providing the post-processed at least one approximate solution to thereby provide an indication of a virtual backbone in the mobile ad-hoc network.

Application of the Method Disclosed Herein in an Optical Telecommunication Network

It will be appreciate that the method disclosed herein may be used in the development of an optical telecommunication network.

As mentioned above, one of the main problems that an optical telecommunication network must overcome is the deterioration of the optical signal as the distance from a source increases. Signals must be regenerated periodically using regenerators. In practice, the optical telecommunication network is designed so that regenerators are placed at nodes of the network in a way such that all nodes of the network can communicate without significant signal impairments. These regenerators can be said to form the backbone of the network.

One can see that designing a smallest-sized backbone as well as finding the minimum number of regenerators in an optical telecommunication network is a matter of solving a minimum connected dominating set problem.

In such embodiment, the input graph is indicative of an optical telecommunication network. The input graph comprises a plurality of nodes and a plurality of edges. Each node of the input graph is representative of a user or a hub and each edge is representative of a connection via a fiber optic cable between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes.

The method for identifying a backbone in an optical telecommunication network comprising a plurality of users and hubs comprises obtaining an indication of an input graph indicative of an optical telecommunication network, the input graph comprising a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a user or a hub and each edge is representative of a connection via a fiber optic cable between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes. The method for identifying a backbone in an optical telecommunication network further comprises generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes. The method for identifying a backbone in an optical telecommunication network further comprises generating a corresponding constrained binary quadratic programming problem using the generated distance table. The method for identifying a backbone in an optical telecommunication network further comprises providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver. The method for identifying a backbone in an optical telecommunication network further comprises obtaining at least one approximate solution from the quantum annealing solver. The method for identifying a backbone in an optical telecommunication network further comprises post-processing the at least one approximate solution and providing the post- processed at least one approximate solution to thereby provide an indication of a backbone in the optical telecommunication network.

Clauses

Clause 1 : A method for determining a minimum connected dominating set in a graph, the method comprising:

obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges;

generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes;

generating a corresponding constrained binary quadratic programming problem using the generated distance table;

providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver;

obtaining at least one approximate solution from the quantum annealing solver; post-processing the at least one approximate solution; and

providing the post-processed at least one approximate solution.

Clause 2: The method as claimed in clause 1 , wherein the quantum annealing solver is an unconstrained quantum annealing solver; further wherein the providing of the corresponding constrained binary quadratic programming problem comprises: generating an unconstrained binary quadratic programming problem using the generated constrained binary quadratic programming problem; and

providing the generated unconstrained binary quadratic programming problem to the unconstrained quantum annealing solver; and

further wherein the at least one approximate solution is obtained from the unconstrained quantum annealing solver.

Clause 3: The method as claimed in clause 1 , wherein the quantum annealing solver is a constrained quantum annealing solver; wherein the providing of the corresponding constrained binary quadratic programming problem comprises:

obtaining a corresponding solver subroutine; and

solving the generated constrained binary quadratic programming problem using the solver subroutine; further wherein the at least one approximate solution is obtained from the solver subroutine.

Clause 4: A method for determining a minimum connected dominating set in a graph, the method comprising:

obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges;

obtaining an indication of a solver to use for determining a minimum connected dominating set;

generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes; generating a corresponding constrained binary quadratic programming problem using the generated distance table;

if the indication of a solver comprises an unconstrained quantum annealing solver:

generating an unconstrained binary quadratic programming problem using the generated constrained binary quadratic programming problem,

providing the unconstrained binary quadratic programming problem to the unconstrained quantum annealing solver,

obtaining at least one approximate solution from the unconstrained quantum annealing solver,

if the indication of a solver comprises a constrained quantum annealing solver:

obtaining a corresponding solver subroutine,

solving the generated constrained binary quadratic programming problem using the solver subroutine, and

obtaining at least one approximate solution from the solver subroutine, post-processing the at least one approximate solution; and

providing the post-processed at least one approximate solution.

Clause 5: The method as claimed in any one of clauses 1 to 4, wherein the indication of an input graph is obtained from at least one of a user interacting with a digital computer, a computer operatively connected to the digital computer, a software package, and an intelligent agent.

Clause 6: The method as claimed in any one of clauses 1 to 5, wherein the post- processed at least one approximate solution is provided to at least one of a user interacting with a digital computer, a computer operatively connected to the digital computer, a software package, and an intelligent agent.

Clause 7: A non-transitory computer-readable storage medium for storing computer- executable instructions which, when executed, cause a digital computer to perform a method for determining a minimum connected dominating set in a graph, the method comprising:

obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges;

generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes;

generating a corresponding constrained binary quadratic programming problem using the generated distance table;

providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver;

obtaining at least one approximate solution from the quantum annealing solver;

post-processing the at least one approximate solution; and

providing the post-processed at least one approximate solution.

Clause 8: A digital computer comprising:

a central processing unit;

a display device;

a communication port for operatively connecting the digital computer to a quantum annealing solver;

a memory unit comprising an application for determining a minimum connected dominating set problem, the application comprising:

instructions for obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges;

instructions for generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes;

instructions for generating a corresponding constrained binary quadratic programming problem using the generated distance table; instructions for providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver;

instructions for obtaining at least one approximate solution from the quantum annealing solver;

instructions for post-processing the at least one approximate solution; and

instructions for providing the post-processed at least one approximate solution; and

a data bus for interconnecting the central processing unit, the display device, the communication port, and the memory unit.

Clause 9: A method for determining a minimum connected dominating set in a graph, the method comprising:

use of a processing unit for obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges;

use of a processing unit for generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes;

use of a processing unit for generating a corresponding constrained binary quadratic programming problem using the generated distance table;

use of a processing unit for providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver;

use of a processing unit for obtaining at least one approximate solution from the quantum annealing solver;

use of a processing unit for post-processing the at least one approximate solution; and

use of a processing unit for providing the post-processed at least one approximate solution. Clause 10: A method for determining a solution to an NP hard combinatorial optimization problem, the method comprising:

obtaining an indication of the NP hard combinatorial optimization problem to solve;

generating a matrix, wherein the generated matrix is one of a distance table and an adjacency matrix of an auxiliary graph depending on a structure of the NP hard combinatorial optimization problem;

generating a corresponding quadratic unconstrained binary optimization problem using the generated matrix;

providing the corresponding quadratic unconstrained binary optimization problem to a solver, wherein the solver is a quadratic unconstrained binary optimization solver;

obtaining an approximate solution to the corresponding quadratic unconstrained binary optimization problem;

converting the approximate solution to the corresponding quadratic unconstrained binary optimization problem into a near-optimal solution to the NP hard combinatorial optimization problem; and

providing the near-optimal solution to the NP hard combinatorial optimization problem. Clause 1 1 : A method for identifying at least one biologically central protein in a protein-protein interaction network comprising a plurality of proteins, the method comprising:

obtaining an indication of an input graph indicative of a protein-protein interaction network, the input graph comprising a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a given protein and each edge of the input graph is representative of a physical interaction between two given proteins; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes;

generating a corresponding constrained binary quadratic programming problem using the generated distance table;

providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver;

obtaining at least one approximate solution from the quantum annealing solver;

post-processing the at least one approximate solution; and

providing the post-processed at least one approximate solution to thereby provide an indication of at least one biologically central protein in the protein-protein interaction network.

Clause 12: Use of the method as claimed in any one of claims 1 to 6 for identifying at least one biologically central protein in a protein-protein interaction network comprising a plurality of proteins, wherein the input graph comprises a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a given protein and each edge of the input graph is representative of a physical interaction between two given proteins. Clause 13: A method for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices, the method comprising:

obtaining an indication of an input graph indicative of a mobile ad-hoc network, the input graph comprising a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a given mobile device having a corresponding energy source and each edge is representative of a wireless connection between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes;

generating a corresponding constrained binary quadratic programming problem using the generated distance table;

providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver;

obtaining at least one approximate solution from the quantum annealing solver;

post-processing the at least one approximate solution; and

providing the post-processed at least one approximate solution to thereby provide an indication of a virtual backbone in the mobile ad-hoc network.

Clause 14: Use of the method as claimed in any one of clauses 1 to 6 for identifying a virtual backbone in a mobile ad-hoc network comprising a plurality of mobile devices, wherein the input graph is comprised of a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a given mobile device having a corresponding energy source and each edge is representative of a wireless connection between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes.

Clause 15: A method for identifying a backbone in an optical telecommunication network comprising a plurality of users and hubs, the method comprising:

obtaining an indication of an input graph indicative of an optical telecommunication network, the input graph comprising a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a user or a hub and each edge is representative of a connection via a fiber optic cable between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other nodes of the plurality of nodes;

generating a corresponding constrained binary quadratic programming problem using the generated distance table;

providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver;

obtaining at least one approximate solution from the quantum annealing solver;

post-processing the at least one approximate solution; and

providing the post-processed at least one approximate solution to thereby provide an indication of a backbone in the optical telecommunication network.

Clause 16: Use of the method as claimed in any one of clauses 1 to 6 for identifying a backbone in an optical telecommunication network comprising a plurality of users and hubs, wherein the input graph is comprised of a plurality of nodes and a plurality of edges, wherein each node of the input graph is representative of a user or a hub and each edge is representative of a connection via a fiber optic cable between two given nodes and each edge has a weight representative of an energy cost for communicating between the two given nodes.

Although the above description relates to a specific preferred embodiment as presently contemplated by the inventor, it will be understood that the invention in its broad aspect includes functional equivalents of the elements described herein.