Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors

• URL: http://arxiv.org/abs/2306.08507v2
• Date: Tue, 19 Sep 2023 14:09:01 GMT
• Title: Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors
• Authors: Ioannis D. Leonidas, Alexander Dukakis, Benjamin Tan, Dimitris G. Angelakis
• Abstract summary: Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
• Score: 48.68474702382697
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables, to evaluate the effectiveness of NISQ devices when applied to industry relevant optimization problems. We apply a quantum variational approach to a testbed of multiple VRPTW instances ranging from 11 to 3964 routes. These intances were formulated as quadratic unconstrained binary optimization (QUBO) problems based on realistic shipping scenarios. We compare our results with standard binary-to-qubit mappings after executing on simulators as well as various quantum hardware platforms, including IBMQ, AWS (Rigetti), and IonQ. These results are benchmarked against the classical solver, Gurobi. Our approach can find approximate solutions to the VRPTW comparable to those obtained from quantum algorithms using the full encoding, despite the reduction in qubits required. These results suggest that using the encoding scheme to fit larger problem sizes into fewer qubits is a promising step in using NISQ devices to find approximate solutions for industry-based optimization problems, although additional resources are still required to eke out the performance from larger problem sizes.

Related papers

• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Improving Quantum and Classical Decomposition Methods for Vehicle Routing [2.4646794072984477]
  We propose an elaborate combination of two decomposition methods, namely graph shrinking and circuit cutting. Our results offer insights into the performance of algorithms for optimization problems within the constraints of current quantum technology.
  arXiv  Detail & Related papers  (2024-04-08T14:19:25Z)
• 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)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
  Vehicle routing problem (VRP) is an NP-hard optimization problem. This work builds a basic VRP solution for 3 and 4 cities using variational quantum eigensolver on a variable ANSATZ.
  arXiv  Detail & Related papers  (2021-12-28T10:20:42Z)
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem [0.7503129292751939]
  We investigate the potential use of a quantum computer to find approximate solutions to the heterogeneous vehicle routing problem. We find that the number of qubits needed for this mapping scales quadratically with the number of customers.
  arXiv  Detail & Related papers  (2021-10-13T15:38:25Z)
• An investigation of IBM Quantum Computing device performance on Combinatorial Optimisation Problems [0.0]
  This paper juxtaposes classical and quantum optimisation algorithms' performance to solve two common COP, the Travelling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP) Two accepted classical optimisation methods, Branch and Bound (BNB) and Simulated Annealing (SA), are compared to two quantum optimisation methods, Variational Quantum Eigensolver (VQE) algorithm and Quantum Approximate optimisation Algorithm (QAOA) Our results show that the VQE performs better than QAOA for these metrics, and we infer that this is due to the increased number of operations required.
  arXiv  Detail & Related papers  (2021-07-08T07:02:50Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages. Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data. Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
  arXiv  Detail & Related papers  (2021-06-24T08:18:42Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.