Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1909.03978

Combining Learned Representations for Combinatorial Optimization

Saavan Patel, Sayeef Salahuddin

Published Sep 9, 2019• 0 citations
arXivHTMLPDF

Abstract

We propose a new approach to combine Restricted Boltzmann Machines (RBMs) that can be used to solve combinatorial optimization problems. This allows synthesis of larger models from smaller RBMs that have been pretrained, thus effectively bypassing the problem of learning in large RBMs, and creating a system able to model a large, complex multi-modal space. We validate this approach by using learned representations to create ``invertible boolean logic'', where we can use Markov chain Monte Carlo (MCMC) approaches to find the solution to large scale boolean satisfiability problems and show viability towards other combinatorial optimization problems. Using this method, we are able to solve 64 bit addition based problems, as well as factorize 16 bit numbers. We find that these combined representations can provide a more accurate result for the same sample size as compared to a fully trained model.

DOI
10.48550/arxiv.1909.03978

Related papers

Logically Synthesized, Hardware-Accelerated, Restricted Boltzmann Machines for Combinatorial Optimization and Integer Factorization

Saavan Patel, Philip Canoza, Sayeef Salahuddin

The Restricted Boltzmann Machine (RBM) is a stochastic neural network capable of solving a variety of difficult tasks such as NP-Hard combinatorial optimization problems and integer factorization. The RBM architecture is also very compact; requiring very few weights and biases. This, along with its simple, parallelizable sampling algorithm for finding the ground state of such problems, makes the RBM amenable to hardware acceleration. However, training of the RBM on these problems can pose a significant challenge, as the training algorithm tends to fail for large problem sizes and efficient mappings can be hard to find. Here, we propose a method of combining RBMs together that avoids the need to train large problems in their full form. We also propose methods for making the RBM more hardware amenable, allowing the algorithm to be efficiently mapped to an FPGA-based accelerator. Using this accelerator, we are able to show hardware accelerated factorization of 16 bit numbers with high accuracy with a speed improvement of 10000x and a power improvement of 32x.

arXiv:2007.13489•Jun 16, 2020•3 citations

Convolutional restricted Boltzmann machine aided Monte Carlo: An application to Ising and Kitaev models

Daniel Alcalde Puente, Ilya Eremin

Machine learning is becoming widely used in analyzing the thermodynamics of many-body condensed matter systems. Restricted Boltzmann machine (RBM) aided Monte Carlo simulations have sparked interest recently, as they manage to speed up classical Monte Carlo simulations. Here we employ the convolutional restricted Boltzmann machine (CRBM) method and show that its use helps to reduce the number of parameters to be learned drastically by taking advantage of translation invariance. Furthermore, we show that it is possible to train the CRBM at smaller lattice sizes, and apply it to larger lattice sizes. To demonstrate the efficiency of CRBM we apply it to the paradigmatic Ising and Kitaev models in two dimensions.

arXiv:2008.05401•Physical review. B./Physical review. B•Nov 30, 2020•14 citations

Convolutional RBM aided Monte Carlo: an application to Ising and Kitaev models

Daniel Alcalde Puente, Ilya Eremin

Machine learning is becoming widely used in analyzing the thermodynamics of many-body condensed matter systems. Restricted Boltzmann Machine (RBM) aided Monte Carlo simulations have sparked interest recently, as they manage to speed up classical Monte Carlo simulations. Here we employ the Convolutional Restricted Boltzmann Machine (CRBM) method and show that its use helps to reduce the number of parameters to be learned drastically by taking advantage of translation invariance. Furthermore, we show that it is possible to train the CRBM at smaller lattice sizes, and apply it to larger lattice sizes. To demonstrate the efficiency of CRBM we apply it to the paradigmatic Ising and Kitaev models in two-dimensions.

•Aug 12, 2020•0 citations

Ising Model Optimization Problems on a FPGA Accelerated Restricted Boltzmann Machine

Saavan Patel, Lili Chen, Philip Canoza +1 more

Abstract In this work we demonstrate usage of the Restricted Boltzmann Machine (RBM) as a stochastic neural network capable of solving NP-Hard Combinatorial Optimization problems efficiently. By mapping the RBM onto a reconfigurable Field Programmable Gate Array (FPGA), we can effectively hardware accelerate the RBM's stochastic sampling algorithm. We benchmark the RBM against the DWave 2000Q Quantum Adiabatic Computer and the Optical Coherent Ising Machine on two such optimization problems: the MAX-CUT problem and the Sherrington-Kirkpatrick (SK) spin glass. The hardware accelerated RBM shows asymptotic scaling either similar or better than these other accelerators. This leads to 10 7 x and 10 5 x time to solution improvement compared to the DWave 2000Q on the MAX-CUT and SK problems respectively, along with a 150x and 1000x improvement compared to the Coherent Ising Machine annealer on those problems. By utilizing commodity hardware running at room temperature, the RBM shows potential for immediate and scalable use.

arXiv:2008.04436•Dec 15, 2020•23 citations

Quantum computation of Restricted Boltzmann Machines by Monte Carlo Methods

Yunkai Yao

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.

Highlights in Science Engineering and Technology•Sep 30, 2022•0 citations

Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization

Kate V. Marshall, Daniel J. Egger, Michael Garn +4 more

