Sampling from an analog processor

Patent metadata

Field	Value
Publication number	US-11238131-B2
Application number	US-201715399461-A
Country	US
Kind code	B2
Filing date	Jan 5, 2017
Priority date	Dec 5, 2013
Publication date	Feb 1, 2022
Grant date	Feb 1, 2022

Abstract

The systems, devices, articles, and methods generally relate to sampling from an available probability distribution. The samples maybe used to create a desirable probability distribution, for instance for use in computing values used in computational techniques including: Importance Sampling and Markov chain Monte Carlo systems. An analog processor may operate as a sample generator, for example by: programming the analog processor with a configuration of the number of programmable parameters for the analog processor, which corresponds to a probability distribution over qubits of the analog processor, evolving the analog processor, and reading out states for the qubits. The states for the qubits in the plurality of qubits correspond to a sample from the probability distribution. Operation of the sampling device may be summarized as including updating a set of samples to include the sample from the probability distribution, and returning the set of samples.

First claim

The invention claimed is:

1. A computational system comprising:
at least one analog processor comprising:
a plurality of qubits;
a plurality of coupling devices, wherein each coupling device provides controllable communicative coupling between a respective pair of the plurality of qubits;

at least one processor-based device communicatively coupled to the at least one analog processor; and
at least one non-transitory computer-readable storage medium that stores processor-executable instructions, which when executed causes at least one processor-based device to:
receive a sample from a function implemented on the at least one analog processor;
run a simulated annealing according to a backwards annealing schedule, the backwards annealing schedule comprising a starting condition, at least one intermediate condition, and a stopping condition, the backwards annealing schedule comprising a variable that defines a reverse annealing evolution and a rule for incrementing the variable along a series between the starting condition and the stopping condition and including the at least one intermediate condition, wherein the simulated annealing starts at the sample and generates a history of states of the simulated annealing as the variable is incremented, the history of states comprising at least one state corresponding to the intermediate condition of the backwards annealing schedule; and
return the history of states of the simulated annealing.

2. The computational system of claim 1 further comprising a readout subsystem responsive to a state of each of the qubits in the plurality of qubits to generate a first sample.

3. The computational system of claim 1 wherein, when executed, the processor-executable instructions further cause the at least one processor-based device to:
provide the backwards annealing schedule, the sample, and the function to a simulated annealer to run the simulated annealing.

4. The computational system of claim 3 wherein the backwards annealing schedule is an accelerated backwards annealing schedule.

5. The computational system of claim 3 wherein, when executed, the processor-executable instructions further cause the at least one processor-based device to:
record the history of states of the simulated annealing.

6. The computational system of claim 1 wherein, when executed, the processor-executable instructions cause the at least one processor-based device to:
compute a weight for the sample from the history of states of the simulated annealing.

7. The computational system of claim 6 wherein, when executed, the processor-executable instructions further cause the at least one processor-based device to:
compute the weight as proportional to a product over a plurality of states in the history of states of the simulated annealing, each term of the product includes an exponent of a multiplication of: a difference between an inverse temperature at a first state in the history of states of the simulated annealing and an inverse temperature at a second state in the history of states of the simulated annealing, and an energy at the second state in the history of states of the simulated annealing.

8. The computational system of claim 6 wherein, when executed, the processor-executable instructions further cause the at least one processor-based device to:
apply the weight to the sample in importance sampling.

9. The computational system of claim 6 wherein, when executed, the processor-executable instructions further cause the at least one processor-based device to:
record the weight.

10. The computational system of claim 6 wherein, when executed, the processor-executable instructions further cause the at least one processor-based device to:
return the weight.

11. The computational system of claim 1 wherein the starting condition, the at least one intermediate condition, and the stopping condition comprise an initial temperature, at least one intermediate temperature, and a final temperature, respectively.

12. A method of operation in a sampling device that comprises both an analog processor and at least one processor-based device communicatively coupled to one another, the analog processor comprising a plurality of qubits, and a plurality of coupling devices, wherein each coupling device provides controllable communicative coupling between a respective pair of the plurality of qubits, the method comprising:
receiving a sample from a function implemented on the analog processor;
running a simulated annealing in accordance with a backwards annealing schedule, the backwards annealing schedule comprising a starting condition, at least one intermediate condition, and a stopping condition, the backwards annealing schedule comprising a variable that defines a reverse annealing evolution and a rule for incrementing the variable along a series between the starting condition and the stopping condition and including the at least one intermediate condition, wherein the simulated annealing starts at the sample and generates a history of states of the simulated annealing as the variable is incremented, the history of states comprising at least one state corresponding to the intermediate condition of the backwards annealing schedule; and
returning the history of states of the simulated annealing.

13. The method of claim 12 further comprising:
providing the backwards annealing schedule, the sample, and the function to a simulated annealer to run the simulated annealing.

14. The method of claim 13 further comprising:
including an accelerated backwards annealing schedule in the backwards annealing schedule.

15. The method of claim 12 further comprising:
computing a weight for the sample from the history of states of the simulated annealing.

16. The method of claim 15 further comprising:
computing the weight as proportional to a product over a plurality of states in the history of states of the simulated annealing, each term of the product includes an exponent of a multiplication of: a difference between an inverse temperature at a first state in the history of states of the simulated annealing and an inverse temperature at a second state in the history of states of the simulated annealing, and an energy at the second state in the history of states of the simulated annealing.

17. The method of claim 15 further comprising:
applying the weight to the sample in importance sampling.

18. The method of claim 15 further comprising:
recording the weight.

19. The method of claim 15 further comprising:
returning the weight.

20. The method of claim 15 further comprising:
recording the history of states of the simulated annealing.

21. The method of claim 12 wherein receiving the sample from the function implemented on an analog processor further comprises:
fixing a first qubit in the plurality of qubits to a known state.

22. The method of claim 12 wherein running a simulated annealing in accordance with a backwards annealing schedule, the backwards annealing schedule comprising a starting condition, at least one intermediate condition, and a stopping condition comprises running a simulated annealing in accordance with a backwards annealing schedule, the backwards annealing schedule comprising an initial temperature, at least one intermediate temperature, and a final temperature, respectively.

23. A non-transitory computer-readable storage medium that stores processor-executable instructions, which when executed cause at le

Assignees

• D Wave Systems Inc

Inventors

• Hamze Firas
• King James
• Andriyash Evgeny
• Mcgeoch Catherine
• Raymond Jack
• Rolfe Jason
• Macready William G
• Lott Aaron
• Thom Murray C

Classifications

• G06N10/60

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

• G06F17/18 Primary

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06N20/00

  Machine learning · CPC title

• G06N10/00

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