Patent Document ID: 9875215
Application ID: 14109657
Patent Flag: 1

Claim One:
1. A method for finding a decomposition for a primal graph having a number of vertices and a number of edges given a hardware specific graph, the hardware specific graph representing a target processor comprising qubits coupleable by couplers, the hardware specific graph comprising a plurality of vertices corresponding to qubits coupleable via a number of edges represented by couplers, the method comprising: in a first stage, building a decomposition of the primal graph, by at least one circuit, given a hardware specific graph, the building by: sequentially adding each vertex in the primal graph to the decomposition, wherein: each vertex in the primal graph is associated with a connected subgraph in a set of connected subgraphs that is a first representation of the decomposition, each edge in the primal graph is represented as a path from a first respective connected subgraph and a second respective connected subgraph, and for each vertex, sequentially adding the vertex in the primal graph to the decomposition minimizes a measure of the decomposition via execution of a greedy algorithm; in a second stage, following the first stage, refining, by the at least one circuit, the decomposition created in the first stage by: removing in sequence each vertex from the decomposition, re-adding the vertex into the decomposition to minimize the measure of the decomposition; returning the decomposition as a problem formulation executable by the target processor; and embedding the problem formulation on the target processor by configuring at least one of the qubits and the couplers of the target processor based on at least one of the vertices and edges of the decomposition; wherein configuring the at least one of the qubits and couplers comprises communicatively coupling a first qubit corresponding to a first vertex of the problem formulation to a second qubit corresponding to a second vertex of the problem formulation by a first coupler corresponding to a first edge of the problem formulation.