Introduction to Optimisation Problems

Start with a decision you can check

Optimisation means choosing an allowed option that gives the best value of a stated objective. A delivery plan might minimise distance; a timetable might minimise clashes; a graph partition might maximise the number of edges crossing a cut. The quantum part comes after that modelling work. A circuit cannot repair an objective that rewards the wrong behaviour or a constraint that was never encoded.

Prerequisites: probabilities and amplitudes, circuits and complexity. No calculus is needed for the first example. The optional mathematical description uses binary variables and a diagonal matrix whose entries are objective values.

WORKED DIAGRAM · A16Triangle MaxCut

A triangle has six optimal assignments, each cutting two edges; an exactly-one constraint keeps only three of them.

The problem contract

Specify the candidate representation, the feasible set, the objective and the desired answer. Do you need a proven optimum, a feasible answer within a tolerance, or the best answer found within a time budget? A solver returning a good candidate has met a different contract from one providing an optimality certificate. The distinction matters when comparing exact classical methods with heuristic quantum methods.

For a binary problem, each variable is zero or one and an n-variable candidate is an n-bit string. A cost function assigns a real number to each string. A quantum optimisation circuit can encode that function into phases or energies, but measurement still returns a candidate string. The application must decode the string and verify its constraints and objective classically.

Worked example: a three-person partition

Let three people be vertices of a triangle, with one edge between every pair. Put each person in group zero or group one. Score one point for each edge whose endpoints are in different groups. This is MaxCut on a triangle. There are eight assignments, but swapping every group label leaves the cut unchanged.

The assignments 000 and 111 have score zero. Each of the other six assignments has score two: one person is separated from the other two, so two edges cross and one does not. A score of three is impossible because three pairwise different binary labels cannot be assigned to three vertices. Enumeration provides a complete correctness reference for this tiny instance.

If you minimise the negative score, the six best assignments have cost negative two. If you instead minimise the score, you solve the opposite problem and choose 000 or 111. State whether the task is minimisation or maximisation before selecting the sign of a Hamiltonian. A sign mistake can produce a perfectly implemented circuit solving the wrong problem.

From a classical objective to a quantum workflow

First write and test a classical evaluator. Next choose a quantum representation and a state-preparation method. Then choose an algorithm, such as QAOA or annealing, with a parameter schedule or training rule. Run the method, sample candidate strings, decode them and evaluate them with the original classical function. Finally compare the result and total effort with appropriate classical solvers.

The objective can be represented by a diagonal operator whose eigenvalue on each basis state is that string’s cost. A low-energy state is then associated with a low-cost assignment. A superposition does not let you read the costs of all assignments at once. Its purpose is to support transformations that may increase the probability of useful assignments before measurement.

For the triangle, a uniform sampler already finds an optimal cut with probability six eighths. This is a surprisingly strong baseline. A quantum circuit giving an optimal string on one trial therefore provides weak evidence of an advantage. A meaningful study should compare success probabilities and costs over many instances, especially ones whose structure is not already trivial for a classical method.

Constraints and penalties

Suppose an application requires exactly one person in group one. Then only 001, 010 and 100 are feasible. A penalty for violating that requirement can be added to the objective, or the algorithm can be designed to remain in the feasible subspace. The penalty weight must be large enough to prevent an infeasible assignment from appearing better than the best feasible one.

An excessively large penalty can also be inconvenient. Hardware coefficient ranges, numerical precision and optimisation landscapes may make small objective differences harder to resolve. A proof that a penalty preserves the desired optimum is different from evidence that the resulting model is easy to optimise. Report both the encoding and the original application objective so readers can assess the consequences.

A second check: feasibility before quality

Return to the triangle with the exactly-one constraint. There are three feasible assignments among eight: 001, 010 and 100. Uniform sampling therefore has feasibility probability three eighths, even though its unconstrained optimum probability was six eighths. Those are different success definitions for the same graph. A report that quotes the unconstrained success rate after introducing the constraint has changed its target without updating the metric.

Every feasible assignment still has cut score two. The other three unconstrained optima violate the exactly-one requirement. This makes an independent feasibility check essential: a score of two alone cannot tell you whether the returned assignment is allowed. In a hundred uniform trials, the expected feasible count is 37.5, not a required integer outcome for every run.

For a larger problem, maintain separate columns for original objective, constraint violations and transformed penalty cost. A single energy number can conceal why a candidate is attractive. This habit also helps debug whether a solver is failing to search effectively or whether the model itself rewards invalid answers.

What can and cannot be promised

General combinatorial optimisation includes computationally difficult families. Neither a large state space nor a quantum label implies an efficient solution to every instance. Some quantum methods have provable guarantees under specific assumptions; others are heuristics whose usefulness must be demonstrated empirically. The original QAOA paper is a primary example of a defined algorithm and specific performance analysis, rather than a universal optimisation claim. Farhi, Goldstone and Gutmann.

The size of a useful output also matters. Returning one candidate differs from enumerating every optimum. Evaluating a candidate can be easy even when finding one is hard. Preserve that separation when designing a verification step: a fast evaluator does not by itself make the optimisation problem easy.

Exercises and worked answers

Exercise 1. On a four-vertex cycle, find the maximum cut score and two assignments achieving it. Explain why this differs from the triangle.

Check the worked answer

Alternating assignments 0101 and 1010 cut all four edges, so the maximum is four. A cycle of even length can alternate group labels consistently; the odd triangle cannot. The upper bound of four is achieved because there are only four edges.

Exercise 2. A method returns an optimum on 75 percent of triangle trials. Is that evidence that it beats uniform random sampling?

Check the worked answer

No. Uniform sampling is optimal on six of eight triangle assignments, also 75 percent. Compare uncertainty intervals and total costs, and use a less trivial instance family before claiming improvement. The correct baseline follows from the problem’s actual structure.

Check your understanding

PAUSE & THINK

How many of the triangle’s eight assignments achieve the maximum cut?

Choose your answer

268

Check my answer

Answer: 6. 000 and 111 cut no edges. Every other assignment separates one vertex from the other two and cuts two edges.