In QAOA for the MaxCut problem, what role does the problem unitary e^(-i*gamma*C) play, where C is the cost Hamiltonian?
AIt measures the quality of the current solution
BIt applies a phase proportional to the cut value of each computational basis state, encoding the objective function into the quantum state
CIt mixes between different solutions to explore the search space
DIt projects the state onto the optimal solution
The problem unitary e^(-i*gamma*C) applies a phase e^(-i*gamma*C(z)) to each computational basis state |z>, where C(z) is the cut value. States with higher cut values acquire different phases than states with lower cut values. This phase encoding is analogous to the oracle in Grover's algorithm — it marks good solutions. The subsequent mixing unitary then creates interference that can amplify high-quality solutions.
Question 2 True / False
QAOA with p=1 (one layer) is guaranteed to find the optimal solution for any combinatorial optimization problem.
TTrue
FFalse
Answer: False
QAOA at depth p=1 is a low-depth heuristic that provides a guaranteed approximation ratio for some problems (e.g., at least 0.6924 of optimal for MaxCut on 3-regular graphs) but does not find the exact optimum in general. As p increases, the algorithm can explore more of the solution space. In the limit p -> infinity, QAOA converges to the adiabatic algorithm and can in principle find the exact optimum, but this requires circuit depth that may grow with problem size.
Question 3 Short Answer
How does QAOA differ from VQE in its circuit structure, and why might this difference matter for practical performance?
Think about your answer, then reveal below.
Model answer: VQE uses a general parameterized ansatz (hardware-efficient or chemically inspired) with no prescribed structure. QAOA has a specific structure: alternating layers of the problem unitary e^(-i*gamma*C) and mixing unitary e^(-i*beta*B), with 2p parameters for p layers. This structure is problem-aware — the problem Hamiltonian C directly encodes the optimization objective. The structured ansatz may resist barren plateaus better than generic ansatze because the parameters have clear physical meaning (problem encoding strength and mixing rate), and the landscape has structure related to the optimization problem.
QAOA's structured ansatz is both its strength and limitation. The problem-specific structure means good parameters often concentrate around certain values independent of instance details, which helps with transferability and initialization. However, the rigid structure limits expressiveness at low depth. VQE's flexibility allows it to adapt to problem structure more freely but at the cost of harder optimization. In practice, both face similar challenges of measurement overhead and classical optimization difficulty.