Sampling from a set of spins with clamping

Patent metadata

Field	Value
Publication number	US-9588940-B2
Application number	US-201514676605-A
Country	US
Kind code	B2
Filing date	Apr 1, 2015
Priority date	Dec 5, 2013
Publication date	Mar 7, 2017
Grant date	Mar 7, 2017

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 qubits in the plurality of qubits; and
a readout subsystem;

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:
draw, via the readout subsystem, a first plurality of samples for a plurality of variables from a function defined on an analog processor;
create a first estimator for the first plurality of samples;
draw a second sample from the first estimator, the second sample including a value for the first variable in the plurality of variables;
for the function, during a first iteration of at least one iteration on the function:
fix an instant first variable in the plurality of variables to a value for a first variable in the plurality of variables, wherein fixing the instant first variable defines:
an instant fixed subset of plurality of variables,
an instant unfixed subset of plurality of variables, and an instant partially fixed version of the function;

draw, via the readout subsystem, an instant plurality of samples for the instant unfixed subset of the plurality of variables from the instant partially fixed version of the function defined on the analog processor;
create an instant estimator for the instant unfixed subset of the plurality of variables from the instant plurality of samples; and
draw an instant value for an instant second variable of the unfixed subset of plurality of variables from the instant estimator.

2. The computational system of claim 1 wherein the processor-executable instructions when executed further cause the at least one processor to:
cause the value for the first variable in the plurality of variables to be stored.

3. The computational system of claim 1 wherein the processor-executable instructions when executed further cause the at least one processor to:
for the function, during the first iteration on the function:
cause the instant value for the instant second variable of the unfixed subset of plurality of variables from the instant estimator to be stored.

4. 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 qubits 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 function defining a probability distribution;
during a respective iteration of at least one iteration:
initialize an analog processor;
allow the analog processor to evolve to a state defined by the function;
draw a sample from the function implemented on the analog processor; and
update a plurality of samples with the sample; and

return the plurality of samples.

5. The computational system of claim 4 wherein the processor-executable instructions when executed further cause the at least one processor to:
cause the plurality of samples to be stored.

6. The computational system of claim 4 wherein the processor-executable instructions when executed further cause the at least one processor to:
encode the function in a problem Hamiltonian wherein the problem Hamiltonian includes a plurality of local bias terms, and a plurality of pairwise coupling terms.

7. The computational system of claim 4 wherein the processor-executable instructions when executed further cause the at least one processor to:
encode the function in a problem Hamiltonian with energy that is proportional to the negative logarithm of a target probability distribution.

8. The computational system of claim 4 wherein the processor-executable instructions when executed further cause the at least one processor to:
during each respective iteration of at least one iteration:
post-process the sample from the function implemented on the analog processor.

9. The computational system of claim 8 wherein the processor-executable instructions when executed further cause the at least one processor to:
during each respective iteration of at least one iteration:
perform a ones' complement of the sample from the function implemented on the analog processor.

10. The computational system of claim 4 wherein the processor-executable instructions when executed further cause the at least one processor to:
post-process the plurality of samples.

11. The computational system of claim 10 wherein the processor-executable instructions when executed further cause the at least one processor to:
change a representative sample in the plurality of samples such that an aggregate value for the plurality of samples converges on an aggregate value for a target distribution.

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 two of the plurality of qubits, the method comprising:
operating the analog processor as a sample generator to provide samples from a probability distribution, wherein a shape of the probability distribution depends on a configuration of a number of programmable parameters for the analog processor, and wherein operating the analog processor as a sample generator comprises:
programming the analog processor with a configuration of the number of programmable parameters for the analog processor, wherein the configuration of a number of programmable parameters corresponds to the probability distribution over the plurality of qubits of the analog processor,
evolving the analog processor, and
reading out states for the qubits in plurality of qubits of the analog processor, wherein the states for the qubits in the plurality of qubits correspond to a sample from the probability distribution;

updating a set of samples to include the sample from the probability distribution; and
returning the set of samples.

13. The method of claim 12 further comprising:
recording the plurality of samples.

14. The method of claim 12 further comprising:
defining a function that implements the shape of the probability distribution; and
evolving the analog processor to a state defined by the function.

15. The method of claim 12 further comprising:
causing the configuration of the number of programmable parameters that correspond to the probability distribution over the plurality of qubits of the analog processor to have an energy proportional to the negative logarithm of a target probability distribution.

16. The method of claim 12 further comprising:
post-processing the sample from the probability distribution.

17. The method of claim 16 further comprising:
performing a ones' complement of the sample from the probability distribution.

18. The method of claim 12 further comprising:
post-processing the plurality of samples.

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

• G06N99/002

  Physics · mapped topic

• 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

• G06N99/005

  Physics · mapped topic

• G06N10/60

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

• G06N20/00

  Machine learning · CPC title