Quantum Approximate Optimization Algorithm

Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved.

Overview

Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm that can run on recent Noisy Intermediate-Scale Quantum (NISQ) devices and has a wide range of applications. QAOA was proposed by Edward Farhi et al. in 2014 [1], and its purpose is to solve combinatorial optimization problems approximately.

Combinatorial optimization problem

In applied mathematics and theoretical computer science, combinatorial optimization is a type of topic that finds the optimal object in a discrete set of objects. In simple terms, the combinatorial optimization problem means that all solutions of the problem are composed of discrete variables, and the optimal solution is to be found in the discrete solution set. Combinatorial optimization problems involve a wide range of areas and are common in real life, such as the design of aircraft routes and the planning of express delivery routes.

Specifically, a combinatorial optimization problem can be described by $n$ bits and $m$ clauses. Each bit is a binary variable whose value is $0$ or $1$, and we use $z_j$ to denote the value of the $j$th bit. Therefore, the value of these $n$ bits can be represented by the bit string $z=z_1z_2\dots z_n$. Each clause is a restriction on some bits. For example, a clause can require the value of the $2$nd bit to be $0$, or it can require the value of the $3$rd bit and the $5$th bit to be the same. For the $j$th clause, we define a function

$$ C_j(z)= \begin{cases} 1 & \text{If the value $z$ of $n$ bits satisfies the condition indicated by clause $j$}\\ 0 & \text{if the value $z$ of $n$ bits does not satisfy the condition indicated by clause $j$} \end{cases}. \tag{1} $$

For example, if the first clause requires the value of the second bit to be 0, then we have $C_1(z_10z_3\dots z_n)=1$ and $C_1(z_11z_3\dots z_n)=0$.

From the definition of $C_j$ in equation (1), we can define the objective function of the combinatorial optimization problem

$$ C(z)=\sum_{j=1}^m w_jC_j(z), \tag{2} $$

where $w_j$ is the weight of the $j$th clause. The combinatorial optimization problem is to find a value $z$ that maximizes the value of the objective function $C(z)$, namely

$$ \underset{z}{\operatorname{argmax}} C(z). \tag{3} $$

In theoretical computer science, there is a famous problem called the Boolean satisfiability problem (SAT). This problem asks that, given $n$ bits and $m$ clauses as inputs, if there exists a value these bits can take so that all the $m$ clauses are satisfied simultaneously. An optimization problem related to SAT is MAX-SAT, which asks that what value these $n$ bits should take so that as many as possible clauses are satisfied. It is worth noting that the way we define a combinatorial optimization problem above is to formulate it as MAX-SAT, or more precisely, weighted MAX-SAT.

Quantum approximate optimization algorithm

Many combinatorial optimization problems are NP-complete or even NP-hard problems, which means that computers may not be able to solve such problems efficiently. An alternative is to find the approximate optimal solution to such problems, and this task can usually be completed efficiently. QAOA is a quantum algorithm that can find an approximate optimal solution to a combinatorial optimization problem.

Encoding combinatorial optimization problem

For the above combinatorial optimization problem, there are $n$ bits and $m$ clauses. The QAOA algorithm transforms this problem into an optimization problem on an $n$-qubit system. Each computational basis state $|z\rangle \in \{0,1\}^n$ of the quantum system corresponds to a value $z$ of $n$ bits in the original problem. At the same time, for the $j$th clause in the original problem, we define a diagonal Hamiltonian $H_{C_j}$ satisfying

$$ H_{C_j}|z\rangle = C_j(z)|z\rangle. \tag{4} $$

Specifically, we can construct the Hamiltonian $H_{C_j}$ through the following equation:

$$ H_{C_j} = \sum_{z\in\{0,1\}^n} C_j(z)|z\rangle\langle z|. \tag{5} $$

For example, assuming that $z^{(1)}$ and $z^{(2)}$ are the values ​​satisfying the $j$th clause, then we can define

$$ H_{C_j} = |z^{(1)}\rangle\langle z^{(1)}| + |z^{(2)}\rangle\langle z^{(2)}|. \tag{6} $$

Therefore, QAOA encodes the objective function $C$ of the combinatorial optimization problem into the Hamiltonian $H_C$ on a system with $n$ qubits, where

$$ H_C = \sum_{j=1}^m w_jH_{C_j}, \tag{7} $$

and

$$ H_C|z\rangle = \sum_{j=1}^m w_jH_{C_j}|z\rangle = \sum_{j=1}^m w_jC_j(z)|z\rangle = C(z)|z\rangle . \tag{8} $$

It is worth noting that if an optimal solution to the original problem is $z_\text{opt}$, then we have

