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:2302.11595 · Physical Review Applied

Optimal Flight-Gate Assignment on a Digital Quantum Computer

Yahui Chai, Lena Funcke, Tobias Hartung, Karl Jansen, Stefan Kühn, Paolo Stornati, Tobias Stollenwerk

Published Dec 13, 2023• 24 citations
arXivHTMLPDF

Abstract

We investigate the performance of the variational quantum eigensolver (VQE) for the problem of optimal flight-gate assignment. This is a combinatorial-optimization problem that aims at finding an optimal assignment of flights to the gates of an airport, in order to minimize the passenger travel time. To study the problem, we adopt a qubit-efficient binary encoding with a cyclic mapping, which is suitable for a digital quantum computer. Using this encoding in conjunction with the conditional value at risk (CVaR) as an aggregation function, we systematically explore the performance of the approach by classically simulating the CVaR VQE. Our results indicate that the method allows for finding a good solution with high probability and that it significantly outperforms the naive VQE approach. We examine the role of entanglement for the performance and find that ans\"atze with entangling gates allow for better results than pure product states. Studying the problem for various sizes, our numerical data show that the scaling of the number of cost-function calls for obtaining a good solution is not exponential for the regimes that we investigate in this work.

DOI
10.1103/physrevapplied.20.064025

Related papers

Gaussian Boson Sampling for Binary Optimization

Jean Cazalis, Yahui Chai, Karl Jansen +2 more

In this study, we consider a Gaussian Boson Sampler for solving a Flight Gate Assignment problem. We employ a Variational Quantum Eigensolver approach using the Conditional Value-at-risk cost function. We provide proof of principle by carrying out numerical simulations on randomly generated instances.

arXiv:2312.07235•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•0 citations

Efficient Variational Quantum Algorithms for the Generalized Assignment Problem

Carlo Mastroianni, Francesco Plastina, Jacopo Settino +1 more

Quantum algorithms offer a compelling new avenue for addressing difficult NP-complete optimization problems, such as the Generalized Assignment Problem (GAP). Given the operational constraints of contemporary Noisy Intermediate-Scale Quantum (NISQ) devices, hybrid quantum-classical approaches, specifically Variational Quantum Algorithms (VQAs) like the Variational Quantum Eigensolver (VQE), promises to be effective approaches to solve real-world optimization problems. This paper proposes an approach, named VQGAP, designed to efficiently solve the GAP by optimizing quantum resources and reducing the required parametrized quantum circuit width with respect to standard VQE. The main idea driving our proposal is to decouple the qubits of ansatz circuits from the binary variables of the General Assignment Problem, by providing encoding/decoding functions transforming the solutions generated by ansatze in the limited quantum space in feasible solutions in the problem variables space, by exploiting the constraints of the problem. Preliminary results, obtained through both noiseless and noisy simulations, indicate that VQGAP exhibits performance and behavior very similar to VQE, while effectively reducing the number of qubits and circuit depth.

quant-pharXiv:2511.02739•Nov 5, 2025•0 citations

Variational Quantum Algorithm Applied to Collision Avoidance of Unmanned Aerial Vehicles

Zhaolong Huang, Qiting Li, Junling Zhao +1 more

Mission planning for multiple unmanned aerial vehicles (UAVs) is a complex problem that is expected to be solved by quantum computing. With the increasing application of UAVs, the demand for efficient conflict management strategies to ensure airspace safety continues to increase. In the era of noisy intermediate-scale quantum (NISQ) devices, variational quantum algorithms (VQA) for optimizing parameterized quantum circuits with the help of classical optimizers are currently one of the most promising strategies to gain quantum advantage. In this paper, we propose a mathematical model for the UAV collision avoidance problem that maps the collision avoidance problem to a quadratic unconstrained binary optimization (QUBO) problem. The problem is formulated as an Ising Hamiltonian, then the ground state is solved using two kinds of VQAs: the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA). We select conditional value-at-risk (CVaR) to further promote the performance of our model. Four examples are given to validate that with our method the probability of obtaining a feasible solution can exceed 90% based on appropriate parameters, and our method can enhance the efficiency of a UAVs' collision avoidance model.

Entropy•Nov 18, 2022•16 citations

Toward Quantum Gate-Model Heuristics for Real-World Planning Problems

Tobias Stollenwerk, Stuart Hadfield, Zhihui Wang

