量子近似优化算法及其应用

xiaozongpeng · 发表于 2022-12-14 18:28

量子近似优化算法及其应用

量子近似优化算法（QAOA）是一种经典和量子的混合算法，是一种在基于门的量子计算机上求解组合优化问题的变分方法。一般而言，组合优化的任务就是从有限的对象中寻找使成本最小化的目标对象，在实际生活中的主要应用包括降低供应链成本、车辆路径、作业分配等。
1.量子近似优化算法QAOA概述

量子近似优化算法（QAOA）最初就是为了解决MaxCut问题而提出的。在含噪声中等规模量子时代（NISQ），量子噪声主要包括量子退相干、旋转误差等。而量子操作数会受到量子噪声的限制，因此利用量子-经典混合算法，借助经典优化器优化量子线路参数、选择最优演化路径可以降低量子线路的深度。
1.1算法介绍

量子近似优化算法（QAOA）就是一类比较典型的量子-经典混合算法，算法主要解决的问题是寻找目标哈密顿量的基态。通过对试验波函数采用特定的变分ansatz找到哈密顿量基态的近似值。该ansatz是根据门电路指定的，涉及2p参数，必须通过在传统计算机上运行最小化算法来优化这些参数。
量子近似优化算法并没有展现出在量子计算中的指数级加速优势，随着量子线路深度的增加，量子噪声引起的误差会随着增加影响量子近似优化算法。因此对于量子近似优化算法而言，现阶段最关键的任务是降低量子近似优化算法中量子线路深度对其性能的影响。量子近似优化算法性能可通过三种度量进行评估，分别为寻找目标哈密顿量的基态、能量期望值、能量期望值与近似比相关的比率。研究的问题实例包括加权最大割问题和2-可满足性问题。量子近似优化算法可在量子计算机模拟器和IBM Q量子计算中心上执行。
1.2算法原理及步骤

，，｛｝，依赖几个。如果依赖不超过两个，直接映射到哈密顿量。如果依赖三个或三个以上，也可以映射到哈密顿量，可能会以引入额外变量为代价。哈密顿量在σ基中是对角化的，基态能量用表示，对应的最小值。量子近似优化算法（QAOA）运行步骤：

首先，量子计算机是在︱，即所有计算基态的均匀叠加，可以通过使用哈达玛门H来实现︱。
再根据以下公式构造波函数的变分ansatz，即：︱βвβрγрвβγ︱，γγр，βββр，γγ，вββ

如果Hc（H）的特征值是整数值，我们可以将γi（βi）的值限制在区间[0，2π]（[0，π]）。在加权最大分割问题的情况下，γi通常不能限制在区间[0，2π]内。等式︱βвβрγрвβγ︱中，参数p决定了实验状态的参数数量。

整数p表示用到Uв、Uc的层数，即分别将Uв、Uc交替作用在初始态︱+〉上p次。记рγ，β最小哈密顿期望值，即рγ，βγ，βγ，β，最小值рγ，βрγ，β。最小值可以在经典计算机上进行。

根据量子力学理论，在计算基础上每次对量子计算机中的量子态进行测量，γ，β。重复多次该步骤生成足够多的样本z。如果想通过最小化рγ，β搜索最理想的(γ，β)，可以通过以下等式进行估计，即：рγ，β。其中，所有总和为采集的样本z，概率近似为特定样本z发生的相对频率。
2.量子近似优化算法及其应用

TensorFlow Quantum (TFQ) 专为解决 NISQ 时代的量子机器学习问题而设计。它将量子计算基元（如构建量子电路）引入 TensorFlow 生态系统。使用 TensorFlow 构建的模型和运算使用这些基元来创建功能强大的量子经典混合系统。下文将以Tensorflow Quantum为示例，演示量子近似优化算法QAOA实现步骤。
2.1典型问题——最大割问题

最大割问题即Max-Cut问题，也属于一个组合优化问题。量子近似优化算法QAOA与酉变换层数p，理论上讲只要层数p足够多就能找到较好的近似解，但与此同时也会耗费大量时间。
对于一个图，最大割的规模比比其他任何一个割都大。即将图的顶点划分为两个互补的集合S和T，使得S和T之间的边数尽可能大。找到这种切割方式的方法被称为最大切割问题。当人们想要顶点集的一个子集S，使得S和互补子集之间的边数尽可能大，等价于得出一个具有尽可能多边的图的二分子图。该问题有一个更通用的版本被称为加权max-cut，其中每条边都与一个实数相关联即它的权重。加权max-cut问题的目标是最大化S与其补码之间的边的总权重。通过翻转所有权重的符号，可以将允许正权和负权重的加权最大切割问题转换为加权最小切割问题。
给定一个无向图G，其顶点i∈V，边缘（i，j）∈E，求解MaxCut问题得到V的两个子集S0和S1，使得S0∪S1=V，S0∩S1=，边数（i，j）中i∈S0和j∈S1，且j尽可能大。根据量子自旋模型，MaxCut问题的解对应于哈密顿量的最低能量本征态，公式表示如下，