$$ \langle z_\text{opt}|H_C|z_\text{opt}\rangle = \langle z_\text{opt}|C(z_\text{opt})|z_\text{opt}\rangle = C( z_\text{opt})\langle z_\text{opt}|z_\text{opt}\rangle = C(z_\text{opt}). \tag{9} $$

Therefore, an optimal solution of the original combinatorial optimization problem is an eigenstate with the largest eigenvalue of the Hamiltonian $H_C$. In addition, for any quantum state $|\psi\rangle$,

$$ \langle\psi|H_C|\psi\rangle \leq C(z_\text{opt}), \tag{10} $$

and the equation takes the equal sign if and only if $|\psi\rangle$ is a superposition state of optimal solutions. It can be obtained from equation (9) and equation (10) that

$$ \max_{|\psi\rangle} \langle\psi|H_C|\psi\rangle = C(z_\text{opt}), \tag{11} $$

and finding the optimal solution of the original combinatorial optimization problem is equivalent to finding an eigenstate with the largest eigenvalue of the Hamiltonian $H_C$, that is, finding a quantum state $|\psi\rangle$ such that

$$ H_C|\psi\rangle = C(z_\text{opt})|\psi\rangle. \tag{12} $$

When we find such a quantum state $|\psi\rangle$, it is probably not a computational basis state, but a superposition of several computational basis states, each of which is an optimal solution of the original combinatorial optimization problem. Therefore, we can obtain an optimal solution to the original combinatorial optimization problem by performing computational basis measurements on $|\psi\rangle$.

Finding an approximate optimal solution

Although it is relatively simple to encode the objective function of the combinatorial optimization problem to be solved into the Hamiltonian $H_C$ of a quantum system, finding the quantum state $|\psi\rangle$ representing an optimal solution from the huge Hilbert space according to equation (11) is not easy. In order to find such a quantum state, we need another Hamiltonian

$$ H_B = \sum_{j=1}^n X_j, \tag{13} $$

where $X_j$ represents the Pauli $X$ gate acting on the $j$th qubit. The two eigenstates of Pauli $X$ gate are $|+\rangle$ and $|-\rangle$, and their corresponding eigenvalues ​​are $1$ and $-1$, respectively:

$$ \begin{align} X|+\rangle &= \begin{bmatrix} 0&1\\1&0 \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\1 \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\1 \end{bmatrix} = |+\rangle,\tag{14}\\ X|-\rangle &= \begin{bmatrix} 0&1\\1&0 \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\-1 \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} -1\\1 \end{bmatrix} = -|-\rangle.\tag{15} \end{align} $$

Therefore, the eigenstate with the largest eigenvalue of $H_B$ is

$$ |s\rangle \equiv \underbrace{|+\rangle\otimes\cdots\otimes|+\rangle}_\text{$n$ terms} = |+\rangle^{\otimes n }. \tag{16} $$

We will use this quantum state $|s\rangle$ as the initial state for the algorithm. After constructing the Hamiltonian $H_C$ and $H_B$, we can start to find an approximate optimal solution to the original combinatorial optimization problem. According to the Hamiltonian $H_C$ and $H_B$, respectively define the unitary transformation

$$ U_C(\gamma) = e^{-i\gamma H_C} \tag{17} $$

and unitary transformation

$$ U_B(\beta) = e^{-i\beta H_B}, \tag{18} $$

where $\gamma$ and $\beta$ are adjustable real parameters. Given any integer $p\geq1$ and the parameters $\vec{\gamma}=(\gamma_1,\dots,\gamma_p)$ and $\vec{\beta}=(\beta_1,\dots,\beta_p) $, we define

$$ |\vec{\gamma},\vec{\beta}\rangle = U_B(\beta_p)U_C(\gamma_p)\cdots U_B(\beta_1)U_C(\gamma_1)|s\rangle. \tag{19} $$

It can be seen that the integer $p$ represents the number of layers of $U_C, U_B$, that is, the $U_C$ and $U_B$ are alternately applied to the initial state $|s\rangle$ $p$ times. Let us denote $F_p(\vec{\gamma},\vec{\beta})$ as the expected value of the Hamiltonian $H_C$ in the quantum state of equation (19):

$$ F_p(\vec{\gamma},\vec{\beta}) = \langle\vec{\gamma},\vec{\beta}|H_C|\vec{\gamma},\vec{\beta}\rangle . \tag{20} $$

By adjusting the parameters $\vec{\gamma},\vec{\beta}$, we can get

$$ M_p = \max_{\vec{\gamma},\vec{\beta}} F_p(\vec{\gamma},\vec{\beta}) \tag{21} $$

