Quantum annealing in the NISQ era: railway conflict management

• URL: http://arxiv.org/abs/2112.03674v2
• Date: Wed, 8 Dec 2021 10:36:00 GMT
• Title: Quantum annealing in the NISQ era: railway conflict management
• Authors: Krzysztof Domino, M\'aty\'as Koniorczyk, Krzysztof Krawiec, Konrad Ja{\l}owiecki, Sebastian Deffner, Bart{\l}omiej Gardas
• Abstract summary: We consider a practical railway dispatching problem: delay and conflict management on single-track railway lines. We introduce a quadratic unconstrained binary optimization (QUBO) model of this problem, compatible with the emerging quantum annealing technology. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers.
• Score: 0.44040106718326594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We are in the Noisy Intermediate-Scale Quantum (NISQ) devices' era, in which quantum hardware has become available for application in real-world problems. However, demonstrating the usefulness of such NISQ devices are still rare. In this work, we consider a practical railway dispatching problem: delay and conflict management on single-track railway lines. We examine the issue of train dispatching consequences caused by the arrival of an already delayed train to the network segment being considered. This problem is computationally hard and needs to be solved almost in real-time. We introduce a quadratic unconstrained binary optimization (QUBO) model of this problem, compatible with the emerging quantum annealing technology. The model's instances can be executed on present-day quantum annealers. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers. As a reference, we also provide solutions calculated with classical methods, including those relevant to the community (linear integer programming) and a sophisticated algorithm based on tensor networks for solving Ising instances. Our preliminary results illustrate the degree of difficulty of real-life railway instances for the current quantum annealing technology. Moreover, our analysis shows that the new generation of quantum annealers (the advantage system) perform much worse on those instances than its predecessor.

Related papers

• On the Baltimore Light RailLink into the quantum future [0.0]
  This work aims to showcase how the inherent noise in NISQ devices can be leveraged to solve real-world problems effectively. We generate and analyze solutions for managing train traffic under disturbances. Our research marks the inaugural application of both quantum computing paradigms to tramway and railway rescheduling.
  arXiv  Detail & Related papers  (2024-06-17T07:17:14Z)
• Computational supremacy in quantum simulation [22.596358764113624]
  We show that superconducting quantum annealing processors can generate samples in close agreement with solutions of the Schr"odinger equation. We conclude that no known approach can achieve the same accuracy as the quantum annealer within a reasonable timeframe.
  arXiv  Detail & Related papers  (2024-03-01T19:00:04Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional Networks [124.7972093110732]
  We propose quantum graph convolutional networks (QuanGCN), which learns the local message passing among nodes with the sequence of crossing-gate quantum operations. To mitigate the inherent noises from modern quantum devices, we apply sparse constraint to sparsify the nodes' connections. Our QuanGCN is functionally comparable or even superior than the classical algorithms on several benchmark graph datasets.
  arXiv  Detail & Related papers  (2022-11-09T21:43:16Z)
• 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)
• Supply Chain Logistics with Quantum and Classical Annealing Algorithms [0.0]
  Noisy intermediate-scale quantum (NISQ) hardware is almost universally incompatible with full-scale optimization problems of practical importance. We investigate a problem of substantial commercial value, multi-truck vehicle routing for supply chain logistics, at the scale used by a corporation in their operations. Our work gives a set of techniques that can be adopted in contexts beyond vehicle routing to apply NISQ devices in a hybrid fashion to large-scale problems of commercial interest.
  arXiv  Detail & Related papers  (2022-05-09T17:36:21Z)
• 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)
• 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)
• Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines [0.4724825031148411]
  We consider a practical railway dispatching problem: delay and conflict management on a single-track railway line. We introduce a quadratic unconstrained binary optimization (QUBO) model of the problem in question, compatible with the emerging quantum annealing technology. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers.
  arXiv  Detail & Related papers  (2020-10-16T08:17:57Z)
• Investigating the Chinese Postman Problem on a Quantum Annealer [0.0]
  D-Wave annealers are promising platforms to solve problems in the form of quadratic unconstrained binary optimization. We provide a formulation of the Chinese postman problem that can be used as a tool for probing the local connectivity of graphs and networks.
  arXiv  Detail & Related papers  (2020-08-06T17:11:54Z)
• On the learnability of quantum neural networks [132.1981461292324]
  We consider the learnability of the quantum neural network (QNN) built on the variational hybrid quantum-classical scheme. We show that if a concept can be efficiently learned by QNN, then it can also be effectively learned by QNN even with gate noise.
  arXiv  Detail & Related papers  (2020-07-24T06:34:34Z)

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.