Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
arXiv:1711.04889 · doi:10.1109/TITS.2019.2891235
Abstract
We present the mapping of a class of simplified air traffic management (ATM) problems (strategic conflict resolution) to quadratic unconstrained boolean optimization (QUBO) problems. The mapping is performed through an original representation of the conflict-resolution problem in terms of a conflict graph, where nodes of the graph represent flights and edges represent a potential conflict between flights. The representation allows a natural decomposition of a real world instance related to wind-optimal trajectories over the Atlantic ocean into smaller subproblems, that can be discretized and are amenable to be programmed in quantum annealers. In the study, we tested the new programming techniques and we benchmark the hardness of the instances using both classical solvers and the D-Wave 2X and D-Wave 2000Q quantum chip. The preliminary results show that for reasonable modeling choices the most challenging subproblems which are programmable in the current devices are solved to optimality with 99% of probability within a second of annealing time.
Paper accepted for publication on: IEEE Transactions on Intelligent Transportation Systems
References in corpus (1)
Cited by in corpus (42)
- Quantum Annealing for Industry Applications: Introduction and Review
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
- Domain wall encoding of discrete variables for quantum annealing and QAOA
- Benchmarking Quantum Annealing Controls with Portfolio Optimization
- Flight Gate Assignment with a Quantum Annealer
- Hybrid quantum ResNet for car classification and its hyperparameter optimization
- Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
- An energetic perspective on rapid quenches in quantum annealing
- Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
- Quantum adiabatic machine learning with zooming
- A symbolic approach to discrete structural optimization using quantum annealing
- Search range in experimental quantum annealing
- Quantum Annealing Approach for the Optimal Real-time Traffic Control using QUBO
- Parity Quantum Optimization: Benchmarks
- Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
- Embedding of Complete Graphs in Broken Chimera Graphs
- Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
- Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
- Towards Finding an Optimal Flight Gate Assignment on a Digital Quantum Computer
- Parity Quantum Optimization: Encoding Constraints
- Fluctuation guided search in quantum annealing
- Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines
- From Ansätze to Z-gates: a NASA View of Quantum Computing
- Semi-supervised time series classification method for quantum computing
- A QUBO formulation for top- eigencentrality nodes
- Petri Net Modeling for Ising Model Formulation in Quantum Annealing
- Quantum optimization with linear Ising penalty functions for customer data science
- Toward a standardized methodology for constructing quantum computing use cases
- Graph minor embedding can affect sampling degenerate ground states using quantum annealing
- QUBO Decision Tree: Annealing Machine Extends Decision Tree Splitting
- Mapping State Transition Susceptibility in Quantum Annealing
- Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
- Quantum annealing in the NISQ era: railway conflict management
- SWIFT-FMQA: Enhancing Factorization Machine with Quadratic-Optimization Annealing via Sliding Window
- Quantum Software Ecosystem Design
- Solving Large Break Minimization Problems in a Mirrored Double Round-robin Tournament Using Quantum Annealing
- Performance of Domain-Wall Encoding for Quantum Annealing
- Optimal Sufficient Requirements on the Embedded Ising Problem in Polynomial Time
- Quantum annealing and condensed matter physics
- QUBO-inspired Molecular Fingerprint for Chemical Property Prediction
- Approximate Approximation on a Quantum Annealer