Sampling from a set spins with clamping
The systems, devices, articles, and methods generally relate to sampling from an available probability distribution. The samples may be 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.
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 function;
receive a temperature ladder that specifies at least a first temperature;
request a plurality of samples from an analog processor implementing the function;
initialize a plurality of Markov chains each including one or more entries with a null value;
associate each Markov chain in the plurality of Markov chains to a respective temperature from the temperature ladder, a first Markov chain associated with the first temperature, and a set of Markov chains in the plurality of Markov chains not associated with the first temperature;
for each respective entry in each Markov chain of the plurality of Markov chains:
if the respective entry is in the first Markov chain, and if a hardware sample is available in the plurality of samples requested from the analog processor implementing the function, update the respective entry in the first Markov chain with the hardware sample, and
otherwise, generate a value for the respective entry, and update the respective entry with the value under a probabilistic acceptance rule; and
return at least one of the Markov chains from the plurality of Markov chains.
2 . The computational system of claim 1 wherein the processor-executable instructions when executed further cause the at least one processor-based device to:
for each respective entry in each Markov chain of the plurality of Markov chains:
if the respective entry is in a respective Markov chain of the set of Markov chains in the plurality of Markov chains, or if the respective entry is in the first Markov chain and a hardware sample is not available in the plurality of samples requested from an analog processor implementing the function:
propose a first new state as the respective entry to the respective Markov chain; and
update the respective entry with first new state in accordance with a first probability.
3 . The computational system of claim 2 wherein the respective entry is in the first Markov chain, or the respective entry is in a respective Markov chain in the set of Markov chains.
4 . The computational system of claim 1 wherein the processor-executable instructions when executed further cause the at least one processor-based device to:
for each of a number of pairs of Markov chains of the plurality of Markov chains, where each respective pair of Markov chains includes a warmer Markov chain, and a cooler Markov chain:
draw a random number; and
swap a first entry in the warmer Markov chain in the respective pair of Markov chains with a second entry in the cooler Markov chain in the respective pair of Markov chains if the random number exceeds a second probability.
5 . The computational system of claim 4 wherein the processor-executable instructions when executed further cause the at least one processor-based device to:
compute the second probability as an exponential of a term proportional to a product:
an energy difference between the first entry in the warmer Markov chain and the second entry in the cooler Markov chain, and
a difference between a first inverse temperature associated with the warmer Markov chain and a second inverse temperature associated with the cooler Markov chain.
6 . The computational system of claim 1 wherein the processor-executable instructions when executed further cause the at least one processor-based device to:
for each respective entry in the first Markov chain of the plurality of Markov chains:
draw a sample from a binary probability distribution; and
if the sample drawn from the binary probability distribution exceeds a third probability update the respective entry in first Markov chain with the hardware sample.
7 . The computational system of claim 1 wherein the processor-executable instructions when executed further cause the at least one processor-based device to:
record the plurality of Markov chains.
8 . 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 the plurality of samples requested from the analog processor.
9 . 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:
receiving a function;
receiving a temperature ladder specifying at least a first temperature;
requesting, asynchronously, a plurality of samples from the analog processor implementing the function;
initializing a plurality of Markov chains each including one or more entries with a null value;
associating with each Markov chain in the plurality of Markov chains to a respective temperature from the temperature ladder wherein a first Markov chain is associated with the first temperature, and a set of Markov chains in the plurality of Markov chains is not associated with the first temperature;
for a respective entry in each Markov chain of the plurality of Markov chains:
if the respective entry is in the first Markov chain associated with the first temperature, and if a hardware sample is available in the plurality of samples requested from the analog processor implementing the function, update the respective entry in first chain associated with the first temperature with the hardware sample, and
otherwise, generate a value for the respective entry and accept the value under a probabilistic update rule; and
returning a Markov chain from the plurality of Markov chains.
10 . The method of claim 9 further comprising:
for the respective entry in each Markov chain of the plurality of Markov chains:
if the respective entry is in a respective Markov chain of the set of Markov chains in the plurality of Markov chains, or if the respective entry is in the first Markov chain associated with the first temperature, and if a hardware sample is not available in the plurality of samples requested from an analog processor implementing the function:
proposing a first new state as the respective entry in the respective Markov chain; and
updating the respective entry with first new state in accordance with a first probability.
11 . The method of claim 10 further comprising
determining if the respective entry is in the first Markov chain associated with the first temperature, or the respective entry is in a respective Markov chain of the set of Markov chains in the plurality of Markov chains.
12 . The method of claim 9 further comprising:
for each of a number of pairs of Markov chains of the plurality of Markov chains, where each respective pair of Markov chains includes a warmer Markov chain, and a cooler Markov chain:
drawing a random number; and
swapping a first entry in the warmer Markov chain in the respective pair of Markov chains with a second entry in the cooler Markov chain in the respective pair of Markov chains if the random number exceeds a second probability.
13 . The method of claim 12 further comprising:
computing the second probability as an exponential proportional to a product of:
an energy difference between the first entry in warmer Markov chain and the second entry in the cooler Markov chain, and
a difference between a first inverse temperature associated with the warmer Markov chain and a second inverse temperature associated with the cooler Markov chain.
14 . The method of claim 13 further comprising:
for the respective entry in each Markov chain of the plurality of Markov chains:
draw a sample from a binary probability distribution; and
if the sample drawn from the binary probability distribution exceeds a third probability, add the hardware sample to the first Markov chain as the respective entry.
15 . The method of claim 9 further comprising:
recording the plurality of Markov chains.