What does a quantum computer actually have to beat?
Start with what a feasible region is (topic 01) and why the best point of a linear problem sits at one of its corners (02). Topic 16 is the algorithm that walks from corner to corner to find it, topic 03 shows that every such problem has a mirror problem whose answer is the price of each limit, and topic 17 lets the objective curve, ending at Goemans–Williamson's semidefinite relaxation of Max-Cut, the classical result that QAOA on the quantum side has to beat. Turn six of these shapes over in 3D →
Linear programming keeps the objective flat: a straight trade-off between variables. Quadratic programming (QP) lets it curve: minimise or maximise a quadratic function of the variables, still subject to linear constraints. Portfolio construction is the standard example: risk enters as a quadratic form (variance), return enters linearly, and Markowitz's 1952 mean-variance framework is exactly this shape.
Whether the curve is a bowl or a saddle decides everything. A convex quadratic. One whose quadratic form never bends the "wrong way", technically positive semidefinite: is still efficiently solvable, by the same interior-point machinery topic 16 just introduced for linear programs. The moment the quadratic form has even one direction that curves downward instead, the nice structure is gone and the problem becomes NP-hard: not harder in some cases, but provably hard in general, with the line between zero such directions and one being the entire boundary.
Semidefinite programming (SDP) is the next rung up the same ladder: instead of optimising over a vector of numbers, optimise a linear function over the cone of positive-semidefinite matrices. The chain is genuinely nested. LP ⊂ QP ⊂ SDP, each strictly more expressive than the last, and every one of them convex and solvable in polynomial time. What SDP buys is the ability to take a problem that is discrete and NP-hard, relax it into something continuous and convex, solve that exactly, and round the continuous answer back down with a provable guarantee on how much is lost. Doing exactly that to Max-Cut is one of the most celebrated results in the field, and the reason this topic ends up mattering to quantum computing.
A quadratic program in standard form, and the line that decides its complexity:
minimise ½xᵀQx + cᵀx
s.t. Ax ≤ b
convex (poly-time solvable) ⟺ Q positive semidefinite
Q has even one negative eigenvalue ⟹ NP-hard
Sahni, "Computationally Related Problems," SIAM Journal on Computing 3 (1974), 262–279, first showed hardness for a fully negative-definite Q. Pardalos & Vavasis, "Quadratic Programming with One Negative Eigenvalue is NP-hard," Journal of Global Optimization 1 (1991), 15–22, sharpened it to the tightest possible statement: a single negative eigenvalue already suffices.
A semidefinite program, in standard form. X an n×n symmetric matrix, ⟨·,·⟩ the trace inner product, X ⪰ 0 meaning positive semidefinite:
maximise ⟨C, X⟩
s.t. ⟨Aᵢ, X⟩ = bᵢ for i = 1..m
X ⪰ 0
Linear programming is the special case where X is forced diagonal; relax that one restriction and LP becomes SDP.
The centrepiece, and the reason this topic sits on the OR/quantum boundary: Goemans & Williamson, "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming," Journal of the ACM 42(6) (1995), 1115–1145. Max-Cut: partition a graph's vertices into two sets to maximise the edges crossing between them: is NP-hard (one of Karp's original 21, topic 04). Relax each vertex's ±1 label to a unit vector yᵢ, and relax the objective the same way:
maximise ½ Σ_(i,j)∈E w_ij (1 − yᵢ·yⱼ) over unit vectors y₁,…,yₙ
= maximise ½ Σ w_ij (1 − Yᵢⱼ) over Y ⪰ 0, diag(Y) = 1
: an SDP, solvable exactly in polynomial time. Then round: draw a uniformly random hyperplane through the origin (a random unit vector r) and put each vertex on the side given by the sign of yᵢ·r. For two vectors at angle θᵢⱼ, the chance a random hyperplane separates them is exactly θᵢⱼ/π, so the rounded cut's expected value is Σ w_ij·θᵢⱼ/π. Comparing that, edge by edge, to the SDP's own contribution ½(1 − cos θᵢⱼ) gives a ratio that depends only on θ:
(θ/π) ÷ ½(1 − cos θ) = (2/π)·θ/(1 − cos θ)
Minimised at θ ≈ 2.331122 rad (about 133.6°), giving α_GW ≈ 0.878567. Since every edge contributes at least this fraction of its SDP share, so does the whole cut:
E[cut value] ≥ α_GW · SDP_OPT ≥ α_GW · OPT α_GW ≈ 0.878567
: unconditional, and the best worst-case ratio then known for any polynomial-time Max-Cut algorithm. The triangle in the figure shows the relaxation's slack directly: SDP value 2.25 against a true optimum of 2, an integrality gap that matches the closed form 9/4.
Is 0.878567 the best any efficient algorithm could ever do, not just this specific rounding scheme? Conditionally, yes: Khot, Kindler, Mossel & O'Donnell, "Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?", SIAM Journal on Computing 37(1) (2007), 319–357, show that beating α_GW + ε for any ε > 0 is NP-hard assuming the Unique Games Conjecture, a widely credited but still unproven hardness assumption. Unlike the Goemans–Williamson guarantee itself, this optimality claim rests on an open conjecture, so it is flagged rather than stated flat.
This is the number a quantum optimiser has to clear. QAOA, the Quantum Approximate Optimization Algorithm (Farhi, Goldstone & Gutmann, arXiv:1411.4028, 2014), was introduced on exactly this problem, and its own authors' analysis is the first honest data point: on 3-regular graphs, QAOA at its shallowest depth (p=1) is guaranteed at least ≈0.6924 of the optimal cut (a bound that is tight on triangle-free graphs) below 0.878567, not above it. A companion negative result at the next depth, Marwaha, "Local Classical MAX-CUT Algorithm Outperforms p=2 QAOA on High-Girth Regular Graphs," Quantum 5, 437 (2021), shows that a simple classical local algorithm matches or beats QAOA at depth p=2 on high-girth regular graphs: the locally tree-like family a bounded-depth quantum circuit is naturally analysed on, since a depth-p QAOA circuit only ever sees a p-hop neighbourhood of each node. Deeper circuits narrow the gap on some graph families; whether they cross 0.878567 on instances anyone actually needs solved is genuinely open, and this page will not assert more than that.
Combinatorial optimisation, exactly this way Max-Cut and Max-SAT are the two problems Goemans and Williamson's own 1995 paper targets directly: the same NP-hard territory topic 10's metaheuristics search without a certificate, using a different tool (an exact convex relaxation with a proven worst-case ratio, not a heuristic search), and SDP relaxations of this style are now the standard rigorous approach across a wide family of NP-hard combinatorial problems, wherever a certified approximation ratio is worth more than an exact answer nobody can compute in time. (For the broader field this one result opens onto: provable approximation ratios for NP-hard problems in general, including set cover and facility location. Williamson & Shmoys, The Design of Approximation Algorithms, CUP, 2011, is the standard text; Williamson is himself a co-author of the Goemans–Williamson result above.)
And on the quantum side of this page The bridges section below names this pairing directly. Goemans–Williamson's SDP is the classical benchmark every quantum Max-Cut claim is implicitly being measured against, whether the paper making the claim says so or not. For the mechanics of QAOA itself: the circuit, the hybrid loop that tunes it, and a worked example on the exact trap graph from Graph City: see The Machinery's QAOA & VQE topic.
Check yourself
What guarantee does Goemans-Williamson's semidefinite relaxation with random-hyperplane rounding give for Max-Cut?
The expected cut is at least alpha_GW (about 0.878567) times the SDP value, which is at least the optimum. 0.6924 is what QAOA at depth 1 is guaranteed on 3-regular graphs.