Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models

Mainstream machine-learning techniques such as deep learning and probabilistic programming rely heavily on sampling from generally intractable probability distributions. There is increasing interest in the potential advantages of using quantum computing technologies as sampling engines to speed up these tasks or to make them more effective. However, some pressing challenges in state-of-the-art quantum annealers have to be overcome before we can assess their actual performance. The sparse connectivity, resulting from the local interaction between quantum bits in physical hardware implementations, is considered the most severe limitation to the quality of constructing powerful generative unsupervised machine-learning models. Here, we use embedding techniques to add redundancy to data sets, allowing us to increase the modeling capacity of quantum annealers. We illustrate our findings by training hardware-embedded graphical models on a binarized data set of handwritten digits and two synthetic data sets in experiments with up to 940 quantum bits. Our model can be trained in quantum hardware without full knowledge of the effective parameters specifying the corresponding quantum Gibbs-like distribution; therefore, this approach avoids the need to infer the effective temperature at each iteration, speeding up learning; it also mitigates the effect of noise in the control parameters, making it robust to deviations from the reference Gibbs distribution. Our approach demonstrates the feasibility of using quantum annealers for implementing generative models, and it provides a suitable framework for benchmarking these quantum technologies on machine-learning-related tasks.

Popular Summary

Mainstream machine learning, which gives computers the ability to learn tasks that they are not explicitly programmed to do, relies heavily on sampling from complex probability distributions. Quantum computing technologies have the potential to greatly speed up these tasks or make them more effective. However, several limitations have hindered demonstrations of how practical this is. Clearing this hurdle could significantly advance the field of artificial intelligence by improving methods that rely on sampling. We have developed a technique that surpasses current limitations and provides a clear demonstration of feasibility.

Our approach implements a densely connected model in a quantum annealer, a type of quantum computer originally proposed as optimizers but here used as samplers instead. Our algorithm shows how quantum annealers can be trained without full knowledge of the control parameters actually implemented by the device, a more efficient and robust approach to cope with noise in near-term devices. We successfully trained the D-Wave 2X, a quantum annealer hosted at NASA, on image data sets in a generative unsupervised learning setting, one of the most difficult and attractive paradigms in machine learning. Our experiments used up to 940 qubits to generate, reconstruct, and classify small images of handwritten digits. The generated images resemble those produced by humans; we include a visual Turing test to challenge the reader to distinguish them.

Finding quantum speedup in this machine-learning setting would have impacts across science, engineering, and society. Ours is a suitable framework for benchmarking quantum sampling methods against classical ones, a key metric to explore in the near future.

Figure 1

Quantum-assisted unsupervised learning. (a) During the training phase, samples generated by the quantum annealer are compared with samples from the data set of, say, black-and-white images. The control parameters are then modified according to a learning rule (see Sec. 3). This process is iterated a given number of times, also known as epochs. (b) After being trained, we can use the quantum annealer, for instance, to reconstruct missing information in a data point, e.g., unknown values of some pixels (red region). To do this, we program the quantum annealer with the control parameters learned, except for the fields of those qubits that represent known pixels. These fields are instead set to large values $h_{\max }$, so the qubits are clamped to the known values of the corresponding pixels. We then generate samples to infer the values of the unknown pixels.

Figure 2

Hardware-embedded models. (a) We first define a graph with arbitrary connectivity between the logical variables that directly encode the data set to be modeled; here, we show a fully connected graph on four variables as an example. Such a graph serves as a scaffolding to build hardware-embedded models with enhanced modeling capacity. (b) We then embed the scaffolding graph in quantum hardware by using minor embedding techniques; this requires the introduction of auxiliary qubits, couplings, and fields. In the example shown here, the logical variable 1 (red) is encoded using two qubits, $1A$ and $1B$, which are connected by an auxiliary coupler $J_{11}^{AB}$; the same is true for variable 2 (blue). The black links correspond to couplings between qubits representing different logical variables. In optimization problems, we are given values for the couplings and fields on the graph of logical variables, as in diagram (a). To solve such optimization problems on a quantum annealer, we first have to pick values for all control parameters such that the ground state of the physical system coincides with the optimal solution of the problem being solved. The selection of control parameters can be done via handcrafted rules when information is available about the model [69] or via heuristic approaches in the more general scenario [49]. The optimal choice of control parameters, i.e., the one that maximizes the probability of finding the ground state, is known as the parameter-setting problem, and it is an open research question. In machine-learning applications, instead, the control parameters are not given but have to be found; they are the variables of the problem. In this case, embedding techniques are used both to transform the original data set [as shown in diagram (c)] into a data set with higher resolution due to redundant variables [as shown in diagram (d)] and to find a representation of such an extended data set in hardware. This allows us to define encoding and decoding maps $f$ and $g$, respectively, to transform between the two data representations. Then, we forget about the scaffolding graph and train the hardware-embedded model on the extended data set. Thus, although the final hardware-embedded model might be interpreted as an embedding of a logical model, this is certainly not the case during learning, which automatically tackles the parameter-setting problem; in a sense, machine learning is parameter setting. While here we use standard embedding techniques to define the maps $f$ and $g$, such functions could, in principle, be learned from data, effectively automating the embedding problem, too.

