量子虚时演化算法

虚时演化(Imaginary time evolution)是研究量子系统的一个有力工具。虚时演化算法作为一种量子经典混合算法对于任意一个给定哈密顿量H的系统均可以近似求解得到其基态向量,即哈密顿量 \(H\) 的最小特征值对应的特征向量。此算法的量子线路浅易于实现,应用范围广泛,可以求解一些经典算法难以解决的问题。

问题背景概述

对于给定哈密顿量 \(H\) 的系统,随着时间 \(t\),系统根据传播变换(propagator) \(e^{-iHt}\) 演化。对应的虚时 \((\tau=it)\) 传播变换为 \(e^{-Ht}\),是一个非幺正算符。

给定哈密顿量 \(H\) 和初态 \(\left|\psi\right\rangle\) ,归一化的虚时演化被定义为

\[\begin{aligned} \left|\psi\left(\tau\right)\right\rangle=A\left(\tau\right)e^{-Ht}\left|\psi\left(0\right)\right\rangle, A\left(\tau\right)=\left({\langle\psi\left(0\right)|e}^{-2Ht} \left|\psi\left(0\right)\right\rangle\right)^\frac{1}{2}. \end{aligned}\]

\(A\left(\tau\right)\) 为归一化因子,通常多体系统的哈密顿量 \(H=\sum_{i}{\lambda_ih_i}\), 其中 \(\lambda_i\) 为实系数,\(h_i\) 为可观测量(observables)并且可以表示为Pauli矩阵的直积。

于是有如下的等价薛定谔方程:

\[\begin{aligned} \frac{\partial\left|\psi\left(\tau\right)\right\rangle}{\partial\tau} =-\left(H-\frac{A^\prime\left(\tau\right)}{A\left(\tau\right)}\right)\left|\psi\left(\tau\right)\right\rangle =-\left(H-E_\tau\right)\left|\psi\left(\tau\right)\right\rangle. \end{aligned}\]

注解

实际应用中,QITE的真正难点在于如何将原问题转化为哈密顿系统求基态问题,以及如何对哈密顿系统给出其哈密顿量。

算法原理

量子虚时演化算法由2个部分:

  1. 通过给定的问题系统哈密顿量,构造相应的薛定谔方程,将薛定谔方程求解问题转化为一个线性方程组求解问题;
  2. 求解线性方程组,得到关键变量的时间演化函数,利用虚时演化的特性求得系统最低能量情况下对应的基态,完成对问题的求解。

量子虚时演化算法可用于在任意已知哈密顿量的哈密顿系统由初态求解任意时刻状态及最终稳态。

从薛定谔方程到微分方程近似解

考虑给定的哈密顿量 \(H\) 所满足的Wick旋转薛定谔方程

\[\begin{aligned} (\frac{\partial}{\partial\tau}-\left(H-E_\tau\right))\left|\psi\left(\tau\right)\right\rangle=0, E_\tau=\left\langle\psi(\tau)\right|H\left|\psi(\tau)\right\rangle. \end{aligned}\]

应用McLachlan变分原理,有

\[\begin{aligned} \delta \left \| \left(\frac{\partial}{\partial\tau}-\left(H-E_\tau\right)\right) \left|\psi\left(\tau\right)\right\rangle \right \|=0. \end{aligned}\]

以测试态 \(\left|\phi\left(\vec{\theta}\left(\tau\right)\right)\right\rangle, \vec{\theta}\left(\tau\right)=\left(\theta_1\left(\tau\right),\theta_2\left(\tau\right), \cdots,\theta_N\left(\tau\right)\right)\) 逼近解 \(\left|\psi\left(\tau\right)\right\rangle\)

\(\dot{\theta_j}=\frac{\partial\theta_j}{\partial\tau}, S=\left(\frac{\partial}{\partial\tau}-\left(H-E_\tau\right)\right)\) ,同时考虑到归一化条件\(\left\langle\phi|\phi\right\rangle=1\),有

\[\begin{split}\begin{aligned} &\frac{\partial\left \| S\left|\phi\left(\tau\right)\right\rangle \right \|}{\partial\dot{\theta_i}} \\ &=\sum_{i,j}\frac{\partial\left\langle\phi\right|}{\partial\theta_i} \frac{\partial\left|\phi\right\rangle}{\partial\theta_j}\dot{\theta_j} +\sum_{i}{(\frac{\partial\left\langle\phi\right|}{\partial\theta_i}}H\left|\phi\right\rangle +\left\langle\phi\right|H\frac{\partial\left|\phi\right\rangle}{\partial\theta_i}) \\ &=\sum_{j} A_{ij}\dot{\theta_j}-C_j=0. \end{aligned}\end{split}\]

其中

\[\begin{split}\begin{aligned} &A_{ij}=Re\left(\frac{\partial\left\langle\phi\right|}{\partial\theta_i}\frac{\partial\left|\phi\right\rangle}{\partial\theta_i}\right),\\ &C_i=-Re\left(\frac{\partial\left\langle\phi\right|}{\partial\theta_i}H\left|\phi\right\rangle\right). \end{aligned}\end{split}\]

于是原薛定谔方程转化为解为 \(\dot{\theta_j}\) 的线性方程组。

虚时演化逼近基态

\(x^\dagger Ax > 0\) 可知 \(A\) 是正定的,其广义逆 \(A^{-1}\) 也是正定的。

于是对系统的平均能量 \(E_\tau\)

\[\begin{split}\begin{aligned} &\frac{{dE}_\tau}{d\tau}=\frac{d\left\langle\psi\left(\tau\right)\left|H\right|\psi\left(\tau\right)\right\rangle}{d\tau}\\ &=\sum_{i}{Re\left(\frac{\partial\left\langle\phi\right|}{\partial\theta_i}H\left|\phi\right\rangle\dot{\theta_i}\right) =-\sum_{i} C_i\dot{\theta_i}}=-\sum_{i,j} C_iA_{i,j}^{-1}C_j\le0. \end{aligned}\end{split}\]

可知运用此量子虚时演化算法会使整个系统的平均能量不断减小。

记测试态 \(\left|\phi\left(\vec{\theta}\right)\right\rangle=V\left(\vec{\theta}\right)\left|\bar{0}\right\rangle =U_N\left(\theta_N\right)\cdots U_2\left(\theta_2\right)U_1\left(\theta_1\right)\left|\bar{0}\right\rangle\),其中\(U_i\) 为幺正算符,\(\bar{0}\) 为系统的初态(并不是基态 \(\left|0\right\rangle\))。

不失一般性地,可以假设每个U_i均仅依赖于一个参数theta_i(否则可以进行量子门操作分解),不妨假设每个 \(U_i\) 均为旋转或受控旋转门,于是其导数可以表示为 \(\frac{{\partial U}_i\left(\theta_i\right)}{\partial\theta_i} =\sum_{k}{f_{k,i}U_i\left(\theta_i\right)\sigma_{k,i}}\)。其中 \(\delta_{k,i}\) 为幺正算符,\(f_{k,i}\) 为标量函数,于是测试态的导数可以表示为 \(\frac{\partial\phi\left(\tau\right)}{\partial\theta_i} =\sum_{k}{f_{k,i}{\widetilde{V}}_{k,i}\left|\bar{0}\right\rangle}\)。其中\({\widetilde{V}}_{k,i}=U_N\left(\theta_N\right)\cdots U_{i+1}\left(\theta_{i+1}\right) U_i\left(\theta_i\right)\sigma_{k,i}{\cdots U}_2\left(\theta_2\right)U_1\left(\theta_1\right)\)

于是对于微分方程组 \(\sum_{j} A_{ij}\dot{\theta_j}=C_j\)

\[\begin{split}\begin{aligned} A_{ij}=Re\left(\sum_{k,l}{f_{k,i}^\ast f_{l,i}\langle\bar{0}|{\widetilde{V}}_{k,i}^\dagger{\widetilde{V}}_{l,j} \left|\bar{0}\right\rangle}\right),\\ C_i=-Re\left(\sum_{k,l}{f_{k,i}^\ast\lambda_l\langle\bar{0}|{\widetilde{V}}_{k,i}^\dagger h_lV \left|\bar{0}\right\rangle}\right). \end{aligned}\end{split}\]

以上两个表达式均符合一般形式 \(aRe\left(e^{i\theta}\langle0|U\left|\bar{0}\right\rangle\right)\),因而可以使用量子线路对其进行构造,\(A_{ij}\) 的构造方式如下:

\[\begin{aligned} \mathrm{\langle}\bar{\mathrm{0}}|{\widetilde{V}}_{k,i}^\dagger{\widetilde{V}}_{l,j}\left|\bar{\mathrm{0}}\right\rangle \mathrm{=\langle}\bar{\mathrm{0}}\mathrm{|}\mathrm{U}_1^\dagger\cdots\mathrm{U}_{i-1}^\dagger\sigma_{k,i}^\dagger \mathrm{U}_i^\dagger\cdots\mathrm{U}_{j-1}^\dagger{\sigma_{i,j}\mathrm{U} }_j^\dagger\cdots U_1\left|\bar{\mathrm{0}}\right\rangle. \end{aligned}\]

