Graph embedding techniques
View Patent ↗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.
1. 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;
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; and
optimizing the embedding of the source graph onto the quantum processor, wherein optimizing the embedding of the source graph onto the quantum processor includes at least one of:
performing a degree-K pruning, wherein K is a positive integer; disconnecting at least one vertex in the target graph from another vertex in the target graph, wherein disconnecting at least one vertex in the target graph from another vertex in the target graph includes deactivating a coupling device therebetween; connecting at least one vertex in the target graph to another vertex in the target graph, wherein connecting at least one vertex in the target graph to another vertex in the target graph includes activating a coupling device therebetween; reducing a total number of vertices in the target graph; reducing a total number of edges in the target graph; reducing an area occupied by the target graph; executing a path finding algorithm to optimize an assignment of the vertices in the target graph; or executing a path finding algorithm to optimize an assignment of the edges in the target graph.
2. The method of claim 1 wherein embedding the source graph onto the quantum processor comprises programming at least some of the qubits in the quantum processor to represent the vertices of the source graph and programming at least some of the coupling devices in the quantum processor to represent the edges of the source graph.
3. The method of claim 2 wherein embedding the source graph onto the quantum processor further comprises:
assigning a first vertex from the source graph to a first island in the target graph, the first island in the target graph comprising a first connected set of vertices in the target graph represented by a first set of qubits in the quantum processor, wherein assigning a first vertex from the source graph to a first island in the target graph includes controlling a first set of coupling devices to couple the first set of the qubits together.
4. The method of claim 3 wherein embedding the source graph onto the quantum processor further comprises:
assigning a second vertex from the source graph to a single vertex in the target graph, the single vertex in the target graph represented by a single qubit in the quantum processor; and
assigning a first edge from the source graph to a single edge in the target graph, the single edge in the target graph represented by a single coupling device in the quantum processor, wherein assigning a first edge from the source graph to a single edge in the target graph includes controlling the single coupling device to couple the single qubit to a qubit from the first set of qubits.
5. The method of claim 3 wherein embedding the source graph onto the quantum processor further comprises:
assigning a second vertex from the source graph to 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 quantum processor, wherein assigning a second vertex from the source graph to a second island in the target graph includes controlling a second set of coupling devices to couple the second set of the qubits together; and
assigning a first edge from the source graph to a first bridge in the target graph, the first bridge in the target graph represented by at least one coupling device in the quantum processor, wherein assigning a first edge from the source graph to a first bridge in the target graph 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.
6. The method of claim 1 wherein the number of vertices in the target graph is greater than the number of vertices in the source graph.
7. 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;
assigning a second set of at least two qubits in the quantum processor to represent a second vertex from the source graph;
controlling a second set of controllable couplings to couple the second set of at least two qubits together; and
assigning at least one coupling device in the quantum processor to represent a first edge from the source graph, wherein assigning at least one coupling device in the quantum processor to represent a first edge from the source graph includes controlling the at least one coupling device to couple at least one qubit from the first set of at least two qubits to at least one qubit from the second set of at least two qubits.
8. The method of claim 7 wherein embedding the source graph onto the quantum processor further comprises:
assigning a single qubit in the quantum processor to represent a third vertex from the source graph; and
assigning a coupling device in the quantum processor to represent a second edge from the source graph, wherein assigning a coupling device in the quantum processor to represent a second edge in the source graph includes controlling the coupling device to couple the single qubit to a qubit from the first set of at least two qubits.
9. The method of claim 7 , further comprising:
optimizing the embedding of the source graph onto the quantum processor.
10. The method of claim 9 wherein optimizing the embedding of the source graph onto the quantum processor includes at least one of:
performing a degree-K pruning, wherein K is a positive integer; deactivating at least one coupling device; activating at least one additional coupling device; reducing a total number of assignments to qubits in the quantum processor; reducing a total number of coupling devices used in the quantum processor; executing a path finding algorithm to optimize the assignment of the qubits; and/or executing a path finding algorithm to optimize the assignment of the coupling devices.
11. 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;
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; and
optimizing the embedding of the source graph onto the quantum processor.
12. The method of claim 11 wherein optimizing the embedding of the source graph onto the quantum processor includes at least one of:
performing a degree-K pruning, wherein K is a positive integer; deactivating at least one coupling device; activating at least one additional coupling device; reducing a total number of assignments to qubits in the quantum processor; reducing a total number of coupling devices used in the quantum processor; executing a path finding algorithm to optimize the assignment of the qubits; and/or executing a path finding algorithm to optimize the assignment of the coupling devices.
13. The method of claim 11 wherein embedding the source graph onto the quantum processor further comprises:
assigning a single qubit in the quantum processor to represent a second vertex from the source graph; and
assigning a coupling device in the quantum processor to represent a first edge from the source graph, wherein assigning a coupling device in the quantum processor to represent a first edge in the source graph includes controlling the coupling device to couple the single qubit to a qubit from the first set of at least two qubits.
14. The method of claim 11 wherein embedding the source graph onto the quantum processor further comprises:
assigning a second set of at least two qubits in the quantum processor to represent a second vertex from the source graph;
controlling a second set of controllable couplings to couple the second set of at least two qubits together; and
assigning at least one coupling device in the quantum processor to represent a first edge from the source graph, wherein assigning at least one coupling device in the quantum processor to represent a first edge from the source graph includes controlling the at least one coupling device to couple at least one qubit from the first set of at least two qubits to at least one qubit from the second set of at least two qubits.