Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization

• URL: http://arxiv.org/abs/2106.09056v2
• Date: Tue, 28 Dec 2021 09:54:35 GMT
• Title: Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
• Authors: \"Ozlem Salehi, Adam Glos, Jaros{\l}aw Adam Miszczak
• Abstract summary: We provide a detailed analysis of the Travelling Salesman Problem with Time Windows (TSPTW) in the context of solving it on a quantum computer. We introduce unconstrained binary optimization and higher order binary optimization formulations of this problem. We demonstrate the advantages of edge-based and node-based formulations of the TSPTW problem.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computing is offering a novel perspective for solving combinatorial optimization problems. To fully explore the possibilities offered by quantum computers, the problems need to be formulated as unconstrained binary models, taking into account limitation and advantages of quantum devices. In this work, we provide a detailed analysis of the Travelling Salesman Problem with Time Windows (TSPTW) in the context of solving it on a quantum computer. We introduce quadratic unconstrained binary optimization and higher order binary optimization formulations of this problem. We demonstrate the advantages of edge-based and node-based formulations of the TSPTW problem. Additionally, we investigate the experimental realization of the presented methods on a quantum annealing device. The provided results pave the path for utilizing quantum computer for a variety of real-world task which can be cast in the form of Travelling Salesman Problem with Time Windows problem.

Related papers

• Quantum-based Distributed Algorithms for Edge Node Placement and Workload Allocation [8.937905773981702]
  We present a mixed-integer linear programming (MILP) model for optimal edge server placement and workload allocation. Existing quantum solvers are limited to solving unconstrained binary programming problems. Our numerical experiments demonstrate the practicality of leveraging quantum supremacy to solve complex optimization problems in edge computing.
  arXiv  Detail & Related papers  (2023-06-01T21:33:08Z)
• Quantum and quantum-inspired optimization for solving the minimum bin packing problem [0.0]
  We consider the problem of filling spent nuclear fuel in deep-repository canisters that is relevant for atomic energy industry. We first redefine the aforementioned problem it in terms of quadratic unconstrained binary optimization. Results of our study indicate on the possibility to solve industry-relevant problems of atomic energy industry using quantum and quantum-inspired optimization.
  arXiv  Detail & Related papers  (2023-01-26T18:04:18Z)
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems [1.1470070927586016]
  We discuss the field of quantum optimization where we solve optimisation problems using quantum computers. We demonstrate this through a proper use case and discuss the current quality of quantum computers. We conclude with discussion on some recent quantum optimization breakthroughs and the current status and future directions.
  arXiv  Detail & Related papers  (2022-12-21T12:56:37Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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)
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer [13.528362112761805]
  We show the largest-to-date execution of a quantum optimization algorithm that preserves constraints on quantum hardware. We execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159. We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.
  arXiv  Detail & Related papers  (2022-06-13T16:21:04Z)
• Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization [0.0]
  We develop an Inexact Infeasible Quantum Interior Point Method to solve linear optimization problems. We also discuss how can we get an exact solution by Iterative Refinement without excessive time of quantum solvers.
  arXiv  Detail & Related papers  (2022-05-02T21:30:56Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Quantum Permutation Synchronization [88.4588059792167]
  We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
  arXiv  Detail & Related papers  (2021-01-19T17:51:02Z)

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.