# US 2017/0255871 A1 · Systems and methods for machine learning

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0255871 A1
- Document ID: US20170255871A1
- Status: Published application
- Kind: A1
- Application number: 15/452,438
- Filed: 2017-03-07
- Published: 2017-09-07
- Earliest claimed: 2016-03-07
- Assignees: D-Wave Systems Inc.
- Applicants: D-Wave Systems Inc.
- Inventors: William G. Macready; Firas Hamze; Fabian A. Chudak; Mani Ranjbar; Jack R. Raymond; Jason T. Rolfe
- Web page: https://patentgrep.com/patent/US20170255871A1

## CPC

- G06N 10/60: Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms
- G06F 18/2415: based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06N 10/00: Quantum computing, i.e. information processing based on quantum-mechanical phenomena
- G06N 20/00: Machine learning
- G06F 2111/10: Numerical modelling
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A hybrid computer comprising a quantum processor can be operated to perform a scalable comparison of high-entropy samplers. Performing a scalable comparison of high-entropy samplers can include comparing entropy and KL divergence of post-processed samplers. A hybrid computer comprising a quantum processor generates samples for machine learning. The quantum processor is trained by matching data statistics to statistics of the quantum processor. The quantum processor is tuned to match moments of the data.

## Claims

### Claim 1

A method of operation of a computational system comprising at least one processor, the method comprising:
receiving information defining a target distribution and a sampling process associated with a sampling distribution by the at least one processor;
receiving a plurality of samples using the sampling process associated with the sampling distribution by the at least one processor;
generating an empirical representation of the sampling distribution based on the plurality of samples by the at least one processor;
generating a post-processed distribution from the plurality of samples by the at least one processor wherein generating a post-processed distribution includes:
determining a first and a second subset of variables; and
expressing a post-processed distribution in a mixture model comprising the sampling distribution and an analytic form for conditional resampling on the first and the second subset of variables;
evaluating a Kullback-Leibler (KL) divergence of the target distribution on the post-processed distribution by the at least one processor; and
comparing the sampling distribution to the target distribution based at least in part on the KL divergence by the at least one processor.

### Claim 2 (depends on 1)

The method of claim 1 wherein receiving a plurality of samples using the sampling process associated with the sampling distribution by the at least one processor includes receiving a plurality of samples from an analog processor.

### Claim 3 (depends on 2)

The method of claim 2 wherein receiving a plurality of samples from an analog processor includes receiving a plurality of samples from a quantum processor.

### Claim 4 (depends on 1)

The method of claim 1 wherein receiving information defining a target distribution includes receiving information defining a Boltzmann distribution.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
generating, by an analog processor, the plurality of samples using the sampling process associated with the sampling distribution, and wherein receiving a plurality of samples using the sampling process associated with the sampling distribution by the at least one processor includes receiving the plurality of samples by a digital processor from the analog processor.

### Claim 6

A computing system comprising at least one processor for comparing a sampling distribution and a target distribution, the computing system operable to:
receive information defining the target distribution and a sampling process associated with the sampling distribution by the at least one processor;
receive a plurality of samples by the at least processor, wherein the plurality of samples are generated using the sampling process associated with the sampling distribution;
generate an empirical representation of the sampling distribution based on the plurality of samples by the at least one processor;
generate a post-processed distribution from the plurality of samples by the at least one processor wherein to generate the post-processed distribution the at least one processor:
determines a first and a second subset of variables;
expresses a post-processed distribution in a mixture model comprising the sampling distribution and an analytic form for conditional resampling on the first and the second subset of variables;
evaluates a Kullback-Leibler (KL) divergence of the target distribution on the post-processed distribution; and
compares the sampling distribution to the target distribution based at least in part on the KL divergence.

### Claim 7 (depends on 6)

The computing system of claim 6 wherein the at least one processor comprises a digital processor and an analog processor.

### Claim 8 (depends on 7)

The computing system of claim 7 wherein the computing system is operable to receive a plurality of samples by the digital processor, wherein the plurality of samples are generated by the analog processor using the sampling process associated with the sampling distribution.

### Claim 9 (depends on 8)

