ConceptIntermediatequantum optimisationLesson 6

Optimization Problems and Their Formulation

Optimization problems range from continuous to combinatorial and convex to non-convex; quantum approaches require casting a problem as QUBO/Ising, turning constraints into penalty terms.

An optimisation problem is to find $x^*=\arg\min_{x\in\mathcal{X}}f(x)$ within a feasible set $\mathcal{X}$. By domain, problems are classified as continuous, such as training the parameters of a variational circuit where $\theta\in\mathbb{R}^P$, or combinatorial, where $\mathcal{X}$ is finite but enormous, such as $\{0,1\}^n$. By shape, they are classified as convex, where every local minimum is a global minimum, as in training an SVM on a fixed kernel, or non-convex, as in most combinatorial problems and circuit training.

In quantum computing, optimisation problems appear in two places. The first is the target problem itself, such as cutting a graph or scheduling. The second is the classical loop inside variational algorithms, where we optimise the circuit's angles. Confusing the two is common: QAOA turns a combinatorial problem into a continuous optimisation problem over the angles $(\gamma,\beta)$, which is itself non-convex.

The standard formulation for quantum approaches is QUBO: $\min_{x\in\{0,1\}^n}x^\top Qx$ (the linear terms sit on the diagonal because $x_i^2=x_i$). Constraints are added with penalty terms: the constraint $\sum_ix_i=k$ becomes $A\big(\sum_ix_i-k\big)^2$ added to the objective, where $A$ is large enough to make violating the constraint unprofitable, but not so large that it swamps the scale of the objective and makes optimisation harder. Lucas (2014) gave formulations for many problems: number partitioning, colouring, vertex cover, the travelling salesman and others.

The cost of the formulation is part of judging an approach: some problems need many auxiliary variables; the travelling salesman problem with $N$ cities needs $N^2$ binary variables in the standard formulation. Devices with limited connectivity also require embedding or extra SWAP gates.

A fair assessment: any quantum result should be compared with the best classical methods available for the same problem, with equivalent measures of time and solution quality, not only with exhaustive or random search.

It is worth noting that an approximate quantum solution does not satisfy the constraints automatically: if the penalty weights are small, the measurement may return strings that violate the constraint, so every candidate solution must be checked and repaired or discarded by classical post-processing.

Mathematical formula

$$\min_{x\in\{0,1\}^n}\ x^{\top}Qx\ +\ A\Big(\sum_i x_i-k\Big)^2$$

Worked example

  1. Number partitioning of the set $\{1,2,3\}$: we want two subsets with equal sums. With $z_i=\pm1$ the objective is $H=(1z_1+2z_2+3z_3)^2$. The choice $z=(+1,+1,-1)$ gives $(1+2-3)^2=0$: the subsets $\{1,2\}$ and $\{3\}$.
  1. The constraint "choose exactly one of two items": the penalty term is $A(x_1+x_2-1)^2$. Its values: $(0,0)\to A$, $(1,0)\to0$, $(0,1)\to0$, $(1,1)\to A$. After expanding and using $x_i^2=x_i$: $A(1-x_1-x_2+2x_1x_2)$, which is a QUBO form.

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005
  2. S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi (1983). Optimization by Simulated Annealing. Science 220(4598):671–680 doi:10.1126/science.220.4598.671
  3. M. Cerezo et al. (2021). Variational quantum algorithms. Nature Reviews Physics 3:625–644 doi:10.1038/s42254-021-00348-9