Systems and methods that formulate embeddings of problems for solving by a quantum processor

Patent metadata

Field	Value
Publication number	US-9501747-B2
Application number	US-201314109663-A
Country	US
Kind code	B2
Filing date	Dec 17, 2013
Priority date	Dec 18, 2012
Publication date	Nov 22, 2016
Grant date	Nov 22, 2016

Abstract

Systems and methods allow formulation of embeddings of problems via targeted hardware (e.g., particular quantum processor). In a first stage, sets of connected subgraphs are successively generated, each set including a respective subgraph for each decision variable in the problem graph, adjacent decisions variables in the problem graph mapped to respective vertices in the hardware graph, the respective vertices which are connected by at least one respective edge in the hardware graph. In a second stage, the connected subgraphs are refined such that no vertex represents more than a single decision variable.

First claim

The invention claimed is:

1. A method for use in embedding a problem in a target processor, the problem represented as a problem graph having a number of decision variables and the target processor comprising qubits coupleable by couplers and represented as a hardware graph having a plurality of vertices corresponding to qubits coupleable via a number of edges corresponding to couplers, the method comprising:
in a first stage,
successively generating a number of sets of connected subgraphs, each set including a respective subgraph for each decision variable in the problem graph, where adjacent decisions variables in the problem graph are mapped to respective vertices in the hardware graph, the respective vertices which are connected by at least one respective edge in the hardware graph, wherein successively generating a number of sets of connected subgraphs includes using used vertices in the hardware graph to represent the decision variables if no unused vertex in the hardware graph is available; and

in a second stage, following the first stage,
refining the connected subgraphs created in the first stage such that no vertex represents more than a single decision variable;
creating a problem formulation executable by the target processor based on the refining of the connected subgraphs; and
transmitting the problem formulation to the target processor for execution by the target processor.

2. The method of claim 1 wherein successively generating a number of sets of connected subgraphs includes using only unused vertices in the hardware graph to represent the decision variables if an unused vertex in the hardware graph is available.

3. The method of claim 1 wherein successively generating a number of sets of connected subgraphs includes using a weighted shortest path determination to find a shortest path that uses only unused vertices of the hardware graph.

4. The method of claim 3 wherein using a weighted shortest path determination includes, for each of at least some of the hardware vertices, exponentially increasing a weight associated with the respective hardware vertex as a function of a total number of decision variables represented by the respective hardware vertex.

5. The method of claim 3 wherein using a weighted shortest path determination includes, for each of at least some of the hardware vertices, exponentially increasing a weight associated with the respective hardware vertex as a function of a fixed value greater than one and a total number of decision variables represented by the respective hardware vertex.

6. The method of claim 3 wherein using a weighted shortest path calculation includes, for each of at least some of the hardware vertices, exponentially increasing a weight associated with the respective hardware vertex as a function of a fixed value between 2 and 10 and a total number of decision variables represented by the respective hardware vertex.

7. The method of claim 3 wherein using a weighted shortest path calculation includes, for each of at least some of the hardware vertices, exponentially increases a weight associated with the respective hardware vertex in accordance with a function given by
wt( g ):=∝ |{i:gεS i }|

where α is greater than 1.

8. The method of claim 1 wherein refining the connected subgraphs includes:
iteratively for each of the decision variables, in an defined order,
removing the connected subgraph which represents the respective decision variable from the mapping of the problem graph to the hardware graph; and
generating a replacement connected subgraph for the respective decision variable; and

after completing the removing of the connected subgraph and the generating of the replacement connected subgraph for each of the decision variables, determining whether the mapping of the problem graph to the hardware graph is improved relative to at least one previous mapping of the problem graph to the hardware graph.

9. The method of claim 8 wherein determining whether the mapping of the problem graph to the hardware graph is improved relative to at least one previous mapping of the problem graph to the hardware graph includes:
comparing a largest number of decision variables represented at a single vertex, the single vertex representing at least as many decision variables as each other vertex of the hardware graph for each of at least two different mappings of the problem graph to the hardware graph.

10. The method of claim 9 wherein determining whether the mapping of the problem graph to the hardware graph is improved relative to at least one previous mapping of the problem graph to the hardware graph includes:
comparing a total sum of lengths of the connected subgraphs for each of at least two different mappings of the problem graph to the hardware graph.

11. The method of claim 10 wherein determining whether the mapping of the problem graph to the hardware graph is improved relative to at least one previous mapping of the problem graph to the hardware graph includes:
comparing a length of a longest one of the connected subgraphs for each of at least two different mappings of the problem graph to the hardware graph.

12. The method of claim 8 , further comprising:
for each of the decision variables, storing information to at least one nontransitory processor-readable medium that identifies the connected subgraphs that represent the respective decision variable; and
storing information to at least one nontransitory processor-readable medium that specifies the paths in the hardware graph that represent each edge in the problem graph.

13. The method of claim 12 , further comprising:
based at least in part on stored information, removing at least a portion of an adjacent connected subgraph which is adjacent to one of the connected subgraphs which is being removed.

14. The method of claim 1 , further comprising:
determining whether there are any vertices in the hardware graph which represent more than one decision variable in the mapping;
determining whether a total number of iterations has exceeded a define number of iterations; and
terminating the method if at the first of determining that there are no vertices in the hardware graph which represent more than one decision variable in the mapping or the defined number of iterations has been reached.

15. The method of claim 1 wherein the problem graph is a quadratic unconstrained binary optimization (QUBO) graph, the target processor is at least one quantum processor that includes a plurality of qubits and a plurality of couplers, the couplers selectively operable to couple selected ones of the qubits to one another, and further comprising:
embedding the QUBO graph onto the quantum processor.

16. The method of claim 1 wherein the hardware graph is a Chimera graph, the at least one processor includes a digital processor, and successively generating a number of sets of connected subgraphs includes successively generating the sets of connected subgraphs in tiles of the Chimera graph by the digital processor.

17. The method of claim 1 wherein successively generating a number of sets of connected subgraphs includes:
determining by the at least one processor whether a respective vertex appears in more than one shortest connected subgraph; and
if the respective vertex appears in more than one shortest connected subgraph, adding the vertex to a connected subgraph other than the shortest connected subgraphs.

18. A system for use in embedding a problem graph in a hardware graph associated with a target processor compr

Assignees

• D Wave Systems Inc

Inventors

• Roy Aidan Patrick

Classifications

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N99/002 Primary

  Physics · mapped topic

• B82Y10/00

  Nanotechnology for information processing, storage or transmission, e.g. quantum computing or single electron logic · CPC title

• G06N10/60 Primary

  Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms · CPC title

• G06N20/00

  Machine learning · CPC title