The computing system of claim 8 wherein the analog processor is a quantum processor.

### Claim 10 (depends on 6)

The computing system of claim 6 wherein the target distribution is a Boltzmann distribution.

### Claim 11

A hybrid computing system comprising at least one digital processor and an analog processor for comparing a sampling distribution and a target distribution, the hybrid computing system operable to:
receive information defining the target distribution and a sampling process associated with the sampling distribution by the at least one digital processor;
receive a plurality of samples by the at least one digital processor, wherein the plurality of samples are generated by the analog processor using the sampling process associated with the sampling distribution;
generate an empirical representation of the sampling distribution based on the plurality of samples by the at least one digital processor;
generate a post-processed distribution from the plurality of samples by the at least one digital processor wherein to generate the post-processed distribution the at least one digital processor:
determines a first and a second subset of variables;
expresses a post-processed distribution in a mixture model comprising the sampling distribution and an analytic form for conditional resampling on the first and the second subset of variables;
evaluates a Kullback-Leibler (KL) divergence of the target distribution on the post-processed distribution by the at least one digital processor; and
compares the sampling distribution to the target distribution based at least in part on the KL divergence by the at least one digital processor.

### Claim 12 (depends on 11)

The hybrid computing system of claim 11 wherein the analog processor is a quantum processor.

### Claim 13 (depends on 11)

The hybrid computing system of claim 11 wherein the target distribution is a Boltzmann distribution.

### Claim 14

A method of operation of a computational system comprising at least one processor, the method comprising:
receiving, by at least one digital processor, information defining a target distribution and a sampling process associated with a sampling distribution;
receiving, by at least one digital processor, a plurality of samples, the plurality of samples generated by at least one analog processor;
generating, by the at least one digital processor, an empirical representation of the sampling distribution based on the received plurality of samples;
generating, by the at least one digital processor, a post-processed distribution from the received plurality of samples, by:
determining a first and a second subset of variables;
expressing a post-processed distribution in a mixture model comprising the sampling distribution and an analytic form for conditional resampling on the first and the second subset of variables;
evaluating a Kullback-Leibler (KL) divergence of the target distribution on the post-processed distribution by the at least one digital processor; and
comparing the sampling distribution to the target distribution based at least in part on the KL divergence.

### Claim 15 (depends on 14)

The method of claim 14, further comprising:
generating, by the at least one analog processor, a plurality of samples using the sampling process associated with the sampling distribution.

### Claim 16 (depends on 15)

The method of claim 15 wherein generating a plurality of samples using the sampling process associated with the sampling distribution includes generating the plurality of samples with a quantum processor.

### Claim 17 (depends on 14)

The hybrid computing system of claim 14 wherein receiving information defining a target distribution includes receiving information that defines a Boltzmann distribution.

### Claim 18

A method for generative machine learning by a computational system comprising a quantum processor and a digital processor, the method comprising:
for a first iteration of a first iterative loop:
determining, by the quantum processor, a first set of spin configurations for which the scalar product of a first weighting vector and a feature vector attains a largest value; and
updating the first weighting vector, by the digital processor, to form an updated weighting vector based at least in part on a difference between the feature vector evaluated at the first set of spin configurations and a vector of feature moments; and
for a subsequent iteration of the first iterative loop:
determining, by the quantum processor, a subsequent set of spin configurations for which the scalar product of a subsequent weighting vector and the feature vector attains a largest value; and
updating the subsequent weighting vector, by the digital processor, based at least in part on a difference between the feature vector evaluated at the subsequent set of spin configurations and the vector of feature moments.

### Claim 19 (depends on 18)

The method of claim 18, further comprising:
for the first iteration of the first iterative loop, performing a first iteration of a second iterative loop, the second iterative loop nested in the first iterative loop, the second iterative loop over a plurality of sets of observed visible variables, the first iteration of the second iterative loop comprising:
determining, by the quantum processor, a first set of hidden variables for which the scalar product of the first weighting vector and the feature vector for a first set of the plurality of sets of observed visible variables attains a largest value;
for the subsequent iteration of the first iterative loop, performing a second iteration of the second iterative loop:
determining, by the quantum processor, values of a second set of hidden variables for which the scalar product of the subsequent weighting vector and the feature vector for a second set of the plurality of sets of observed visible variables attains a largest value.

