QAOA Mixer Ansatz — X-Mixer and XY-Mixer

What You'll Learn:

• How QAOA alternates cost and mixer unitaries to approximate solutions to combinatorial optimization problems
• Why the choice of mixer determines the algorithm's search space and constraint satisfaction
• How the XY-mixer preserves Hamming weight for constrained optimization (TSP, portfolio selection)
• How to evaluate QAOA performance via approximation ratio and compare mixer strategies

Level: Advanced | Time: 30 minutes | Qubits: 4 | Framework: Cirq

Prerequisites

• MaxCut QAOA -- cost function encoding, basic QAOA structure
• GHZ State -- multi-qubit entanglement, CNOT decomposition

The Idea

Many important optimization problems -- scheduling, routing, portfolio selection -- can be encoded as finding the bitstring that maximizes some cost function C(z). The Quantum Approximate Optimization Algorithm (QAOA) tackles this by preparing a parameterized quantum state that concentrates probability amplitude on high-cost bitstrings.

QAOA works by alternating two operations:

1. Cost unitary U_C(gamma) = exp(-i gamma C): imprints the cost function as relative phases
2. Mixer unitary U_M(beta) = exp(-i beta B): drives exploration of the solution space

The key insight is that the mixer determines which states the algorithm can reach. The standard X-mixer explores all 2^n bitstrings freely, but many real problems have constraints (e.g., "select exactly k items"). Using the wrong mixer wastes resources exploring infeasible solutions.

The XY-mixer solves this by preserving Hamming weight -- if you start in a subspace with exactly k ones, you stay there. This turns a constrained problem into an unconstrained search within the feasible subspace.

How It Works

QAOA Circuit Structure

The trial state after p layers is:

|gamma, beta> = [prod_{l=1}^{p} U_M(beta_l) U_C(gamma_l)] |+>^n

Starting from uniform superposition, each layer applies the cost unitary (encoding the problem) followed by the mixer (driving transitions between candidate solutions).

Cost Layer (MaxCut)

For MaxCut, the cost function counts edges crossing a partition:

C = sum_{(i,j) in E} (1 - Z_i Z_j) / 2

Each edge contributes a ZZ interaction, decomposed as:

exp(-i gamma Z_i Z_j / 2) = CNOT(i,j) . RZ(gamma)(j) . CNOT(i,j)

X-Mixer (Standard)

CODECopy
B = sum_i X_i
U_M(beta) = prod_i exp(-i beta X_i) = prod_i RX(2 beta)

Independent single-qubit rotations that can transition between any pair of computational basis states. This is the original mixer from Farhi et al. (2014).

XY-Mixer (Hamming-Weight Preserving)

B_{XY} = sum_i (X_i X_{i+1} + Y_i Y_{i+1}) / 2

The XX+YY interaction swaps excitations between adjacent qubits without creating or destroying them. Implemented via the iSWAP gate:

iSWAP^t = exp(i t pi/4 (XX + YY))

This confines the search to the subspace with fixed Hamming weight -- essential for problems with cardinality constraints (Hadfield et al. 2019, Wang et al. 2020).

Circuit Diagram

X-Mixer (p=1, 4 qubits, complete graph)

CODECopy
         ┌───┐ ┌──────────────────────┐ ┌──────────┐
q_0: ────┤ H ├─┤                      ├─┤ RX(2beta)├───
         ├───┤ │    Cost Layer         │ ├──────────┤
q_1: ────┤ H ├─┤  CNOT-RZ(gamma)-CNOT ├─┤ RX(2beta)├───
         ├───┤ │  for each edge        │ ├──────────┤
q_2: ────┤ H ├─┤                      ├─┤ RX(2beta)├───
         ├───┤ │                      │ ├──────────┤
q_3: ────┤ H ├─┤                      ├─┤ RX(2beta)├───
         └───┘ └──────────────────────┘ └──────────┘

XY-Mixer (p=1, 4 qubits)

CODECopy
         ┌───┐ ┌──────────────────────┐ ┌───────────────────┐
