Systems and methods for analog processing of problem graphs having arbitrary size and/or connectivity

Patent metadata

Field	Value
Publication number	US-12039407-B2
Application number	US-202318203880-A
Country	US
Kind code	B2
Filing date	May 31, 2023
Priority date	Mar 2, 2016
Publication date	Jul 16, 2024
Grant date	Jul 16, 2024

Abstract

Computational systems implement problem solving using hybrid digital/quantum computing approaches. A problem may be represented as a problem graph which is larger and/or has higher connectivity than a working and/or hardware graph of a quantum processor. A quantum processor may be used determine approximate solutions, which solutions are provided as initial states to one or more digital processors which may implement classical post-processing to generate improved solutions. Techniques for solving problems on extended, more-connected, and/or “virtual full yield” variations of the processor's actual working and/or hardware graphs are provided. A method of operation in a computational system comprising a quantum processor includes partitioning a problem graph into sub-problem graphs, and embedding a sub-problem graph onto the working graph of the quantum processor. The quantum processor and a non-quantum processor-based device generate partial samples. A controller causes a processing operation on the partial samples to generate complete samples.

First claim

The invention claimed is:

1. A method of operation in a computational system, the computational system comprising at least one digital processor and at least one analog processor comprising a plurality of qubits and one or more coupling devices arranged to form a hardware graph for embedding a problem graph, the method comprising:
receiving, by the at least one digital processor, a plurality of problems, each problem representable as a problem graph having a respective problem size;
selecting, by the at least one digital processor, a first problem from the plurality of problems based on at least one first problem property;
determining, by the at least one digital processor, a placement of the problem graph representing the first problem on a placement graph;
until no remaining problem of the plurality of problems has a problem size that can be accommodated by remaining space of the placement graph, iteratively:
selecting, by the at least one digital processor, an additional problem from the plurality of problems based on at least one additional problem property, and
determining, by the at least one digital processor, a placement of the problem graph representing the additional problem on an unoccupied region of the placement graph;

embedding, by the at least one digital processor, the placement graph comprising the problem graphs representing the first problem and each additional problem onto the hardware graph of the at least one analog processor for execution thereon;
receiving, from the at least one analog processor, an output based on results of an execution of the placement graph by the at least one analog processor; and,
generating, by the at least one digital processor, a first solution to the first problem and an additional solution to each additional problem through disaggregation of representations of a first solution and each additional solution from the output.

2. The method of claim 1 , wherein prior to the selecting, by the digital processor, a first problem from the plurality of problems, the method comprises generating a plurality of problem clusters from the plurality of problems for placement onto the placement graph.

3. The method of claim 2 , the generating a plurality of problem clusters from the plurality of problems comprises determining problem clusters based on a distance metric defined over a subset of problem properties, wherein one or more cluster partition functions are determined based on one or more problem properties of the subset of problem properties.

4. The method of claim 2 , wherein:
subsequent to the generating a plurality of problem clusters from the plurality of problems, the method comprises selecting a problem cluster from the plurality of problem clusters;
the selecting, by the at least one digital processor, a first problem from the plurality of problems based on at least one first problem property comprises selecting the first problem from the selected problem cluster; and,
the selecting, by the at least one digital processor, an additional problem from the plurality of problems based on at least one additional problem property comprises selecting the additional problem from the selected problem cluster.

5. The method of claim 4 , wherein the selecting a problem cluster from the plurality of problem clusters comprises:
determining a cluster problem property of each problem cluster, wherein the cluster problem property is a mean value of a problem property of all problems in a respective problem cluster; and,
selecting the problem cluster based on a value of the cluster problem property.

6. The method of claim 4 , wherein the selecting a problem cluster from the plurality of problem clusters comprises: selecting the problem cluster that includes a problem satisfying the at least one first problem property.

7. The method of claim 4 , wherein:
the generating a plurality of problem clusters from the plurality of problems comprises generating a plurality of problem clusters in which all problems in a respective problem cluster share the at least one first problem property; and,
the selecting, by the at least one digital processor, an additional problem from the plurality of problems based on at least one additional problem property comprises: the selecting the additional problem from the selected problem cluster based on at least one additional problem property.

8. The method of claim 7 , wherein:
the generating a plurality of problem clusters from the plurality of problems comprises generating a plurality of problem clusters in which all problems in a respective problem cluster have at least one or more of: a same problem size, a same problem computation temperature, a same number of samples to be produced, and a same overall annealing time; and,
the selecting the additional problem from the selected problem cluster based on at least one additional problem property comprises selecting the additional problem from the selected problem cluster based on at least one of: a problem priority, a placement in a problem queue, the problem size, a problem computation temperature, a number of samples to be produced, and an overall annealing time.

9. The method of claim 2 , wherein the generating a plurality of problem clusters comprises executing a clustering algorithm over the plurality of problems, wherein the clustering algorithm is one of: a k-means clustering algorithm, a fuzzy C-means clustering algorithm, hierarchical clustering, and a mixture of Gaussians.

10. The method of claim 1 , wherein the determining, by the at least one digital processor, a placement of the problem graph representing the additional problem on an unoccupied region of the placement graph comprises:
rejecting the additional problem based on a negative determination of whether the problem graph representing the additional problem fits onto the unoccupied region of the placement graph; and,
placing the rejected additional problem to a front of a problem queue comprising unplaced problems of the plurality of problems.

11. The method of claim 1 , wherein the determining, by the at least one digital processor, a placement of the problem graph representing the additional problem on an unoccupied region of the placement graph comprises:
moving a previously-placed problem from a first region of the placement graph to at least partly occupy the unoccupied region of the placement graph; and,
placing a current additional problem onto at least a portion of the first region of the placement graph.

12. The method of claim 1 , wherein the selecting, by the at least one digital processor, a first problem from the plurality of problems based on at least one first problem property comprises selecting a first problem based on one or more of: a highest problem priority, a placement at a front of a problem queue, and a nearest proximity of a problem computation temperature to a current temperature.

13. The method of claim 1 , wherein the at least one additional problem property is one or more of:
the problem size;
a problem priority;
a placement in a problem queue;
a proximity of a problem computation temperature relative to a problem computation temperature of the first problem;
a same number of samples to be produced as a number of samples to be produced by the first problem; and,
a same overall annealing time as an overall annealing time of the first problem.

14. The method of claim 1 , wherein the generating, by the at least one digital processor, a first solution to the first problem and an additional solution to each additional problem through disaggregation comprises:
dividing the output into a plurality of

Assignees

• D Wave Systems Inc

Inventors

• Thom Murray C
• Roy Aidan P
• Chudak Fabian A
• Bian Zhengbing
• Macready William G
• Israel Robert B
• Boothby Kelly T R
• Yarkoni Sheir
• Xue Yanbo
• Korenkevych Dmytro

Classifications

• G06N10/60 Primary

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

• G06N10/00 Primary

  Quantum computing, i.e. information processing based on quantum-mechanical phenomena · CPC title