Systems and methods for embedding problems into an analog processor

Patent metadata

Field	Value
Publication number	US-11880741-B2
Application number	US-202016988232-A
Country	US
Kind code	B2
Filing date	Aug 7, 2020
Priority date	Apr 18, 2016
Publication date	Jan 23, 2024
Grant date	Jan 23, 2024

Abstract

Generate an automorphism of the problem graph, determine an embedding of the automorphism to the hardware graph and modify the embedding of the problem graph into the hardware graph to correspond to the embedding of the automorphism to the hardware graph. Determine an upper-bound on the required chain strength. Calibrate and record properties of the component of a quantum processor with a digital processor, query the digital processor for a range of properties. Generate a bit mask and change the sign of the bias of individual qubits according to the bit mask before submitting a problem to a quantum processor, apply the same bit mask to the bit result. Generate a second set of parameters of a quantum processor from a first set of parameters via a genetic algorithm.

First claim

The invention claimed is:

1. A method for assigning coupling strengths to couplers in chains of qubits in a hardware graph of an analog processor via a hybrid processor comprising a digital processor and the analog processor, the method comprising:
embedding a problem graph into the hardware graph of the analog processor to produce an embedded problem graph, the embedded problem graph containing at least one chain of qubits;
determining via the digital processor whether the at least one chain in the embedded problem graph is broken;
if the at least one chain is broken, determining via the digital processor a location of a break in the at least one chain; and
increasing respective coupling strengths of couplers in the analog processor at the location of the break by finding an upper-bound on a required chain strength by verifying that for each chain C of the embedded problem −J(e)>b(C, e) is respected for each edge e in C, wherein b(C, e) is defined as b(C, e):=min{b(C 1 (e)), b(C 2 (e))} and b(C):=Σ vϵC |h(v)|+Σ vϵC Σ uϵU v |J(v, u)| and J(e) is the coupling strength applied to edge e.

2. The method of claim 1 wherein determining via the digital processor whether the at least one chain in the embedded problem graph is broken includes receiving via the digital processor samples from the analog processor.

3. The method of claim 1 further comprising:
causing the analog processor to evolve following a non-uniform annealing schedule across the hardware graph of the analog processor.

4. The method of claim 3 wherein causing the analog processor to evolve following a non-uniform annealing schedule across the hardware graph of the analog processor includes causing the analog processor to pause evolving for a time interval before resuming evolving.

5. The method of claim 3 wherein causing the analog processor to evolve following a non-uniform annealing schedule across the hardware graph of the analog processor includes causing the analog processor to evolve according to a non-linear rate of evolution.

6. The method of claim 1 further comprising:
iteratively repeating until an exit condition is met:
sampling from the analog processor via the digital processor;
determining via the digital processor whether the at least one chain in the embedded problem graph is broken;
if the at least one chain is broken, determining via the digital processor the location of the break; and
increasing the respective coupling strengths of couplers in the analog processor at the location of the break.

7. A hybrid computing system, comprising:
an analog processor into which a problem is embeddable, the problem representable as a problem graph and the analog processor representable as a hardware graph comprising chains of qubits communicatively coupled by couplers;
a digital processor in communication with the analog processor, wherein in operation the digital processor:
embeds the problem graph into the hardware graph of the analog processor to produce an embedded problem graph, the embedded problem graph containing at least one chain;
determines via the digital processor whether the at least one chain in the embedded problem graph is broken;
if the at least one chain is broken, determines via the digital processor a location of a break in the at least one chain; and
increases respective coupling strengths of one or more of the couplers in the analog processor at the location of the break by finding an upper-bound on a required chain strength by verifying that for each chain C of the embedded problem −J(e)>b(C, e) is respected for each edge e in C, wherein b(C, e) is defined as b(C, e):=min{b(C 1 (e)), b(C 2 (e))} and b(C):=Σ vϵC |h(v)|+Σ vϵC Σ uϵU v |J(v, u)| and J(e) is the coupling strength applied to edge e.

8. The hybrid computing system of claim 7 wherein in operation the digital processor receives samples from the analog processor to determine whether the at least one chain in the embedded problem graph is broken.

9. The hybrid computing system of claim 7 wherein in operation the digital processor further causes the analog processor to evolve following a non-uniform annealing schedule across the hardware graph of the analog processor.

10. The hybrid computing system of claim 9 wherein in operation the digital processor causes the analog processor to evolve following a non-uniform annealing schedule by evolving for a time interval before resuming evolving.

11. The hybrid computing system of claim 9 wherein in operation the digital processor causes the analog processor to evolve following a non-uniform annealing schedule by evolving according to a non-linear rate of evolution.

12. The hybrid computing system of claim 7 further comprising in operation the digital processor iteratively repeating until an exit condition is met:
sampling from the analog processor via the digital processor;
determining via the digital processor whether the at least one chain in the embedded problem graph is broken;
if the at least one chain is broken, determining via the digital processor the location of the break; and
increasing the respective coupling strengths of one or more of the couplers in the analog processor at the location of the break.

Assignees

• D Wave Systems Inc

Inventors

• Israel Robert B
• Lanting Trevor M
• King Andrew D

Classifications

• G06G7/62 Primary

  for electric systems or apparatus · CPC title

• G06N10/00 Primary

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

• G06N3/126

  Evolutionary algorithms, e.g. genetic algorithms or genetic programming · CPC title

• G06N20/00

  Machine learning · CPC title