Optimisation formulations

Many computationally hard problems in ATM/UTM — scheduling, routing, resource allocation, airspace configuration — are combinatorial optimisation problems: finding the best arrangement from a finite but exponentially large set of possibilities. To solve such problems on quantum hardware, they must first be expressed in a form that quantum computers can process.

QUBO — Quadratic Unconstrained Binary Optimisation

A QUBO problem is defined by minimising a quadratic function over binary variables:

minimise ∑_i Q_ii x_i+ ∑_i<j Q_ij x_i x_j

where x_i ∈ 1 are binary decision variables and Q is a matrix of coefficients. The objective is purely quadratic with no constraints — any constraints must be encoded as penalty terms added to the objective function.

QUBO is the native input format for quantum annealers and can also be solved on gate-model quantum computers using variational algorithms. Many classical combinatorial problems — including graph partitioning, job scheduling, and set covering — can be naturally expressed as QUBO instances.

Ising model

The Ising model is a physically motivated formulation equivalent to QUBO. It uses spin variables s_i ∈ -1 and expresses the objective as a Hamiltonian:

H(s) = ∑_i h_i s_i+ ∑_i<j J_ij s_i s_j

where h_i represents local fields and J_ij coupling strengths. The transformation between QUBO and Ising is straightforward: x_i = (1 + s_i) / 2.

The Ising formulation is natural for quantum annealers, which physically realise a time-dependent version of this Hamiltonian and evolve the system towards its ground state — the configuration that minimises the energy.

Encoding ATM constraints as penalties

Translating an ATM operational problem into QUBO form requires encoding each constraint as a penalty term. For example, requiring that each aircraft is assigned to exactly one gate becomes a penalty that increases the objective when zero or multiple assignments occur. The weight of each penalty must balance the need to enforce the constraint against the risk of distorting the objective landscape.

The JANUS project investigates these encodings for a range of ATM problems, including airspace sectorisation, traffic flow management, and flight scheduling. The resulting formulations are documented in the project catalogue (D4.1) and made available to the research community.