QAOA（Quantum Approximate Optimization Algorithm）and Maxcut with Python code implementation

(中文在後面喔!)

Hi, this is ostrich! Today we are going to introduce QAOA. Let’s begin!

Introduction and High Level Interpretation

Many real-world problems can be formulated as combinatorial optimization problems.

For example, the class scheduling problem involves arranging a school or university’s class schedule, satisfying all course and classroom constraints, and possibly achieving specific objectives such as minimizing classroom utilization or minimizing student idle time.

QAOA (Quantum Approximate Optimization Algorithm) is a hybrid quantum-classical variational algorithm designed to address combinatorial optimization problems.

Similar to contemporary neural networks, in QAOA, the state is prepared by a p-level circuit specified by 2p variable parameters, namely, two learnable parameters β and γ. The training computation is performed on a quantum computer, while parameter updates occur on a classical computer.

It’s important to note that QAOA aims to “approximate” the optimal solution as closely as possible, rather than directly finding the optimal solution.

Pic1: Schematic of a p-level QAOA

What is QAOA (Detail)

The optimization problem is represented in the form of an N-bit binary string

the classical objective function is assumed to be

To run on a quantum computer, the classical objective function is encoded into the Hamiltonian terms of a quantum problem.

p-level QAOA

For an initial state |+>, generated through H_C and H_B,

the wave function is formed by applying an operator represented by the learnable parameters β and γ.

Define F as the expectation value of H_C.

Let β* and γ* be the parameters that maximize the value of F.

The measure of the approximation level is given by

where C_max represents the optimal solution.

MaxCut Problem

The MaxCut problem is a common application of QAOA.

In the MaxCut problem, given a graph with vertices and edges, the goal is to find a partition of the vertices into two groups such that the number of cut edges, or the maximum cut, is maximized.

來源: Mindspore

This can be expressed as

In this way, if i and j are anti-aligned, it will result in σz_i σz_k = -1, and this contributes a non-zero term to wij.

Once σz_i σz_k = 1, it implies that both vertices are in the same partition.

Conversely, when σz_i σz_k = -1, it indicates that the two vertices are in different partitions.

Anti-aligned: This term is commonly used to describe quantum bits in a spin system, where each spin can be in an “up” or “down” state. If the σz value of spin i is +1 (“up”) and the σz value of spin j is -1 (“down”), or vice versa, meaning they have opposite orientations, then σzi * σzj is -1. This indicates that these two spins are “anti-aligned.”

In this case, the wavefunction can be expressed as

Here, assuming it’s an unweighted graph,

we can illustrate its circuit.

Python Code Implementation

Here, we utilize Qiskit for practical implementation.

from qiskit import Aer, QuantumCircuit, transpile, assemble
from qiskit.visualization import plot_histogram
import matplotlib.pyplot as plt
import numpy as np

# Define the MaxCut problem instance (graph)
graph = {
    'edges': [(0, 1), (1, 2), (2, 3), (3, 0)],
    'weights': [1, 2, 3, 1]
}

# Create the QAOA circuit
def qaoa_circuit(gamma, beta, graph):
    n = len(graph['weights'])
    qc = QuantumCircuit(n, n)
    
    # Apply Hadamard gate to all qubits
    qc.h(range(n))
    
    # Apply the Ising-type gates for each edge
    for edge, weight in zip(graph['edges'], graph['weights']):
        qc.cx(edge[0], edge[1])
        qc.u(2 * gamma * weight, 0, 0, edge[1])
        qc.cx(edge[0], edge[1])
    
    # Apply single qubit X-rotations
    qc.rx(2 * beta, range(n))
    
    return qc

# Evaluate the QAOA circuit
def evaluate_qaoa(gamma, beta, graph, n_shots=1000):
    qc = qaoa_circuit(gamma, beta, graph)
    qc.measure(range(len(graph['weights'])), range(len(graph['weights'])))
    
    aer_sim = Aer.get_backend('aer_simulator')
    transpiled_qc = transpile(qc, aer_sim)
    qobj = assemble(transpiled_qc)
    
    result = aer_sim.run(qobj).result()
    counts = result.get_counts(qc)
    
    # Calculate the objective function value
    obj_val = 0
    for bit_string, count in counts.items():
        bit_weight = sum([int(bit) * weight for bit, weight in zip(bit_string, graph['weights'])])
        obj_val += bit_weight * count / n_shots
    
    return obj_val

# Optimize QAOA parameters
def optimize_qaoa(graph, n_shots=1000, n_steps=50):
    # Initial parameters
    gamma = np.random.uniform(0, np.pi, n_steps)
    beta = np.random.uniform(0, np.pi, n_steps)
    
    # Optimization loop
    for step in range(n_steps):
        obj_val = evaluate_qaoa(gamma[step], beta[step], graph, n_shots=n_shots)
        print(f"Step {step + 1}/{n_steps} - Objective Value: {obj_val}")
    
    return gamma, beta

# Run the optimization
gamma_opt, beta_opt = optimize_qaoa(graph)
print(f"Optimal gamma: {gamma_opt[-1]}")
print(f"Optimal beta: {beta_opt[-1]}")

The output would look like this:

...
Step 48/50 - Objective Value: 3.5090000000000003
Step 49/50 - Objective Value: 3.7139999999999995
Step 50/50 - Objective Value: 3.4870000000000005
Optimal gamma: 0.15040460352335366
Optimal beta: 2.8055643903007557

The optimal values for β and γ can be computed.

The circuit is depicted as follows:

from qiskit.visualization import plot_histogram
qc = qaoa_circuit(gamma=gamma_opt[-1], beta=beta_opt[-1], graph=graph)
qc.draw('mpl')

