Patent ID: 7984012

Claim:
A computer-implemented method of embedding a source graph into a target graph in a computing system, wherein the computing system includes a processor comprising a network of qubits and coupling devices operable to couple respective pairs of the qubits, the source graph includes a number of vertices and a number edges, wherein the edges in the source graph define relationships between pairs of the vertices in the source graph, and the target graph includes a number of vertices and a number of edges, wherein each vertex in the target graph is represented by at least one respective qubit in the computing system and each edge in the target graph is represented by at least one respective coupling device in the computing system, the method comprising: for a first vertex in the source graph, forming a first island in the target graph, the first island comprising a first connected set of vertices in the target graph represented by a first set of qubits in the computing system, wherein forming a first island in the target graph includes controlling a first set of coupling devices to couple the first set of qubits together; for a second vertex in the source graph, forming a second island in the target graph, the second island comprising a second connected set of vertices in the target graph represented by a second set of qubits in the computing system, wherein forming a second island in the target graph includes controlling a second set of coupling devices to couple the second set of qubits together; and for a first edge in the source graph that defines a relationship between the first vertex in the source graph and the second vertex in the source graph, forming a first inter-island bridge in the target graph, the first inter-island bridge comprising at least one inter-island edge connecting a first vertex in the first island in the target graph to a first vertex in the second island in the target graph, wherein forming a first inter-island bridge includes controlling at least one coupling device to couple at least one qubit from the first set of qubits to at least one qubit from the second set of qubits.