Flight Gate Assignment with a Quantum Annealer Optimal flight gate assignment is a highly relevant optimization problem from airport management. Among others, an important goal is the minimization of the total transit time of the passengers. The corresponding objective function is quadratic in the binary decision variables encoding the flighttogate assignment. Hence, it is a quadratic assignment problem being hard to solve in general. In this work we investigate the solvability of this problem with a DWave quantum annealer. These machines are optimizers for quadratic unconstrained optimization problems (QUBO). Therefore the flight gate assignment problem seems to be well suited for these machines. We use real world data from a midsized German airport as well as simulation based data to extract typical instances small enough to be amenable to the DWave machine. In order to mitigate precision problems, we employ bin packing on the passenger numbers to reduce the precision requirements of the extracted instances. We find that, for the instances we investigated, the bin packing has little effect on the solution quality. Hence, we were able to solve small problem instances extracted from real data with the DWave 2000Q quantum annealer.

Solving Large Maximum Clique Problems on a Quantum Annealer Commercial quantum annealers from DWave Systems can find high quality solutions of quadratic unconstrained binary optimization problems that can be embedded onto its hardware. However, even though such devices currently offer up to 2048 qubits, due to limitations on the connectivity of those qubits, the size of problems that can typically be solved is rather small (around 65 variables). This limitation poses a problem for using DWave machines to solve applicationrelevant problems, which can have thousands of variables. For the important Maximum Clique problem, this article investigates methods for decomposing larger problem instances into smaller ones, which can subsequently be solved on DWave. During the decomposition, we aim to prune as many generated subproblems that donxe2x80x99t contribute to the solution as possible, in order to reduce the computational complexity. The reduction methods presented in this article include upper and lower bound heuristics in conjunction with graph decomposition, vertex and edge extraction, and persistency analysis.