Max-Cut with Quantum Algorithms (QAOA and Quantum Max-Cut)

Overview

Max-Cut asks you to split the vertices of a graph into two groups so that as many edges as possible connect vertices in different groups. It is a classic hard optimization problem with uses in circuit layout, network design, and statistical physics, and it has become the standard test problem for quantum optimization because it is simple to state and its structure matches the natural interactions of a quantum computer.

The name appears in two related senses. In the first, quantum devices such as QAOA circuits and annealers are used to find good cuts of an ordinary graph. In the second, quantum Max-Cut is a different problem: finding the lowest-energy state of a quantum Heisenberg antiferromagnet defined on a graph, which is a question in quantum complexity theory. This page covers both, because readers meet both names.

The problem it solves

Dividing a network into two groups such that the number of connections crossing between the groups is as large as possible.

History and background

Max-Cut is one of Karp's original 21 NP-complete problems from 1972. In 1995 Goemans and Williamson gave a semidefinite programming algorithm that guarantees a cut of at least 0.878 times the optimum, and under the unique games conjecture that ratio cannot be improved by any efficient classical algorithm. Håstad showed in 2001 that it is NP-hard to approximate Max-Cut better than 16 over 17, about 0.941.

Farhi, Goldstone, and Gutmann used Max-Cut on three-regular graphs as the first test of QAOA in 2014, proving that one layer guarantees an approximation ratio of 0.6924. Later calculations by Wurtz and Love gave 0.7559 for two layers and 0.7924 for three, still below Goemans-Williamson. Experiments followed, including a 40-qubit trapped-ion study by Pagano and coauthors in 2020 and Google's 2021 study of non-planar graphs on up to 23 qubits. In parallel, Gharibian and Parekh published an approximation algorithm for quantum Max-Cut in 2019, and Anshu, Gosset, and Morenz studied beyond-product-state approximations in 2020.

How it works

Encodes possible partitions as quantum states, using QAOA's alternating optimization structure to search for partitions with a high cut value.

Label each vertex with a spin that points up or down. An edge is cut if its two endpoints have opposite spins. Writing the cost as an energy, each edge contributes a term that is lowest when the two spins disagree, so the best cut is the lowest-energy configuration of an antiferromagnetic Ising model on the graph. That is exactly the kind of energy landscape that annealers and QAOA are built to explore.

QAOA alternates a cost layer, which puts a phase on each edge depending on whether it is cut, with a mixing layer that moves amplitude between configurations. For low depth the circuit is local: the result at a vertex depends only on the neighborhood within p steps. That locality makes the performance computable by hand, and also reveals a limit, because a local rule cannot see global structure such as whether a graph is bipartite.

Quantum Max-Cut changes the question. The edge term becomes the sum of the three Pauli interactions, XX plus YY plus ZZ, between the two qubits, which is the projector onto the singlet state. The best state is no longer a bit string but an entangled quantum state, and the problem is QMA-hard. Product states give only a limited approximation ratio, which is why researchers study entangled approximations.

Step by step

1. Take a graph with n vertices and edge set E, and assign one qubit to each vertex.
2. Write the cost Hamiltonian as the sum over edges of one half times the quantity 1 minus the product of the Pauli Z operators on the two endpoints, so that each cut edge contributes 1.
3. Prepare all qubits in the equal superposition and apply p alternating layers of the cost unitary and the mixer with parameters gamma and beta.
4. Measure all qubits to obtain bit strings, compute the cut value of each, and estimate the expected cut size.
5. Use a classical optimizer to adjust the 2p parameters to maximize the expected cut, repeating the quantum runs for each trial.
6. Output the best bit string seen, and compare its cut with a classical solver such as Goemans-Williamson or a local search heuristic.

A worked example

On a triangle, the best cut separates one vertex from the other two and cuts 2 of 3 edges. A uniformly random assignment cuts 1.5 edges on average. QAOA with one layer and well-chosen angles raises the expected cut above 1.5 and makes the optimal bit strings the most likely outcomes, with six equally good solutions in total.

On a three-regular graph with 1,000 vertices, a random cut gives a fraction of 0.5 of the edges. One-layer QAOA guarantees 0.6924 of the optimum on average, while the classical Goemans-Williamson algorithm guarantees 0.878 and simple local search routinely gets above 0.9 of the maximum in practice. That is why current claims focus on scaling and on structured instances rather than raw cut quality.

Complexity and resources

What hardware it needs

• One qubit per vertex and two-qubit gates along each edge, which needs connectivity matching the graph or swap gates.
• Gate fidelity high enough for p layers, with error mitigation, and many shots per parameter evaluation.
• For quantum Max-Cut Hamiltonians, the ability to prepare entangled low-energy states, for example with variational circuits.

Applications

• Benchmarking QAOA and annealers on a standard problem across hardware vendors.
• Circuit layout, clustering, and community detection, where cuts model separation.
• Studying frustrated quantum magnets and antiferromagnets through the quantum Max-Cut Hamiltonian.
• Testing proposals for quantum advantage in optimization.

Limitations and caveats

• No quantum algorithm has beaten the best classical solvers on Max-Cut instances of practical size.
• Low-depth QAOA has proven limits on some graph families, including the overlap gap property on random regular graphs.
• Noise limits depth, so hardware experiments are far from the asymptotic regime.
• Quantum Max-Cut is a different problem from graph Max-Cut, and results on one do not transfer directly to the other.

Common misconceptions

• A quantum computer does not solve Max-Cut exactly in polynomial time. The problem is NP-hard.
• Finding a good cut on a 20-vertex graph is not evidence of advantage, since classical solvers handle millions of vertices.
• Quantum Max-Cut is not the same as running Max-Cut on a quantum computer.

How it compares

• The Goemans-Williamson semidefinite algorithm is a strong, polynomial-time classical baseline with a provable ratio.
• Quantum annealing targets the same Ising energy with an analog protocol and similar open questions.
• Grover-style search gives a quadratic speedup for exact search but needs deep circuits.

Real-world impact

The most commonly used benchmark for testing and comparing QAOA implementations across different quantum hardware platforms, due to its simple, well-understood classical structure.

Why it matters

Max-Cut is the fruit fly of quantum optimization: simple enough to analyze mathematically and rich enough to expose the real limits of near-term methods. Results on it shape how the community interprets claims about quantum advantage in optimization.

The quantum Max-Cut Hamiltonian also connects optimization to condensed matter physics, since its ground states describe frustrated magnets that are hard for classical computers to simulate.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Approximate Optimization Algorithm (QAOA)
• Related algorithm: Quantum Annealing
• Related algorithm: Quantum Approaches to the Traveling Salesman Problem
• Related algorithm: Quantum Algorithms for Semidefinite Programming

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database