Towards Finding an Optimal Flight Gate Assignment on a Digital Quantum Computer

Abstract

We investigate the performance of the variational quantum eigensolver (VQE) for the optimal flight gate assignment problem. This problem 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 the method significantly outperforms the naive VQE approach. We examine the role of entanglement for the performance, and find that ansätze 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 we investigate in this work.

References in corpus (21)

• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• The theory of variational hybrid quantum-classical algorithms
• The Variational Quantum Eigensolver: a review of methods and best practices
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Quantum chemistry calculations on a trapped-ion quantum simulator
• Improving Variational Quantum Optimization using CVaR
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Towards simulating 2D effects in lattice gauge theories on a quantum computer
• SU(2) hadrons on a quantum computer
• Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
• Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks
• Quantum Annealing for Constrained Optimization
• A case study of variational quantum algorithms for a job shop scheduling problem
• Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
• Airport Gate Scheduling for Passengers, Aircraft, and Operation
• Accelerating lattice quantum field theory calculations via interpolator optimization using NISQ-era quantum computing
• Gauge invariant quantum circuits for $U(1)$ and Yang-Mills lattice gauge theories
• Zeta-regularized vacuum expectation values

Cited by in corpus (5)

• An approach to solve the coarse-grained Protein folding problem in a Quantum Computer
• Utility of NISQ devices: optimizing experimental parameters for the fabrication of Au atomic junction using gate-based quantum computers
• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
• Resource-Efficient Quantum Optimization via Higher-Order Encoding
• Gaussian Boson Sampling for binary optimization