等式2
其中特征值zi=1(1）б算子表示顶点i属于子集S（S）。显然，等式2的特征值是整数值。加权最大割问题是一个扩展，图G的边（i，j）由权重加权。相应的哈密顿量读数如下：

2.2环境准备

NetworkX是一个可创建、操作和研究复杂网络的结构、动态和功能库，可通过以下方式安装。
pip install networkx
2.3算法执行步骤

2.3.1创建各个代码模块

第一步是生成MaxCut问题的实例，首先需要使用NetworkX生成具有10个节点的一个随机3正则图。

# generate a 3 - regular graph with 10 nodes
maxcut_graph=nx.random_regular_graph(n=10, d =3)

下一步是定义10个量子比特

# define 10 qubits
cirq_qubits = cirq . GridQubit . rect (1 , 10)

创建生成哈达玛门层初始化所有计算的叠加态。

# create layer of hadamards to initialize the superposition state of all computational states
hadamard_circuit = cirq . Circuit ()
for node in maxcut_graph . nodes () :
qubit = cirq_qubits [ node ]
hadamard_circuit . append ( cirq.H.on( qubit ) )

定义量子近似优化模块的个参数a、b和混合哈密顿成本

# define the two parameters for one block of QAOA
qaoa_parameters = sympy . symbols (’a b’)
# define the the mixing and the cost Hamiltonians
mixing_ham = 0
for node in maxcut_graph . nodes () :
qubit = cirq_qubits [ node ]
mixing_ham += cirq . PauliString ( cirq . X ( qubit ))
cost_ham = maxcut_graph . number_of_edges () /2

for edge in maxcut_graph . edges () :
qubit1 = cirq_qubits [ edge [0]]
qubit2 = cirq_qubits [ edge [1]]
cost_ham += cirq . PauliString (1/2*( cirq . Z (
qubit1 ) * cirq . Z ( qubit2 ) ) )

生成量子近似优化算法的量子线路。

# generate the qaoa circuit
qaoa_circuit = tfq . util . exponential ( operators =
[ cost_ham , mixing_ham ] , coefficients = qaoa_parameters )
2.3.2使用已创建模块解决Max-Cut问题

随后，可以使用这些成分来构建模型解决最大割问题。由于已经将图形映射到QAOA线路中，因此没有QAOA输入数据和标签。使用TFQ框架需要指定哈达玛线路作为输入，并将其转换为TFQ张量。然后我们可以使用QAOA线路和TFQ PQC层中的成本构造一个tf.keras模型，并使用单个实例样本训练QAOA的变分参数。其中哈达玛门作为输入层，损耗函数的目标值为0，因为这是该优化问题的理论最小值。步骤如下：

定义量子近似优化算法模型

# define the model and training data
model_circuit , model_readout = qaoa_circuit ,
cost_ham
input_ = [ hadamard_circuit ]
input_ = tfq.convert_ to_tensor( input_ )
optimum = [0]

可以使用QAOA线路和TFQ PQC层中的成本构造一个tf.keras模型

# Build the Keras model .
optimum = np . array ( optimum )
model = tf.keras.Sequential ()
model . add ( tf. keras.layers.Input ( shape =() , dtype = tf.dtypes.string ) )
model.add ( tfq.layers.PQC ( model_circuit,model_readout ) )
model . compile ( loss = tf . keras . losses .
mean_absolute_error , optimizer = tf . keras .
optimizers . Adam () )
history = model . fit ( input_ , optimum , epochs =1000 ,
verbose =1)

3.量子近似优化算法实践（等产品可用再补充）

启科量子自主研发一款量子编程框架QuTrunk，为量子编程开发提供了一个通用的软件环境。QuTrunk使用Python作为宿主语言，利用Python的语法特性实现针对量子程序的DSL(领域专用语言)，所有支持Python编程的IDE均可安装使用QuTrunk。
QuTrunk基于量子逻辑门、量子线路等概念提供量子编程所需的各类API。这些API分别由相应的模块实现，比如QCircuit实现量子线路功能，Qubit实现量子比特，Qureg实现量子寄存器，Command对应每个量子门操作的指令， Backend代表运行量子线路的后端模块，gate模块实现了各类基础量子门操作。同时QuTrunk还可以作为其他上层量子计算应用的基础，比如：量子算法、量子可视化编程、量子机器学习等。
目前QuTrunk以QuSprout作为后端。QuSprout也是启科量子自研的一款基于经典计算资源的量子计算模拟软件，支持支持多线程、多节点、GPU加速，也可预安装在QuBox 中。QuTrunk为量子编程工作提供了量子编程框架，建立起一套统一的量子编程规范，进而实现量子程序开发的“降本增效”。
使用QuTrunk实现量子近似优化算法，需准备以下环境：
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

from numpy import pi
from QuTrunk.core import RX, UN, ZZ, Circuit, H, Hamiltonian, QubitOperator
from QuTrunk.framework import MQAnsatzOnlyLayer
from QuTrunk.simulator import Simulator

参考来源：
1.https://doi.org/10.1007/s11128-020-02692-8
2.《A Quantum Approximate Optimization Algorithm》
3.https://www.apache.org/licenses/LICENSE-2.0
扫描添加微信邀请进入量子计算交流群：

本文使用文章同步助手同步

		自动登录	找回密码
密码			立即注册

量子近似优化算法及其应用

本帖子中包含更多资源