### Claim 20 (depends on 18)

The method of claim 18, further comprising:
before performing the first iteration, initializing, by the digital processor, the first weighting vector.

### Claim 21 (depends on 20)

The method of claim 20 wherein initializing the first weighting vector includes assigning the same value to each component of the first weighting vector.

### Claim 22 (depends on 18)

The method of claim 18 wherein updating the first weighting vector based at least in part on a difference between the feature vector evaluated at the first set of spin configurations and a vector of feature moments includes updating the first weighting vector by forming the sum of a previous weighting vector and a difference between the vector of feature moments over a target distribution on a set of spin configurations and the feature vector evaluated at the first set of spin configurations.

### Claim 23 (depends on 18)

The method of claim 18, further comprising:
defining a graph comprising a plurality of vertices V and a plurality of edges E; and
before performing the first iteration, defining the feature vector, the feature vector comprising one or more components, each component comprising a feature function that maps a set of spin configurations s into real numbers, each spin configuration associated with a respective vertex of the graph.

### Claim 24 (depends on 23)

The method of claim 23, further comprising:
before performing the first iteration, receiving, by the digital processor, the vector of feature moments over a target distribution on the set of spin configurations.

### Claim 25 (depends on 23)

The method of claim 23, wherein the set of spin configurations s is a random variable on {−1,1}n and the feature function is of the form αisi for iεV or αi,jsisj for {i, j}εE, and αi, αi,j are real numbers.

### Claim 26 (depends on 18)

The method of claim 18, further comprising:
following the subsequent iteration, outputting at least one set of the first set of spin configurations or the subsequent set of spin configurations by the digital processor.

### Claim 27

A method for discriminative machine learning by a computational system comprising a quantum processor and a digital processor, the method comprising:
for a first iteration of a first iterative loop:
performing a first iteration of a second iterative loop, the second iterative loop nested in the first iterative loop, the second iterative loop over a plurality of sets of observed visible variables, the first iteration of the second iterative loop comprising:
determining, by the quantum processor, a first set of labels for which the scalar product of a first weighting vector and the feature vector for a first set of the plurality of sets of observed visible variables attains a largest value;
updating the first weighting vector, by the digital processor, to form an updated weighting vector based at least in part on an average discrepancy between the feature vector and a vector of feature moments, the average discrepancy determined over the plurality of sets of observed visible variables;
for a subsequent iteration of the first iterative loop:
performing a second iteration of the second iterative loop comprising:
determining, by the quantum processor, a second set of labels for which the scalar product of a subsequent weighting vector and the feature vector for a second set of the plurality of sets of observed visible variables attains a largest value;
updating the subsequent weighting vector, by the digital processor, to form an updated weighting vector based at least in part on an average discrepancy between the feature vector and a vector of feature moments, the average discrepancy determined over the plurality of sets of observed visible variables; and
outputting at least one of the weighting vectors.

### Claim 28 (depends on 27)

The method of claim 27, further comprising:
receiving an input vector; and
determining the most likely label for the input vector.

### Claim 29 (depends on 28)

The method of claim 28 wherein determining the most likely label for the input vector includes performing a plurality of iterations of a third iterative loop over each of the output weighting vectors, each iteration comprising determining, by the quantum processor, a label for which the scalar product of the respective weighting vector and the feature vector attains a largest value.

### Claim 30 (depends on 28)

The method of claim 28, further comprising:
for the first iteration of the first iterative loop, and the first iteration of the second iterative loop:
determining, by the quantum processor, a first set of hidden variables for which the scalar product of the first weighting vector and the feature vector for a first set of the plurality of sets of observed visible variables attains a largest value; and
for the subsequent iteration of the first iterative loop, and the second iteration of the second iterative loop:
determining, by the quantum processor, a second set of hidden variables for which the scalar product of the subsequent weighting vector and the feature vector for a second set of the plurality of sets of observed visible variables attains a largest value.