\(C_{ij}\) 有类似结果,于是可以用量子线路构造 \(A_{ij}, C_{ij}\)

因此可以引入线性方程组的量子算法,完成求解后得到 \(\dot{\theta_j}=\frac{\partial\theta_j}{\partial\tau}\), 进而将 \(\phi\left(\vec{\theta}\right)\) 进行虚时演化,可以得到系统稳定状态下的基态 \(\theta\)

于是完成了对于任意给定的哈密顿量 \(H\) 对应的系统基态的近似求解。

量子线路图与参考代码

QITE算法中构造线性方程组的左端项矩阵和右端项的量子线路图如下所示

_images/QITE.png

基于QPanda-2.0的QITE算法实现代码参见QPanda-2.0下QITE算法程序源码 ,QPanda-2.0中QITE算法相关代码是一个类,因而下面将介绍所有相关的输入输出接口函数。

QITE();
void setHamiltonian(const PauliOperator& h)
void setAnsatzGate(const std::vector<AnsatzGate>& ansatz_gate)
void setIterNum(size_t num)
void setDeltaTau(double delta_tau)
void setUpthrowNum(size_t num)
void setParaUpdateMode(UpdateMode mode)
int exec();
prob_tuple getResult();

以上函数中,第一个函数为类的构造函数,后续6个函数作用分别为设置哈密顿量,拟设、迭代数、\(\tau\) 的变化率、重置迭代次数、收敛模式参考梯度值或梯度方向、执行虚时演化和获得列表格式的概率结果。

我们可以将量子变分虚时演化算法应用到网络节点重要性排序问题上,综合已有结论快速求解得到节点的重要性权重。选择如下图所示的网络节点重要性排序问题进行代码实现,

_images/QITE_ex1.png

此问题的QITE求解代码实例如下

#include "QPanda.h"
#include "QAlg/QITE/QITE.h"
#include "Components/NodeSortProblemGenerator/NodeSortProblemGenerator.h"
USING_QPANDA

int main(void)
{
   std::vector<std::vector<double>> node7graph{
     // A  B  C  D  E  F  G
       {0, 1 ,0 ,0, 0, 0, 0},
       {1, 0 ,1 ,0, 0, 0, 0},
       {0, 1 ,0 ,1, 1, 1, 0},
       {0, 0 ,1 ,0, 1, 0, 1},
       {0, 0 ,1 ,1, 0, 1, 1},
       {0, 0 ,1 ,0, 1, 0, 1},
       {0, 0 ,0 ,1, 1, 1, 0}
   };

   std::vector< std::vector<std::vector<double>>> graph_vec;

   graph_vec.push_back(node7graph);

   for (int g = 0; g < graph_vec.size(); g++)
   {
      auto graph = graph_vec[g];
      auto node_num = graph.size();

      std::cout << node_num << " graph" << std::endl;

      NodeSortProblemGenerator problem;
      problem.setProblemGraph(graph);
      problem.exec();
      auto ansatz_vec = problem.getAnsatz();

      size_t cnt_num = 1;
      size_t iter_num = 100;
      size_t upthrow_num = 3;
      double delta_tau = 2.6;
      QITE::UpdateMode update_mode = QITE::UpdateMode::GD_DIRECTION;

      srand((int)time(0));
      for (auto cnt = 0; cnt < cnt_num; cnt++)
      {
            std::string log_filename = std::to_string(node_num) + "_num_" +
               std::to_string(cnt) + "_tau_" + std::to_string(delta_tau);

            std::fstream fout;
            fout.open(log_filename + "_init_para.txt", std::ios::out);
            for (auto i = 0; i < ansatz_vec.size(); i++)
            {
               ansatz_vec[i].theta = (rand() / double(RAND_MAX)) * 2 * PI;
               fout << ansatz_vec[i].theta << std::endl;
            }
            fout.close();

            QITE qite;
            qite.setHamiltonian(problem.getHamiltonian());
            qite.setAnsatzGate(ansatz_vec);
            qite.setIterNum(iter_num);
            qite.setDeltaTau(delta_tau);
            qite.setUpthrowNum(upthrow_num);
            qite.setParaUpdateMode(update_mode);
            qite.setLogFile(log_filename);
            auto ret = qite.exec();
            if (ret != 0)
            {
               return ret;
            }
            qite.getResult();
      }
   }

   return 0;
}

可以直接推导得知此7点网络图的节点重要性最大的节点应当为3号,因此结果应当抛出最重要节点3,写法为 \(00000100:1.00\),如下所示的输出结果符合预期。

7 graph
Measure result:
4 0.99995