Figure 3

OptDigits preprocessing steps. The original $8\times 8$ pictures are cropped to $7\times 6$ arrays by removing columns from the left and the right, as well as by deleting a row from the bottom. Finally, the four-bit gray scale is thresholded at the midpoint and binarized to $\{-1,+1\}$. Figure 4 shows some pictures from the test set.

Figure 4

OptDigits experiment. (a) We show 36 samples from the test set, with each pixel being either dark blue ($+1$) or white ($-1$). See Fig. 3 and the main text for a description of the preprocessing steps. (b) A uniform salt-and-pepper noise shown in red corrupts each picture. The model cannot use information from the red area. (c)–(f) Reconstructions obtained after 1, 10, 1000, and 6000 learning iterations. A light blue pixel indicates a tie of the majority vote over the corresponding subgraph. We can visually verify that the model has learned to generate digits. The learning stops at iteration 6000 because further iterations would bring some parameters out of the dynamic range of the DW2X device.

Figure 5

BAS experiment. (a) We show 36 samples from the test set, with each pixel being either dark blue ($+1$) or white ($-1$). (b) A $5\times 4$ block of noise shown in red corrupts each picture. The model cannot use information from the red area, and yet the remaining pixels contain enough information to reconstruct the original picture. (c)–(f) Reconstructions obtained after 1, 10, 1000, and 3850 learning iterations. The average number of mistaken pixels is 50% in (c), 18.6% in (d), 2.95% in (e), and finally 0.65% in (f). This is an almost perfect reconstruction. The learning stops at iteration 3850 because further iterations would bring some parameters out of the dynamical range of the DW2X device.

Figure 6

Visual Turing test(a)–(h). The reader is invited to distinguish between human-generated pictures from the test set and machine-generated pictures sampled from the model. Columns identify classes one to four; rows identify the source—human or machine. The solution is given in Ref. [79].

Figure 7

Comparison of different learning settings. The plots show mean and 1 standard deviation of the proxy ${\mathrm{\Lambda }}_{\mathrm{av}}$ for 10 random instances and for different learning procedures. We use exact gradient for the 15-variable logical graph and quantum annealing (QA) or simulated thermal annealing (SA) for the corresponding 76-qubit physical graph. A learning procedure is considered successful if it can generalize, that is, if it matches the proxy of the training set (green band). (a) The logical model (blue band) matches faster than the physical model (red squares) when the same learning rate is used. This suggests that the larger number of parameters does not help the physical model. (b) Quantum annealing on the physical graph (red circles) enables faster matching than exact gradient on the logical graph (blue band) when the same learning rate $\eta =0.0025$ is used. However, the exact-gradient procedure equipped with a larger learning rate $\eta =0.01$ (orange band) outperforms the quantum-assisted algorithm. In turn, the quantum-assisted algorithm outperforms all other learning procedures when equipped with the larger learning rate $\eta =0.01$ (purple triangles). Notice that neither the computation of ${\mathrm{\Lambda }}_{\mathrm{av}}$ nor the exact-gradient learning is tractable, in general.

Figure 8

Embedding. We show 46 logical variables embedded into DW2X’s chimera graph using 940 physical variables. Qubits belonging to a logical variable are identified by the same number and linked by edges of the same color. This embedding uses 86% of DW2X’s qubits.