{ "cells": [ { "cell_type": "markdown", "metadata": { "ExecuteTime": { "end_time": "2021-01-06T07:10:17.389768Z", "start_time": "2021-01-06T07:10:17.379639Z" } }, "source": [ "# Solving Max-Cut Problem with QAOA\n", "\n", " Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. " ] }, { "cell_type": "markdown", "metadata": { "ExecuteTime": { "end_time": "2021-01-06T07:12:18.621281Z", "start_time": "2021-01-06T07:12:18.308211Z" } }, "source": [ "## Overview\n", "\n", "In the [tutorial on Quantum Approximate Optimization Algorithm](./QAOA_EN.ipynb), we talked about how to encode a classical combinatorial optimization problem into a quantum optimization problem and slove it with Quantum Approximate Optimization Algorithm [1] (QAOA). In this tutorial, we will take the Max-Cut Problem as an example to further elaborate on QAOA.\n", "\n", "### Max-Cut Problem\n", "\n", "The Max-Cut Problem is a common combinatorial optimization problem in graph theory, and it has important applications in statistical physics and circuit design. The maximum cut problem is an NP-hard problem, so there is no efficient algorithm that can solve this problem perfectly.\n", "\n", "In graph theory, a graph is represented by a pair of sets $G=(V, E)$, where the elements in the set $V$ are the vertices of the graph, and each element in the set $E$ is a pair of vertices, representing an edge connecting these two vertices. For example, the graph in the figure below is represented by $V=\\{0,1,2,3\\}$ and $E=\\{(0,1),(1,2),(2,3),(3, 0)\\}$.\n", "\n", "![G](figures/maxcut-fig-maxcut_g.png \"Figure 1: A graph with four vertices and four edges\")\n", "