References:

[1]Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

這邊開始是中文~

大家好 我是鴕鳥~今天要來介紹QAOA，事不宜遲讓我們開始吧

Introduction and High Level Interpretation

在我們現實中很多問題都可以以組合最佳化問題(combinatorial optimization problems)來表示。

例如: 課程表排列問題，安排一個學校或大學的課程表，滿足所有課程和教室的限制條件，並且可能有一些特定的目標，如最小化教室利用率或最小化學生空閒時間。

而QAOA（Quantum Approximate Optimization Algorithm）是一種混合量子-經典變分算法，目標為應對組合優化問題。

與現今的神經網路一樣，在QAOA中，狀態是由一個由2p項可變參數指定的p-level circuit準備的，也就是兩個可學習的參數β,γ。而訓練計算過程於量子電腦中進行，更新參數則是在傳統電腦上進行。

※QAOA做的事情是盡可能”接近”最佳解，而不是尋找最佳解。

Pic1: Schematic of a p-level QAOA

What is QAOA (Detail)

最佳化問題會以N-bit binary string的方式表示

並假設古典的目標函數為

為了能在量子電腦上跑，將古典的目標函數encode成量子問題的Hamiltonian項

p-level QAOA

對於初始態|+>，透過H_C與

兩者來生成Wave function

其中參數β, γ為可學習的。並將其視為一個operator。

並定義F為H_C的期望值

令β*,γ*為使F最大值的參數

而衡量近似程度的標準為

其中C_max則是最佳解

MaxCut問題

QAOA最常見的例子就是使用在Maxcut上

所謂的Maxcut問題為給定一張圖(其中包含頂點與邊)，求一種分割方法，將所有頂點（Vertex）分割成兩群，同時使得被切斷的邊（Edge）數量或最大。

來源: Mindspore

可以將其寫成

這樣一來，若i, j是anti-aligned的，會使σz_i σz_k = -1此時wij就會有一個非零的貢獻。

一旦σz_i σz_k = 1意味著兩頂點都在同一個分區。

反之σz_i σz_k = -1意味著兩頂點在不同分區。

Anti-aligned: 這通常用來描述自旋系統中的量子比特，其中每個自旋可以處於 “up” 或 “down” 狀態。如果自旋 i 的 σz 值為 +1（”up”），而自旋 j 的 σz 值為 -1（”down”），或者反之，即它們是反向取向的，那麼 σzi * σzj 就是 -1。這表示這兩個自旋是 “anti-aligned”。

此時Wavefunction可以寫成(以圖的Edge沒有Weight為例)

其中(假設是無權重圖)

我們可以畫出其Circuit

Python 程式碼實現

這邊我們使用qiskit來實際操作一次

from qiskit import Aer, QuantumCircuit, transpile, assemble
from qiskit.visualization import plot_histogram
import matplotlib.pyplot as plt
import numpy as np

# 隨便創建一張圖
graph = {
    'edges': [(0, 1), (1, 2), (2, 3), (3, 0)],
    'weights': [1, 2, 3, 1]
}

# 建立QAOA circuit
def qaoa_circuit(gamma, beta, graph):
    n = len(graph['weights'])
    qc = QuantumCircuit(n, n)

    qc.h(range(n))
    for edge, weight in zip(graph['edges'], graph['weights']):
        qc.cx(edge[0], edge[1])
        qc.u(2 * gamma * weight, 0, 0, edge[1])
        qc.cx(edge[0], edge[1])
    
    qc.rx(2 * beta, range(n))
    
    return qc

# 評估QAOA circuit
def evaluate_qaoa(gamma, beta, graph, n_shots=1000):
    qc = qaoa_circuit(gamma, beta, graph)
    qc.measure(range(len(graph['weights'])), range(len(graph['weights'])))
    
    aer_sim = Aer.get_backend('aer_simulator')
    transpiled_qc = transpile(qc, aer_sim)
    qobj = assemble(transpiled_qc)
    
    result = aer_sim.run(qobj).result()
    counts = result.get_counts(qc)
    
    obj_val = 0
    for bit_string, count in counts.items():
        bit_weight = sum([int(bit) * weight for bit, weight in zip(bit_string, graph['weights'])])
        obj_val += bit_weight * count / n_shots
    
    return obj_val

# 更新QAOA參數
def optimize_qaoa(graph, n_shots=1000, n_steps=50):
    # 參數初始化
    gamma = np.random.uniform(0, np.pi, n_steps)
    beta = np.random.uniform(0, np.pi, n_steps)
    
    # 更新Loop
    for step in range(n_steps):
        obj_val = evaluate_qaoa(gamma[step], beta[step], graph, n_shots=n_shots)
        print(f"Step {step + 1}/{n_steps} - Objective Value: {obj_val}")
    
    return gamma, beta

# Run
gamma_opt, beta_opt = optimize_qaoa(graph)
print(f"Optimal gamma: {gamma_opt[-1]}")
print(f"Optimal beta: {beta_opt[-1]}")

Output會像這樣

...
Step 48/50 - Objective Value: 3.5090000000000003
Step 49/50 - Objective Value: 3.7139999999999995
Step 50/50 - Objective Value: 3.4870000000000005
Optimal gamma: 0.15040460352335366
Optimal beta: 2.8055643903007557

可以計算出最佳的β, γ

Circuit畫出來長這樣

from qiskit.visualization import plot_histogram

qc = qaoa_circuit(gamma=gamma_opt[-1], beta=beta_opt[-1], graph=graph)
qc.draw('mpl')

References:

[1]Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices