# US 2017/0286852 A1 · Method and system for solving a minimum connected dominating set problem using quantum annealing for distance optimization

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0286852 A1
- Document ID: US20170286852A1
- Status: Published application
- Kind: A1
- Application number: 15/085,651
- Filed: 2016-03-30
- Published: 2017-10-05
- Earliest claimed: 2016-03-30
- Assignees: 1Qb Information Technologies Inc.
- Applicants: 1Qb Information Technologies Inc.
- Inventors: Seyed Saeed Changiz REZAIE; Brad WOODS; Pooya RONAGH
- Web page: https://patentgrep.com/patent/US20170286852A1

## CPC

- G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202)
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 5/048: Fuzzy inferencing
- G06N 20/00: Machine learning
- G06Q 10/40: Business processes related to social networking or social networking services
- H04L 67/306: User profiles
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method is disclosed 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 node 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.

## Claims

### Claim 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 node 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.

### Claim 2 (depends on 1)

The method as claimed in claim 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.

### Claim 3 (depends on 1)

The method as claimed in claim 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.

### Claim 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 node 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.

### Claim 5 (depends on 1)

The method as claimed in claim 1, 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.

### Claim 6 (depends on 1)

The method as claimed in claim 1, 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.

### Claim 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 node 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.

### Claim 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 node 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.

### Claim 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 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 node 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.
