Systems and methods that formulate problems for solving by a quantum processor using hardware graph decomposition

Patent metadata

Field	Value
Publication number	US-9875215-B2
Application number	US-201314109657-A
Country	US
Kind code	B2
Filing date	Dec 17, 2013
Priority date	Dec 18, 2012
Publication date	Jan 23, 2018
Grant date	Jan 23, 2018

Abstract

Systems and methods formulate problems for solving by a quantum processor using hardware graph decomposition. A decomposition of a primal graph may be built in a first stage based on a hardware specific graph, and refined in a second stage by, for example, removing vertices from the decomposition. The hardware specific graph may be a graph that is specific to a piece of hardware, for instance a quantum processor comprising a plurality of qubits and couplers operable to communicatively couple pairs of qubits.

First claim

The invention claimed is:

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.

2. The method of claim 1 further comprising:
receiving the primal graph and the hardware specific graph.

3. The method of claim 1 wherein the hardware specific graph is a Chimera graph.

4. The method of claim 1 wherein the measure of the decomposition is over the first representation of the decomposition.

5. The method of claim 4 wherein the measure of the decomposition over the first representation of the decomposition is proportional to the length of the set of connected subgraphs.

6. The method of claim 1 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 qubits that includes a respective bag-width.

7. The method of claim 6 wherein the measure of the decomposition over the second representation of the decomposition includes a summation over the bag-width of the decomposition.

8. The method of claim 6 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.

9. The method of claim 1 wherein the measure of the decomposition is over a second representation of the decomposition and includes a maximum bag-width of a number of bag-widths of the decomposition.

10. The method of claim 1 wherein sequentially adding each vertex in the primal graph to the decomposition further comprises:
finding a minimum cost qubit of the hardware specific graph; and
finding a weighted shortest path through a set of unused vertices in the hardware specific graph.

11. The method of claim 1 wherein the primal graph is associated with a quadratic unconstrained binary optimization (QUBO) problem, the hardware specific graph is representative of at least one quantum processor that includes a plurality of qubits and a plurality of couplers.

12. The method of claim 1 , further comprising:
assigning a truth assignment to a plurality of variables associated with the primal graph by the at least one circuit;
while the truth assignment has not converged:
for each bag in a plurality of bags, conducting a local search from the truth assignment to generate a candidate set of new truth assignments by the at least one circuit;
comparing the truth assignment to the candidate set of new truth assignments by the at least one circuit; and
updating the truth assignment with the best of the candidate set of truth assignments if a new truth assignment from the candidate set of new truth assignments is better than the truth assignment by the at least one circuit.

Assignees

• D Wave Systems Inc

Inventors

• Macready William
• Roy Aidan Patrick

Classifications

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06F17/10 Primary

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06N99/002

  Physics · mapped topic

• G06N10/60

  Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms · CPC title

• G06N10/40

  Physical realisations or architectures of quantum processors or components for manipulating qubits, e.g. qubit coupling or qubit control · CPC title