Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1711.04889 · IEEE Transactions on Intelligent Transportation Systems

Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management

Tobias Stollenwerk, Bryan O’Gorman, Davide Venturelli, Salvatore Mandrà, Olga K. Rodionova, Hokkwan Ng, Banavar Sridhar, Eleanor Gilbert Rieffel, Rupak Biswas

Published Feb 18, 2019• 146 citations
arXivHTMLPDF

Abstract

We present the mapping of a class of simplified air traffic management problems (strategic conflict resolution) to quadratic unconstrained Boolean optimization problems. The mapping is performed through an original representation of the conflict-resolution problem in terms of a conflict graph, where the nodes of the graph represent flights and the 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 this paper, 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.

DOI
10.1109/tits.2019.2891235

Related papers

Quantum Annealing in the NISQ Era: Railway Conflict Management

Krzysztof Domino, Mátyás Koniorczyk, Krzysztof Krawiec +3 more

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, demonstrations of 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 train dispatching consequences of the arrival of an already delayed train to a given network segment. 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, which is 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 the conventional solution of a linear integer version of the model as well as the solution of the QUBO model using a tensor network-based algorithm. 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) does not perform well on those instances, either.

arXiv:2112.03674•Entropy•Jan 18, 2023•35 citations

A quantum annealing approach for boolean satisfiability problem

Juexiao Su, Tianheng Tu, Lei He

Quantum annealing device has shown a great potential in solving discrete problems that are theoretically and empirically hard. Boolean Satisfiability (SAT) problem, determining if there is an assignment of variables that satisfies a given Boolean function, is the first proven NP-complete problem widely used in various domains. Here, we present a novel mapping of the SAT problem to the quadratic unconstrained binary optimization problem (QUBO), and further develop a tool flow embedding the proposed QUBO to the architecture of the commercialized quantum computer D-Wave. By leveraging electronic design automation techniques including synthesis, placement and routing, this is not only the first work providing the detail flow that embeds the QUBO, but also a technique scalable for real world applications and some hard SAT problems with over 6000 variables in QUBO. Based on our results, we discuss the challenges in solving SAT using the current generation of annealing device, and explore the problem solving capability of future quantum annealing computers.

ACM/IEEE Design Automation Conference (DAC)•May 25, 2016•39 citations

Quantum Annealing Approaches to the Phase-Unwrapping Problem in Synthetic-Aperture Radar Imaging

Khaled A. Helal Kelany, N.J. Dimopoulos, Clemens P. J. Adolphs +2 more

The focus of this work is to explore the use of quantum annealing solvers for the problem of phase unwrapping of synthetic aperture radar (SAR) images. Although solutions to this problem exist based on network programming, these techniques do not scale well to larger-sized images. Our approach involves formulating the problem as a quadratic unconstrained binary optimization (QUBO) problem, which can be solved using a quantum annealer. Given that present embodiments of quantum annealers remain limited in the number of qubits they possess, we decompose the problem into a set of subproblems that can be solved individually. These individual solutions are close to optimal up to an integer constant, with one constant per sub-image. In a second phase, these integer constants are determined as a solution to yet another QUBO problem. We test our approach with a variety of software-based QUBO solvers and on a variety of images, both synthetic and real. Additionally, we experiment using D-Wave Systems's quantum annealer, the D-Wave 2000Q. The software-based solvers obtain high-quality solutions comparable to state-of-the-art phase-unwrapping solvers. We are currently working on optimally mapping the problem onto the restricted topology of the quantum annealer to improve the quality of the solution.

arXiv:2010.00220•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•7 citations

Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines

Krzysztof Domino, Mátyás Koniorczyk, Krzysztof Krawiec +2 more

In this work, we consider a practical railway dispatching problem: delay and conflict management on a single-track railway line. We examine the issue of train dispatching consequences caused by the arrival of an already delayed train to the segment being considered. This problem is computationally hard and often needs to be solved timely. Here, we introduce a quadratic unconstrained binary optimization (QUBO) model of the problem in question, 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 QUBO problems.

arXiv:2010.08227•Oct 16, 2020•18 citations

Transcription and optimization of an interplanetary trajectory through quantum annealing

Federico De Grossi, Andrea Carbone, Dario Spiller +3 more

