Topic · Stub
Optimization
By QuantumAlgorithms.ai editorial. This page is AI-assisted and sourced from the primary papers cited on it. It is not a named expert review. First published . Updated .
Combinatorial optimization as it appears in this library: an approximation ratio for QAOA, a quadratic black-box search, and the classical algorithms beside them.
This is a short orientation, not a survey. It connects the algorithms currently in the library.
Optimization is not one quantum algorithm. In this library it is two different statements, plus the classical results they have to sit beside.
QAOA is a short parameterized circuit. Farhi, Goldstone, and Gutmann prove that at depth p = 1, on connected 3-regular graphs, the expected MaxCut is at least 0.6924 times optimal. They also say this does not match classical algorithms already known for that problem. Goemans and Williamson give a randomized classical algorithm for MaxCut with expected approximation ratio at least 0.878, on general graphs, from a semidefinite program. Quoting 0.6924 without that comparison turns a careful negative sentence in the QAOA paper into a advertisement.
The same preprint explains the circuit: cost unitary, mixer, p layers, classical choice of angles. For fixed p on bounded-degree MaxCut, the angles can be chosen by a classical calculation on a small neighborhood. That is a theorem about preprocessing, not a general claim that every scheduling problem has been given a quantum speedup. Hadfield and coauthors generalize the mixer for constrained problems. Their paper is a design framework. It does not replace the 0.6924 ratio with a stronger worst-case guarantee.
Grover's algorithm is the other tool people invoke, usually by ignoring structure. Unstructured search over the feasible set costs on the order of the square root of the number of candidates, and Bennett, Bernstein, Brassard, and Vazirani show you should not expect asymptotically fewer black-box queries. If the optimization problem has structure — and the ones worth solving usually do — discarding it to apply Grover is a modeling choice, not a reduction the problem forced on you. Amplitude amplification is the subroutine version, for when a quantum procedure already succeeds with small probability.
A problem statement that has been rewritten as a diagonal Hamiltonian is an encoding. The encoding is useful when someone then proves a ratio, a query bound, or an experiment with a classical baseline. This stub stops at the encodings this library can actually point at.
References
- Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv:1411.4028. arXiv
- Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6), 1115–1145. DOI
- Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (pp. 212–219). ACM. DOI · arXiv
- Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5), 1510–1523. DOI · arXiv
- Hadfield, S., Wang, Z., O'Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019). From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12(2), 34. DOI · arXiv
- Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002). Quantum amplitude amplification and estimation. In Quantum Computation and Information, Contemporary Mathematics (Vol. 305, pp. 53–74). American Mathematical Society. arXiv
Quantum algorithms is the guide. The complexity table is the row-by-row comparison.