Many challenging scheduling, planning, and resource allocation problems come with real-world input data and hard problem constraints, and reduce to optimizing a cost function over a combinatorially defined feasible set, such as colorings of a graph. Toward tackling such problems with quantum computers using quantum approximate optimization algorithms, we present novel efficient quantum alternating operator ansatz (QAOA) constructions for optimization problems over proper colorings of chordal graphs. As our primary application, we consider the flight-gate assignment problem, where flights are assigned to airport gates as to minimize the total transit time of all passengers, and feasible assignments correspond to proper graph colorings of a conflict graph derived instancewise from the input data. We leverage ideas from classical algorithms and graph theory to show our constructions have the desirable properties of restricting quantum state evolution to the feasible subspace, and satisfying a particular reachability condition for most problem parameter regimes. Using classical preprocessing we show that we can always find and construct a suitable initial quantum (superposition) state efficiently. We show our constructions in detail, including explicit decompositions to a universal set of basic quantum gates, which we use to bound the required resource scaling as low-degree polynomials of the input parameters. In particular, we derive novel QAOA mixing operators and show that their implementation cost is commensurate with that of the QAOA phase operator for flight-gate assignment. A number of quantum circuit diagrams are included such that our constructions may be used as a template toward development and implementation of quantum gate-model approaches for a wider variety of potentially impactful real-world applications.

IEEE Transactions on Quantum Engineering•Jan 1, 2020•33 citations

Improving Variational Quantum Optimization using CVaR

Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert +2 more

Hybrid quantum/classical variational algorithms can be implemented on noisy intermediate-scale quantum computers and can be used to find solutions for combinatorial optimization problems. Approaches discussed in the literature minimize the expectation of the problem Hamiltonian for a parameterized trial quantum state. The expectation is estimated as the sample mean of a set of measurement outcomes, while the parameters of the trial state are optimized classically. This procedure is fully justified for quantum mechanical observables such as molecular energies. In the case of classical optimization problems, which yield diagonal Hamiltonians, we argue that aggregating the samples in a different way than the expected value is more natural. In this paper we propose the Conditional Value-at-Risk as an aggregation function. We empirically show -- using classical simulation as well as quantum hardware -- that this leads to faster convergence to better solutions for all combinatorial optimization problems tested in our study. We also provide analytical results to explain the observed difference in performance between different variational algorithms.

arXiv:1907.04769•Quantum•Apr 20, 2020•304 citations

Performance analysis of a filtering variational quantum algorithm

Gabriel Marin-Sanchez, David Amaro

Abstract Even a minor boost in solving combinatorial optimization problems can greatly benefit multiple industries. Quantum computers, with their unique information processing capabilities, hold promise for delivering such enhancements. The filtering variational quantum eigensolver (F-VQE) is a variational hybrid quantum algorithm designed to solve combinatorial optimization problems on existing quantum computers with limited qubit number, connectivity, and fidelity. In this work we employ instantaneous quantum polynomial circuits as our parameterized quantum circuits. We propose a hardware-efficient implementation that respects limited qubit connectivity and show that they halve the number of circuits necessary to evaluate the gradient with the parameter-shift rule. To assess the potential of this protocol in the context of combinatorial optimization, we conduct extensive numerical analysis. We compare the performance against three classical baseline algorithms on weighted MaxCut and the asymmetric traveling salesperson problem (ATSP). We employ noiseless simulators for problems encoded on 13–29 qubits, and up to 37 qubits on the IBMQ real quantum devices. The ATSP encoding employed reduces the number of qubits and avoids the need of constraints compared to the standard quadratic unconstrained binary optimization/Ising model. Despite some observed positive signs, we conclude that significant development is necessary for a practical advantage with F-VQE.

