ExperimentAdvancedquantum optimisation

QAOA p = 2 on a Weighted Graph

On the weighted 5-node graph (optimum cut 12 of total weight 13), depth p = 2 improves the approximation ratio over p = 1.

Goal

Compare the two depths on a weighted problem.

Approximate duration: 8 minutes

Steps

  1. Choose weighted5 and $p=1$ and record the ratio.
  2. Change to $p=2$.
  3. Compare the probability of the optimal solutions.
  4. Read the optimal values of $\gamma$ and $\beta$.
Loading the simulator…
What theory predicts

Theory predicts an optimal cut of 12 (the solutions 01101 and 10010), a random average of 6.5, and a ratio for $p=2$ greater than or equal to that for $p=1$. In the engine's run the ratio was about $0.81$ at $p=1$ and about $0.89$ at $p=2$ (it depends on the optimiser).

The graph's edges: (0,1,2), (0,2,1), (1,2,3), (1,3,1), (2,4,2), (3,4,4) in the form (node, node, weight). The maximum cut is 12, achieved by the partition 01101 or 10010. In the weighted case $H_C=\sum w_{ij}(1-Z_iZ_j)/2$, and the cost layer is implemented with $R_{ZZ}(-\gamma w_{ij})$ gates.

Increasing $p$ cannot lower the theoretical optimal value (because $p=2$ includes $p=1$ by setting $\gamma_2=\beta_2=0$), but the optimiser may get stuck at a local value. In the engine's run, $p=1$ gave a ratio of about $0.81$ and $p=2$ about $0.89$. The simulation computes $2^n$ amplitudes, so it is a teaching tool, not a competitive solver; and there is no general proof that QAOA outperforms classical algorithms on Max-Cut.

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
  2. Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005
  3. Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.