q_0: ────┤ H ├─┤                      ├─┤ iSWAP^t ─●       │
         ├───┤ │    Cost Layer         │ │          │       │
q_1: ────┤ H ├─┤  CNOT-RZ(gamma)-CNOT ├─┤──────────● ─●   │
         ├───┤ │  for each edge        │ │             │   │
q_2: ────┤ H ├─┤                      ├─┤─────────────● ─●│
         ├───┤ │                      │ │                │ │
q_3: ────┤ H ├─┤                      ├─┤────────────────●─│
         └───┘ └──────────────────────┘ └───────────────────┘

The Math

QAOA Objective

QAOA maximizes the expected cost:

<C> = <gamma, beta| C |gamma, beta>

The approximation ratio r = <C> / C_max measures how close QAOA gets to the optimal solution. For MaxCut on 3-regular graphs with p=1, Farhi et al. proved r >= 0.6924, beating the classical random threshold of 0.5.

X-Mixer: Full Hilbert Space

The X-mixer generates the full SU(2^n) algebra. Starting from |+>^n, the reachable set is all 2^n computational basis states. This is appropriate when every bitstring is a feasible solution.

XY-Mixer: Constrained Subspace

The XY interaction preserves the total magnetization:

[B_{XY}, sum_i Z_i] = 0

If the initial state has Hamming weight k, all reachable states also have weight k. The dimension of the search space drops from 2^n to C(n, k).

For the complete analysis of XY-mixer performance bounds, see Wang et al. (2020).

Parameter Count

Each QAOA layer introduces exactly 2 variational parameters (gamma_l, beta_l), giving 2p total parameters independent of the number of qubits or edges.

Expected Output

Performance depends on parameter optimization. Random parameters (as in the demo) give a baseline; classical optimization (COBYLA, L-BFGS-B) significantly improves the ratio.

Running the Circuit

PYTHONCopy
from circuit import run_circuit, verify_qaoa_mixer

# Standard X-mixer for unconstrained MaxCut
result = run_circuit(n_qubits=4, p=2, mixer='x')
print(f"Best cut: {result['best_cut_found']}/{result['max_possible_cut']}")
print(f"Approx ratio: {result['approximation_ratio']:.2%}")

# XY-mixer for constrained problems
result_xy = run_circuit(n_qubits=4, p=2, mixer='xy')
print(f"XY best cut: {result_xy['best_cut_found']}/{result_xy['max_possible_cut']}")

# Verification suite
v = verify_qaoa_mixer()
for check in v["checks"]:
    status = "PASS" if check["passed"] else "FAIL"
    print(f"[{status}] {check['name']}: {check['detail']}")

Try It Yourself

1. Increase depth: Run with p=1, 2, 3, 4 and plot the approximation ratio. Does it monotonically improve? (It should, but random parameters may not show this clearly.)

2. Sparse vs. dense graphs: Replace the default complete graph with a cycle graph (edges = [(i, (i+1) % n) for i in range(n)]). How does sparsity affect the approximation ratio?

3. XY-mixer Hamming weight: Initialize in a state with Hamming weight 2 (e.g., |0011>) instead of |+>^n. After applying the XY-mixer, verify that all measured bitstrings still have weight 2.

4. Parameter optimization: Use scipy.optimize.minimize with COBYLA to optimize gamma and beta. Compare the optimized ratio with the random-parameter baseline.

What's Next

• Barren Plateaus -- Why deep variational circuits can have vanishing gradients
• Expressibility -- Quantifying how much of Hilbert space an ansatz can reach
• Hardware-Efficient Ansatz -- Device-native alternative to problem-inspired ansatze

Comparison: Mixer Strategies

Applications

References

• Farhi, E., Goldstone, J., & Gutmann, S. (2014). "A Quantum Approximate Optimization Algorithm." arXiv: 1411.4028.
• Hadfield, S. et al. (2019). "From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz." Algorithms 12(2), 34. DOI: 10.3390/a12020034.
• Wang, Z. et al. (2020). "XY mixers: Analytical and numerical results for the quantum alternating operator ansatz." Physical Review A 101, 012320. DOI: 10.1103/PhysRevA.101.012320.