Restricted Boltzmann Machines trained with different numbers of iterations were used to provide a large diverse set of energy functions each containing many local valleys (LVs). They were used to confirm the property of the D-Wave quantum annealer (QA) to find potentially important LVs in the energy functions of Markov Random Fields that may be missed by classical searches. Even after a prohibitively long classical search by simulated annealing (SA), as many as 30-50% of the QA-found LVs remained not found by the SA. In order to establish if those LVs represent potentially important regions of the configuration space, they were compared to LVs that were found by both techniques. With respect to most of the important LV parameters, the LVs found only by the QA (missed by SA) were distributed in a wide range of the parameters' values. In an attempt to explain which LVs could not be found easily by the SA, it was established that for large or small, shallow or deep, wide or narrow LVs, the LVs found only by the QA are distinguished by a few-times smaller size of the LV basin of attraction (BoA). Apparently, the size of the BoA is much less important for QA search compared to the classical search, allowing QA to easily find many potentially important (e.g., wide and deep) LVs missed by even prohibitively lengthy classical searches.
Restricted Boltzmann Machines trained with different numbers of iterations were used to provide a large diverse set of energy functions each containing many local valleys (LVs). They were used to confirm the property of the D-Wave quantum annealer (QA) to find potentially important LVs in the energy functions of Markov Random Fields that may be missed by classical searches. Even after a prohibitively long classical search by simulated annealing (SA), as many as 30-50% of the QA-found LVs remained not found by the SA. In order to establish if those LVs represent potentially important regions of the configuration space, they were compared to LVs that were found by both techniques. With respect to most of the important LV parameters, the LVs found only by the QA (missed by SA) were distributed in a wide range of the parameters' values. In an attempt to explain which LVs could not be found easily by the SA, it was established that for large or small, shallow or deep, wide or narrow LVs, the LVs found only by the QA are distinguished by a few-times smaller size of the LV basin of attraction (BoA). Apparently, the size of the BoA is much less important for QA search compared to the classical search, allowing QA to easily find many potentially important (e.g., wide and deep) LVs missed by even prohibitively lengthy classical searches.
A local-valley (LV)-centered approach to assessing the quality of sampling from Restricted Boltzmann Machines (RBMs) was applied to the latest generation of the D-Wave quantum annealer. D-Wave and Gibbs samples from a classically trained RBM were obtained at conditions relevant to contrastive-divergence-based RBM learning. The samples were compared for the number of LVs to which they belonged and the energy of the corresponding local minima. No significant (desirable) increase in the number of the LVs has been achieved by decreasing the D-Wave annealing time. At any training epoch, the states sampled by the D-Wave belonged to a somewhat higher number of LVs than in the Gibbs sampling. However, many of those LVs found by the two techniques differed. For high-probability sampled states, the two techniques were (unfavorably) less complementary and more overlapping. Nevertheless, many potentially "important" local minima, i.e., those having intermediate, even if not high, probability values, were found by only one of the two sampling techniques while missed by the other. The two techniques overlapped less at later than earlier training epochs, which is precisely the stage of the training when modest improvements to the sampling quality could make meaningful differences for the RBM trainability. The results of this work may explain the failure of previous investigations to achieve substantial (or any) improvement when using D-Wave-based sampling. However, the results reveal some potential for improvement, e.g., using a combined classical-quantum approach.
A D-Wave quantum annealer (QA) having a 2048 qubit lattice, with no missing qubits and couplings, allowed embedding of a complete graph of a Restricted Boltzmann Machine (RBM). A handwritten digit OptDigits data set having 8x7 pixels of visible units was used to train the RBM using a classical Contrastive Divergence. Embedding of the classically-trained RBM into the D-Wave lattice was used to demonstrate that the QA offers a high-efficiency alternative to the classical Markov Chain Monte Carlo (MCMC) for reconstructing missing labels of the test images as well as a generative model. At any training iteration, the D-Wave-based classification had classification error more than two times lower than MCMC. The main goal of this study was to investigate the quality of the sample from the RBM model distribution and its comparison to a classical MCMC sample. For the OptDigits dataset, the states in the D-Wave sample belonged to about two times more local valleys compared to the MCMC sample. All the lowest-energy (the highest joint probability) local minima in the MCMC sample were also found by the D-Wave. The D-Wave missed many of the higher-energy local valleys, while finding many "new" local valleys consistently missed by the MCMC. It was established that the "new" local valleys that the D-Wave finds are important for the model distribution in terms of the energy of the corresponding local minima, the width of the local valleys, and the height of the escape barrier.
Abstract Modest statistical differences between the sampling performances of the D-Wave quantum annealer (QA) and the classical Markov Chain Monte Carlo (MCMC), when applied to Restricted Boltzmann Machines (RBMs), are explored to explain, and possibly address, the absence of significant and consistent improvements in RBM trainability when the D-Wave sampling was used in previous investigations. A novel hybrid sampling approach, combining the classical and the QA contributions, is investigated as a promising way to benefit from the modest differences between the two sampling methods. No improvements in the RBM training are achieved in this work, thereby suggesting that the differences between the QA-based and MCMC sampling, mainly found in the medium-to-low probability regions of the distribution, which are less important for the quality of the sample, are insufficient to benefit the training. Difficulties in achieving sufficiently high quality of embedding RBMs into the lattice of the newer generation of D-Wave hardware could be further complicating the task. On the other hand, the ability to generate samples of sufficient variety from lower-probability parts of the distribution has a potential to benefit other machine learning applications, such as the mitigation of catastrophic forgetting (CF) during incremental learning. The feasibility of using QA-generated patterns of desirable classes for CF mitigation by the generative replay is demonstrated in this work for the first time. While the efficiency of the CF mitigation using the D-Wave QA was comparable to that of the classical mitigation, both the speed of generating a large number of distinct desirable patterns and the potential for further improvement make this approach promising for a variety of challenging machine learning applications.
The next generation D-Wave quantum computer (QC) having more than 2000 qubits was demonstrated to be adequate for embedding graphs of restricted Boltzmann machines (RBMs) having the connectivity between RBM units (though still limited) already sufficient for successful training by classical algorithms. As a verification of the validity and quality of the employed embedding approach, the RBM was trained by classical contrastive divergence (CD), while the D-Wave was initially used only in the recognition step for reconstruction of incomplete test images (8 × 8 bars-and-stripes), and for their classification. The label classification errors by the D-Wave compared favorably to those obtained by classical Gibbs sampling, indicating that the QC was successfully finding the most energetically favorable combinations of the unknown visible RBM units/labels for the given fixed incomplete input image. The valid RBM embedding was further applied to investigate opportunities for using QCs in the RBM training, and specifically for replacing the classical Gibbs technique in generating a representative sample from the RBM model distribution. Statistical comparison of samples obtained by the Gibbs technique versus 10000 sample states generated from the D-Wave revealed significant differences in the observed outcomes. The D-Wave samples were found insufficiently representative of the model distribution, specifically by missing many local valley found by the Gibbs sampling. On the other hand, the D-Wave possessed an ability to find local valleys of the configuration space that were consistently missed by the classical sampling algorithms, which could potentially be very interesting for sampling applications.
In recent years, the diversification of problems that require computers to solve has attracted attention to the construction of meta-heuristics that can be applied to a wide range of problems, and to specialized computers that implement these meta-heuristics in their devices. The representative meta-heuristics are Simulated Annealing (SA) and its extension to quantum computation, Quantum Annealing (QA), and its path-integral Monte Carlo method for classical simulation Crosson and Harrow showed that for certain problems where QA outperformed SA, SQA achieved performance close to that of QA, and SQA sometimes outperformed SA by an exponential time factor. On the other hand, it remains unclear whether SQA can work efficiently on a wide range of other problems. In this study, we experimentally compared SA and SQA on instances of the restricted Boltzmann machine RBM, known as a fundamental building block in deep learning, and 3SAT, a fundamental combinatorial optimization problem. The results show that SQA gives slightly better solutions than SA as the problem size increases for RBM in terms of both accuracy and computation time in our setting, but the opposite trend is observed for 3SAT, indicating that there is no significant difference between the two methods. From the viewpoint of artificial intelligence research, it is necessary to further examine whether deep learning can be made more efficient by applying QA and SQA to RBM.
In this work we revisit and expand on a 2015 study that used a D-Wave quantum annealer as a sampling engine to assist in the training of a Deep Neural Network. The original 2015 results were reproduced using more recent D-Wave hardware. We systematically compare this quantum-assisted training method to a wider range of classical techniques, including: Contrastive Divergence with a different choice of optimizer; Contrastive Divergence with an increased number of steps (CD-k); and Simulated Annealing (SA). We find that quantum-assisted training still outperforms the CD with Gibbs sampling-based techniques; however, SA is able to match the performance of quantum-assisted training trivially using a quench-like schedule with a single sweep at high temperature followed by one at the target temperature.