Insights on Training Neural Networks for QUBO Tasks

• URL: http://arxiv.org/abs/2004.14036v1
• Date: Wed, 29 Apr 2020 09:09:17 GMT
• Title: Insights on Training Neural Networks for QUBO Tasks
• Authors: Thomas Gabor, Sebastian Feld, Hila Safi, Thomy Phan, Claudia Linnhoff-Popien (LMU Munich)
• Abstract summary: Current hardware limitations restrict the potential when solving quadratic unconstrained binary optimization problems. We train neural networks to solve arbitrary QUBO problems, sketching means to use neuromorphic hardware as a simulator or an additional co-processor for quantum computing.
• Score: 8.784674687542603
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Current hardware limitations restrict the potential when solving quadratic unconstrained binary optimization (QUBO) problems via the quantum approximate optimization algorithm (QAOA) or quantum annealing (QA). Thus, we consider training neural networks in this context. We first discuss QUBO problems that originate from translated instances of the traveling salesman problem (TSP): Analyzing this representation via autoencoders shows that there is way more information included than necessary to solve the original TSP. Then we show that neural networks can be used to solve TSP instances from both QUBO input and autoencoders' hiddenstate representation. We finally generalize the approach and successfully train neural networks to solve arbitrary QUBO problems, sketching means to use neuromorphic hardware as a simulator or an additional co-processor for quantum computing.

Related papers

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm for jointly encoding multiple sets of marginal distributions.
  arXiv  Detail & Related papers  (2024-07-18T22:05:21Z)
• Verified Neural Compressed Sensing [58.98637799432153]
  We develop the first (to the best of our knowledge) provably correct neural networks for a precise computational task. We show that for modest problem dimensions (up to 50), we can train neural networks that provably recover a sparse vector from linear and binarized linear measurements. We show that the complexity of the network can be adapted to the problem difficulty and solve problems where traditional compressed sensing methods are not known to provably work.
  arXiv  Detail & Related papers  (2024-05-07T12:20:12Z)
• Quantum Annealing and Graph Neural Networks for Solving TSP with QUBO [0.0]
  The paper explores the application of Quadratic Unconstrained Binary Optimization (QUBO) models in solving the Travelling Salesman Problem (TSP) through Quantum Annealing algorithms and Graph Neural Networks. It introduces a Graph Neural Network solution for TSP (QGNN-TSP), which learns the underlying structure of the problem and produces competitive solutions via gradient descent over a QUBO-based loss function.
  arXiv  Detail & Related papers  (2024-02-21T05:55:00Z)
• Training Multi-layer Neural Networks on Ising Machine [41.95720316032297]
  This paper proposes an Ising learning algorithm to train quantized neural network (QNN) As far as we know, this is the first algorithm to train multi-layer feedforward networks on Ising machines.
  arXiv  Detail & Related papers  (2023-11-06T04:09:15Z)
• Realization of a quantum neural network using repeat-until-success circuits in a superconducting quantum processor [0.0]
  In this paper, we use repeat-until-success circuits enabled by real-time control-flow feedback to realize quantum neurons with non-linear activation functions. As an example, we construct a minimal feedforward quantum neural network capable of learning all 2-to-1-bit Boolean functions. This model is shown to perform non-linear classification and effectively learns from multiple copies of a single training state consisting of the maximal superposition of all inputs.
  arXiv  Detail & Related papers  (2022-12-21T03:26:32Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL) This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
  arXiv  Detail & Related papers  (2022-10-23T11:58:05Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
  We show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems. We numerically demonstrate that the MNIST image dataset satisfies such conditions. We provide empirical evidence for $O(log n)$ training of a convolutional neural network with pooling.
  arXiv  Detail & Related papers  (2021-07-19T23:41:03Z)
• Quantum Computing for Artificial Intelligence Based Mobile Network Optimization [0.0]
  We discuss how certain radio access network optimization problems can be modelled using the concept of constraint satisfaction problems in artificial intelligence. As a case study, we discuss root sequence index (RSI) assignment problem - an important LTE/NR physical random access channel configuration related automation use-case. We formulate RSI assignment as quadratic unconstrained binary optimization (QUBO) problem constructed using data ingested from a commercial mobile network, and solve it using a cloud-based commercially available quantum computing platform.
  arXiv  Detail & Related papers  (2021-06-26T01:05:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.