Quantum annealing in the NISQ era: railway conflict management
arXiv:2112.03674 · doi:10.3390/e25020191
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.
arXiv commentarXiv admin note: substantial text overlap with arXiv:2010.08227
References in corpus (33)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- The density-matrix renormalization group
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Adiabatic Quantum Computing
- Matrix product states represent ground states faithfully
- Dynamics of a Quantum Phase Transition and Relaxation to a Steady State
- Dynamics of quantum phase transition: exact solution in quantum Ising model
- Hybrid quantum-classical algorithms and quantum error mitigation
- Robustness of adiabatic quantum computation
- Spin-Glass Theory for Pedestrians
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Adiabatic Theorem without a Gap Condition
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
- Achieving a quantum smart workforce
- Quantum Annealing for Constrained Optimization
- Adiabaticity in open quantum systems
- Space-time renormalization in phase transition dynamics
- Scalable spin-glass optical simulator
- Demonstration of nonstoquastic Hamiltonian in coupled superconducting flux qubits
- A quantum annealer with fully programmable all-to-all coupling via Floquet engineering
- Dynamics of a quantum phase transition in the 1D Bose-Hubbard model: excitations and correlations induced by a quench
- Implementation of a Hybrid Classical-Quantum Annealing Algorithm for Logistic Network Design
- Kibble-Zurek scaling of the irreversible entropy production
- Quantum neural networks to simulate many-body quantum systems
- Decomposition algorithms for solving NP-hard problems on a quantum annealer
- Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
- EXPEDIS: An Exact Penalty Method over Discrete Sets
- Disorder-assisted graph coloring on quantum annealers
- Separability gap and large deviation entanglement criterion