Traveling Salesman Problem from a Tensor Networks Perspective

• URL: http://arxiv.org/abs/2311.14344v2
• Date: Sat, 13 Jul 2024 10:20:34 GMT
• Title: Traveling Salesman Problem from a Tensor Networks Perspective
• Authors: Alejandro Mata Ali, Iñigo Perez Delgado, Aitor Moreno Fdez. de Leceta,
• Abstract summary: We present a novel quantum-inspired algorithm for solving the Traveling Salesman Problem (TSP) We adapt it to different generalizations of the TSP and apply it to the job reassignment problem, a real productive industrial case.
• Score: 44.99833362998488
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a novel quantum-inspired algorithm for solving the Traveling Salesman Problem (TSP) and some of its variations using tensor networks. This approach consists on the simulated initialization of a quantum system with superposition of all possible combinations, an imaginary time evolution, a projection, and lastly a partial trace to search for solutions. This is a heuristically approximable algorithm to obtain approximate solutions with a more affordable computational cost. We adapt it to different generalizations of the TSP and apply it to the job reassignment problem, a real productive industrial case.

Related papers

• A Non-Variational Quantum Approach to the Job Shop Scheduling Problem [0.3078691410268859]
  We introduce Iterative-QAOA, a variant of QAOA designed to mitigate near-term hardware limitations.<n>We benchmark the algorithm on Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) instances on IonQ Forte Generation QPUs.<n>We find that Iterative-QAOA robustly converges to find optimal solutions as well as high-quality, near-optimal solutions for all problem instances evaluated.
  arXiv  Detail & Related papers  (2025-10-30T16:14:13Z)
• Knapsack and Shortest Path Problems Generalizations From A Quantum-Inspired Tensor Network Perspective [40.5694560588179]
  We present two quantum-inspired algorithms to solve the knapsack and the shortest path problems.<n>The methods provide an exact equation which returns the optimal solution of the problems.
  arXiv  Detail & Related papers  (2025-06-13T12:27:34Z)
• Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
  We show that every computation problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any problem, both inversion, constraint satisfaction and optimization.
  arXiv  Detail & Related papers  (2025-02-09T18:16:53Z)
• Quantum Annealing and Tensor Networks: a Powerful Combination to Solve Optimization Problems [0.0]
  The aim of this thesis is not to compare quantum devices with tensor network algorithms. We explore a potential synergy between these technologies, focusing on how two flagship algorithms might collaborate in the future. This thesis outlines an approach to this problem using finite automata, which we apply to construct the MPO for our case study.
  arXiv  Detail & Related papers  (2024-12-07T09:20:20Z)
• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA) We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA)
  arXiv  Detail & Related papers  (2024-09-20T08:27:42Z)
• Predicting Probabilities of Error to Combine Quantization and Early Exiting: QuEE [68.6018458996143]
  We propose a more general dynamic network that can combine both quantization and early exit dynamic network: QuEE. Our algorithm can be seen as a form of soft early exiting or input-dependent compression. The crucial factor of our approach is accurate prediction of the potential accuracy improvement achievable through further computation.
  arXiv  Detail & Related papers  (2024-06-20T15:25:13Z)
• Tensor Completion via Integer Optimization [7.813563137863005]
  The main challenge with the tensor completion problem is a fundamental tension between computation power and the information-theoretic sample complexity rate. Past approaches either achieve the information-theoretic rate but lack practical algorithms to compute the corresponding solution. This paper develops a novel tensor completion algorithm that resolves this tension by achieving both provable convergence (in numerical tolerance) in a linear number of oracle steps and the information-theoretic rate.
  arXiv  Detail & Related papers  (2024-02-06T21:44:07Z)
• Task Scheduling Optimization from a Tensor Network Perspective [41.94295877935867]
  We present a novel method for task optimization in industrial plants using quantum-inspired tensor network technology. We simulate a quantum system with all possible combinations, perform an imaginary time evolution and a series of projections to satisfy the constraints.
  arXiv  Detail & Related papers  (2023-11-17T10:10:46Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• Optimization of Robot Trajectory Planning with Nature-Inspired and Hybrid Quantum Algorithms [0.0]
  We solve robot trajectory planning problems at industry-relevant scales. Our end-to-end solution integrates highly versatile random-key algorithms with model stacking and ensemble techniques. We show how the latter can be integrated into our larger pipeline, providing a quantum-ready hybrid solution to the problem.
  arXiv  Detail & Related papers  (2022-06-08T02:38:32Z)
• 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-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
  We propose a quantum-inspired tensor-network-based algorithm for general locally constrained optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem. Our results show the effectiveness of this construction and potential applications.
  arXiv  Detail & Related papers  (2022-03-29T05:44:07Z)
• Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks [75.33431791218302]
  We study the training problem of deep neural networks and introduce an analytic approach to unveil hidden convexity in the optimization landscape. We consider a deep parallel ReLU network architecture, which also includes standard deep networks and ResNets as its special cases.
  arXiv  Detail & Related papers  (2021-10-18T18:00:36Z)

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.