Quantum computing offers an alternative paradigm for addressing combinatorial optimization problems compared to classical computing. Despite recent hardware improvements, the execution of empirical quantum optimization experiments at scales known to be hard for state-of-the-art classical solvers is not yet in reach. In this work, we offer a different way to approach combinatorial optimization with near-term quantum computing. Motivated by the promising results observed in using quantum-enhanced Markov chain Monte Carlo (QeMCMC) for approximating complicated probability distributions, we combine ideas of sampling from the device with QeMCMC together with warm-starting and parallel tempering, in the context of combinatorial optimization. We demonstrate empirically that our algorithm recovers the global optima for instances of the Maximum Independent Set problem (MIS) up to 117 decision variables using 117 qubits on IBM quantum hardware. We show early evidence of a scaling advantage of our algorithm compared to similar classical methods for the chosen instances of MIS. MIS is practically relevant across domains like financial services and molecular biology, and, in some cases, already difficult to solve to optimality classically with only a few hundred decision variables.

quant-pharXiv:2602.06171•Feb 9, 2026•0 citations
We propose a new approach to combine Restricted Boltzmann Machines (RBMs) that can be used to solve combinatorial optimization problems. This allows synthesis of larger models from smaller RBMs that have been pretrained, thus effectively bypassing the problem of learning in large RBMs, and creating a system able to model a large, complex multi-modal space. We validate this approach by using learned representations to create ``invertible boolean logic'', where we can use Markov chain Monte Carlo (MCMC) approaches to find the solution to large scale boolean satisfiability problems and show viability towards other combinatorial optimization problems. Using this method, we are able to solve 64 bit addition based problems, as well as factorize 16 bit numbers. We find that these combined representations can provide a more accurate result for the same sample size as compared to a fully trained model.
The Restricted Boltzmann Machine (RBM) is a stochastic neural network capable of solving a variety of difficult tasks such as NP-Hard combinatorial optimization problems and integer factorization. The RBM architecture is also very compact; requiring very few weights and biases. This, along with its simple, parallelizable sampling algorithm for finding the ground state of such problems, makes the RBM amenable to hardware acceleration. However, training of the RBM on these problems can pose a significant challenge, as the training algorithm tends to fail for large problem sizes and efficient mappings can be hard to find. Here, we propose a method of combining RBMs together that avoids the need to train large problems in their full form. We also propose methods for making the RBM more hardware amenable, allowing the algorithm to be efficiently mapped to an FPGA-based accelerator. Using this accelerator, we are able to show hardware accelerated factorization of 16 bit numbers with high accuracy with a speed improvement of 10000x and a power improvement of 32x.
Machine learning is becoming widely used in analyzing the thermodynamics of many-body condensed matter systems. Restricted Boltzmann machine (RBM) aided Monte Carlo simulations have sparked interest recently, as they manage to speed up classical Monte Carlo simulations. Here we employ the convolutional restricted Boltzmann machine (CRBM) method and show that its use helps to reduce the number of parameters to be learned drastically by taking advantage of translation invariance. Furthermore, we show that it is possible to train the CRBM at smaller lattice sizes, and apply it to larger lattice sizes. To demonstrate the efficiency of CRBM we apply it to the paradigmatic Ising and Kitaev models in two dimensions.
Machine learning is becoming widely used in analyzing the thermodynamics of many-body condensed matter systems. Restricted Boltzmann Machine (RBM) aided Monte Carlo simulations have sparked interest recently, as they manage to speed up classical Monte Carlo simulations. Here we employ the Convolutional Restricted Boltzmann Machine (CRBM) method and show that its use helps to reduce the number of parameters to be learned drastically by taking advantage of translation invariance. Furthermore, we show that it is possible to train the CRBM at smaller lattice sizes, and apply it to larger lattice sizes. To demonstrate the efficiency of CRBM we apply it to the paradigmatic Ising and Kitaev models in two-dimensions.
Abstract In this work we demonstrate usage of the Restricted Boltzmann Machine (RBM) as a stochastic neural network capable of solving NP-Hard Combinatorial Optimization problems efficiently. By mapping the RBM onto a reconfigurable Field Programmable Gate Array (FPGA), we can effectively hardware accelerate the RBM's stochastic sampling algorithm. We benchmark the RBM against the DWave 2000Q Quantum Adiabatic Computer and the Optical Coherent Ising Machine on two such optimization problems: the MAX-CUT problem and the Sherrington-Kirkpatrick (SK) spin glass. The hardware accelerated RBM shows asymptotic scaling either similar or better than these other accelerators. This leads to 10 7 x and 10 5 x time to solution improvement compared to the DWave 2000Q on the MAX-CUT and SK problems respectively, along with a 150x and 1000x improvement compared to the Coherent Ising Machine annealer on those problems. By utilizing commodity hardware running at room temperature, the RBM shows potential for immediate and scalable use.
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.
Quantum computing offers an alternative paradigm for addressing combinatorial optimization problems compared to classical computing. Despite recent hardware improvements, the execution of empirical quantum optimization experiments at scales known to be hard for state-of-the-art classical solvers is not yet in reach. In this work, we offer a different way to approach combinatorial optimization with near-term quantum computing. Motivated by the promising results observed in using quantum-enhanced Markov chain Monte Carlo (QeMCMC) for approximating complicated probability distributions, we combine ideas of sampling from the device with QeMCMC together with warm-starting and parallel tempering, in the context of combinatorial optimization. We demonstrate empirically that our algorithm recovers the global optima for instances of the Maximum Independent Set problem (MIS) up to 117 decision variables using 117 qubits on IBM quantum hardware. We show early evidence of a scaling advantage of our algorithm compared to similar classical methods for the chosen instances of MIS. MIS is practically relevant across domains like financial services and molecular biology, and, in some cases, already difficult to solve to optimality classically with only a few hundred decision variables.