arXiv:2404.08933•New Journal of Physics•May 1, 2025•4 citations
We investigate the performance of the variational quantum eigensolver (VQE) for the problem of optimal flight-gate assignment. This is a combinatorial-optimization problem that aims at finding an optimal assignment of flights to the gates of an airport, in order to minimize the passenger travel time. To study the problem, we adopt a qubit-efficient binary encoding with a cyclic mapping, which is suitable for a digital quantum computer. Using this encoding in conjunction with the conditional value at risk (CVaR) as an aggregation function, we systematically explore the performance of the approach by classically simulating the CVaR VQE. Our results indicate that the method allows for finding a good solution with high probability and that it significantly outperforms the naive VQE approach. We examine the role of entanglement for the performance and find that ans"atze with entangling gates allow for better results than pure product states. Studying the problem for various sizes, our numerical data show that the scaling of the number of cost-function calls for obtaining a good solution is not exponential for the regimes that we investigate in this work.
Quantum algorithms offer a compelling new avenue for addressing difficult NP-complete optimization problems, such as the Generalized Assignment Problem (GAP). Given the operational constraints of contemporary Noisy Intermediate-Scale Quantum (NISQ) devices, hybrid quantum-classical approaches, specifically Variational Quantum Algorithms (VQAs) like the Variational Quantum Eigensolver (VQE), promises to be effective approaches to solve real-world optimization problems. This paper proposes an approach, named VQGAP, designed to efficiently solve the GAP by optimizing quantum resources and reducing the required parametrized quantum circuit width with respect to standard VQE. The main idea driving our proposal is to decouple the qubits of ansatz circuits from the binary variables of the General Assignment Problem, by providing encoding/decoding functions transforming the solutions generated by ansatze in the limited quantum space in feasible solutions in the problem variables space, by exploiting the constraints of the problem. Preliminary results, obtained through both noiseless and noisy simulations, indicate that VQGAP exhibits performance and behavior very similar to VQE, while effectively reducing the number of qubits and circuit depth.
Mission planning for multiple unmanned aerial vehicles (UAVs) is a complex problem that is expected to be solved by quantum computing. With the increasing application of UAVs, the demand for efficient conflict management strategies to ensure airspace safety continues to increase. In the era of noisy intermediate-scale quantum (NISQ) devices, variational quantum algorithms (VQA) for optimizing parameterized quantum circuits with the help of classical optimizers are currently one of the most promising strategies to gain quantum advantage. In this paper, we propose a mathematical model for the UAV collision avoidance problem that maps the collision avoidance problem to a quadratic unconstrained binary optimization (QUBO) problem. The problem is formulated as an Ising Hamiltonian, then the ground state is solved using two kinds of VQAs: the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA). We select conditional value-at-risk (CVaR) to further promote the performance of our model. Four examples are given to validate that with our method the probability of obtaining a feasible solution can exceed 90% based on appropriate parameters, and our method can enhance the efficiency of a UAVs' collision avoidance model.
Many challenging scheduling, planning, and resource allocation problems come with real-world input data and hard problem constraints, and reduce to optimizing a cost function over a combinatorially defined feasible set, such as colorings of a graph. Toward tackling such problems with quantum computers using quantum approximate optimization algorithms, we present novel efficient quantum alternating operator ansatz (QAOA) constructions for optimization problems over proper colorings of chordal graphs. As our primary application, we consider the flight-gate assignment problem, where flights are assigned to airport gates as to minimize the total transit time of all passengers, and feasible assignments correspond to proper graph colorings of a conflict graph derived instancewise from the input data. We leverage ideas from classical algorithms and graph theory to show our constructions have the desirable properties of restricting quantum state evolution to the feasible subspace, and satisfying a particular reachability condition for most problem parameter regimes. Using classical preprocessing we show that we can always find and construct a suitable initial quantum (superposition) state efficiently. We show our constructions in detail, including explicit decompositions to a universal set of basic quantum gates, which we use to bound the required resource scaling as low-degree polynomials of the input parameters. In particular, we derive novel QAOA mixing operators and show that their implementation cost is commensurate with that of the QAOA phase operator for flight-gate assignment. A number of quantum circuit diagrams are included such that our constructions may be used as a template toward development and implementation of quantum gate-model approaches for a wider variety of potentially impactful real-world applications.
Hybrid quantum/classical variational algorithms can be implemented on noisy intermediate-scale quantum computers and can be used to find solutions for combinatorial optimization problems. Approaches discussed in the literature minimize the expectation of the problem Hamiltonian for a parameterized trial quantum state. The expectation is estimated as the sample mean of a set of measurement outcomes, while the parameters of the trial state are optimized classically. This procedure is fully justified for quantum mechanical observables such as molecular energies. In the case of classical optimization problems, which yield diagonal Hamiltonians, we argue that aggregating the samples in a different way than the expected value is more natural. In this paper we propose the Conditional Value-at-Risk as an aggregation function. We empirically show -- using classical simulation as well as quantum hardware -- that this leads to faster convergence to better solutions for all combinatorial optimization problems tested in our study. We also provide analytical results to explain the observed difference in performance between different variational algorithms.
Abstract Even a minor boost in solving combinatorial optimization problems can greatly benefit multiple industries. Quantum computers, with their unique information processing capabilities, hold promise for delivering such enhancements. The filtering variational quantum eigensolver (F-VQE) is a variational hybrid quantum algorithm designed to solve combinatorial optimization problems on existing quantum computers with limited qubit number, connectivity, and fidelity. In this work we employ instantaneous quantum polynomial circuits as our parameterized quantum circuits. We propose a hardware-efficient implementation that respects limited qubit connectivity and show that they halve the number of circuits necessary to evaluate the gradient with the parameter-shift rule. To assess the potential of this protocol in the context of combinatorial optimization, we conduct extensive numerical analysis. We compare the performance against three classical baseline algorithms on weighted MaxCut and the asymmetric traveling salesperson problem (ATSP). We employ noiseless simulators for problems encoded on 13–29 qubits, and up to 37 qubits on the IBMQ real quantum devices. The ATSP encoding employed reduces the number of qubits and avoids the need of constraints compared to the standard quadratic unconstrained binary optimization/Ising model. Despite some observed positive signs, we conclude that significant development is necessary for a practical advantage with F-VQE.