Abstract This study employed a quantum-annealing framework to solve spacecraft trajectory optimization problems. Quantum annealing belongs to the field of quantum computing and is a promising technique for tackling hard binary optimization problems by employing quantum annealers. To address the optimal control of a trajectory using quantum annealing, a transcription procedure was introduced to express the problem in the binary optimization form required. The proposed procedure leverages the pseudospectral method to discretize the trajectory and represents the dynamical constraints as algebraic equality constraints at specific nodes. Subsequently, both a linearization procedure and binary representation strategy for the real-valued variables of the problem were presented, leading to the quadratic binary unconstrained optimization form. The quantum-annealing-based method was tested in the context of an interplanetary low-thrust transfer from the Earth to Mars. First, we discussed which instances of the problem, especially in terms of their dimensions, are implementable on currently available quantum annealers; then, a solution was sought by employing annealers from D-Wave systems. Solutions from hybrid solvers that combine classical and quantum resources, and fully quantum solvers were explored. The results demonstrate the validity of the transcription approach, demonstrate the ability of the hybrid solver to tackle the case-study problem, and highlight the promising features and current limitations of practical trajectory optimization with quantum annealing.

Astrodynamics•Apr 1, 2025•5 citations

Quantum Annealing for Air Traffic Management

Tobias Stollenwerk

The scheduling and maneuver planning for transatlantic flights is a hard real world problem. We report on our recent efforts to map a this problem to the D-Wave quantum annealer.

•Jul 26, 2016•0 citations
We present the mapping of a class of simplified air traffic management problems (strategic conflict resolution) to quadratic unconstrained Boolean optimization problems. The mapping is performed through an original representation of the conflict-resolution problem in terms of a conflict graph, where the nodes of the graph represent flights and the 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 this paper, 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.
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, demonstrations of 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 train dispatching consequences of the arrival of an already delayed train to a given network segment. 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, which is 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 the conventional solution of a linear integer version of the model as well as the solution of the QUBO model using a tensor network-based algorithm. 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) does not perform well on those instances, either.
Quantum annealing device has shown a great potential in solving discrete problems that are theoretically and empirically hard. Boolean Satisfiability (SAT) problem, determining if there is an assignment of variables that satisfies a given Boolean function, is the first proven NP-complete problem widely used in various domains. Here, we present a novel mapping of the SAT problem to the quadratic unconstrained binary optimization problem (QUBO), and further develop a tool flow embedding the proposed QUBO to the architecture of the commercialized quantum computer D-Wave. By leveraging electronic design automation techniques including synthesis, placement and routing, this is not only the first work providing the detail flow that embeds the QUBO, but also a technique scalable for real world applications and some hard SAT problems with over 6000 variables in QUBO. Based on our results, we discuss the challenges in solving SAT using the current generation of annealing device, and explore the problem solving capability of future quantum annealing computers.
The focus of this work is to explore the use of quantum annealing solvers for the problem of phase unwrapping of synthetic aperture radar (SAR) images. Although solutions to this problem exist based on network programming, these techniques do not scale well to larger-sized images. Our approach involves formulating the problem as a quadratic unconstrained binary optimization (QUBO) problem, which can be solved using a quantum annealer. Given that present embodiments of quantum annealers remain limited in the number of qubits they possess, we decompose the problem into a set of subproblems that can be solved individually. These individual solutions are close to optimal up to an integer constant, with one constant per sub-image. In a second phase, these integer constants are determined as a solution to yet another QUBO problem. We test our approach with a variety of software-based QUBO solvers and on a variety of images, both synthetic and real. Additionally, we experiment using D-Wave Systems's quantum annealer, the D-Wave 2000Q. The software-based solvers obtain high-quality solutions comparable to state-of-the-art phase-unwrapping solvers. We are currently working on optimally mapping the problem onto the restricted topology of the quantum annealer to improve the quality of the solution.
In this work, we consider a practical railway dispatching problem: delay and conflict management on a single-track railway line. We examine the issue of train dispatching consequences caused by the arrival of an already delayed train to the segment being considered. This problem is computationally hard and often needs to be solved timely. Here, we introduce a quadratic unconstrained binary optimization (QUBO) model of the problem in question, 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 QUBO problems.
Abstract This study employed a quantum-annealing framework to solve spacecraft trajectory optimization problems. Quantum annealing belongs to the field of quantum computing and is a promising technique for tackling hard binary optimization problems by employing quantum annealers. To address the optimal control of a trajectory using quantum annealing, a transcription procedure was introduced to express the problem in the binary optimization form required. The proposed procedure leverages the pseudospectral method to discretize the trajectory and represents the dynamical constraints as algebraic equality constraints at specific nodes. Subsequently, both a linearization procedure and binary representation strategy for the real-valued variables of the problem were presented, leading to the quadratic binary unconstrained optimization form. The quantum-annealing-based method was tested in the context of an interplanetary low-thrust transfer from the Earth to Mars. First, we discussed which instances of the problem, especially in terms of their dimensions, are implementable on currently available quantum annealers; then, a solution was sought by employing annealers from D-Wave systems. Solutions from hybrid solvers that combine classical and quantum resources, and fully quantum solvers were explored. The results demonstrate the validity of the transcription approach, demonstrate the ability of the hybrid solver to tackle the case-study problem, and highlight the promising features and current limitations of practical trajectory optimization with quantum annealing.