Graph embedding techniques
AssigneeD-Wave Systems Inc.
InventorsMichael Coury, William G. Macready, David Grant
Life of this patent
Estimating the term…
Abstract
Approaches to embedding source graphs into targets graphs in a computing system are disclosed. Such may be advantageously facilitate computation with computing systems that employ one or more analog processors, for example one or more quantum processors.
Claims16
A method for use in the solution of a problem by a quantum processor that comprises a number of qubits with coupling devices therebetween, the method comprising:
- mapping the problem into a source graph having a graph format which includes a number of vertices and a number of edges, the edges connecting respective pairs of the vertices;
- and
- embedding the source graph onto the quantum processor as a target graph which includes a number of vertices and a number of edges, wherein each vertex from the source graph is represented by at least one respective qubit in the quantum processor and each edge from the source graph is represented by at least one respective coupling device in the quantum processor, and wherein at least one vertex from the source graph is represented by two or more qubits in the quantum processor.
A method for use in the solution of a problem by a quantum processor that comprises a number of qubits with coupling devices therebetween, the method comprising:
- mapping the problem into a source graph having a graph format which includes a number of vertices and a number of edges, the edges connecting respective pairs of the vertices;
- and embedding the source graph onto the quantum processor, wherein embedding the source graph onto the quantum processor comprises assigning a first set of at least two qubits in the quantum processor to represent a first vertex from the source graph and controlling a first set of coupling devices to couple the first set of at least two qubits together.
A method of embedding a problem onto a quantum processor that comprises a number of qubits with coupling devices therebetween, wherein the problem comprises a number of variables with relationships therebetween, the method comprising:
- programming at least some of the qubits in the quantum processor to represent the variables from the problem, wherein a first set of at least two qubits in the quantum processor represent a first variable from the problem;
- and
- programming at least some of the coupling devices in the quantum processor to represent the relationships between the variables from the problem, wherein at least a first coupling device couples the first set of at least two qubits together.
Dependencies are inferred from the claim text.