3.1 Principles of Quadratic Unconstrained Binary Optimisation
QUBO represents optimisation problems in which a quadratic function of N binary variables, q1,…,qN, has to be minimised over all possible 2N assignments of its variables. The function to be minimised is referred to as the cost function, and it can be written as
|
where q := (q1,…,qN) ∈{0,1}N represents the assignment of N binary decision variables.
A broad class of optimisation problems with many practical applications admits a QUBO formulation [212]. To solve hard QUBO instances in an exact way, known classical algorithms require exponential time (in the problem size defined as the number of binary decision variables, N) [127]. Several approximate classical methods have been devised to reduce the computational cost; however, it is the fast maturing quantum annealing that aspires to demonstrate material speedup on the hardest QUBO instances, such as NP-hard discrete portfolio optimisation...
