Quantum Optimization
Quantum optimization comprises approaches such as QAOA and quantum annealing that encode a combinatorial optimization problem in an Ising Hamiltonian and seek its ground or low-energy states, with no proven general advantage.
Combinatorial optimisation problems ask for the best assignment of binary variables $x\in\{0,1\}^n$ that maximises or minimises an objective function. Many of them, such as Max-Cut, number partitioning and colouring, are NP-hard. Quantum approaches share a first step: reformulating the problem as a QUBO (quadratic unconstrained binary optimisation), $f(x)=\sum_iq_ix_i+\sum_{i<j}Q_{ij}x_ix_j$, and then turning it into a diagonal Ising Hamiltonian by the substitution $x_i=(1-z_i)/2$, where $z_i\in\{+1,-1\}$ are the eigenvalues of $Z_i$. Each bit string then becomes a computational basis state, and its energy is the value of the objective function. Lucas (2014) collected Ising formulations for a large number of well-known NP problems.
After the encoding there are main approaches. QAOA is a variational gate algorithm that alternates between evolution under the cost Hamiltonian and a mixing Hamiltonian, with its angles optimised classically. Quantum annealing is an analogue physical process that starts in the ground state of a simple Hamiltonian and moves slowly to the problem Hamiltonian. VQE can also be used with the problem Hamiltonian itself.
The precise scientific position: quantum computers are not believed to solve NP-hard problems efficiently in the worst case, and there is so far no evidence of a practical advantage in combinatorial optimisation over the best classical methods, such as the Goemans–Williamson approximation algorithm for Max-Cut, simulated annealing or specialised solvers. The open questions concern whether better or faster approximate solutions can be obtained for certain families of problems. That is why results are always compared with strong classical baselines, not with random search.
The optimisation lab offers three modes: "ising" to show the Hamiltonian and the energies of the states, "qaoa" to simulate a QAOA circuit, and "classical" to compare with a classical solution. Because the graphs are small (up to a few nodes), the optimal solution is always known by exhaustive enumeration of the $2^n$ states, which allows the approximation ratio to be measured exactly, but it also means these examples do not reflect the difficulty of large problems.
The quality of the solutions of these approaches is usually assessed by the approximation ratio $r=\langle C\rangle/C_{\max}$ or by the probability of obtaining the optimal solution on measurement; the two measures differ, and $r$ can be high while the probability of the optimum is low.
Mathematical formula
Worked example
Convert the "cut" function for a single edge, $f(x_1,x_2)=x_1+x_2-2x_1x_2$, into Ising form.
With the substitution $x_i=(1-z_i)/2$: $x_1+x_2=1-\tfrac{z_1+z_2}{2}$, and $2x_1x_2=\tfrac{(1-z_1)(1-z_2)}{2}=\tfrac{1-z_1-z_2+z_1z_2}{2}$.
The difference: $f=1-\tfrac{z_1+z_2}{2}-\tfrac12+\tfrac{z_1+z_2}{2}-\tfrac{z_1z_2}{2}=\tfrac{1-z_1z_2}{2}$.
Check: $z_1=z_2$ gives 0 (the two bits are equal, the edge is not cut), and $z_1=-z_2$ gives 1. This is the Max-Cut term for each edge.
Test your understanding
The quiz needs JavaScript.
Related topics
References
- Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005
- Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
- Michel X. Goemans; David P. Williamson (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42(6):1115–1145 doi:10.1145/227683.227684
