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

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.

1 - 36 . (canceled) 
     
     
         37 . A method for use in embedding a problem in a target processor, the problem represented as a problem graph having a number of vertices and a number of edges 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, building a decomposition of the problem graph, by at least one circuit, given a hardware graph, the building by:   sequentially adding each vertex in the problem graph to the decomposition,   wherein:
 each vertex in the problem 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 problem graph is represented as a path from a first respective connected subgraph and a second respective connected subgraph, and 
 sequentially adding of a vertex in the problem graph to the decomposition which 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; and 
 transmitting a problem formulation executable by the target processor based on the refining of the decomposition. 
   
     
     
         38 . The method of  claim 37  further comprising receiving the problem graph and the hardware graph. 
     
     
         39 . The method of  claim 37  wherein the hardware graph is a Chimera graph. 
     
     
         40 . The method of  claim 37  wherein the measure of the decomposition is over the first representation of the decomposition. 
     
     
         41 . The method of  claim 40  wherein the measure of the decomposition over the first representation of the decomposition is proportional to the length of the connected subgraphs the set of connected subgraphs. 
     
     
         42 . The method of  claim 37  wherein the measure of the decomposition is over a second representation of the decomposition, the second representation of the decomposition is a plurality of bags, and each bag is a set of one or more variables represented at one or more qubit that includes a respective bag-width. 
     
     
         43 . The method of  claim 42  wherein the measure of the decomposition over the second representation of the decomposition includes a summation over the bag-width of the decomposition. 
     
     
         44 . The method of  claim 42  wherein the measure of the decomposition over the second representation of the decomposition includes a maximum bag-width of the bag-width of the decomposition. 
     
     
         45 . The method of  claim 37  wherein the measure of the decomposition is over the second representation of the decomposition and includes a maximum bag-width of a number of bag-widths of the decomposition. 
     
     
         46 . The method of  claim 37  wherein sequentially adding a vertex in the problem graph to the decomposition further comprises:
 finding a minimum cost qubit the hardware graph; and 
 finding a weighted shortest path through a set of unused vertices in the hardware graph. 
 
     
     
         47 . The method of  claim 37  wherein the problem graph is associated with a quadratic unconstrained binary optimization (QUBO) problem, the hardware graph is representative of least one quantum processor that includes a plurality of qubits and a plurality of couplers. 
     
     
         48 . A method for solving a quadratic unconstrained binary optimization (QUBO) problem, the QUBO problem representable as a problem graph having a number of decision variables, the method performed by one or more processors and comprising:
 receiving a decomposition of the problem graph, wherein the decomposition of the graph includes a plurality of bags;   assigning, by the one or more processors, a truth assignment to a plurality of decision variables of the problem graph;   while the truth assignment has not converged:
 conducting, by the one or more processors, for each bag in the plurality of bags, a local search from the truth assignment to generate a candidate set of new truth assignments; 
 comparing the truth assignment to the candidate set of new truth assignments; and 
 updating, by the one or more processors, the truth assignment based on a result of the comparing the truth assignment to the candidate set of new truth assignments. 
   
     
     
         49 . The method of  claim 48  wherein comparing the truth assignment to the candidate set of new truth assignments comprises executing an objective function by a target processor, the target processor comprising qubits coupleable by couplers and represented as a hardware graph having a plurality of vertices coupleable via a number of edges, the objective function based on one or more interactions in the QUBO problem between decision variables. 
     
     
         50 . The method of  claim 49  wherein executing the objective function comprises assigning a penalty value to assignments where a decision variable corresponds to different truth assignments in different bags. 
     
     
         51 . The method of  claim 50  wherein the penalty value increases with time during the performance of the method. 
     
     
         52 . The method of  claim 49  wherein conducting a local search from the truth assignment to generate the candidate set of new truth assignments comprises:
 for a first bag, selecting a first truth assignment for a first variable associated with a first bag, and 
 for each other bag of the plurality of bags associated with the first variable, selecting the first truth assignment for the first variable. 
 
     
     
         53 . The method of  claim 49  wherein conducting a local search from the truth assignment to generate the candidate set of new truth assignments comprises:
 in a first stage, selecting truth assignments for each variable associated with each bag; and 
 in a second stage, resolving inconsistencies between truth assignments for each variable by, for at least one bag, reselecting at least one truth assignment for at least one variable to correspond to a truth assignment for the at least one variable in at least one other bag. 
 
     
     
         54 . The method of  claim 53  wherein reselecting the at least one truth assignment comprises determining at least one shared truth assignment shared by a majority of bags for the at least one variable and reselecting the at least one truth assignment to correspond to the at least one shared truth assignment. 
     
     
         55 . A system for solving a quadratic unconstrained binary optimization (QUBO) problem, the QUBO problem representable as a problem graph having a number of decision variables, the system comprising:
 at least one nontransitory processor-readable medium; and   at least one processor communicatively coupled to the at least one nontransitory processor-readable medium, and which in operation is configured to:   receive a decomposition of the primal graph, wherein the decomposition of the graph includes a plurality of bags;   assign a truth assignment to a plurality of decision variables of the primal graph;   while the truth assignment has not converged:
 conduct, for each bag in the plurality of bags, a local search from the truth assignment to generate a candidate set of new truth assignments; 
 compare the truth assignment to the candidate set of new truth assignments; and 
 update the truth assignment based on a result of the comparing the truth assignment to the candidate set of new truth assignments.