as the approximate optimal solution under a given number of layers $p$. So far, we have transformed the problem of searching for the quantum state $|\psi\rangle$ into a problem of searching for the parameters $\vec{\gamma},\vec{\beta}$. It is worth noting that the search space given by $p$ layers of $U_C, U_B$ is larger than that of $p-1$ layers, so

$$ M_p \geq M_{p-1}. \tag{22} $$

In fact, when $p$ is large enough,

$$ \lim_{p\to\infty} M_p = \max_z C(z). \tag{23} $$

Decoding the quantum solution

In the previous paragraph, we simplify the search for the quantum state $|\psi\rangle$ into the search for the parameterized quantum state $|\vec{\gamma},\vec{\beta}\rangle$, but at the same time, we have also reduced the search space. That is to say, given the number of layers $p$, there may be no parameters $\vec{\gamma},\vec{\beta}$ such that $F_p(\vec{\gamma},\vec{\beta}) = C(z_\text{opt})$. Suppose that the parameters $\vec{\gamma}^*$ and $\vec{\beta}^*$ make $F_p$ the largest, that is, $F_p(\vec{\gamma}^*,\vec{\beta}^* ) = M_p$. Then under ideal circumstances, the quantum state $|\vec{\gamma}^*,\vec{\beta}^*\rangle$ contains the information of an optimal solution. But it should be noted that only $p$ layers are used here, so it is very likely that $M_p < C(z_\text{opt})$. Therefore, in general $|\vec{\gamma}^*,\vec{\beta}^*\rangle$ only contains information about an approximate optimal solution. Furthermore, we assume that the quantum state $|\vec{\gamma}^*,\vec{\beta}^*\rangle$ is the superposition state of $l$ computational basis state, namely

$$ |\vec{\gamma}^*,\vec{\beta}^*\rangle = c_1|z^{(1)}\rangle + \cdots + c_l|z^{(l)}\rangle. \tag{24} $$

Normally, the larger the probability $|c_j|^2$ that a state $|z^{(j)}\rangle$ is measured on the computational basis, the more likely that the corresponding bit string $z^{(j) }$ is an optimal solution. Thus, we prepare $|\vec{\gamma}^*,\vec{\beta}^*\rangle$ and measure it to get a bit string $z$ and calculate the value of $C(z)$. Repeat this process many times, and we can get a bit string $z$ that makes $C(z)$ close to or even exceed $M_p$.

Adiabatic theorem

Why do we use the above method to construct the quantum state $|\vec{\gamma},\vec{\beta}\rangle$? QAOA tries to find an approximate optimal solution to an optimization problem. A similar algorithm is the quantum adiabatic algorithm [2] (QAA). The difference is that QAA is designed to find an optimal solution to the optimization problem rather than an approximate one. Similar to QAOA, QAA transforms an optimization problem into a problem of finding the ground state of a Hamiltonian, and uses the adiabatic theorem to solve it. Consider the Hamiltonian

$$ H(t) = (1-\frac tT)H_B + \frac tT H_C, \tag{25} $$

of a quantum system. At initial, time $t=0$, and the Hamiltonian of the system is $H(0) = H_B$. As time passes, the Hamiltonian of the system gradually changes from $H_B$ to $H_C$. When $t=T$, the Hamiltonian of the system becomes $H(T) = H_C$. The adiabatic theorem in quantum mechanics tells us that if the system is in an eigenstate of $H_B$ at the beginning, then as long as the evolution time $T$ is long enough, the system will be in the eigenstate of the corresponding energy level of $H_C$ when the Hamiltonian of the system completely evolves to $H_C$. Therefore, if the system is initially in $|s\rangle$, that is, the eigenstate with the largest eigenvalue of $H_B$, after a sufficiently long evolution time $T$, the quantum state of the system will become the eigenstate with the largest eigenvalue of $H_C$. [3]

One way to simulate the evolution of the Hamiltonian $H(t)$ over time $t$ is to alternately apply the unitary transformations $U_C(\gamma)$ and $U_B(\beta)$ on the quantum system, and the accuracy of simulation depends on the value of $\gamma,\beta$. In addition, in order for the evolution of the system to follow the adiabatic theorem, a sufficiently long evolution time is required, so the value of $p$ is required to be large enough. Therefore, combining equation (22) we can deduce the conclusion in equation (23).

---

References

[1] Farhi, E., Goldstone, J. & Gutmann, S. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 (2014).

[2] Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M. Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106 (2000).

[3] Duan, R. Quantum Adiabatic Theorem Revisited. arXiv:2003.03063 (2020).